Swastik Kopparty

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2023

Extracting Mergers and Projections of Partitions.

[BibT_eX]

[DOI]

Vishvajeet N

Electron. Colloquium Comput. Complex., 2023

On the degree of polynomials computing square roots mod p.

[BibT_eX]

[DOI]

Kiran Kedlaya

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

2022

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

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Geometric Rank of Tensors and Subrank of Matrix Multiplication.

[BibT_eX]

[DOI]

Guy Moshkovitz

Jeroen Zuiddam

Electron. Colloquium Comput. Complex., 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]

Ronen Shaltiel

Jad Silbak

Electron. Colloquium Comput. Complex., 2019

On List Recovery of High-Rate Tensor Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

DEEP-FRI: Sampling Outside the Box Improves Soundness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Improved decoding of Folded Reed-Solomon and Multiplicity Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Worst-case to average case reductions for the distance to a code.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2017

Decoding Reed-Muller Codes over Product Sets.

[BibT_eX]

[DOI]

John Y. Kim

Theory Comput., 2017

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

[BibT_eX]

[DOI]

J. ACM, 2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Mrinal Kumar

Michael E. Saks

Theory Comput., 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

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

[BibT_eX]

[DOI]

J. ACM, 2016

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

[BibT_eX]

[DOI]

Sivakanth Gopi

Rafael Mendes de Oliveira

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2016

Explicit subspace designs.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Comb., 2016

Robust positioning patterns.

[BibT_eX]

[DOI]

Ross Berkowitz

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

2015

List-Decoding Multiplicity Codes.

[BibT_eX]

[DOI]

Theory Comput., 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

2014

High-rate codes with sublinear-time decoding.

[BibT_eX]

[DOI]

Sergey Yekhanin

J. ACM, 2014

Roots and coefficients of polynomials over finite fields.

[BibT_eX]

[DOI]

Qiang Wang

Finite Fields Their Appl., 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.

[BibT_eX]

[DOI]

Amir Shpilka

Electron. Colloquium Comput. Complex., 2014

Simultaneous Approximation of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Amey Bhangale

Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2014

2013

Random graphs and the parity quantifier.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

J. ACM, 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

New affine-invariant codes from lifting.

[BibT_eX]

[DOI]

Alan Guo

Madhu Sudan

Electron. Colloquium Comput. Complex., 2012

A new family of locally correctable codes based on degree-lifted algebraic geometry 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

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

On the List-Decodability of Random Linear Codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Johan Håstad

Electron. Colloquium Comput. Complex., 2010

Affine Dispersers from Subspace Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2009

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Optimal testing of Reed-Muller codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]

Electron. Colloquium Comput. Complex., 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 (FOCS 2006), 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]