@inproceedings{bib_A_We_2026, AUTHOR = {Chillara, Suryajith and Gupta, Kriti }, TITLE = {A Weight Dichotomy for the Multiplicity–Storage Tradeoff in Coded PIR}, BOOKTITLE = {Information Theory Workshop}. YEAR = {2026}}

A fundamental tension in coded Private Information Retrieval (PIR) lies in balancing the storage overhead placed on servers against the communication and query complexity demanded from the user. The Woodruff–Yekhanin (WY) scheme~cite{WY05} and cite{DGY11, DG15, GKS25} achieve low query complexity by letting servers compute high-order directional derivatives over a fully replicated Reed–Muller codeword, while the Lavauzelle–Nardi (LN) scheme~cite{LN21} minimizes storage to a single encoded curve per server, at the price of maximum query complexity. We establish that a genuine intermediate multiplicity–storage tradeoff exists emph{if and only if} the line-degree parameter $omega geq 2$. For $omega = 1$ (affine-line-based coding), enabling even first-order multiplicity forces complete WY-like codeword replication. For Weighted Reed–Muller (WRM) codes with weight $eta = omega geq 2$, the non-surjectivity of polynomials of degree at least 2 over finite fields creates algebraic "slack" that supports fractional co-location: a server stores $t = s+1$ parallel-class curves, and a Vandermonde inversion lets the user extract the desired derivative while keeping the private query direction hidden. Conditional on a natural Polynomial Image Independence Conjecture (PIIC), whose $s=1$ case is the classical Weil bound, the marginal storage cost of each additional multiplicity unit follows a geometric series that halves at every step. The protocol achieves strict $omega$-privacy: any coalition of up to $omega$ servers learns nothing about the target index.

@inproceedings{bib_Shor_2026, AUTHOR = {Chillara, Suryajith and Gajjar, Kshitij and G, Nithish Raja }, TITLE = {Shortest Paths with Linear Edge Weights}, BOOKTITLE = {Annual Symposium on Foundations of Computer Science}. YEAR = {2026}}

We study shortest paths in directed graphs whose edge weights are of the form $$ mathsf{wt}(e) = a_{e,1} lambda_1 + a_{e,2} lambda_2 + a_{e,3} lambda_3 + cdots + a_{e,d} lambda_d + a_{e,d+1}.$$ Here, each $a_{e,i}inmathbb{R}$ is a fixed constant for each edge $e$, whereas each $lambda_i$ is a shared variable across the entire graph. So, there could be different shortest paths in the graph for different values of the $lambda_i$'s. The number of such shortest paths is of interest in several combinatorial optimization problems. This is called the emph{Parametric Shortest Paths} problem, and has been studied since the 1980s. For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(log n)}$. She also proved a matching lower bound of $n^{Omega(log n)}$, which was later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years. In this paper, we close this long line of research by showing an $n^{O(dlog n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Omega(dlog n)}$ can be obtained by trivially extending existing lower bound constructions for $d=1$. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(log{n}+log{q})}$. Finally, building upon work on the emph{Point Location} problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a emph{Shortest Path Oracle} which takes as input a point $overline{x}in mathbb{R}^d$, and outputs a shortest path at $overline{lambda}=overline{x}$ in sublinear time (for a wide regime of $d$). All earlier upper bound proofs proceeded by arranging the vertices of the graph in layers, splitting the graph across its middle layer into two ``halves'', and then recursing on each half-graph. We deviate from this proof methodology by ``halving'' the graph in a different way: we eliminate all the odd-numbered layers and retain only the even-numbered layers, whilst maintaining requisite shortest paths of the original graph. We then view shortest paths in the half-graph as convex objects in $d$-dimensional space, which leads us to the required recurrence.

@inproceedings{bib_Mult_2026, AUTHOR = {Pruthvi, Boyapati V S S and Chillara, Suryajith and Vempati, Pratyush }, TITLE = {Multilinear Formula Lower Bounds for Sparse Determinants}, BOOKTITLE = {Computational Complexity Conference}. YEAR = {2026}}

Raz (2009) proved that multilinear formulas computing the determinant of a generic $n times n$ matrix require size $n^{Omega(log n)}$. A fundamental question in understanding this lower bound is identifying which structural properties of the determinant drive this hardness. Is it the quadratic number of variables? The dense connectivity? Specific algebraic symmetries? We establish that density is not essential. We prove the existence of $n times n$ symbolic matrices with only $Theta(n log^6 n)$ nonzero entries - reducing the variable count by a factor of $n/{log^6 n}$ - such that any multilinear formula computing their determinants still requires size $n^{Omega(log n)}$. Our construction uses rectangle sampling from the complete bipartite graph to generate sparse matrices that simultaneously maintain perfect matchings (ensuring nonzero determinant) while exhibiting diagonal imbalance under random vertex permutations - a geometric property we identify as the key driver of factor imbalance in Raz's framework. This demonstrates that Raz's partial derivatives method is remarkably robust to sparsification, and suggests that the fundamental source of multilinear hardness for determinant lies in expansion-like combinatorial structure rather than density. Our techniques combine concentration inequalities for dependent random variables with insights from random graph theory.

