default search action
11th ITCS 2020: Seattle, WA, USA
- Thomas Vidick:
11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA. LIPIcs 151, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-134-4 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Elazar Goldenberg, Karthik C. S.
:
Hardness Amplification of Optimization Problems. 1:1-1:13 - Orr Paradise:
Smooth and Strong PCPs. 2:1-2:41 - Ariel Schvartzman, S. Matthew Weinberg
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence. 3:1-3:25 - Stacey Jeffery
Span Programs and Quantum Space Complexity. 4:1-4:37 - Eli Ben-Sasson
DEEP-FRI: Sampling Outside the Box Improves Soundness. 5:1-5:32 - Nir Bitansky
On the Cryptographic Hardness of Local Search. 6:1-6:29 - Klim Efremenko
Interactive Coding with Constant Round and Communication Blowup. 7:1-7:34 - Xiaohui Bei
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. 8:1-8:48 - Omri Ben-Eliezer, Eldar Fischer, Amit Levi
Hard Properties with (Very) Short PCPPs and Their Applications. 9:1-9:27 - Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo
Kronecker Powers of Tensors and Strassen's Laser Method. 10:1-10:28 - Andrea Lincoln
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. 11:1-11:17 - Siqi Liu, Sidhanth Mohanty, Elizabeth Yang:
High-Dimensional Expanders from Expanders. 12:1-12:32 - Jeremiah Blocki
Approximating Cumulative Pebbling Cost Is Unique Games Hard. 13:1-13:27 - Michael Mitzenmacher:
Scheduling with Predictions and the Price of Misprediction. 14:1-14:18 - Kira Goldner
Reducing Inefficiency in Carbon Auctions with Imperfect Competition. 15:1-15:21 - Michael P. Kim, Aleksandra Korolova, Guy N. Rothblum, Gal Yona:
Preference-Informed Fairness. 16:1-16:23 - Jin-Yi Cai, Artem Govorov:
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. 17:1-17:15 - Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. 18:1-18:19 - Fedor Part, Iddo Tzameret:
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. 19:1-19:37 - Ran Raz
The Random-Query Model and the Memory-Bounded Coupon Collector. 20:1-20:11 - Greg Bodwin, Ofer Grossman:
Strategy-Stealing Is Non-Constructive. 21:1-21:12 - Noah Fleming, Yuichi Yoshida:
Distribution-Free Testing of Linear Functions on ℝⁿ. 22:1-22:19 - Yael Hitron, Nancy A. Lynch, Cameron Musco, Merav Parter:
Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks. 23:1-23:31 - Georg Loho
Signed Tropical Convexity. 24:1-24:35 - András Gilyén, Tongyang Li
Distributional Property Testing in a Quantum World. 25:1-25:19 - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Local Testability in the Non-Signaling Setting. 26:1-26:37 - Amartya Shankha Biswas
Local Access to Huge Random Objects Through Partial Sampling. 27:1-27:65 - Ronitt Rubinfeld, Arsen Vasilyan:
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. 28:1-28:34 - Gal Sadeh, Edith Cohen
Sample Complexity Bounds for Influence Maximization. 29:1-29:36 - Nir Bitansky, Nathan Geier:
On Oblivious Amplification of Coin-Tossing Protocols. 30:1-30:13 - Christopher Jung, Katrina Ligett
A New Analysis of Differential Privacy's Generalization Guarantees. 31:1-31:17 - Domagoj Bradac
Robust Algorithms for the Secretary Problem. 32:1-32:26 - Nathaniel Harms:
Universal Communication, Universal Graphs, and Graph Labeling. 33:1-33:27 - Rahul Ilango:
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. 34:1-34:26 - Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian:
Equivalence of Systematic Linear Data Structures and Matrix Rigidity. 35:1-35:20 - Mohammad Hassan Ameri
Computationally Data-Independent Memory Hard Functions. 36:1-36:28 - Andrej Bogdanov
Learning and Testing Variable Partitions. 37:1-37:22 - Suman K. Bera, Noujan Pashanasangi, C. Seshadhri:
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. 38:1-38:20 - Fedor V. Fomin
Parameterization Above a Multiplicative Guarantee. 39:1-39:13 - Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg
Ad Hoc Multi-Input Functional Encryption. 40:1-40:41 - Shuichi Hirahara:
Unexpected Power of Random Strings. 41:1-41:13 - Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
Consensus vs Broadcast, with and Without Noise (Extended Abstract). 42:1-42:13 - Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing Linear Inequalities of Subgraph Statistics. 43:1-43:9 - Guy Blanc, Jane Lange, Li-Yang Tan:
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. 44:1-44:44 - Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla:
Algorithms and Adaptivity Gaps for Stochastic k-TSP. 45:1-45:25 - Nils Bertschinger
Strategic Payments in Financial Networks. 46:1-46:16 - William Lochet
Fault Tolerant Subgraphs with Applications in Kernelization. 47:1-47:22 - Yael Hitron, Merav Parter, Gur Perri:
The Computational Cost of Asynchronous Neural Communication. 48:1-48:47 - Konstantin Makarychev, Yury Makarychev
Certified Algorithms: Worst-Case Analysis and Beyond. 49:1-49:14 - Ruben Becker
Low Diameter Graph Decompositions by Approximate Distance Computation. 50:1-50:29 - Yihan Zhang
Generalized List Decoding. 51:1-51:83 - Spyros Angelopoulos
Online Computation with Untrusted Advice. 52:1-52:15 - Andrea Lincoln
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. 53:1-53:18 - Nima Anari
Matching Is as Easy as the Decision Problem, in the NC Model. 54:1-54:25 - Avrim Blum, Thodoris Lykouris
Advancing Subgroup Fairness via Sleeping Experts. 55:1-55:24 - Tomer Grossman, Ilan Komargodski, Moni Naor:
Instance Complexity and Unlabeled Certificates in the Decision Tree Model. 56:1-56:38 - Alessandro Chiesa, Siqi Liu:
On the Impossibility of Probabilistic Proofs in Relativized Worlds. 57:1-57:30 - Anna Gál, Robert Robere:
Lower Bounds for (Non-Monotone) Comparator Circuits. 58:1-58:13 - Nathan Lindzey, Ansis Rosmanis:
A Tight Lower Bound For Non-Coherent Index Erasure. 59:1-59:37 - Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
Optimal Single-Choice Prophet Inequalities from Samples. 60:1-60:10 - Linda Cai, Clayton Thomas, S. Matthew Weinberg
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard. 61:1-61:32 - Erik D. Demaine, Dylan H. Hendrickson
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. 62:1-62:42 - Adam Bouland
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). 63:1-63:2 - Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg
New Query Lower Bounds for Submodular Function Minimization. 64:1-64:16 - Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia:
Computation-Aware Data Aggregation. 65:1-65:38 - Francisco Maturana
Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage. 66:1-66:26 - Federico Echenique
Incentive Compatible Active Learning. 67:1-67:20 - Rahul Santhanam
Pseudorandomness and the Minimum Circuit Size Problem. 68:1-68:26 - Maryam Aliakbarpour
Testing Properties of Multiple Distributions with Few Samples. 69:1-69:41 - Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich
Beyond Natural Proofs: Hardness Magnification and Locality. 70:1-70:48 - Benny Applebaum, Zvika Brakerski, Sanjam Garg
Separating Two-Round Secure Computation From Oblivious Transfer. 71:1-71:18 - Guillaume Lagarde, Jakob Nordström
Trade-Offs Between Size and Degree in Polynomial Calculus. 72:1-72:16 - Shant Boodaghians, Rucha Kulkarni, Ruta Mehta:
Smoothed Efficient Algorithms and Reductions for Network Coordination Games. 73:1-73:15 - Tali Kaufman, David Mass:
Local-To-Global Agreement Expansion via the Variance Method. 74:1-74:14 - T.-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi:
MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. 75:1-75:52 - Agelos Georgakopoulos
Choice and Bias in Random Walks. 76:1-76:19 - Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
Graph Spanners in the Message-Passing Model. 77:1-77:18 - Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein:
Computational Hardness of Certifying Bounds on Constrained PCA Problems. 78:1-78:29 - Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-Deterministic Streaming. 79:1-79:25 - Marshall Ball
Limits to Non-Malleability. 80:1-80:32 - Marshall Ball
Cryptography from Information Loss. 81:1-81:27 - James Bartusek
Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. 82:1-82:39 - Josh Alman, Virginia Vassilevska Williams:
OV Graphs Are (Probably) Hard Instances. 83:1-83:18 - Parikshit Gopalan, Roie Levin, Udi Wieder:
Finding Skewed Subcubes Under a Distribution. 84:1-84:30 - Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal:
Combinatorial Lower Bounds for 3-Query LDCs. 85:1-85:8 - Marshall Ball
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be? 86:1-86:22
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 2024-11-11 21:15 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: