38 Search Results for "Thierauf, Thomas"


Document
RANDOM
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

Authors: Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf

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


Abstract
Kaltofen [STOC 1986] gave a randomized algorithm to factor multivariate polynomials given by algebraic circuits. We derandomize the algorithm in some special cases. For an n-variate polynomial f of degree d from a class 𝒞 of algebraic circuits, we design a deterministic algorithm to find all its irreducible factors of degree ≤ δ, for constant δ. The running time of this algorithm stems from a deterministic PIT algorithm for class 𝒞 and a deterministic algorithm that tests divisibility of f by a polynomial of degree ≤ δ. By using the PIT algorithm for constant-depth circuits by Limaye, Srinivasan and Tavenas [FOCS 2021] and the divisibility results by Forbes [FOCS 2015], this generalizes and simplifies a recent result by Kumar, Ramanathan and Saptharishi [SODA 2024]. They designed a subexponential-time algorithm that, given a blackbox access to f computed by a constant-depth circuit, outputs its irreducible factors of degree ≤ δ. When the input f is sparse, the time complexity of our algorithm depends on a whitebox PIT algorithm for ∑_i m_i g_i^{d_i}, where m_i are monomials and deg(g_i) ≤ δ. All the previous algorithms required a blackbox PIT algorithm for the same class. Our second main result considers polynomials f, where each irreducible factor has degree at most δ. We show that all the irreducible factors with their multiplicities can be computed in polynomial time with blackbox access to f. Finally, we consider factorization of sparse polynomials. We show that in order to compute all the sparse irreducible factors efficiently, it suffices to derandomize irreducibility preserving bivariate projections for sparse polynomials.

Cite as

Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf. Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 75:1-75:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.APPROX/RANDOM.2024.75,
  author =	{Dutta, Pranjal and Sinhababu, Amit and Thierauf, Thomas},
  title =	{{Derandomizing Multivariate Polynomial Factoring for Low Degree Factors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{75:1--75:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.75},
  URN =		{urn:nbn:de:0030-drops-210687},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.75},
  annote =	{Keywords: algebraic complexity, factoring, low degree, weight isolation, divisibility}
}
Document
A Direct Reduction from the Polynomial to the Adversary Method

Authors: Aleksandrs Belovs

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)


Abstract
The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.

Cite as

Aleksandrs Belovs. A Direct Reduction from the Polynomial to the Adversary Method. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{belovs:LIPIcs.TQC.2024.11,
  author =	{Belovs, Aleksandrs},
  title =	{{A Direct Reduction from the Polynomial to the Adversary Method}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.11},
  URN =		{urn:nbn:de:0030-drops-206814},
  doi =		{10.4230/LIPIcs.TQC.2024.11},
  annote =	{Keywords: Polynomials, Quantum Adversary Bound}
}
Document
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs

Authors: Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)


Abstract
Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem [Andrea S. LaPaugh and Christos H. Papadimitriou, 1984] known as the EP problem. Nedev [Zhivko Prodanov Nedev, 1999] proved in 1999, that for directed planar graphs, the problem can be solved in polynomial time. More than two decades since then, we make the first progress in extending the tractable classes of graphs for this problem. We give a polynomial time algorithm to solve the EP problem for classes of H-minor-free directed graphs, where H is a single-crossing graph. We make two new technical contributions along the way, that might be of independent interest. The first, and perhaps our main, contribution is the construction of small, planar, parity-mimicking networks. These are graphs that mimic parities of all possible paths between a designated set of terminals of the original graph. Finding vertex disjoint paths between given source-destination pairs of vertices is another fundamental problem, known to be NP-complete in directed graphs [Steven Fortune et al., 1980], though known to be tractable in planar directed graphs [Alexander Schrijver, 1994]. We encounter a natural variant of this problem, that of finding disjoint paths between given pairs of vertices, but with constraints on parity of the total length of paths. The other significant contribution of our paper is to give a polynomial time algorithm for the 3-disjoint paths with total parity problem, in directed planar graphs with some restrictions (and also in directed graphs of bounded treewidth).

Cite as

Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma. The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.MFCS.2024.43,
  author =	{Chauhan, Archit and Datta, Samir and Gupta, Chetan and Sharma, Vimal Raj},
  title =	{{The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.43},
  URN =		{urn:nbn:de:0030-drops-205992},
  doi =		{10.4230/LIPIcs.MFCS.2024.43},
  annote =	{Keywords: Graph Algorithms, EvenPath, Polynomial-time Algorithms, Reachability}
}
Document
Lower Bounds for Set-Multilinear Branching Programs