@inproceedings{bib_Frac_2025, AUTHOR = {Jakhar, Gunank Singh and Kurri, Gowtham Raghunath and Chillara, Suryajith and Prabhakaran, Vinod M. }, TITLE = {Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications}, BOOKTITLE = {International Symposium on Information Theory}. YEAR = {2025}}

Submodular functions are known to satisfy various forms of fractional subadditivity. This work investigates the conditions for equality to hold exactly or approximately in the fractional subadditivity of submodular functions. We establish that a small gap in the inequality implies that the function is close to being modular, and that the gap is zero if and only if the function is modular. We then present natural implications of these results for special cases of submodular functions, such as entropy, relative entropy, and matroid rank. As a consequence, we characterize the necessary and sufficient conditions for equality to hold in Shearer's lemma, recovering a result of Ellis et al. (2016) as a special case. We leverage our results to propose a new multivariate mutual information, which generalizes Watanabe's total correlation (1960), Han's dual total correlation (1975), and Csiszar and Narayan's shared information (2004), and analyze its properties. Among these properties, we extend Watanabe's characterization of total correlation as the maximum correlation over partitions to fractional partitions. When applied to matrix determinantal inequalities for positive definite matrices, our results recover the equality conditions of the classical determinantal inequalities of Hadamard, Szasz, and Fischer as special cases.

@inproceedings{bib_Bran_2025, AUTHOR = {Chillara, Suryajith and G, Nithish Raja }, TITLE = {Branching Programs with Extended Memory: New Insights}, BOOKTITLE = {International Conference on Algorithms and Complexity}. YEAR = {2025}}

One of the central themes of Algebraic Complexity Theory is to understand the relative computation power of algebraic complexity classes VP and VNP. VP is a class of polynomial families which can be computed efficiently by algebraic circuits. VNP is a class of polynomials which can be efficiently expressed through polynomial families in VP, but we do not know if they can be computed efficiently. It is a long standing open problem in this area to show that VP is a strict subset of VNP. At this juncture, it is fair to believe that newer characterization of these complexity classes could help us understand these models better (and possibly help us in resolving this question in restricted settings like non-commutativity at the very least). It is well known that Algebraic Branching Programs (ABPs) characterize the class VBP (or equivalently VPskew ). Recently, Mengel [MFCS, 2013] showed that ABPs can be extended with memory and the computational models thus obtained can be used to characterize VP and VNP. In particular, Mengel showed that ABPs with a single stack characterize VP, and branching programs with random-access memory characterize VNP. In this work we show that algebraic branching programs with just 2 stacks efficiently simulates the polynomial families in VNP, and two stack branching programs are VNP-complete. Further, we observe that k-stack branching programs (for all polynomially bounded k) are no more powerful than 2-stack branching programs (upto a polynomial blowup in size). This strengthens the work of Mengel in the following way – VBP vs. VP vs. VNP are characterized by algebraic branching programs with 0, 1, and 2 stacks, respectively, or no-memory, a stack as memory, and a queue as memory respectively, which hold even in the non-commutative setting. We also refine Mengel’s characterization of VP through stack-height characterization.

@inproceedings{bib_On_H_2023, AUTHOR = {Shpilka, Amir and Grichener, Coral and Chillara, Suryajith }, TITLE = {On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts}, BOOKTITLE = {Symposium on Theoretical Aspects of Computer Science}. YEAR = {2023}}

We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.

@inproceedings{bib_Func_2021, AUTHOR = {Chillara, Suryajith }, TITLE = {Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}, BOOKTITLE = {Foundations of Software Technology and Theoretical Computer Science}. YEAR = {2021}}

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d O(1) - variate and degree d polynomial Pd ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to Pd, then C must have size 2 Ω(√ d log d) . The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC0 circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC0 can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form – sums of powers of polynomials) of 2 logO(1) n size. Thus they argued that a 2 ω(poly log n) “functional” lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the “corresponding Boolean function” of Q against non-uniform ACC0 . In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log2 n) ≤ d ≤ n 0.01, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O d k2
that functionally computes Iterated Matrix Multiplication polynomial IMMn,d (∈ VP) over {0, 1} n 2d must have size n Ω(k) . Since Iterated Matrix Multiplication IMMn,d over {0, 1} n 2d is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC0 from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMMn,d (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMMn,d, for a slightly larger range of individual degree. 2012 ACM Subject Classification Theory of computation → Circuit complexity; Theory of computation → Algebraic complexity theory Keywords and phrases Functional Lower