Swastik Kopparty

Mrinal Kumar

Harry Sha

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Improved PIR Schemes using Matching Vectors and Derivatives.

[BibT_eX]

[DOI]

Fatemeh Ghasemi

Madhu Sudan

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Error-Correcting Graph Codes.

[BibT_eX]

[DOI]

Aditya Potukuchi

Harry Sha

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields.

[BibT_eX]

[DOI]

Fatemeh Ghasemi

Gal Gross

Proceedings of the Approximation, 2025

2024

Character sums over AG codes.

[BibT_eX]

[DOI]

Amnon Ta-Shma

Kedem Yakirevitch

Electron. Colloquium Comput. Complex., 2024

Small Shadow Partitions.

[BibT_eX]

[DOI]

Harry Sha

Electron. Colloquium Comput. Complex., 2024

On the Degree of Polynomials Computing Square Roots Mod p.

[BibT_eX]

[DOI]

Kiran S. Kedlaya

Proceedings of the 39th Computational Complexity Conference, 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]

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2023

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time O(n log n) over all Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Extracting Mergers and Projections of Partitions.

[BibT_eX]

[DOI]

Vishvajeet N

Proceedings of the Approximation, 2023

2022

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves - (ECFFT Part II).

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

2021

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

2020

DEEP-FRI: Sampling Outside the Box Improves Soundness.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Proximity Gaps for Reed-Solomon Codes.

[BibT_eX]

[DOI]

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

Geometric Rank of Tensors and Subrank of Matrix Multiplication.

[BibT_eX]

[DOI]

Guy Moshkovitz

Jeroen Zuiddam

Proceedings of the 35th Computational Complexity Conference, 2020

On Multilinear Forms: Bias, Correlation, and Tensor Rank.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).

[BibT_eX]

[DOI]

Irit Dinur

Or Meir

SIAM J. Comput., 2019

Quasilinear Time List-Decodable Codes for Space Bounded Channels.

[BibT_eX]

[DOI]

Jad Silbak

Ronen Shaltiel

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

On List Recovery of High-Rate Tensor Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Theory Comput., 2018

A Cauchy-Davenport Theorem for Linear Maps.

[BibT_eX]

[DOI]

Simao Herdade

John Kim

Comb., 2018

Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

Aditya Potukuchi

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-optimal approximation algorithm for simultaneous Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Improved Decoding of Folded Reed-Solomon and Multiplicity Codes.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Worst-Case to Average Case Reductions for the Distance to a Code.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Local Testing and Decoding of High-Rate Error-Correcting Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound.

[BibT_eX]

[DOI]

Sivakanth Gopi

Rafael Mendes de Oliveira

Noga Ron-Zewi

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Maximally Recoverable Codes for Grid-like Topologies.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

List-Decoding Algorithms for Lifted Codes.

[BibT_eX]

[DOI]

Alan Guo

IEEE Trans. Inf. Theory, 2016

Guest Column: Local Testing and Decoding of High-Rate Error-Correcting Codes.

[BibT_eX]

[DOI]

SIGACT News, 2016

A local central limit theorem for triangles in a random graph.

[BibT_eX]

[DOI]

Justin Gilmer

Random Struct. Algorithms, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Robust positioning patterns.

[BibT_eX]

[DOI]

Ross Berkowitz

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Decoding Reed-Muller Codes Over Product Sets.

[BibT_eX]

[DOI]

John Y. Kim

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

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

[BibT_eX]

[DOI]

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

The complexity of computing the minimum rank of a sign pattern matrix.

[BibT_eX]

[DOI]

Amey Bhangale

CoRR, 2015

Equivalence of Polynomial Identity Testing and Polynomial Factorization.

[BibT_eX]

[DOI]

Amir Shpilka

Comput. Complex., 2015

Simultaneous Approximation of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Amey Bhangale

Sushant Sachdeva

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Roots and coefficients of polynomials over finite fields.

[BibT_eX]

[DOI]

Qiang Wang

Finite Fields Their Appl., 2014

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Mrinal Kumar

Michael E. Saks

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.

[BibT_eX]

[DOI]

Amir Shpilka

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

A new family of locally correctable codes based on degree-lifted algebraic geometry codes.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

New affine-invariant codes from lifting.

[BibT_eX]

[DOI]

Alan Guo

Madhu Sudan

Proceedings of the Innovations in Theoretical Computer Science, 2013

Explicit Subspace Designs.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Some remarks on multiplicity codes.

[BibT_eX]

[DOI]

Proceedings of the Discrete Geometry and Algebraic Combinatorics, 2013

2012

Certifying Polynomials for AC0[⊕] circuits, with applications.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2012

List-Decoding Multiplicity Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Certifying polynomials for AC^0(parity) circuits, with applications.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Review of algebraic function fields and codes by Henning Stichtenoth.

[BibT_eX]

[DOI]

SIGACT News, 2011

The homomorphism domination exponent.

[BibT_eX]

[DOI]

Benjamin Rossman

Eur. J. Comb., 2011

High-rate codes with sublinear-time decoding.

[BibT_eX]

[DOI]

Sergey Yekhanin

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

On the complexity of powering in finite fields.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Algebraic methods in randomness and pseudorandomness.

[BibT_eX]

[DOI]

PhD thesis, 2010

Subspace polynomials and limits to list decoding of Reed-Solomon codes.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2010

Local list-decoding and testing of random linear codes from high error.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On the list-decodability of random linear codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Johan Håstad

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Some Recent Results on Local Testing of Sparse Linear Codes.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Random graphs and the parity quantifier.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Affine dispersers from subspace polynomials.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On the Communication Complexity of Read-Once AC^0 Formulae.

[BibT_eX]

[DOI]

T. S. Jayram

Prasad Raghavendra

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Tolerant Linearity Testing and Locally Testable Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

Universal capacity of channels with given rate-distortion in absence of common randomness, and failure of universal source-channel separation.

[BibT_eX]

[DOI]

Mukul Agarwal

Sanjoy K. Mitter

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Decodability of group homomorphisms beyond the johnson bound.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Detecting Rational Points on Hypersurfaces over Finite Fields.

[BibT_eX]

[DOI]

Sergey Yekhanin

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2006

How to Construct a Correct and Scalable iBGP Configuration.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2006. 25th IEEE International Conference on Computer Communications, 2006

Subspace Polynomials and List Decoding of Reed-Solomon Codes.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

Local Decoding and Testing for Homomorphisms.

[BibT_eX]

[DOI]

Elena Grigorescu

Madhu Sudan

Proceedings of the Approximation, 2006

2005

A framework for pursuit evasion games in Rn.

[BibT_eX]

[DOI]

Chinya V. Ravishankar

Inf. Process. Lett., 2005

2004

Roads, Codes and Spatiotemporal Queries.

[BibT_eX]

[DOI]

Sandeep Gupta

Chinya V. Ravishankar

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

2002

Split TCP for mobile ad hoc networks.

[BibT_eX]

[DOI]