Authors: Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)


Abstract
In this paper, we prove super-polynomial lower bounds for the model of sum of ordered set-multilinear algebraic branching programs, each with a possibly different ordering (∑smABP). Specifically, we give an explicit nd-variate polynomial of degree d such that any ∑smABP computing it must have size n^ω(1) for d as low as ω(log n). Notably, this constitutes the first such lower bound in the low degree regime. Moreover, for d = poly(n), we demonstrate an exponential lower bound. This result generalizes the seminal work of Nisan (STOC, 1991), which proved an exponential lower bound for a single ordered set-multilinear ABP. The significance of our lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (TAMC, 2024), which showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs - for a polynomial of sufficiently low degree - would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant’s longstanding conjecture that the permanent polynomial can not be computed efficiently by ABPs. More precisely, their work shows that if one could obtain such lower bounds when the degree is bounded by O(log n/ log log n), then it would imply super-polynomial lower bounds against general ABPs. Our results strengthen the works of Arvind & Raja (Chic. J. Theor. Comput. Sci., 2016) and Bhargav, Dwivedi & Saxena (TAMC, 2024), as well as the works of Ramya & Rao (Theor. Comput. Sci., 2020) and Ghoshal & Rao (International Computer Science Symposium in Russia, 2021), each of which established lower bounds for related or restricted versions of this model. They also strongly answer a question from the former two, which asked to prove super-polynomial lower bounds for general ∑smABP.

Cite as

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, and Amir Shpilka. Lower Bounds for Set-Multilinear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2024.20,
  author =	{Chatterjee, Prerona and Kush, Deepanshu and Saraf, Shubhangi and Shpilka, Amir},
  title =	{{Lower Bounds for Set-Multilinear Branching Programs}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.20},
  URN =		{urn:nbn:de:0030-drops-204167},
  doi =		{10.4230/LIPIcs.CCC.2024.20},
  annote =	{Keywords: Lower Bounds, Algebraic Branching Programs, Set-multilinear polynomials}
}
Document
Track A: Algorithms, Complexity and Games
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.

Cite as

Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit},
  title =	{{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16},
  URN =		{urn:nbn:de:0030-drops-201598},
  doi =		{10.4230/LIPIcs.ICALP.2024.16},
  annote =	{Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT}
}
Document
Border Complexity of Symbolic Determinant Under Rank One Restriction

Authors: Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj

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


Abstract
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation i.e. whether VBP = VBP^ ̅. The power of approximation is well understood for some restricted models of computation, e.g. the class of depth-two circuits, read-once oblivious ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two ABPs. The former three classes are known to be closed under approximation [Markus Bläser et al., 2020], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomial-sized formulas [Bringmann et al., 2017]. In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where for each 1 ≤ i ≤ n, A_i is of rank one. This class has been studied extensively [Edmonds, 1968; Jack Edmonds, 1979; Murota, 1993] and efficient identity testing algorithms are known for it [Lovász, 1989; Rohit Gurjar and Thomas Thierauf, 2020]. We show that this class is closed under approximation. In the language of algebraic geometry, we show that the set obtained by taking coordinatewise products of pairs of points from (the Plücker embedding of) a Grassmannian variety is closed.

Cite as

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. Border Complexity of Symbolic Determinant Under Rank One Restriction. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.2,
  author =	{Chatterjee, Abhranil and Ghosh, Sumanta and Gurjar, Rohit and Raj, Roshan},
  title =	{{Border Complexity of Symbolic Determinant Under Rank One Restriction}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{2:1--2:15},
  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.2},
  URN =		{urn:nbn:de:0030-drops-182721},
  doi =		{10.4230/LIPIcs.CCC.2023.2},
  annote =	{Keywords: Border Complexity, Symbolic Determinant, Valuated Matroid}
}
Document
Arithmetic Circuit Complexity of Division and Truncation

Authors: Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu

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


