Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) by Backurs, Arturs, Indyk, Piotr

Get full text
Get full text
Get full text

Approximate counting, the Lovasz local lemma, and inference in graphical models by Moitra, Ankur

Get full text
Get full text

Regression from dependent observations by Daskalakis, Constantinos, Dikkala, Sai Nishanth, Panageas, Ioannis

Get full text

AND testing and robust judgement aggregation by Filmus, Yuval, Lifshitz, Noam, Minzer, Dor, Mossel, Elchanan

Get full text

AND testing and robust judgement aggregation by Filmus, Yuval, Lifshitz, Noam, Minzer, Dor, Mossel, Elchanan

Get full text

Communication complexity of estimating correlations by Hadar, U., Liu, J., Polyanskiy, Yury, Shayevitz, O.

Get full text

A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges by Bernstein, Aaron, Karger, David R.

Get full text
Get full text

NP-Hardness of Approximately Solving Linear Equations Over Reals by Khot, Subhash, Moshkovitz Aaronson, Dana Hadar

Get full text
Get full text

Sparse Quantum Codes from Quantum Circuits by Bacon, Dave, Flammia, Steven T., Harrow, Aram W., Shi, Jonathan

Get full text
Get full text

Efficiently learning structured distributions from untrusted batches by Chen, Sitan, Li, Jerry, Moitra, Ankur

Get full text

Efficiently learning structured distributions from untrusted batches by Chen, Sitan, Li, Jerry, Moitra, Ankur

Get full text

Learning poisson binomial distributions by Daskalakis, Constantinos, Diakonikolas, Ilias, Servedio, Rocco A.

Get full text
Get full text

Rational proofs by Azar, Pablo Daniel, Micali, Silvio

Get full text
Get full text
Get full text

Nearly optimal sparse fourier transform by Hassanieh, Haitham, Indyk, Piotr, Katabi, Dina, Price, Eric C.

Get full text
Get full text
Get full text
Get full text

A simple, combinatorial algorithm for solving SDD systems in nearly-linear time by Orecchia, Lorenzo, Zhu, Zeyuan Allen, Kelner, Jonathan Adam, Sidford, Aaron D.

Get full text
Get full text
Get full text

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing by Aaronson, Scott, Ambainis, Andris

Get full text
Get full text

On Approximability of Satisfiable k-CSPs: II by Bhangale, Amey, Khot, Subhash, Minzer, Dor

Get full text

On Approximability of Satisfiable k-CSPs: III by Bhangale, Amey, Khot, Subhash, Minzer, Dor

Get full text

Commitments to Quantum States by Gunn, Sam, Ju, Nathan, Ma, Fermi, Zhandry, Mark

Get full text

Testing Distributional Assumptions of Learning Algorithms by Rubinfeld, Ronitt, Vasilyan, Arsen

Get full text