Shubhangi Saraf

According to our database, Shubhangi Saraf authored at least 58 papers between 2009 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Proximity Gaps for Reed-Solomon Codes.

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

J. ACM, October, 2023

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

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

SIAM J. Comput., June, 2023

Near-Optimal Set-Multilinear Formula Lower Bounds.

Deepanshu Kush, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2023

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

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2023

Exponential Lower Bounds Against Sums of ROABPs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2023

Linear Independence, Alternants and Applications.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2023

Lower Bounds for Set-Multilinear Branching Programs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

CoRR, 2023

2022

Improved Low-Depth Set-Multilinear Circuit Lower Bounds.

Deepanshu Kush, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2022

2021

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2021

2020

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

J. ACM, 2020

2019

On List Recovery of High-Rate Tensor Codes.

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

Electron. Colloquium Comput. Complex., 2019

Reconstruction of Depth-$4$ Multilinear Circuits.

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Electron. Colloquium Comput. Complex., 2019

DEEP-FRI: Sampling Outside the Box Improves Soundness.

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2019

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

Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf

Discret. Comput. Geom., 2019

2018

Finite Field Kakeya and Nikodym Sets in Three Dimensions.

Ben Lund, Shubhangi Saraf, Charles Wolf

SIAM J. Discret. Math., 2018

Helly-Type Theorems in Property Testing.

Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf

Int. J. Comput. Geom. Appl., 2018

Improved decoding of Folded Reed-Solomon and Multiplicity Codes.

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Electron. Colloquium Comput. Complex., 2018

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

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2018

Black-Box Identity Testing of Depth-4 Multilinear Circuits.

Shubhangi Saraf, Ilya Volkovich

Comb., 2018

2017

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

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Theory Comput., 2017

Arithmetic Circuits with Locally Low Algebraic Rank.

Mrinal Kumar, Shubhangi Saraf

Theory Comput., 2017

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

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

J. ACM, 2017

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

Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.

Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2017

Maximally Recoverable Codes for Grid-like Topologies.

Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

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

2016

Locally Decodable Codes.

Shubhangi Saraf

Encyclopedia of Algorithms, 2016

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

Swastik Kopparty, Shubhangi Saraf

SIGACT News, 2016

Incidence Bounds for Block Designs.

Ben Lund, Shubhangi Saraf

SIAM J. Discret. Math., 2016

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

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2016

Maximally Recoverable Codes for Grid-like Topologies.

Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

CoRR, 2016

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Comb., 2016

2015

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

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2015

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

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2015

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2015

Equivalence of Polynomial Identity Testing and Polynomial Factorization.

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Comput. Complex., 2015

2014

High-rate codes with sublinear-time decoding.

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

J. ACM, 2014

On the power of homogeneous depth 4 arithmetic circuits.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2014

Lower Bounds for Approximate LDCs.

Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2014

Lower Bounds for Approximate LDC.

Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf

CoRR, 2014

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

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Proceedings of the Symposium on Theory of Computing, 2014

Recent Progress on Lower Bounds for Arithmetic Circuits.

Shubhangi Saraf

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

2013

Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

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

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

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

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Electron. Colloquium Comput. Complex., 2013

2012

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

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Electron. Colloquium Comput. Complex., 2012

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

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2012

Sylvester-Gallai type theorems for approximate collinearity.

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Electron. Colloquium Comput. Complex., 2012

2011

The method of multiplicities.

Shubhangi Saraf

PhD thesis, 2011

Noisy Interpolation of Sparse Polynomials, and Applications.

Shubhangi Saraf, Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2011

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2011

2010

Some Recent Results on Local Testing of Sparse Linear Codes.

Swastik Kopparty, Shubhangi Saraf

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

2009

Acute and nonobtuse triangulations of polyhedral surfaces.

Shubhangi Saraf

Eur. J. Comb., 2009

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

Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2009

Blackbox Polynomial Identity Testing for Depth 3 Circuits.

Neeraj Kayal, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2009

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

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Electron. Colloquium Comput. Complex., 2009

Tolerant Linearity Testing and Locally Testable Codes.

Swastik Kopparty, Shubhangi Saraf

Proceedings of the Approximation, 2009