Shubhangi Saraf

Narmada Varadarajan

CoRR, October, 2025

Constant-depth circuits for polynomial GCD over any characteristic.

[BibT_eX]

[DOI]

Somnath Bhattacharjee

Shanthanu S. Rai

Varun Ramanathan

Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2025

Closure under factorization from a result of Furstenberg.

[BibT_eX]

[DOI]

Somnath Bhattacharjee

Shanthanu S. Rai

Varun Ramanathan

Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2025

Deterministic factorization of constant-depth algebraic circuits in subexponential time.

[BibT_eX]

[DOI]

Somnath Bhattacharjee

Varun Ramanathan

Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2025

Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3.

[BibT_eX]

[DOI]

Devansh Shringi

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2024

Lower Bounds for Set-Multilinear Branching Programs.

[BibT_eX]

[DOI]

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

Exponential Lower Bounds Against Sums of ROABPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Linear Independence, Alternants, and Applications.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Near-Optimal Set-Multilinear Formula Lower Bounds.

[BibT_eX]

[DOI]

Deepanshu Kush

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Improved Low-Depth Set-Multilinear Circuit Lower Bounds.

[BibT_eX]

[DOI]

Deepanshu Kush

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Reconstruction of Depth-4 Multilinear Circuits.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 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

2019

On List Recovery of High-Rate Tensor Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Finite Field Kakeya and Nikodym Sets in Three Dimensions.

[BibT_eX]

[DOI]

Ben Lund

Charles Wolf

SIAM J. Discret. Math., 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

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.

[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]

Eli Ben-Sasson

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals.

[BibT_eX]

[DOI]

Theory Comput., 2017

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.

[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

On the Number of Ordinary Lines Determined by Sets in Complex Space.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Locally Decodable Codes.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

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

[BibT_eX]

[DOI]

SIGACT News, 2016

Incidence Bounds for Block Designs.

[BibT_eX]

[DOI]

Ben Lund

SIAM J. Discret. Math., 2016

Maximally Recoverable Codes for Grid-like Topologies.

[BibT_eX]

[DOI]

CoRR, 2016

Tight lower bounds for linear 2-query LCCs over finite fields.

[BibT_eX]

[DOI]

Comb., 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

Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Arithmetic Circuits with Locally Low Algebraic Rank.

[BibT_eX]

[DOI]

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

Equivalence of Polynomial Identity Testing and Polynomial Factorization.

[BibT_eX]

[DOI]

Amir Shpilka

Comput. Complex., 2015

2014

Lower Bounds for Approximate LDC.

[BibT_eX]

[DOI]

CoRR, 2014

The limits of depth reduction for arithmetic formulas: it's all about the top fan-in.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Breaking the quadratic barrier for 3-LCC's over the reals.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Helly-Type Theorems in Property Testing.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits.

[BibT_eX]

[DOI]

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

Lower Bounds for Approximate LDCs.

[BibT_eX]

[DOI]

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

On the Power of Homogeneous Depth 4 Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Recent Progress on Lower Bounds for Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 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

Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Breaking the quadratic barrier for 3-LCCs over the Reals.

[BibT_eX]

[DOI]

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

2012

Improved rank bounds for design matrices and a new proof of Kelly's theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Sylvester-Gallai type theorems for approximate collinearity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

2011

The method of multiplicities.

[BibT_eX]

[DOI]

PhD thesis, 2011

Black-box identity testing of depth-4 multilinear circuits.

[BibT_eX]

[DOI]

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

High-rate codes with sublinear-time decoding.

[BibT_eX]

[DOI]

Sergey Yekhanin

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

Tight Lower Bounds for 2-query LCCs over Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Noisy Interpolation of Sparse Polynomials, and Applications.

[BibT_eX]

[DOI]

Sergey Yekhanin

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

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

Some Recent Results on Local Testing of Sparse Linear Codes.

[BibT_eX]

[DOI]

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

2009

Acute and nonobtuse triangulations of polyhedral surfaces.

[BibT_eX]

[DOI]

Eur. J. Comb., 2009

Blackbox Polynomial Identity Testing for Depth 3 Circuits.

[BibT_eX]

[DOI]

Neeraj Kayal

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 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

Tolerant Linearity Testing and Locally Testable Codes.

[BibT_eX]

[DOI]