Innovations in Theoretical Computer Science 2018|
Barriers for Rank Methods in Arithmetic Complexity
Klim Efremenko, Ankit Garg, Rafael Oliveira and Avi Wigderson. |
|
Further limitations of the known approaches for matrix multiplication
Josh Alman and Virginia Vassilevska Williams. |
|
Quantum Query Algorithms are Completely Bounded Forms
Srinivasan Arunachalam, Jop Briet and Carlos Palazuelos. |
|
A Complete Characterization of Unitary Quantum Space
Bill Fefferman and Cedric Lin. |
|
Lattice-Based Locality Sensitive Hashing is Optimal
Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota and Elena Grigorescu. |
|
Approximate Clustering with Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal and Amit Kumar. |
|
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian and Makrand Sinha. |
|
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm and S. Matthew Weinberg. |
|
Relaxed Locally Correctable Codes
Tom Gur, Govind Ramnarayan and Ron Rothblum. |
|
Local decoding and testing of polynomials over grids
Srikanth Srinivasan and Madhu Sudan. |
|
Proofs of Proximity for Distribution Testing
Alessandro Chiesa and Tom Gur. |
|
Efficient Testing without Efficient Regularity
Asaf Shapira and Lior Gishboliner. |
|
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Yuqing Kong and Grant Schoenebeck. |
|
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case
Yuqing Kong and Grant Schoenebeck. |
|
An Axiomatic Study of Scoring Rule Markets
Rafael Frongillo and Bo Waggoner. |
|
On Price versus Quality
Avrim Blum and Yishay Mansour. |
|
Pseudo-Deterministic Proofs
Shafi Goldwasser, Ofer Grossman and Dhiraj Holden. |
|
Simple doubly-efficient interactive proof systems for locally-characterizable sets
Oded Goldreich and Guy Rothblum. |
|
Zero-Knowledge Proofs of Proximity
Itay Berman, Ron Rothblum and Vinod Vaikuntanathan. |
|
Foundations of Homomorphic Secret Sharing Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin and Stefano Tessaro. |
|
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
Jelena Diakonikolas and Lorenzo Orecchia. |
|
Non-Negative Sparse Regression and Column Subset Selection with L_1 Error Aditya Bhaskara and Silvio Lattanzi. |
|
Convergence Results for Neural Networks via Electrodynamics
Rina Panigrahy, Ali Rahimi, Sushant Sachdeva and Qiuyi Zhang. |
|
Graph Clustering using Effective Resistance
Vedat Levi Alev, Nima Anari, Lap Chi Lau and Shayan Oveis Gharan. |
|
Scheduling with Explorable Uncertainty
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meissner. |
|
A Local-Search Algorithm for Steiner Forest
Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and José Verschae. |
|
Selection Problems in the Presence of Implicit Bias Jon Kleinberg and Manish Raghavan. |
|
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi. |
|
Distance-preserving graph contractions
Frieder Smolny, Karl Däubel, Aaron Bernstein, Max Klimm, Yann Disser and Torsten Mütze. |
|
Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles and Bernhard Haeupler. |
|
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs Shay Solomon. |
|
Long-term Memory and the Densest K-Subgraph Problem Robert Legenstein, Wolfgang Maass, Christos Papadimitriou and Santosh Vempala. |
|
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs
Olaf Beyersdorff, Joshua Blinkhorn and Luke Hinde. |
|
Stabbing Planes
Noah Fleming, Robert Robere, Paul Beame, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov and Toniann Pitassi. |
|
Towards a Unified Complexity Theory of Total Functions
Paul Goldberg and Christos Papadimitriou. |
|
Matrix Completion and Related Problems via Strong Duality Maria-Florina Balcan, Yingyu Liang, David P. Woodruff and Hongyang Zhang. |
|
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru and David P. Woodruff. |
|
A Quasi-Random Approach to Matrix Spectral Analysis
Lior Eldar and Michael Ben-Or. |
|
Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory.
Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson. |
|
Differential Privacy on Finite Computers
Victor Balcer and Salil Vadhan. |
|
Finite Sample Differentially Private Confidence Intervals
Vishesh Karwa and Salil Vadhan. |
|
A Candidate for a Strong Separation of Information and Communication Mark Braverman, Anat Ganor, Gillat Kol and Ran Raz. |
|
Information Value of the Game Mark Braverman and Young Kun Ko. |
|
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore and Andrew Morgan. |
|
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair and Michael Kowalczyk. |
|
Limits for Rumor Spreading in stochastic populations Lucas Boczkowski, Ofer Feinerman, Amos Korman and Emanuele Natale. |
|
Toward a Theory of Markov Influence Systems and their Renormalization Bernard Chazelle. |
|
Learning Dynamics and the Co-Evolution of Competing Sexual Species
Georgios Piliouras and Leonard Schulman. |
|
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning Dana Moshkovitz and Michal Moshkovitz. |
|
Pseudorandom Generators for Low Sensitivity Functions
Pooya Hatami and Avishay Tal. |
|
Agnostic Learning by Refuting
Pravesh K Kothari and Roi Livni. |
|
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
Greg Yang. |
|
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Jacob Steinhardt, Moses Charikar and Gregory Valiant. |
|
Recovering Structured Probability Matrices
Qingqing Huang, Sham M. Kakade, Weihao Kong and Gregory Valiant. |
|
Learning Discrete Distributions from Untrusted Batches
Mingda Qiao and Gregory Valiant. |
|
Competing bandits: learning under competition
Yishay Mansour, Aleksandrs Slivkins and Zhiwei Steven Wu. |
|
Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch and Virginia Williams. |
|
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network Irit Dinur and Pasin Manurangsi. |
|
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds Amir Abboud and Aviad Rubinstein. |