default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID10th ITCS 2019: San Diego, California, USA
- Avrim Blum:
10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA. LIPIcs 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-095-8 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xii
- Shipra Agrawal, Mohammad Shadravan, Cliff Stein:
Submodular Secretary Problem with Shortlists. 1:1-1:19 - Dorit Aharonov, Leo Zhou
:
Hamiltonian Sparsification and Gap-Simulation. 2:1-2:21 - Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow:
On Solving Linear Systems in Sublinear Time. 3:1-3:19 - Benny Applebaum, Prashant Nalini Vasudevan:
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe. 4:1-4:14 - Nick Arnosti, S. Matthew Weinberg:
Bitcoin: A Natural Oligopoly. 5:1-5:1 - Sepehr Assadi, Michael Kapralov, Sanjeev Khanna:
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. 6:1-6:20 - Per Austrin, Petteri Kaski, Kaie Kubjas:
Tensor Network Complexity of Multilinear Maps. 7:1-7:21 - Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan:
A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. 8:1-8:20 - Boaz Barak, Pravesh K. Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. 9:1-9:12 - Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan:
Algorithms, Bounds, and Strategies for Entangled XOR Games. 10:1-10:18 - Omri Ben-Eliezer:
Testing Local Properties of Arrays. 11:1-11:20 - Eli Ben-Sasson, Eden Saig:
The Complexity of User Retention. 12:1-12:30 - Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao:
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. 13:1-13:16 - Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker:
Almost Envy-Free Allocations with Connected Bundles. 14:1-14:21 - Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani:
"Quantum Supremacy" and the Complexity of Random Circuit Sampling. 15:1-15:2 - Elette Boyle, Rio LaVigne, Vinod Vaikuntanathan:
Adversarially Robust Property-Preserving Hash Functions. 16:1-16:20 - Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. 17:1-17:16 - Igor Carboni Oliveira, Rahul Santhanam, Roei Tell:
Expander-Based Cryptography Meets Natural Proofs. 18:1-18:14 - André Chailloux:
A Note on the Quantum Query Complexity of Permutation Symmetric Functions. 19:1-19:7 - Deeparnab Chakrabarty, C. Seshadhri:
Adaptive Boolean Monotonicity Testing in Total Influence Time. 20:1-20:7 - Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
On Locality-Sensitive Orderings and Their Applications. 21:1-21:17 - Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal:
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. 22:1-22:15 - Lijie Chen, Ruosong Wang:
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. 23:1-23:20 - Wei Chen, Shang-Hua Teng, Hanrui Zhang:
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. 24:1-24:20 - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. 25:1-25:17 - Chi-Ning Chou, Kai-Min Chung, Chi-Jen Lu:
On the Algorithmic Power of Spiking Neural Networks. 26:1-26:20 - Constantinos Daskalakis, Ioannis Panageas:
Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. 27:1-27:18 - Anindya De, Philip M. Long, Rocco A. Servedio:
Density Estimation for Shift-Invariant Multidimensional Distributions. 28:1-28:20 - Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi:
From Local to Robust Testing via Agreement Testing. 29:1-29:18 - Irit Dinur, Oded Goldreich, Tom Gur:
Every Set in P Is Strongly Testable Under a Suitable Encoding. 30:1-30:17 - Shaddin Dughmi, David Kempe, Ruixin Qiang:
Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice. 31:1-31:20 - Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson:
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. 32:1-32:20 - Cynthia Dwork, Christina Ilvento:
Fairness Under Composition. 33:1-33:20 - Yuval Filmus, Ryan O'Donnell, Xinyu Wu:
A Log-Sobolev Inequality for the Multislice, with Applications. 34:1-34:12 - Anna Gál, Avishay Tal, Adrian Trejo Nuñez:
Cubic Formula Size Lower Bounds Based on Compositions with Majority. 35:1-35:13 - Sumegha Garg, Jon Schneider:
The Space Complexity of Mirror Games. 36:1-36:14 - Oded Goldreich, Dana Ron:
The Subgraph Testing Model. 37:1-37:19 - Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov:
Adventures in Monotone Complexity and TFNP. 38:1-38:19 - Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan:
Algorithmic Polarization for Hidden Markov Models. 39:1-39:19 - Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff:
On the Communication Complexity of Key-Agreement Protocols. 40:1-40:16 - Linus Hamilton, Ankur Moitra:
The Paulsen Problem Made Simple. 41:1-41:6 - Thibaut Horel, Sunoo Park, Silas Richelson, Vinod Vaikuntanathan:
How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts. 42:1-42:20 - Klaus Jansen, Lars Rohwedder:
On Integer Programming and Convolution. 43:1-43:17 - Klaus Jansen, Kim-Manuel Klein, Marten Maack, Malin Rau:
Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. 44:1-44:19 - Yan Jin, Elchanan Mossel, Govind Ramnarayan:
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. 45:1-45:14 - Ce Jin:
Simulating Random Walks on Graphs in the Streaming Model. 46:1-46:15 - Markus Bläser, Gorav Jindal:
On the Complexity of Symmetric Polynomials. 47:1-47:14 - Daniel M. Kane, Richard Ryan Williams:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. 48:1-48:15 - Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm:
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. 49:1-49:21 - Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, Erik Vee:
Semi-Online Bipartite Matching. 50:1-50:20 - Troy Lee, Maharshi Ray, Miklos Santha:
Strategies for Quantum Races. 51:1-51:21 - Amit Levi, Erik Waingarten:
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. 52:1-52:20 - Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Secret Sharing with Binary Shares. 53:1-53:20 - Nati Linial, Toniann Pitassi, Adi Shraibman:
On the Communication Complexity of High-Dimensional Permutations. 54:1-54:20 - Jingcheng Liu, Alistair Sinclair, Piyush Srivastava:
Fisher Zeros and Correlation Decay in the Ising Model. 55:1-55:8 - Dylan M. McKay, Richard Ryan Williams:
Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. 56:1-56:20 - Christos H. Papadimitriou, Santosh S. Vempala:
Random Projection in the Brain and Computation with Assemblies of Neurons. 57:1-57:19 - Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee:
Local Computation Algorithms for Spanners. 58:1-58:21 - Krzysztof Pietrzak:
Proofs of Catalytic Space. 59:1-59:25 - Krzysztof Pietrzak:
Simple Verifiable Delay Functions. 60:1-60:15 - Aaron Potechin:
Sum of Squares Lower Bounds from Symmetry and a Good Story. 61:1-61:20 - Zachary Chase, Siddharth Prasad:
Learning Time Dependent Choice. 62:1-62:19 - Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma:
Erasures vs. Errors in Local Decoding and Property Testing. 63:1-63:21 - Adi Rosén, Florent Urrutia:
A New Approach to Multi-Party Peer-to-Peer Communication Complexity. 64:1-64:19 - Aaron Schild:
A Schur Complement Cheeger Inequality. 65:1-65:15 - Kim Thang Nguyen:
Game Efficiency Through Linear Programming Duality. 66:1-66:20
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-10-26 23:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