Abstract
Given polynomials f,g,h ∈ 𝔽[x₁,…,x_n] such that f = g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s,deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). The result is an exponential improvement over Strassen’s classic result (Strassen'73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). Further, we show that any univariate polynomial family (f_d)_d, defined by the initial segment of the power series expansion of rational function g_d(x)/h_d(x) up to degree d (i.e. f_d = g_d/h_d od x^{d+1}), where circuit size of g is s_d and degree of g_d is at most d, can be computed by a circuit of size poly(s_d,deg(h_d),log d). We also show a hardness result when the degrees of the rational functions are high (i.e. Ω (d)), assuming hardness of the integer factorization problem. Finally, we extend this conditional hardness to simple algebraic functions as well, and show that for every prime p, there is an integral algebraic power series with its minimal polynomial satisfying a degree p polynomial equation, such that its initial segment is hard to compute unless integer factoring is easy, or a multiple of n! is easy to compute. Both, integer factoring and computation of multiple of n!, are believed to be notoriously hard. In contrast, we show examples of transcendental power series whose initial segments are easy to compute.

Cite as

Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu. Arithmetic Circuit Complexity of Division and Truncation. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 25:1-25:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.CCC.2021.25,
  author =	{Dutta, Pranjal and Jindal, Gorav and Pandey, Anurag and Sinhababu, Amit},
  title =	{{Arithmetic Circuit Complexity of Division and Truncation}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{25:1--25:36},
  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.25},
  URN =		{urn:nbn:de:0030-drops-142990},
  doi =		{10.4230/LIPIcs.CCC.2021.25},
  annote =	{Keywords: Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization}
}
Document
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization

Authors: Pranjal Dutta, Nitin Saxena, and Thomas Thierauf

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
For a polynomial f, we study the sum of squares representation (SOS), i.e. f = ∑_{i ∈ [s]} c_i f_i² , where c_i are field elements and the f_i’s are polynomials. The size of the representation is the number of monomials that appear across the f_i’s. Its minimum is the support-sum S(f) of f. For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of, a full-support univariate polynomial, f of degree d is S(f) ≥ d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) ≥ d^{0.5+ε(d)}, for a sub-constant function ε(d) > ω(√{log log d/log d}), implies that VP ≠ VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Θ(d). We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.

Cite as

Pranjal Dutta, Nitin Saxena, and Thomas Thierauf. A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.ITCS.2021.23,
  author =	{Dutta, Pranjal and Saxena, Nitin and Thierauf, Thomas},
  title =	{{A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.23},
  URN =		{urn:nbn:de:0030-drops-135629},
  doi =		{10.4230/LIPIcs.ITCS.2021.23},
  annote =	{Keywords: VP, VNP, hitting set, circuit, polynomial, sparsity, SOS, SOC, PIT, lower bound}
}
Document
Factorization of Polynomials Given By Arithmetic Branching Programs

Authors: Amit Sinhababu and Thomas Thierauf

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


Abstract
Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).

Cite as

Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33,
  author =	{Sinhababu, Amit and Thierauf, Thomas},
  title =	{{Factorization of Polynomials Given By Arithmetic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{33:1--33:19},
  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.33},
  URN =		{urn:nbn:de:0030-drops-125854},
  doi =		{10.4230/LIPIcs.CCC.2020.33},
  annote =	{Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness}
}
Document
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Authors: Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We present a geometric approach towards derandomizing the {Isolation Lemma} by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of weights, where each weight is an integer and quasi-polynomially bounded, that can isolate a vertex in any 0/1 polytope for which each face lies in an affine space defined by a totally unimodular matrix. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the Isolation Lemma for {bipartite perfect matching} and {matroid intersection}. We prove our result by associating a {lattice} to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids.

Cite as

Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.ICALP.2018.74,
  author =	{Gurjar, Rohit and Thierauf, Thomas and Vishnoi, Nisheeth K.},
  title =	{{Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.74},
  URN =		{urn:nbn:de:0030-drops-90782},
  doi =		{10.4230/LIPIcs.ICALP.2018.74},
  annote =	{Keywords: Derandomization, Isolation Lemma, Total unimodularity, Near-shortest vectors in Lattices, Regular matroids}
}
Document
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)

Authors: Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans

Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)


Abstract
Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples. The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called chasm at depth 4 suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model (and these are tied to central questions regarding the power of randomness in computation). Another surprising connection is that the algebraic techniques invented to show lower bounds now prove useful to develop efficient algorithms. For example, Williams showed how to use the polynomial method to obtain faster all-pair-shortest-path algorithms. This emphases once again the central role of algebra in computer science. The seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar can play an important role in educating a diverse community about the latest new techniques, spurring further progress.

Cite as

Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). In Dagstuhl Reports, Volume 6, Issue 10, pp. 13-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Article{kabanets_et_al:DagRep.6.10.13,
  author =	{Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher},
  title =	{{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)}},
  pages =	{13--32},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{10},
  editor =	{Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.10.13},
  URN =		{urn:nbn:de:0030-drops-69504},
  doi =		{10.4230/DagRep.6.10.13},
  annote =	{Keywords: Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits}
}
Document
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs

Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

Cite as

Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.CCC.2015.323,
  author =	{Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin and Thierauf, Thomas},
  title =	{{Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{323--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323},
  URN =		{urn:nbn:de:0030-drops-50647},
  doi =		{10.4230/LIPIcs.CCC.2015.323},
  annote =	{Keywords: PIT, Hitting-set, Sum of ROABPs, Evaluation Dimension, Rank Concentration}
}
Document
Algebra in Computational Complexity (Dagstuhl Seminar 14391)

Authors: Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)


Abstract
At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples. The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called "chasm at depth 4" suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model, and these are tied to central questions regarding the power of randomness in computation. Representation theory has emerged as an important tool in three separate lines of work: the "Geometric Complexity Theory" approach to P vs. NP and circuit lower bounds, the effort to resolve the complexity of matrix multiplication, and a framework for constructing locally testable codes. Coding theory has seen several algebraic innovations in recent years, including multiplicity codes, and new lower bounds. This seminar brought together researchers who are using a diverse array of algebraic methods in a variety of settings. It plays an important role in educating a diverse community about the latest new techniques, spurring further progress.

Cite as

Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans. Algebra in Computational Complexity (Dagstuhl Seminar 14391). In Dagstuhl Reports, Volume 4, Issue 9, pp. 85-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.4.9.85,
  author =	{Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher},
  title =	{{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}},
  pages =	{85--105},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{9},
  editor =	{Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.85},
  URN =		{urn:nbn:de:0030-drops-48851},
  doi =		{10.4230/DagRep.4.9.85},
  annote =	{Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits}
}
Document
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)

Authors: Manindra Agrawal, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)


Abstract
At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The PCP characterization of NP and the Agrawal-Kayal-Saxena polynomial-time primality test are two prominent examples. Recently, there have been some works going in the opposite direction, giving alternative combinatorial proofs for results that were originally proved algebraically. These alternative proofs can yield important improvements because they are closer to the underlying problems and avoid the losses in passing to the algebraic setting. A prominent example is Dinur's proof of the PCP Theorem via gap amplification which yielded short PCPs with only a polylogarithmic length blowup (which had been the focus of significant research effort up to that point). We see here (and in a number of recent works) an exciting interplay between algebraic and combinatorial techniques. This seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and combinatorial methods in a variety of settings.

Cite as

Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). In Dagstuhl Reports, Volume 2, Issue 10, pp. 60-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.2.10.60,
  author =	{Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher},
  title =	{{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}},
  pages =	{60--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{10},
  editor =	{Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.10.60},
  URN =		{urn:nbn:de:0030-drops-39034},
  doi =		{10.4230/DagRep.2.10.60},
  annote =	{Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits}
}
Document
09421 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)


Abstract
From 11.10. to 16.10.2009, the Dagstuhl Seminar 09421 ``Algebraic Methods in Computational Complexity '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.1,
  author =	{Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher},
  title =	{{09421 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.1},
  URN =		{urn:nbn:de:0030-drops-24181},
  doi =		{10.4230/DagSemProc.09421.1},
  annote =	{Keywords: Computational Complexity, Algebra}
}
  • Refine by Author
  • 17 Thierauf, Thomas
  • 7 Buhrman, Harry
  • 7 Fortnow, Lance
  • 6 Agrawal, Manindra
  • 5 Umans, Christopher
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Algebraic complexity theory
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 5 Computational Complexity
  • 5 lower bounds
  • 4 derandomization
  • 3 Computational complexity
  • 3 circuits
  • Show More...

  • Refine by Type
  • 38 document

  • Refine by Publication Year
  • 8 2008
  • 8 2010
  • 6 2005
  • 5 2024
  • 2 2015
  • 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