Shubhangi Saraf

138 papers A* 21A 13B 1Journal 96Unranked 4
YearRankTypeTitle / Venue / Authors
2026 A ed.
17th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026
ITCS
Shubhangi Saraf
2026 J jnl
Linear Independence, Alternants and Applications.
SIAM J. Comput.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2025 J jnl
Closure under factorization from a result of Furstenberg.
CoRR
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Closure under factorization from a result of Furstenberg.
Electron. Colloquium Comput. Complex.
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Constant-depth circuits for polynomial GCD over any characteristic.
CoRR
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Constant-depth circuits for polynomial GCD over any characteristic.
Electron. Colloquium Comput. Complex.
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 A* conf
Deterministic factorization of constant-depth algebraic circuits in subexponential time.
FOCS
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Deterministic factorization of constant-depth algebraic circuits in subexponential time.
CoRR
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Deterministic factorization of constant-depth algebraic circuits in subexponential time.
Electron. Colloquium Comput. Complex.
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
2025 J jnl
Integer points in dilates of polytopes.
CoRR
Shubhangi Saraf, Narmada Varadarajan
2025 J jnl
On Proximity Gaps for Reed-Solomon Codes.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf
2025 J jnl
On Proximity Gaps for Reed-Solomon Codes.
IACR Cryptol. ePrint Arch.
Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf
2025 J jnl
Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$.
Electron. Colloquium Comput. Complex.
Shubhangi Saraf, Devansh Shringi
2025 A conf
Reconstruction of Depth 3 Arithmetic Circuits with Top Fan-In 3.
CCC
Shubhangi Saraf, Devansh Shringi
2025 J jnl
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-in.
Electron. Colloquium Comput. Complex.
Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan
2025 J jnl
Reconstruction of Depth-4 Multilinear Circuits.
ACM Trans. Comput. Theory
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2024 J jnl
Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381).
Dagstuhl Reports
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, Jacobo Torán, Kilian Rothmund
2024 A conf
Lower Bounds for Set-Multilinear Branching Programs.
CCC
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
Exponential Lower Bounds Against Sums of ROABPs.
Electron. Colloquium Comput. Complex.
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes.
SIAM J. Comput.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
2023 J jnl
Linear Independence, Alternants and Applications.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023 A* conf
Linear Independence, Alternants, and Applications.
STOC
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023 J jnl
Lower Bounds for Set-Multilinear Branching Programs.
CoRR
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 A conf
Near-Optimal Set-Multilinear Formula Lower Bounds.
CCC
Deepanshu Kush, Shubhangi Saraf
2023 J jnl
Near-Optimal Set-Multilinear Formula Lower Bounds.
Electron. Colloquium Comput. Complex.
Deepanshu Kush, Shubhangi Saraf
2023 J jnl
Proximity Gaps for Reed-Solomon Codes.
J. ACM
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
2023 J jnl
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes.
CoRR
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
2023 J jnl
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
2022 A conf
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
CCC
Deepanshu Kush, Shubhangi Saraf
2022 J jnl
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
CoRR
Deepanshu Kush, Shubhangi Saraf
2022 J jnl
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
Electron. Colloquium Comput. Complex.
Deepanshu Kush, Shubhangi Saraf
2021 J jnl
On List Recovery of High-Rate Tensor Codes.
IEEE Trans. Inf. Theory
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
2021 J jnl
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.
CoRR
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021 J jnl
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021 A* conf
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.
STOC
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020 A ed.
35th Computational Complexity Conference, CCC 2020, Saarbrücken, Germany (Virtual Conference), July 28-31, 2020
CCC
Shubhangi Saraf
2020 A conf
DEEP-FRI: Sampling Outside the Box Improves Soundness.
ITCS
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
2020 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
J. ACM
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020 A* conf
Proximity Gaps for Reed-Solomon Codes.
FOCS
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
2020 J jnl
Proximity Gaps for Reed-Solomon Codes.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
2020 J jnl
Proximity Gaps for Reed-Solomon Codes.
IACR Cryptol. ePrint Arch.
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf
2020 A* conf
Reconstruction of Depth-4 Multilinear Circuits.
SODA
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2019 J jnl
DEEP-FRI: Sampling Outside the Box Improves Soundness.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
2019 J jnl
DEEP-FRI: Sampling Outside the Box Improves Soundness.
IACR Cryptol. ePrint Arch.
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
2019 J jnl
DEEP-FRI: Sampling outside the box improves soundness.
CoRR
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
2019 — conf
On List Recovery of High-Rate Tensor Codes.
APPROX-RANDOM
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
2019 J jnl
On List Recovery of High-Rate Tensor Codes.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas
2019 J jnl
On the Number of Ordinary Lines Determined by Sets in Complex Space.
Discret. Comput. Geom.
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
2019 J jnl
Reconstruction of Depth-$4$ Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Arithmetic Circuits with Locally Low Algebraic Rank.
CoRR
Mrinal Kumar, Shubhangi Saraf
2018 J jnl
Black-Box Identity Testing of Depth-4 Multilinear Circuits.
Comb.
Shubhangi Saraf, Ilya Volkovich
2018 A* conf
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
FOCS
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
CoRR
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.
Electron. Colloquium Comput. Complex.
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018 J jnl
Finite Field Kakeya and Nikodym Sets in Three Dimensions.
SIAM J. Discret. Math.
Ben Lund, Shubhangi Saraf, Charles Wolf
2018 J jnl
Helly-Type Theorems in Property Testing.
Int. J. Comput. Geom. Appl.
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
2018 A* conf
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes.
FOCS
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
2018 J jnl
Improved decoding of Folded Reed-Solomon and Multiplicity Codes.
CoRR
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
2018 J jnl
Improved decoding of Folded Reed-Solomon and Multiplicity Codes.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters
2018 J jnl
Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound.
IEEE Trans. Inf. Theory
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
2018 A conf
Worst-Case to Average Case Reductions for the Distance to a Code.
CCC
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf
2018 J jnl
Worst-case to average case reductions for the distance to a code.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf
2017 J jnl
Arithmetic Circuits with Locally Low Algebraic Rank.
Theory Comput.
Mrinal Kumar, Shubhangi Saraf
2017 J jnl
High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity.
J. ACM
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
2017 J jnl
Local Testing and Decoding of High-Rate Error-Correcting Codes.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Shubhangi Saraf
2017 A* conf
Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound.
SODA
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
2017 A* conf
Maximally Recoverable Codes for Grid-like Topologies.
SODA
Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin
2017 A* conf
On the Number of Ordinary Lines Determined by Sets in Complex Space.
SoCG
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
2017 J jnl
On the Power of Homogeneous Depth 4 Arithmetic Circuits.
SIAM J. Comput.
Mrinal Kumar, Shubhangi Saraf
2017 J jnl
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals.
Theory Comput.
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2017 J jnl
Towards an algebraic natural proofs barrier via polynomial identity testing.
CoRR
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2017 J jnl
Towards an algebraic natural proofs barrier via polynomial identity testing.
Electron. Colloquium Comput. Complex.
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2016 A conf
Arithmetic Circuits with Locally Low Algebraic Rank.
CCC
Mrinal Kumar, Shubhangi Saraf
2016 J jnl
Guest Column: Local Testing and Decoding of High-Rate Error-Correcting Codes.
SIGACT News
Swastik Kopparty, Shubhangi Saraf
2016 A* conf
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity.
STOC
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
2016 J jnl
Incidence Bounds for Block Designs.
SIAM J. Discret. Math.
Ben Lund, Shubhangi Saraf
2016 — ch.
Locally Decodable Codes.
Encyclopedia of Algorithms
Shubhangi Saraf
2016 J jnl
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound.
Electron. Colloquium Comput. Complex.
Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf
2016 J jnl
Maximally Recoverable Codes for Grid-like Topologies.
CoRR
Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang, Sergey Yekhanin
2016 J jnl
On the number of ordinary lines determined by sets in complex space.
CoRR
Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf
2016 A conf
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing.
CCC
Mrinal Kumar, Shubhangi Saraf
2016 J jnl
Tight lower bounds for linear 2-query LCCs over finite fields.
Comb.
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
2015 J jnl
Arithmetic circuits with locally low algebraic rank.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2015 J jnl
Equivalence of Polynomial Identity Testing and Polynomial Factorization.
Comput. Complex.
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2015 J jnl
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity.
CoRR
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
2015 J jnl
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf
2015 J jnl
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
2015 J jnl
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing.
CoRR
Mrinal Kumar, Shubhangi Saraf
2015 J jnl
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2015 J jnl
The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In.
SIAM J. Comput.
Mrinal Kumar, Shubhangi Saraf
2014 A* conf
Breaking the quadratic barrier for 3-LCC's over the reals.
STOC
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2014 A conf
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.
CCC
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2014 J jnl
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
2014 B conf
Helly-Type Theorems in Property Testing.
LATIN
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
2014 J jnl
High-rate codes with sublinear-time decoding.
J. ACM
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin
2014 J jnl
Lower Bounds for Approximate LDC.
CoRR
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
2014 — conf
Lower Bounds for Approximate LDCs.
ICALP (1)
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
2014 J jnl
Lower Bounds for Approximate LDCs.
Electron. Colloquium Comput. Complex.
Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf
2014 A* conf
On the Power of Homogeneous Depth 4 Arithmetic Circuits.
FOCS
Mrinal Kumar, Shubhangi Saraf
2014 J jnl
On the power of homogeneous depth 4 arithmetic circuits.
CoRR
Mrinal Kumar, Shubhangi Saraf
2014 J jnl
On the power of homogeneous depth 4 arithmetic circuits.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2014 A conf
Recent Progress on Lower Bounds for Arithmetic Circuits.
CCC
Shubhangi Saraf
2014 — conf
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits.
ICALP (1)
Mrinal Kumar, Shubhangi Saraf
2014 A* conf
The limits of depth reduction for arithmetic formulas: it's all about the top fan-in.
STOC
Mrinal Kumar, Shubhangi Saraf
2013 A* conf
A new family of locally correctable codes based on degree-lifted algebraic geometry codes.
STOC
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf
2013 J jnl
Breaking the quadratic barrier for 3-LCCs over the Reals.
CoRR
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2013 J jnl
Breaking the quadratic barrier for 3-LCCs over the Reals.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2013 J jnl
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.
SIAM J. Comput.
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2013 J jnl
Helly-Type Theorems in Property Testing.
CoRR
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf
2013 J jnl
Local List-Decoding and Testing of Random Linear Codes from High Error.
SIAM J. Comput.
Swastik Kopparty, Shubhangi Saraf
2013 J jnl
Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2013 J jnl
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits.
CoRR
Mrinal Kumar, Shubhangi Saraf
2013 J jnl
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2013 J jnl
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in.
CoRR
Mrinal Kumar, Shubhangi Saraf
2013 J jnl
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in.
Electron. Colloquium Comput. Complex.
Mrinal Kumar, Shubhangi Saraf
2012 J jnl
A new family of locally correctable codes based on degree-lifted algebraic geometry codes.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf
2012 J jnl
Improved rank bounds for design matrices and a new proof of Kelly's theorem
CoRR
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012 J jnl
Improved rank bounds for design matrices and a new proof of Kelly's theorem.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012 J jnl
Sylvester-Gallai type theorems for approximate collinearity
CoRR
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2012 J jnl
Sylvester-Gallai type theorems for approximate collinearity.
Electron. Colloquium Comput. Complex.
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson
2011 J jnl
Black-Box Identity Testing of Depth-4 Multilinear Circuits.
Electron. Colloquium Comput. Complex.
Shubhangi Saraf, Ilya Volkovich
2011 A* conf
Black-box identity testing of depth-4 multilinear circuits.
STOC
Shubhangi Saraf, Ilya Volkovich
2011 A* conf
High-rate codes with sublinear-time decoding.
STOC
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin
2011 A conf
Noisy Interpolation of Sparse Polynomials, and Applications.
CCC
Shubhangi Saraf, Sergey Yekhanin
2011 J jnl
Noisy Interpolation of Sparse Polynomials, and Applications.
Electron. Colloquium Comput. Complex.
Shubhangi Saraf, Sergey Yekhanin
2011 — —
The method of multiplicities.
Shubhangi Saraf
2011 A* conf
Tight Lower Bounds for 2-query LCCs over Finite Fields.
FOCS
Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf
2011 J jnl
Tight lower bounds for 2-query LCCs over finite fields.
Electron. Colloquium Comput. Complex.
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
2010 J jnl
High-rate codes with sublinear-time decoding.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin
2010 A* conf
Local list-decoding and testing of random linear codes from high error.
STOC
Swastik Kopparty, Shubhangi Saraf
2010 — ch.
Some Recent Results on Local Testing of Sparse Linear Codes.
Property Testing
Swastik Kopparty, Shubhangi Saraf
2009 J jnl
Acute and nonobtuse triangulations of polyhedral surfaces.
Eur. J. Comb.
Shubhangi Saraf
2009 A* conf
Blackbox Polynomial Identity Testing for Depth 3 Circuits.
FOCS
Neeraj Kayal, Shubhangi Saraf
2009 J jnl
Blackbox Polynomial Identity Testing for Depth 3 Circuits.
Electron. Colloquium Comput. Complex.
Neeraj Kayal, Shubhangi Saraf
2009 A* conf
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.
FOCS
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2009 J jnl
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers.
Electron. Colloquium Comput. Complex.
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2009 J jnl
Local list-decoding and testing of random linear codes from high-error.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Shubhangi Saraf
2009 — conf
Tolerant Linearity Testing and Locally Testable Codes.
APPROX-RANDOM
Swastik Kopparty, Shubhangi Saraf