Shubhangi Saraf
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Shubhangi Saraf has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
- Zeev Dvir
Department of Computer Science and Department of Mathematics, Princeton University, Princeton, USA
8 shared publications - Swastik Kopparty
Rutgers University
6 shared publications - Avi Wigderson
School of Mathematics, Institute for Advanced Study, Princeton, USA
3 shared publications - Guang-Da Hu
Shanghai Jian Qiao University, Shanghai, China
3 shared publications - Mrinal Kumar
Department of Computer Science Rutgers University
3 shared publications Charles Wolf
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1704-1715
Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1704-1715
Open AccessReconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-In
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1157-1167
On Proximity Gaps of Reed-Solomon Codes
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1157-1167
Open AccessOn Proximity Gaps of Reed-Solomon Codes
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 174-185
Closure under Factorization from a Result of Furstenberg
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 174-185
Open AccessClosure under Factorization from a Result of Furstenberg
- Open Access
- 28 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Reconstruction of Depth-4 Multilinear Circuits
We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ ( k ) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k , given black-box access to a polynomial \(f \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {F}|) \) and outputs a multilinear ΣΠΣΠ ( k ) circuit of size quasi-poly( n , s ) that computes f . Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ ( k ) circuits were known only for the case of k = 2 [GKL12,Vol17].- 28 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessReconstruction of Depth-4 Multilinear Circuits
We present a deterministic algorithm for reconstructing multilinear ΣΠΣΠ ( k ) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k , given black-box access to a polynomial \(f \in \mathbb {F}[x_{1},x_{2},\ldots,x_{n} ] \) computable by a multilinear ΣΠΣΠ ( k ) circuit of size s , the algorithm runs in time quasi-poly( \(n,s,|\mathbb {F}|) \) and outputs a multilinear ΣΠΣΠ ( k ) circuit of size quasi-poly( n , s ) that computes f . Our result solves an open problem posed in [GKL12] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ΣΠΣΠ ( k ) circuits were known only for the case of k = 2 [GKL12,Vol17]. - Open Access
- 11 October 2023
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 70 (5) , 1-57
Proximity Gaps for Reed–Solomon Codes
A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ 𝔽 q n , then every affine space is either entirely δ-close to the code or, alternatively, at most an ( n/q )-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on a formal element of an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.
- 11 October 2023
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 70 (5) , 1-57
Open AccessProximity Gaps for Reed–Solomon Codes
A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ 𝔽 q n , then every affine space is either entirely δ-close to the code or, alternatively, at most an ( n/q )-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on a formal element of an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.
- Open Access
Improved Low-Depth Set-Multilinear Circuit Lower Bounds
We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega \left( n^{1/\Delta}/\Delta\right)}$. The hard polynomial $f$ comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form $(\log n)^{\Omega (\Delta n^{1/\Delta})}$ was shown for the size of product-depth $\Delta$ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as $f$. Moreover, our lower bounds are novel for any $\Delta\geq 2$. For general set-multilinear formulas, a lower bound of the form $ n^{\Omega(\log n)}$ was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form $(\log n)^{\Omega(\log n)}$ for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form $n^{\Omega(\log n)}$, albeit for the same polynomial $f$ in VNP (the NW polynomial). As observed by LST, if the same $n^{\Omega(\log n)}$ size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.Open AccessImproved Low-Depth Set-Multilinear Circuit Lower Bounds
We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega \left( n^{1/\Delta}/\Delta\right)}$. The hard polynomial $f$ comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form $(\log n)^{\Omega (\Delta n^{1/\Delta})}$ was shown for the size of product-depth $\Delta$ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as $f$. Moreover, our lower bounds are novel for any $\Delta\geq 2$. For general set-multilinear formulas, a lower bound of the form $ n^{\Omega(\log n)}$ was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form $(\log n)^{\Omega(\log n)}$ for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form $n^{\Omega(\log n)}$, albeit for the same polynomial $f$ in VNP (the NW polynomial). As observed by LST, if the same $n^{\Omega(\log n)}$ size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas. - Open Access
On the number of ordinary lines determined by sets in complex space
Kelly's theorem states that a set of $n$ points affinely spanning $\mathbb{C}^3$ must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least $3n/2$ ordinary lines, unless the configuration has $n-1$ points in a plane and one point outside the plane (in which case there are at least $n-1$ ordinary lines). In addition, when at most $2n/3$ points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with 4 and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span 4 or more dimensions, with at most $2n/3$ points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines.Open AccessOn the number of ordinary lines determined by sets in complex space
Kelly's theorem states that a set of $n$ points affinely spanning $\mathbb{C}^3$ must determine at least one ordinary complex line (a line passing through exactly two of the points). Our main theorem shows that such sets determine at least $3n/2$ ordinary lines, unless the configuration has $n-1$ points in a plane and one point outside the plane (in which case there are at least $n-1$ ordinary lines). In addition, when at most $2n/3$ points are contained in any plane, we prove a theorem giving stronger bounds that take advantage of the existence of lines with 4 and more points (in the spirit of Melchior's and Hirzebruch's inequalities). Furthermore, when the points span 4 or more dimensions, with at most $2n/3$ points contained in any three dimensional affine subspace, we show that there must be a quadratic number of ordinary lines. - 14 September 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (1) , 296-316
On List Recovery of High-Rate Tensor Codes
We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS’17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time$N^{o(1)}$ . This improves over prior work by Gopi et. al. (SODA’17; IEEE Transactions on Information Theory’18) that only gave query complexity$N^{ \varepsilon }$ with rate that is exponentially small in$1/ \varepsilon $ . 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of$N^{\Omega (1/\log \log N)}$ on the product of query complexity and output list size for locally list recovering high-rate tensor codes.- 14 September 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (1) , 296-316
On List Recovery of High-Rate Tensor Codes
We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS’17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is approximately locally list recoverable, as well as globally list recoverable in probabilistic near-linear time. This was used in turn to give the first capacity-achieving list decodable codes with (1) local list decoding algorithms, and with (2) probabilistic near-linear time global list decoding algorithms. This also yielded constant-rate codes approaching the Gilbert-Varshamov bound with probabilistic near-linear time global unique decoding algorithms. In the current work we obtain the following results: 1) The tensor product of an efficient (poly-time) high-rate globally list recoverable code is globally list recoverable in deterministic near-linear time. This yields in turn the first capacity-achieving list decodable codes with deterministic near-linear time global list decoding algorithms. It also gives constant-rate codes approaching the Gilbert-Varshamov bound with deterministic near-linear time global unique decoding algorithms. 2) If the base code is additionally locally correctable, then the tensor product is (genuinely) locally list recoverable. This yields in turn (non-explicit) constant-rate codes approaching the Gilbert-Varshamov bound that are locally correctable with query complexity and running time$N^{o(1)}$ . This improves over prior work by Gopi et. al. (SODA’17; IEEE Transactions on Information Theory’18) that only gave query complexity$N^{ \varepsilon }$ with rate that is exponentially small in$1/ \varepsilon $ . 3) A nearly-tight combinatorial lower bound on output list size for list recovering high-rate tensor codes. This bound implies in turn a nearly-tight lower bound of$N^{\Omega (1/\log \log N)}$ on the product of query complexity and output list size for locally list recovering high-rate tensor codes.- Open Access
DEEP-FRI: Sampling outside the box improves soundness
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative form of a theorem which says that if an affine space $U$ is $\delta$-far in relative Hamming distance from a linear code $V$ - this is the worst-case assumption - then most elements of $U$ are almost $\delta$-far from $V$ - this is the average case. This leads to an optimal analysis of the soundness of the FRI protocol of [Ben-Sasson, et.al., eprint 2018] for proving proximity to Reed-Solomon codes. To further improve soundness, we sample outside the box. We suggest a new protocol which asks a prover for values of a polynomial at points outside the domain of evaluation of the Reed-Solomon code. We call this technique Domain Extending for Eliminating Pretenders (DEEP). We use the DEEP technique to devise two new protocols: (1) An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness of the protocol improves upon that of the FRI protocol while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. (2) An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$.Open AccessDEEP-FRI: Sampling outside the box improves soundness
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative form of a theorem which says that if an affine space $U$ is $\delta$-far in relative Hamming distance from a linear code $V$ - this is the worst-case assumption - then most elements of $U$ are almost $\delta$-far from $V$ - this is the average case. This leads to an optimal analysis of the soundness of the FRI protocol of [Ben-Sasson, et.al., eprint 2018] for proving proximity to Reed-Solomon codes. To further improve soundness, we sample outside the box. We suggest a new protocol which asks a prover for values of a polynomial at points outside the domain of evaluation of the Reed-Solomon code. We call this technique Domain Extending for Eliminating Pretenders (DEEP). We use the DEEP technique to devise two new protocols: (1) An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness of the protocol improves upon that of the FRI protocol while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. (2) An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$. - 24 October 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (4) , 778-808
On the Number of Ordinary Lines Determined by Sets in Complex Space
- 24 October 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (4) , 778-808
On the Number of Ordinary Lines Determined by Sets in Complex Space