19 Search Results for "Saptharishi, Ramprasad"

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.31
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Authors: Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan

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

Abstract
We study the following natural question on random sets of points in 𝔽₂^m: Given a random set of k points Z = {z₁, z₂, … , z_k} ⊆ 𝔽₂^m, what is the dimension of the space of degree at most r multilinear polynomials that vanish on all points in Z? We show that, for r ≤ γ m (where γ > 0 is a small, absolute constant) and k = (1-ε)⋅binom(m, ≤ r) for any constant ε > 0, the space of degree at most r multilinear polynomials vanishing on a random set Z = {z_1,…, z_k} has dimension exactly binom(m, ≤ r) - k with probability 1 - o(1). This bound shows that random sets have a much smaller space of degree at most r multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of binom(m, ≤ r) - binom(log₂ k, ≤ r) ≫ binom(m, ≤ r) - k. Using this bound, we show that high-degree Reed-Muller codes (RM(m,d) with d > (1-γ) m) "achieve capacity" under the Binary Erasure Channel in the sense that, for any ε > 0, we can recover from (1-ε)⋅binom(m, ≤ m-d-1) random erasures with probability 1 - o(1). This also implies that RM(m,d) is also efficiently decodable from ≈ binom(m, ≤ m-(d/2)) random errors for the same range of parameters.
Cite as

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan. Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 31:1-31:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhandari_et_al:LIPIcs.CCC.2022.31,
  author =	{Bhandari, Siddharth and Harsha, Prahladh and Saptharishi, Ramprasad and Srinivasan, Srikanth},
  title =	{{Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{31:1--31:14},
  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.31},
  URN =		{urn:nbn:de:0030-drops-165934},
  doi =		{10.4230/LIPIcs.CCC.2022.31},
  annote =	{Keywords: Reed-Muller codes, polynomials, weight-distribution, vanishing ideals, erasures, capacity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.44
If VNP Is Hard, Then so Are Equations for It

Authors: Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee, Kumar, Ramya, Saptharishi and Tengse (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.
Cite as

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, and Anamay Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 44:1-44:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.STACS.2022.44,
  author =	{Kumar, Mrinal and Ramya, C. and Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{If VNP Is Hard, Then so Are Equations for It}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.44},
  URN =		{urn:nbn:de:0030-drops-158547},
  doi =		{10.4230/LIPIcs.STACS.2022.44},
  annote =	{Keywords: Computational Complexity, Algebraic Circuits, Algebraic Natural Proofs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.53
On Finer Separations Between Subclasses of Read-Once Oblivious ABPs

Authors: C. Ramya and Anamay Tengse

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials). Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank. Our proof of the above result builds on the results of Marinari, Möller and Mora (1993), and Möller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs.
Cite as

C. Ramya and Anamay Tengse. On Finer Separations Between Subclasses of Read-Once Oblivious ABPs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 53:1-53:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.STACS.2022.53,
  author =	{Ramya, C. and Tengse, Anamay},
  title =	{{On Finer Separations Between Subclasses of Read-Once Oblivious ABPs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{53:1--53:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.53},
  URN =		{urn:nbn:de:0030-drops-158636},
  doi =		{10.4230/LIPIcs.STACS.2022.53},
  annote =	{Keywords: Algebraic Complexity Theory, Algebraic Branching Programs, Commutative Matrices}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.10
Tight Chang’s-Lemma-Type Bounds for Boolean Functions

Authors: Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Chang’s lemma (Duke Mathematical Journal, 2002) is a classical result in mathematics, with applications spanning across additive combinatorics, combinatorial number theory, analysis of Boolean functions, communication complexity and algorithm design. For a Boolean function f that takes values in {-1, 1} let r(f) denote its Fourier rank (i.e., the dimension of the span of its Fourier support). For each positive threshold t, Chang’s lemma provides a lower bound on δ(f) := Pr[f(x) = -1] in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least 1/t. In this work we examine the tightness of Chang’s lemma with respect to the following three natural settings of the threshold: - the Fourier sparsity of f, denoted k(f), - the Fourier max-supp-entropy of f, denoted k'(f), defined to be the maximum value of the reciprocal of the absolute value of a non-zero Fourier coefficient, - the Fourier max-rank-entropy of f, denoted k''(f), defined to be the minimum t such that characters whose coefficients are at least 1/t in magnitude span a r(f)-dimensional space. In this work we prove new lower bounds on δ(f) in terms of the above measures. One of our lower bounds, δ(f) = Ω(r(f)²/(k(f) log² k(f))), subsumes and refines the previously best known upper bound r(f) = O(√{k(f)}log k(f)) on r(f) in terms of k(f) by Sanyal (Theory of Computing, 2019). We improve upon this bound and show r(f) = O(√{k(f)δ(f)}log k(f)). Another lower bound, δ(f) = Ω(r(f)/(k''(f) log k(f))), is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of absolute values of level-1 Fourier coefficients in terms of 𝔽₂-degree. We further show that Chang’s lemma for the above-mentioned choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions witnessing their tightness. All the functions we construct are modifications of the Addressing function, where we replace certain input variables by suitable functions. Our final contribution is to construct Boolean functions f for which our lower bounds asymptotically match δ(f), and for any choice of the threshold t, the lower bound obtained from Chang’s lemma is asymptotically smaller than δ(f). Our results imply more refined deterministic one-way communication complexity upper bounds for XOR functions. Given the wide-ranging application of Chang’s lemma to areas like additive combinatorics, learning theory and communication complexity, we strongly feel that our refinements of Chang’s lemma will find many more applications.
Cite as

Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight Chang’s-Lemma-Type Bounds for Boolean Functions. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.10,
  author =	{Chakraborty, Sourav and Mande, Nikhil S. and Mittal, Rajat and Molli, Tulasimohan and Paraashar, Manaswi and Sanyal, Swagato},
  title =	{{Tight Chang’s-Lemma-Type Bounds for Boolean Functions}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.10},
  URN =		{urn:nbn:de:0030-drops-155215},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.10},
  annote =	{Keywords: Analysis of Boolean functions, Chang’s lemma, Parity decision trees, Fourier dimension}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.14
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four

Authors: Suryajith Chillara

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} ∈ 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 P_d, then C must have size 2^Ω(√dlog{d}). The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC⁰ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC⁰ can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form - sums of powers of polynomials) of 2^(log^O(1) n) size. Thus they argued that a 2^{ω(polylog 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 ACC⁰. In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log²n) ≤ d ≤ n^{0.01}, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O(d/k²) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (∈ VP) over {0,1}^{n²d} must have size n^Ω(k). Since Iterated Matrix Multiplication IMM_{n,d} over {0,1}^{n²d} 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 ACC⁰ from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMM_{n,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 IMM_{n,d}, for a slightly larger range of individual degree.
Cite as

Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chillara:LIPIcs.FSTTCS.2021.14,
  author =	{Chillara, Suryajith},
  title =	{{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14},
  URN =		{urn:nbn:de:0030-drops-155251},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.14},
  annote =	{Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.4
A Lower Bound on Determinantal Complexity

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The determinantal complexity of a polynomial P ∈ 𝔽[x₁, …, x_n] over a field 𝔽 is the dimension of the smallest matrix M whose entries are affine functions in 𝔽[x₁, …, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑_{i = 1}^n x_i^n is at least 1.5n - 3. For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max{n,d}. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max{n,d}, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [Jarod Alper et al., 2017] for the same polynomial.
Cite as

Mrinal Kumar and Ben Lee Volk. A Lower Bound on Determinantal Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 4:1-4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2021.4,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{A Lower Bound on Determinantal Complexity}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.4},
  URN =		{urn:nbn:de:0030-drops-142781},
  doi =		{10.4230/LIPIcs.CCC.2021.4},
  annote =	{Keywords: Determinantal Complexity, Algebraic Circuits, Lower Bounds, Singular Variety}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.7
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

Authors: Prerona Chatterjee

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
The motivating question for this work is a long standing open problem, posed by Nisan [Noam Nisan, 1991], regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question remains open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011]) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards resolving the VF_{nc} vs VBP_{nc} question, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n²-variate degree d abecedarian polynomial f_{n,d}(𝐱) such that - f_{n, d}(𝐱) can be computed by an abecedarian ABP of size O(nd); - any abecedarian formula computing f_{n, log n}(𝐱) must have size at least n^{Ω(log log n)}. We also show that a super-polynomial lower bound against abecedarian formulas for f_{log n, n}(𝐱) would separate the powers of formulas and ABPs in the non-commutative setting.
Cite as

Prerona Chatterjee. Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 7:1-7:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chatterjee:LIPIcs.CCC.2021.7,
  author =	{Chatterjee, Prerona},
  title =	{{Separating ABPs and Some Structured Formulas in the Non-Commutative Setting}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.7},
  URN =		{urn:nbn:de:0030-drops-142812},
  doi =		{10.4230/LIPIcs.CCC.2021.7},
  annote =	{Keywords: Non-Commutative Formulas, Lower Bound, Separating ABPs and Formulas}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.2
A Quadratic Lower Bound for Algebraic Branching Programs

Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We show that any Algebraic Branching Program (ABP) computing the polynomial ∑_{i=1}^n xⁿ_i has at least Ω(n²) vertices. This improves upon the lower bound of Ω(nlog n), which follows from the classical result of Baur and Strassen [Volker Strassen, 1973; Walter Baur and Volker Strassen, 1983], and extends the results of Kumar [Mrinal Kumar, 2019], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial ∑_{i=1}^n xⁿ_i can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑_{i=1}^n xⁿ_i + ε(𝐱), for a structured "error polynomial" ε(𝐱). To complete the proof, we then observe that the lower bound in [Mrinal Kumar, 2019] is robust enough and continues to hold for all polynomials ∑_{i=1}^n xⁿ_i + ε(𝐱), where ε(𝐱) has the appropriate structure.
Cite as

Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk. A Quadratic Lower Bound for Algebraic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2020.2,
  author =	{Chatterjee, Prerona and Kumar, Mrinal and She, Adrian and Volk, Ben Lee},
  title =	{{A Quadratic Lower Bound for Algebraic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.2},
  URN =		{urn:nbn:de:0030-drops-125546},
  doi =		{10.4230/LIPIcs.CCC.2020.2},
  annote =	{Keywords: Algebraic Branching Programs, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.14
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't

Authors: Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory [Stanley, 1999], in Schubert calculus [Ledoux and Malham, 2010] as well as in Enumerative combinatorics [Gasharov, 1996; Stanley, 1984; Stanley, 1999]. In recent years, they have also shown up in various incarnations in Computer Science, e.g, Quantum computation [Hallgren et al., 2000; Ryan O'Donnell and John Wright, 2015] and Geometric complexity theory [Ikenmeyer and Panova, 2017]. However, unlike some other families of symmetric polynomials like the Elementary Symmetric polynomials, the Power Symmetric polynomials and the Complete Homogeneous Symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question, and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.
Cite as

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14,
  author =	{Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth},
  title =	{{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{14:1--14:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.14},
  URN =		{urn:nbn:de:0030-drops-125660},
  doi =		{10.4230/LIPIcs.CCC.2020.14},
  annote =	{Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.11
Constructing Faithful Homomorphisms over Fields of Finite Characteristic

Authors: Prerona Chatterjee and Ramprasad Saptharishi

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken et al. [Malte Beecken et al., 2013] and exploited by them and Agrawal et al. [Manindra Agrawal et al., 2016] to design algebraic independence based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields were unknown due to the failure of the Jacobian criterion over finite characteristic fields. Building on a recent criterion of Pandey, Saxena and Sinhababu [Anurag Pandey et al., 2018], we construct explicit faithful maps for some natural classes of polynomials in fields of positive characteristic, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken, Mittmann and Saxena [Malte Beecken et al., 2013] and Agrawal, Saha, Saptharishi, Saxena [Manindra Agrawal et al., 2016] in the positive characteristic setting.
Cite as

Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2019.11,
  author =	{Chatterjee, Prerona and Saptharishi, Ramprasad},
  title =	{{Constructing Faithful Homomorphisms over Fields of Finite Characteristic}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.11},
  URN =		{urn:nbn:de:0030-drops-115733},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.11},
  annote =	{Keywords: Faithful Homomorphisms, Identity Testing, Algebraic Independence, Finite characteristic fields}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.78
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

Authors: Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 syntactically multilinear (Sigma Pi Sigma Pi) circuit of size at most exp ({O (sqrt{n log n})}). For degree d = omega(n/log n), this improves upon the upper bound of exp ({O(sqrt{d}log n)}) obtained by Tavenas [Sébastien Tavenas, 2015] for general circuits, and is known to be asymptotically optimal in the exponent when d < n^{epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp ({Omega (sqrt{n log n})}) proved by Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009], and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth Delta of size at most exp inparen{O inparen{Delta * (n/log n)^{1/Delta} * log n}}. It follows from the lower bounds of Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009] that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to o inparen{inparen{n/log n}^{1/Delta}* log n}.
Cite as

Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78,
  author =	{Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad},
  title =	{{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{78:1--78:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.78},
  URN =		{urn:nbn:de:0030-drops-106548},
  doi =		{10.4230/LIPIcs.ICALP.2019.78},
  annote =	{Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.6
Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees

Authors: Ramprasad Saptharishi and Anamay Tengse

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [Guillaume Lagarde et al., 2016] and Lagarde, Limaye and Srinivasan [Guillaume Lagarde et al., 2017]) and give the following constructions: - An explicit hitting set of quasipolynomial size for UPT circuits, - An explicit hitting set of quasipolynomial size for FewPT circuits (circuits with constantly many parse tree shapes), - An explicit hitting set of polynomial size for UPT circuits (of known parse tree shape), when a parameter of preimage-width is bounded by a constant. The above three results are extensions of the results of [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016] to the setting of UPT circuits, and hence also generalize their results in the commutative world from read-once oblivious algebraic branching programs (ROABPs) to UPT-set-multilinear circuits. The main idea is to study shufflings of non-commutative polynomials, which can then be used to prove suitable depth reduction results for UPT circuits and thereby allow a careful translation of the ideas in [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016].
Cite as

Ramprasad Saptharishi and Anamay Tengse. Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 6:1-6:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{saptharishi_et_al:LIPIcs.FSTTCS.2018.6,
  author =	{Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.6},
  URN =		{urn:nbn:de:0030-drops-99050},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.6},
  annote =	{Keywords: Unambiguous Circuits, Read-once Oblivious ABPs, Polynomial Identity Testing, Lower Bounds, Algebraic Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.31
An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields

Authors: Mrinal Kumar and Ramprasad Saptharishi

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In this paper, we show exponential lower bounds for the class of homogeneous depth-5 circuits over all small finite fields. More formally, we show that there is an explicit family {P_d} of polynomials in VNP, where P_d is of degree d in n = d^{O(1)} variables, such that over all finite fields GF(q), any homogeneous depth-5 circuit which computes P_d must have size at least exp(Omega_q(sqrt{d})). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)^n to GF(q) as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [Kumar-Saraf].
Cite as

Mrinal Kumar and Ramprasad Saptharishi. An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 31:1-31:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2017.31,
  author =	{Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{31:1--31:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.31},
  URN =		{urn:nbn:de:0030-drops-75142},
  doi =		{10.4230/LIPIcs.CCC.2017.31},
  annote =	{Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.38
Finer Separations Between Shallow Arithmetic Circuits

Authors: Mrinal Kumar and Ramprasad Saptharishi

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
In this paper, we show that there is a family of polynomials P_n, where P_n is a polynomial in n variables of degree at most d = O(log^2(n)), such that * P_n can be computed by linear sized homogeneous depth-5 arithmetic circuits, * P_n can be computed by poly(n) sized non-homogeneous depth-3 arithmetic circuits. * Any homogeneous depth-4 arithmetic circuit computing P_n must have size at least n^{Omega(sqrt(d))}. This shows that the parameters for the depth reduction results of [Agrawal-Vinay 08, Koiran 12, Tavenas 13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-5 circuits and non-homogeneous depth-3 circuits, and over an appropriate range of parameters, qualitatively improve a result of [Kumar-Saraf 14], which showed that the parameters of depth reductions are optimal for algebraic branching programs. As an added advantage, our proofs are much shorter and simpler than the two known proofs of n^{Omega(sqrt(d))} lower bound for homogeneous depth-4 circuits [Kayal-Limaye-Saha-Srinivasan 14, Kumar-Saraf 14], albeit our proofs only work when d = O(log^2(n)).
Cite as

Mrinal Kumar and Ramprasad Saptharishi. Finer Separations Between Shallow Arithmetic Circuits. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 38:1-38:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2016.38,
  author =	{Kumar, Mrinal and Saptharishi, Ramprasad},
  title =	{{Finer Separations Between Shallow Arithmetic Circuits}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{38:1--38:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.38},
  URN =		{urn:nbn:de:0030-drops-68730},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.38},
  annote =	{Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}
  • Refine by Author
  • 11 Saptharishi, Ramprasad
  • 8 Kumar, Mrinal
  • 3 Chatterjee, Prerona
  • 3 Tengse, Anamay
  • 3 Volk, Ben Lee
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Algebraic complexity theory
  • 4 Theory of computation → Circuit complexity
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 4 arithmetic circuits
  • 4 lower bounds
  • 3 Lower Bounds
  • 3 depth reduction
  • 2 Algebraic Branching Programs
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 4 2021
  • 3 2016
  • 3 2022
  • 2 2019
  • 2 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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