SSShubhangi Saraf

Shubhangi Saraf

*This is an algorithmically generated author record based on publicly available information.

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


Shubhangi Saraf has a total of 40 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

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

    by Shubhangi Saraf, Devansh Shringi, Narmada Varadarajan

  • Open Access

    On Proximity Gaps of Reed-Solomon Codes

    by Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, Shubhangi Saraf


  • Open Access

    Closure under Factorization from a Result of Furstenberg

    by Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

  • Open Access

    Reconstruction of Depth-4 Multilinear Circuits

    by Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

    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

    Proximity Gaps for Reed–Solomon Codes

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

    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

    by Deepanshu Kush, Shubhangi Saraf

    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

    by Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf

    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.

  • On List Recovery of High-Rate Tensor Codes

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

    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

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

    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$.


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

    by Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf