37 Search Results for "Kumar, Mrinal"

Document
DOI: 10.4230/LIPIcs.ESA.2025.89
A Simple Algorithm for Trimmed Multipoint Evaluation

Authors: Nick Fischer, Melvin Kallmayer, and Leo Wennmann

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an n-variate polynomial with bounded individual degree d and total degree D, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA '21], [Dell, Haak, Kallmayer, Wennmann; SODA '25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC '13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background.
Cite as

Nick Fischer, Melvin Kallmayer, and Leo Wennmann. A Simple Algorithm for Trimmed Multipoint Evaluation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 89:1-89:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.89,
  author =	{Fischer, Nick and Kallmayer, Melvin and Wennmann, Leo},
  title =	{{A Simple Algorithm for Trimmed Multipoint Evaluation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{89:1--89:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.89},
  URN =		{urn:nbn:de:0030-drops-245574},
  doi =		{10.4230/LIPIcs.ESA.2025.89},
  annote =	{Keywords: Algebraic Algorithms, Multipoint Evaluation, Interpolation, LU Decomposition}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.34
Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications

Authors: Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) is invariant under simultaneous permutations of the coordinates of u and v.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost 𝒪(1)-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid 𝒮ⁿ to an Abelian group, correcting from a near-optimal (1/|𝒮|^d - ε) fraction of errors for every ε > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.
Cite as

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan. Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2025.34,
  author =	{Amireddy, Prashanth and Behera, Amik Raj and Srinivasan, Srikanth and Sudan, Madhu},
  title =	{{Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  URN =		{urn:nbn:de:0030-drops-244004},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.34},
  annote =	{Keywords: Markov Chains, Random Walk, Multislices, Representation Theory of Symmetric Group, Local Correction, Low-degree Polynomials, Polynomial Distance Lemma}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.19
Monotone Bounded-Depth Complexity of Homomorphism Polynomials

Authors: C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.
Cite as

C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi. Monotone Bounded-Depth Complexity of Homomorphism Polynomials. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargav_et_al:LIPIcs.MFCS.2025.19,
  author =	{Bhargav, C.S. and Chen, Shiteng and Curticapean, Radu and Dwivedi, Prateek},
  title =	{{Monotone Bounded-Depth Complexity of Homomorphism Polynomials}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.19},
  URN =		{urn:nbn:de:0030-drops-241269},
  doi =		{10.4230/LIPIcs.MFCS.2025.19},
  annote =	{Keywords: algebraic complexity, homomorphisms, monotone circuit complexity, bounded-depth circuits, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.4
Hardness of Clique Approximation for Monotone Circuits

Authors: Jarosław Błasiok and Linus Meierhöfer

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We consider a problem of approximating the size of the largest clique in a graph, using a monotone circuit. Concretely, we focus on distinguishing a random Erdős–Rényi graph 𝒢_{n,p}, with p = n^{-2/(α-1)} chosen st. with high probability it does not even contain an α-clique, from a random clique on β vertices (where α ≤ β). Using the approximation method of Razborov, Alon and Boppana showed in their influential work in 1987 that as long as √{α} β < n^{1-δ}/log n, this problem requires a monotone circuit of size n^Ω(δ√α), implying a lower bound of 2^Ω̃(n^{1/3}) for the exact version of the problem Clique_k when k≈ n^{2/3}. Recently, Cavalar, Kumar, and Rossman improved their result by showing a tight lower bound n^Ω(k), in a limited range k ≤ n^{1/3}, implying a comparable 2^Ω̃(n^{1/3}) lower bound after choosing the largest admissible k. We combine the ideas of Cavalar, Kumar and Rossman with recent breakthrough results on sunflower conjecture by Alweiss, Lovett, Wu, and Zhang to show that as long as α β < n^{1-δ}/log n, any monotone circuit rejecting 𝒢_{n,p} graph while accepting a β-clique needs to have size at least n^Ω(δ²α); this implies a stronger 2^Ω̃(√n) lower bound for the unrestricted version of the problem. We complement this result with a construction of an explicit monotone circuit of size O(n^{δ² α/2}) which rejects 𝒢_{n,p}, and accepts any graph containing β-clique whenever β > n^{1-δ}. In particular, those two theorems give a precise characterization of the smallest β-clique that can be distinguished from 𝒢_{n, 1/2}: when β > n / 2^{C √{log n}}, there is a polynomial-size circuit that solves it, while for β < n / 2^ω(√{log n}) every circuit needs size n^ω(1).
Cite as

Jarosław Błasiok and Linus Meierhöfer. Hardness of Clique Approximation for Monotone Circuits. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blasiok_et_al:LIPIcs.CCC.2025.4,
  author =	{B{\l}asiok, Jaros{\l}aw and Meierh\"{o}fer, Linus},
  title =	{{Hardness of Clique Approximation for Monotone Circuits}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.4},
  URN =		{urn:nbn:de:0030-drops-236987},
  doi =		{10.4230/LIPIcs.CCC.2025.4},
  annote =	{Keywords: circuit lower bounds, monotone circuits, sunflower conjecture}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.15
Algebraic Pseudorandomness in VNC⁰

Authors: Robert Andrews

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.
Cite as

Robert Andrews. Algebraic Pseudorandomness in VNC⁰. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andrews:LIPIcs.CCC.2025.15,
  author =	{Andrews, Robert},
  title =	{{Algebraic Pseudorandomness in VNC⁰}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.15},
  URN =		{urn:nbn:de:0030-drops-237092},
  doi =		{10.4230/LIPIcs.CCC.2025.15},
  annote =	{Keywords: Polynomial identity testing, Algebraic circuits, Ideal Proof System}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.36
Lifting with Colourful Sunflowers

Authors: Susanna F. de Rezende and Marc Vinyals

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P.
Cite as

Susanna F. de Rezende and Marc Vinyals. Lifting with Colourful Sunflowers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2025.36,
  author =	{de Rezende, Susanna F. and Vinyals, Marc},
  title =	{{Lifting with Colourful Sunflowers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.36},
  URN =		{urn:nbn:de:0030-drops-237303},
  doi =		{10.4230/LIPIcs.CCC.2025.36},
  annote =	{Keywords: lifting, sunflower, clique, colouring, monotone circuit, cutting planes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.22
New Bounds for the Ideal Proof System in Positive Characteristic

Authors: Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM 2018). Our results extend the works of Forbes, Shpilka, Tzameret, and Wigderson (Theory of Computing 2021) and also of Govindasamy, Hakoniemi, and Tzameret (FOCS 2022). These works primarily focused on proof systems over fields of characteristic 0, and we are able to extend these results to positive characteristic. The question of proving general IPS lower bounds over positive characteristic is motivated by the important question of proving AC⁰[p]-Frege lower bounds. This connection was observed by Grochow and Pitassi (J. ACM 2018). Additional motivation comes from recent developments in algebraic complexity theory due to Forbes (CCC 2024) who showed how to extend previous lower bounds over characteristic 0 to positive characteristic. In our work, we adapt the functional lower bound method of Forbes et al. (Theory of Computing 2021) to prove exponential-size lower bounds for various subsystems of IPS. In order to establish these size lower bounds, we first prove a tight degree lower bound for a variant of Subset Sum over positive characteristic. This forms the core of all our lower bounds. Additionally, we derive upper bounds for the instances presented above. We show that they have efficient constant-depth IPS refutations. This demonstrates that constant-depth IPS refutations are stronger than the proof systems considered above even in positive characteristic. We also show that constant-depth IPS can efficiently refute a general class of instances, namely all symmetric instances, thereby further uncovering the strength of these algebraic proofs in positive characteristic.
Cite as

Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan. New Bounds for the Ideal Proof System in Positive Characteristic. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{behera_et_al:LIPIcs.ICALP.2025.22,
  author =	{Behera, Amik Raj and Limaye, Nutan and Ramanathan, Varun and Srinivasan, Srikanth},
  title =	{{New Bounds for the Ideal Proof System in Positive Characteristic}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.22},
  URN =		{urn:nbn:de:0030-drops-233992},
  doi =		{10.4230/LIPIcs.ICALP.2025.22},
  annote =	{Keywords: Ideal Proof Systems, Algebraic Complexity, Positive Characteristic}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.52
Uniform Bounds on Product Sylvester-Gallai Configurations

Authors: Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let 𝕂 be an algebraically closed field of characteristic zero, and let ℱ = {F_1, …, F_m} ⊂ 𝕂[x_1, …, x_N] denote a collection of irreducible homogeneous polynomials of degree at most d, where each F_i is not a scalar multiple of any other F_j for i ≠ j. We define ℱ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials F_i, F_j ∈ ℱ, the following condition is satisfied: ∏_{k≠i, j} F_k ∈ rad (F_i, F_j) . We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function λ : ℕ → ℕ, independent of 𝕂, N, and m, such that any product Sylvester-Gallai configuration must satisfy: dim(span_𝕂(ℱ)) ≤ λ(d). This result generalizes the main theorems from (Shpilka 2019, Peleg and Shpilka 2020, Oliveira and Sengupta 2023), and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.
Cite as

Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Uniform Bounds on Product Sylvester-Gallai Configurations. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.SoCG.2025.52,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Sengupta, Akash Kumar},
  title =	{{Uniform Bounds on Product Sylvester-Gallai Configurations}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.52},
  URN =		{urn:nbn:de:0030-drops-232043},
  doi =		{10.4230/LIPIcs.SoCG.2025.52},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2025.4
Some Recent Advancements in Monotone Circuit Complexity (Invited Talk)

Authors: Susanna F. de Rezende

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In 1985, Razborov [Razborov, 1985] proved the first superpolynomial size lower bound for monotone Boolean circuits for the perfect matching the clique functions, and, independently, Andreev [Andreev, 1985] obtained exponential size lower bounds. These breakthroughs were soon followed by further advancements in monotone complexity, including better lower bounds for clique [Alon and Boppana, 1987; Ingo Wegener, 1987], superlogarithmic depth lower bounds for connectivity by Karchmer and Wigderson [Karchmer and Wigderson, 1990], and the separations mon-NC ≠ mon-P and that mon-NC^i ≠ mon-NC^{i+1} by Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999]. Karchmer and Wigderson [Karchmer and Wigderson, 1990] proved their result by establishing a relation between communication complexity and (monotone) circuit depth, and Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999] introduced a new technique, now called lifting theorems, for obtaining communication lower bounds from query complexity lower bounds, In this talk, we will survey recent advancements in monotone complexity driven by query-to-communication lifting theorems. A decade ago, Göös, Pitassi, and Watson [Mika Göös et al., 2018] brought to light the generality of the result of Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999] and reignited this line of work. A notable extension is the lifting theorem [Ankit Garg et al., 2020] for a model of DAG-like communication [Alexander A. Razborov, 1995; Dmitry Sokolov, 2017] that corresponds to circuit size. These powerful theorems, in their different flavours, have been instrumental in addressing many open questions in monotone circuit complexity, including: optimal 2^Ω(n) lower bounds on the size of monotone Boolean formulas computing an explicit function in NP [Toniann Pitassi and Robert Robere, 2017]; a complete picture of the relation between the mon-AC and mon-NC hierarchies [Susanna F. de Rezende et al., 2016]; a near optimal separation between monotone circuit and monotone formula size [Susanna F. de Rezende et al., 2020]; exponential separation between NC^2 and mon-P [Ankit Garg et al., 2020; Mika Göös et al., 2019]; and better lower bounds for clique [de Rezende and Vinyals, 2025; Lovett et al., 2022], improving on [Cavalar et al., 2021]. Very recently, lifting theorems were also used to prove supercritical trade-offs for monotone circuits showing that there are functions computable by small circuits for which any small circuit must have superlinear or even superpolynomial depth [de Rezende et al., 2024; Göös et al., 2024]. We will explore these results and their implications, and conclude by discussing some open problems.
Cite as

Susanna F. de Rezende. Some Recent Advancements in Monotone Circuit Complexity (Invited Talk). In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende:LIPIcs.STACS.2025.4,
  author =	{de Rezende, Susanna F.},
  title =	{{Some Recent Advancements in Monotone Circuit Complexity}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.4},
  URN =		{urn:nbn:de:0030-drops-228291},
  doi =		{10.4230/LIPIcs.STACS.2025.4},
  annote =	{Keywords: monotone circuit complexity, query complexity, lifting theorems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.68
New Pseudorandom Generators and Correlation Bounds Using Extractors

Authors: Vinayak M. Kumar

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalization of structured low-degree 𝔽₂-polynomials that we did not have correlation bounds for before. In particular: - We construct a PRG for width-2 poly(n)-length branching programs which read d bits at a time with seed length 2^O(√{log n}) ⋅ d²log²(1/ε). This comes quadratically close to optimal dependence in d and log(1/ε). Improving the dependence on n would imply nontrivial PRGs for log n-degree 𝔽₂-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on d with seed length of O(dlog n + d2^dlog(1/ε)). - We provide the first nontrivial (and nearly optimal) correlation bounds and PRGs against size-n^Ω(log n) AC⁰ circuits with either n^{.99} SYM gates (computing an arbitrary symmetric function) or n^{.49} THR gates (computing an arbitrary linear threshold function). This is a generalization of sparse 𝔽₂-polynomials, which can be simulated by an AC⁰ circuit with one parity gate at the top. Previous work of Servedio and Tan only handled n^{.49} SYM gates or n^{.24} THR gates, and previous work of Lovett and Srinivasan only handled polynomial-size circuits. - We give exponentially small correlation bounds against degree-n^O(1) 𝔽₂-polynomials which are set-multilinear over some arbitrary partition of the input into n^{1-O(1)} parts (noting that at n parts, we recover all low degree polynomials). This vastly generalizes correlation bounds against degree-d polynomials which are set-multilinear over a fixed partition into d blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty, and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds for more general models of computation. Although this technique has been used in previous work, they rely on the model simplifying drastically under random restrictions. We view our results as a proof of concept that such fortification can be done even for classes that do not enjoy such behavior.
Cite as

Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.ITCS.2025.68,
  author =	{Kumar, Vinayak M.},
  title =	{{New Pseudorandom Generators and Correlation Bounds Using Extractors}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{68:1--68:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.68},
  URN =		{urn:nbn:de:0030-drops-226961},
  doi =		{10.4230/LIPIcs.ITCS.2025.68},
  annote =	{Keywords: Pseudorandom Generators, Correlation Bounds, Constant-Depth Circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.93
Polynomials, Divided Differences, and Codes

Authors: S. Venkitesh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Multiplicity codes (Kopparty et al., J. ACM 2014) are multivariate polynomial codes where the codewords are described by evaluations of polynomials (with a degree bound) and their derivatives up to some order (the multiplicity parameter), on a suitably chosen affine set of points. While efficient decoding algorithms were known in some special cases of point sets, by a reduction to univariate multiplicity codes, a general algorithm for list decoding up to the distance of the code when the point set is an arbitrary finite grid, was obtained only recently (Bhandari et al., IEEE TIT 2023). This required the characteristic of the field to be zero or larger than the degree bound, which is somewhat necessary since list decoding up to distance with small output list size is not possible when the characteristic is significantly smaller than the degree. In this work, we present an alternative construction based on divided differences of polynomials, that conceptually resembles the classical multiplicity codes but has good list decodability "insensitive to the field characteristic". We obtain a simple algorithm that list decodes this code up to distance for arbitrary finite grids over all finite fields. Our construction can also be interpreted as a folded Reed-Muller code, which may be of independent interest.
Cite as

S. Venkitesh. Polynomials, Divided Differences, and Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 93:1-93:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{venkitesh:LIPIcs.ITCS.2025.93,
  author =	{Venkitesh, S.},
  title =	{{Polynomials, Divided Differences, and Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{93:1--93:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-227216},
  doi =		{10.4230/LIPIcs.ITCS.2025.93},
  annote =	{Keywords: Error-correcting code, polynomial code, Reed-Solomon code, Reed-Muller code, folded Reed-Solomon code, folded Reed-Muller code, multiplicity code, divided difference, q-derivative, polynomial method, list decoding, list decoding capacity, linear algebraic list decoding}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.33
Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

Authors: Shanthanu S. Rai

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree d over finite field 𝔽_q. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time Õ(d⁴log⁴q). Our construction extends Shoup’s deterministic algorithm (FOCS 1988) for the same problem, which runs in time Õ(d⁴p^{1/2}log⁴q) (where p is the characteristic of the field 𝔽_q). Shoup had shown a reduction from constructing irreducible polynomials to factoring polynomials over finite fields. We show that by using a fast randomized factoring algorithm, the above reduction yields an efficient pseudo-deterministic algorithm for constructing irreducible polynomials over finite fields.
Cite as

Shanthanu S. Rai. Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rai:LIPIcs.FSTTCS.2024.33,
  author =	{Rai, Shanthanu S.},
  title =	{{Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.33},
  URN =		{urn:nbn:de:0030-drops-222227},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.33},
  annote =	{Keywords: Algebra and Computation, Finite fields, Factorization, Pseudo-deterministic, Polynomials}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.27
Determinants vs. Algebraic Branching Programs

Authors: Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We show that for every homogeneous polynomial of degree d, if it has determinantal complexity at most s, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most O(d⁵s). Moreover, we show that for most homogeneous polynomials, the width of the resulting homogeneous ABP is just s-1 and the size is at most O(ds). Thus, for constant degree homogeneous polynomials, their determinantal complexity and ABP complexity are within a constant factor of each other and hence, a super-linear lower bound for ABPs for any constant degree polynomial implies a super-linear lower bound on determinantal complexity; this relates two open problems of great interest in algebraic complexity. As of now, super-linear lower bounds for ABPs are known only for polynomials of growing degree [Mrinal Kumar, 2019; Prerona Chatterjee et al., 2022], and for determinantal complexity the best lower bounds are larger than the number of variables only by a constant factor [Mrinal Kumar and Ben Lee Volk, 2022]. While determinantal complexity and ABP complexity are classically known to be polynomially equivalent [Meena Mahajan and V. Vinay, 1997], the standard transformation from the former to the latter incurs a polynomial blow up in size in the process, and thus, it was unclear if a super-linear lower bound for ABPs implies a super-linear lower bound on determinantal complexity. In particular, a size preserving transformation from determinantal complexity to ABPs does not appear to have been known prior to this work, even for constant degree polynomials.
Cite as

Abhranil Chatterjee, Mrinal Kumar, and Ben Lee Volk. Determinants vs. Algebraic Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ITCS.2024.27,
  author =	{Chatterjee, Abhranil and Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Determinants vs. Algebraic Branching Programs}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.27},
  URN =		{urn:nbn:de:0030-drops-195550},
  doi =		{10.4230/LIPIcs.ITCS.2024.27},
  annote =	{Keywords: Determinant, Algebraic Branching Program, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.19
Criticality of AC⁰-Formulae

Authors: Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function f : {0,1}ⁿ → {0,1} is the minimum λ ≥ 1 such that for all positive integers t and all p ∈ [0,1], Pr_{ρ∼ℛ_p}[DT_{depth}(f|_ρ) ≥ t] ≤ (pλ)^t, where ℛ_p refers to the distribution of p-random restrictions. Håstad’s celebrated switching lemma shows that the criticality of any k-DNF is at most O(k). Subsequent improvements to correlation bounds of AC⁰-circuits against parity showed that the criticality of any AC⁰-circuit of size S and depth d+1 is at most O(log S)^d and any regular AC⁰-formula of size S and depth d+1 is at most O((1/d)⋅log S)^d. We strengthen these results by showing that the criticality of any AC⁰-formula (not necessarily regular) of size S and depth d+1 is at most O((log S)/d)^d, resolving a conjecture due to Rossman. This result also implies Rossman’s optimal lower bound on the size of any depth-d AC⁰-formula computing parity [Comput. Complexity, 27(2):209-223, 2018.]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC⁰-formulae.
Cite as

Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of AC⁰-Formulae. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{harsha_et_al:LIPIcs.CCC.2023.19,
  author =	{Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh},
  title =	{{Criticality of AC⁰-Formulae}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.19},
  URN =		{urn:nbn:de:0030-drops-182898},
  doi =		{10.4230/LIPIcs.CCC.2023.19},
  annote =	{Keywords: AC⁰ circuits, AC⁰ formulae, criticality, switching lemma, correlation bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.38
Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Authors: Deepanshu Kush and Shubhangi Saraf

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
In this paper, 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² variables, and of degree n, such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). 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)^Ω(Δ n^{1/Δ}) was shown for the size of product-depth Δ 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 Δ ≥ 2. The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general set-multilinear circuit lower bounds via depth reduction results. In the setting of general set-multilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(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^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(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.
Cite as

Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kush_et_al:LIPIcs.CCC.2022.38,
  author =	{Kush, Deepanshu and Saraf, Shubhangi},
  title =	{{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.38},
  URN =		{urn:nbn:de:0030-drops-166003},
  doi =		{10.4230/LIPIcs.CCC.2022.38},
  annote =	{Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas}
}
  • Refine by Type
  • 37 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 11 2025
  • 2 2024
  • 1 2023
  • 3 2022
  • 5 2021
  • Show More...

  • Refine by Author
  • 18 Kumar, Mrinal
  • 6 Volk, Ben Lee
  • 5 Saptharishi, Ramprasad
  • 3 Harsha, Prahladh
  • 3 Saraf, Shubhangi
  • Show More...

  • Refine by Series/Journal
  • 37 LIPIcs

  • Refine by Classification
  • 20 Theory of computation → Algebraic complexity theory
  • 12 Theory of computation → Circuit complexity
  • 3 Theory of computation → Proof complexity
  • 2 Mathematics of computing → Coding theory
  • 2 Theory of computation → Communication complexity
  • Show More...

  • Refine by Keyword
  • 7 arithmetic circuits
  • 7 lower bounds
  • 4 Algebraic Complexity
  • 3 Lower Bounds
  • 3 depth reduction
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact