Shubhangi Saraf

ORCID

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 71

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

STOC

Computational Complexity Conference

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Lower Bounds for Set-Multilinear Branching Programs. CCC (2024)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Lower Bounds for Set-Multilinear Branching Programs. CoRR (2023)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes. SIAM J. Comput. 52 (3) (2023)
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
Exponential Lower Bounds Against Sums of ROABPs. Electron. Colloquium Comput. Complex. (2023)
Deepanshu Kush, Shubhangi Saraf
Near-Optimal Set-Multilinear Formula Lower Bounds. Electron. Colloquium Comput. Complex. (2023)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes. Electron. Colloquium Comput. Complex. (2023)
Deepanshu Kush, Shubhangi Saraf
Near-Optimal Set-Multilinear Formula Lower Bounds. CCC (2023)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Linear Independence, Alternants and Applications. Electron. Colloquium Comput. Complex. (2023)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes. CoRR (2023)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Linear Independence, Alternants, and Applications. STOC (2023)
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
Proximity Gaps for Reed-Solomon Codes. J. ACM 70 (5) (2023)
Deepanshu Kush, Shubhangi Saraf
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. CCC (2022)
Deepanshu Kush, Shubhangi Saraf
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. Electron. Colloquium Comput. Complex. (2022)
Deepanshu Kush, Shubhangi Saraf
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. CoRR (2022)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. CoRR (2021)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
On List Recovery of High-Rate Tensor Codes. IEEE Trans. Inf. Theory 67 (1) (2021)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. STOC (2021)
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
DEEP-FRI: Sampling Outside the Box Improves Soundness. ITCS (2020)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. J. ACM 67 (2) (2020)
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
Proximity Gaps for Reed-Solomon Codes. Electron. Colloquium Comput. Complex. 27 (2020)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction of Depth-4 Multilinear Circuits. SODA (2020)
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
Proximity Gaps for Reed-Solomon Codes. IACR Cryptol. ePrint Arch. 2020 (2020)
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
Proximity Gaps for Reed-Solomon Codes. FOCS (2020)
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
DEEP-FRI: Sampling outside the box improves soundness. CoRR (2019)
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
DEEP-FRI: Sampling Outside the Box Improves Soundness. Electron. Colloquium Comput. Complex. 26 (2019)
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
On List Recovery of High-Rate Tensor Codes. Electron. Colloquium Comput. Complex. 26 (2019)
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
On the Number of Ordinary Lines Determined by Sets in Complex Space. Discret. Comput. Geom. 61 (4) (2019)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Reconstruction of Depth-$4$ Multilinear Circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
DEEP-FRI: Sampling Outside the Box Improves Soundness. IACR Cryptol. ePrint Arch. 2019 (2019)
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
On List Recovery of High-Rate Tensor Codes. APPROX-RANDOM (2019)
Ben Lund, Shubhangi Saraf, Charles Wolf
Finite Field Kakeya and Nikodym Sets in Three Dimensions. SIAM J. Discret. Math. 32 (4) (2018)
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound. IEEE Trans. Inf. Theory 64 (8) (2018)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. Electron. Colloquium Comput. Complex. 25 (2018)
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf
Worst-case to average case reductions for the distance to a code. Electron. Colloquium Comput. Complex. 25 (2018)
Shubhangi Saraf, Ilya Volkovich
Black-Box Identity Testing of Depth-4 Multilinear Circuits. Comb. 38 (5) (2018)
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf
Worst-Case to Average Case Reductions for the Distance to a Code. Computational Complexity Conference (2018)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
Improved decoding of Folded Reed-Solomon and Multiplicity Codes. CoRR (2018)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes. FOCS (2018)
Mrinal Kumar, Shubhangi Saraf
Arithmetic Circuits with Locally Low Algebraic Rank. CoRR (2018)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. FOCS (2018)
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. CoRR (2018)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. Int. J. Comput. Geom. Appl. 28 (4) (2018)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
Improved decoding of Folded Reed-Solomon and Multiplicity Codes. Electron. Colloquium Comput. Complex. 25 (2018)
Swastik Kopparty, Shubhangi Saraf
Local Testing and Decoding of High-Rate Error-Correcting Codes. Electron. Colloquium Comput. Complex. 24 (2017)
Mrinal Kumar, Shubhangi Saraf
Arithmetic Circuits with Locally Low Algebraic Rank. Theory Comput. 13 (1) (2017)
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity. J. ACM 64 (2) (2017)
Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin
Maximally Recoverable Codes for Grid-like Topologies. SODA (2017)
Mrinal Kumar, Shubhangi Saraf
On the Power of Homogeneous Depth 4 Arithmetic Circuits. SIAM J. Comput. 46 (1) (2017)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. 24 (2017)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR (2017)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals. Theory Comput. 13 (1) (2017)
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
On the Number of Ordinary Lines Determined by Sets in Complex Space. SoCG (2017)
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound. SODA (2017)
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. STOC (2016)
Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang, Sergey Yekhanin
Maximally Recoverable Codes for Grid-like Topologies. CoRR (2016)
Mrinal Kumar, Shubhangi Saraf
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. Computational Complexity Conference (2016)
Swastik Kopparty, Shubhangi Saraf
Guest Column: Local Testing and Decoding of High-Rate Error-Correcting Codes. SIGACT News 47 (3) (2016)
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
On the number of ordinary lines determined by sets in complex space. CoRR (2016)
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
Tight lower bounds for linear 2-query LCCs over finite fields. Comb. 36 (1) (2016)
Ben Lund, Shubhangi Saraf
Incidence Bounds for Block Designs. SIAM J. Discret. Math. 30 (4) (2016)
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound. Electron. Colloquium Comput. Complex. 23 (2016)
Mrinal Kumar, Shubhangi Saraf
Arithmetic Circuits with Locally Low Algebraic Rank. Computational Complexity Conference (2016)
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity. CoRR (2015)
Mrinal Kumar, Shubhangi Saraf
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing. CoRR (2015)
Mrinal Kumar, Shubhangi Saraf
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing. Electron. Colloquium Comput. Complex. 22 (2015)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Polynomial Factorization. Comput. Complex. 24 (2) (2015)
Mrinal Kumar, Shubhangi Saraf
The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In. SIAM J. Comput. 44 (6) (2015)
Mrinal Kumar, Shubhangi Saraf
Arithmetic circuits with locally low algebraic rank. Electron. Colloquium Comput. Complex. 22 (2015)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Computational Complexity Conference (2014)
Mrinal Kumar, Shubhangi Saraf
On the power of homogeneous depth 4 arithmetic circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Shubhangi Saraf
Recent Progress on Lower Bounds for Arithmetic Circuits. Computational Complexity Conference (2014)
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
Lower Bounds for Approximate LDCs. ICALP (1) (2014)
Mrinal Kumar, Shubhangi Saraf
On the power of homogeneous depth 4 arithmetic circuits. CoRR (2014)
Mrinal Kumar, Shubhangi Saraf
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in. STOC (2014)
Mrinal Kumar, Shubhangi Saraf
On the Power of Homogeneous Depth 4 Arithmetic Circuits. FOCS (2014)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. LATIN (2014)
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Electron. Colloquium Comput. Complex. 21 (2014)
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
Lower Bounds for Approximate LDC. CoRR (2014)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Breaking the quadratic barrier for 3-LCC's over the reals. STOC (2014)
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin
High-rate codes with sublinear-time decoding. J. ACM 61 (5) (2014)
Mrinal Kumar, Shubhangi Saraf
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits. ICALP (1) (2014)
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
Lower Bounds for Approximate LDCs. Electron. Colloquium Comput. Complex. 21 (2014)
Mrinal Kumar, Shubhangi Saraf
Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin. Electron. Colloquium Comput. Complex. 20 (2013)
Mrinal Kumar, Shubhangi Saraf
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. Electron. Colloquium Comput. Complex. 20 (2013)
Mrinal Kumar, Shubhangi Saraf
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. CoRR (2013)
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf
A new family of locally correctable codes based on degree-lifted algebraic geometry codes. STOC (2013)
Mrinal Kumar, Shubhangi Saraf
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in. CoRR (2013)
Mrinal Kumar, Shubhangi Saraf
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in. Electron. Colloquium Comput. Complex. 20 (2013)
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
Helly-Type Theorems in Property Testing. CoRR (2013)
Swastik Kopparty, Shubhangi Saraf
Local List-Decoding and Testing of Random Linear Codes from High Error. SIAM J. Comput. 42 (3) (2013)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Breaking the quadratic barrier for 3-LCCs over the Reals. Electron. Colloquium Comput. Complex. 20 (2013)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Breaking the quadratic barrier for 3-LCCs over the Reals. CoRR (2013)
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. SIAM J. Comput. 42 (6) (2013)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Improved rank bounds for design matrices and a new proof of Kelly's theorem. Electron. Colloquium Comput. Complex. 19 (2012)
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Improved rank bounds for design matrices and a new proof of Kelly's theorem CoRR (2012)
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Sylvester-Gallai type theorems for approximate collinearity. Electron. Colloquium Comput. Complex. 19 (2012)
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Sylvester-Gallai type theorems for approximate collinearity CoRR (2012)

Shubhangi Saraf.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shubhangi Saraf