9 citations · 11 across the 10 of their papers we have counts for
13 papers
On Han- and Shearer-Type Information Inequalities: Equality Conditions and Combinatorial Applications
Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara +1
Madiman and Tetali established strong and weak fractional inequalities that subsume classical entropy subset inequalities such as Han's inequality and Shearer's lemma. In this work…
Shortest Paths with Linear Edge Weights
Suryajith Chillara, Kshitij Gajjar, Nithish Raja
We study shortest paths in directed graphs whose edge weights are of the form Here…
Conditioning Strengthens Classical Entropy and Matrix Inequalities: A Submodular Approach
Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara +1
Dembo, Cover, and Thomas (1991) developed an elegant information-theoretic framework for proving determinantal inequalities for positive definite matrices, which relies on the stru…
Generalized Information Inequalities via Submodularity, and Two Combinatorial Problems
Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara +1
It is well known that there is a strong connection between entropy inequalities and submodularity, since the entropy of a collection of random variables is a submodular function. U…
Fractional Subadditivity of Submodular Functions: Equality Conditions and Their Applications
Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara +1
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 frac…
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
Suryajith Chillara, Coral Grichener, Amir Shpilka
We say that two given polynomials , over a ring , are equivalent under shifts if there exists a vector such that . Grigoriev and Karpin…
Functional lower bounds for restricted arithmetic circuits of depth four
Suryajith Chillara
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit -variate and degree polynomial such that if any depth four cir…
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree
Suryajith Chillara
Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers and such that , any syntactic depth four circuit of bounded…
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye +1
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth to one of product-depth in the multilinear setting. We show that for every po…
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
In this paper, we study the algebraic formula complexity of multiplying many matrices, denoted , and show that the well-known divide-and-conquer a…
The Chasm at Depth Four, and Tensor Rank : Old results, new insights
Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi +1
Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size i…
On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields
Suryajith Chillara, Partha Mukhopadhyay
Recently, Gupta et.al. [GKKS2013] proved that over Q any -variate and -degree polynomial in VP can also be computed by a depth three circuit of size $2^{O(\sqrt{…
Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
Suryajith Chillara, Partha Mukhopadhyay
Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to…