Noga Ron-Zewi

S. Venkitesh

CoRR, 2024

2023

Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes.

[BibT_eX]

[DOI]

SIAM J. Comput., June, 2023

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2023

Finer-grained Reductions in Fine-grained Hardness of Approximation.

[BibT_eX]

[DOI]

Elie Abboud

CoRR, 2023

2022

Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020).

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Marek Cygan

Christian Wulff-Nilsen

SIAM J. Comput., June, 2022

From Local to Robust Testing via Agreement Testing.

[BibT_eX]

[DOI]

Theory Comput., 2022

2021

Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Ivona Bezáková

László A. Végh

Theory Comput., 2021

Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead.

[BibT_eX]

[DOI]

Ron Rothblum

Electron. Colloquium Comput. Complex., 2021

2020

Local List Recovery of High-Rate Tensor Codes and Applications.

[BibT_eX]

[DOI]

Brett Hemenway

SIAM J. Comput., 2020

Linear-time Erasure List-decoding of Expander Codes.

[BibT_eX]

[DOI]

Gilles Zémor

Electron. Colloquium Comput. Complex., 2020

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).

[BibT_eX]

[DOI]

Ronen Shaltiel

Nithin Varma

Electron. Colloquium Comput. Complex., 2020

Efficient List-Decoding with Constant Alphabet and List Sizes.

[BibT_eX]

[DOI]

Zeyu Guo

Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Local Proofs Approaching the Witness Length [Extended Abstract].

[BibT_eX]

[DOI]

Ron D. Rothblum

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Local Proofs Approaching the Witness Length.

[BibT_eX]

[DOI]

Ron Rothblum

Electron. Colloquium Comput. Complex., 2019

LDPC Codes Achieve List-Decoding Capacity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

On List Recovery of High-Rate Tensor Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Erasures vs. Errors in Local Decoding and Property Testing.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Nithin Varma

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Explicit Capacity Approaching Coding for Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

Erasures versus Errors in Local Decoding and Property Testing.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Nithin Varma

Electron. Colloquium Comput. Complex., 2018

Improved decoding of Folded Reed-Solomon and Multiplicity Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

From Local to Robust Testing via Agreement Testing.

[BibT_eX]

[DOI]

Irit Dinur

Tali Kaufman

Electron. Colloquium Comput. Complex., 2018

2017

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity.

[BibT_eX]

[DOI]

J. ACM, 2017

Local List Recovery of High-rate Tensor Codes & Applications.

[BibT_eX]

[DOI]

Brett Hemenway

Electron. Colloquium Comput. Complex., 2017

Sparse affine-invariant linear codes are locally testable.

[BibT_eX]

[DOI]

Rafael Mendes de Oliveira

Madhu Sudan

Comput. Complex., 2017

2016

Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound.

[BibT_eX]

[DOI]

Sivakanth Gopi

Swastik Kopparty

Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2016

2015

Absolutely Sound Testing of Lifted Codes.

[BibT_eX]

[DOI]

Elad Haramaty

Madhu Sudan

Theory Comput., 2015

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity.

[BibT_eX]

[DOI]

Swastik Kopparty

Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2015

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Towards Optimal Deterministic Coding for Interactive Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

On Public Key Encryption from Noisy Codewords.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

Additive combinatorics methods in computational complexity.

[BibT_eX]

[DOI]

PhD thesis, 2014

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

[BibT_eX]

[DOI]

Shachar Lovett

J. ACM, 2014

2013

A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes.

[BibT_eX]

[DOI]

Madhu Sudan

Theory Comput., 2013

2012

Vector representation of graph domination.

[BibT_eX]

[DOI]

Noga Zewi

J. Graph Theory, 2012

Space Complexity in Polynomial Calculus.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Sampling-based proofs of almost-periodicity results and algorithmic applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

An additive combinatorics approach to the log-rank conjecture in communication complexity.

[BibT_eX]

[DOI]

Shachar Lovett

Noga Zewi

Electron. Colloquium Comput. Complex., 2011

2010

From Affine to Two-Source Extractors via Approximate Duality.

[BibT_eX]

[DOI]