Search Results

Documents authored by Saurabh, Nitin

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.64
On the Communication Complexity of Finding a King in a Tournament

Authors: Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

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

Abstract
A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: - We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS'91, Göös, Pitassi, Watson, SICOMP'18] imply a bound of Θ̃(log² n) for finding a source (if it exists, or outputting that there is no source) in a tournament. - The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ̃(√n). - The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ̃(n) and Θ̃(√n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP'03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.
Cite as

Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Communication Complexity of Finding a King in a Tournament. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 64:1-64:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.APPROX/RANDOM.2024.64,
  author =	{Mande, Nikhil S. and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Communication Complexity of Finding a King in a Tournament}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{64:1--64:23},
  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.64},
  URN =		{urn:nbn:de:0030-drops-210571},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.64},
  annote =	{Keywords: Communication complexity, tournaments, query complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.71
Approximate Degree Composition for Recursive Functions

Authors: Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, and Nitin Saurabh

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

Abstract
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e. functions obtained by composing a base function with itself a number of times. Let h^d denote the standard d-fold composition of the base function h. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: - The outer function f:{0,1}ⁿ → {0,1} is a recursive function of the form h^d, with h being any base function and d = Ω(log log n). - The inner function is a recursive function of the form h^d, with h being any constant arity base function (other than AND and OR) and d = Ω(log log n), where n is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be efficiently eliminated if the inner or outer function is a recursive function.
Cite as

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, and Nitin Saurabh. Approximate Degree Composition for Recursive Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2024.71,
  author =	{Chakraborty, Sourav and Kayal, Chandrima and Mittal, Rajat and Paraashar, Manaswi and Saurabh, Nitin},
  title =	{{Approximate Degree Composition for Recursive Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{71:1--71:17},
  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.71},
  URN =		{urn:nbn:de:0030-drops-210642},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.71},
  annote =	{Keywords: Approximate degree, Boolean function, Composition theorem}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.30
Randomized and Quantum Query Complexities of Finding a King in a Tournament

Authors: Nikhil S. Mande, Manaswi Paraashar, and Nitin Saurabh

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called kings of the underlying tournament. Despite active recent research in the area, the best-known upper and lower bounds on the deterministic query complexity (with query access to directions of edges) of finding a king in a tournament on n vertices are from over 20 years ago, and the bounds do not match: the best-known lower bound is Ω(n^{4/3}) and the best-known upper bound is O(n^{3/2}) [Shen, Sheng, Wu, SICOMP'03]. Our contribution is to show tight bounds (up to logarithmic factors) of Θ̃(n) and Θ̃(√n) in the randomized and quantum query models, respectively. We also study the randomized and quantum query complexities of finding a maximum out-degree vertex in a tournament.
Cite as

Nikhil S. Mande, Manaswi Paraashar, and Nitin Saurabh. Randomized and Quantum Query Complexities of Finding a King in a Tournament. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.FSTTCS.2023.30,
  author =	{Mande, Nikhil S. and Paraashar, Manaswi and Saurabh, Nitin},
  title =	{{Randomized and Quantum Query Complexities of Finding a King in a Tournament}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.30},
  URN =		{urn:nbn:de:0030-drops-194039},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.30},
  annote =	{Keywords: Query complexity, quantum computing, randomized query complexity, tournament solutions, search problems}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.63
On the Composition of Randomized Query Complexity and Approximate Degree

Authors: Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

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

Abstract
For any Boolean functions f and g, the question whether R(f∘g) = Θ̃(R(f) ⋅ R(g)), is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg̃(f∘g) = Θ̃(deg̃(f)⋅deg̃(g)). These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R and deg̃ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g) = Ω(noisyR(f)⋅ R(g)). This implies that composition holds whenever noisyR(f) = Θ̃(R(f)). We show two results: 1. When R(f) = Θ(n), then noisyR(f) = Θ(R(f)). In other words, composition holds whenever the randomized query complexity of the outer function is full. 2. If R composes with respect to an outer function, then noisyR also composes with respect to the same outer function. On the other hand, no result of the type deg̃(f∘g) = Ω(M(f) ⋅ deg̃(g)) (for some non-trivial complexity measure M(⋅)) was known to the best of our knowledge. We prove that deg̃(f∘g) = Ω̃(√{bs(f)} ⋅ deg̃(g)), where bs(f) is the block sensitivity of f. This implies that deg̃ composes when deg̃(f) is asymptotically equal to √{bs(f)}. It is already known that both R and deg̃ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
Cite as

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Composition of Randomized Query Complexity and Approximate Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 63:1-63:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2023.63,
  author =	{Chakraborty, Sourav and Kayal, Chandrima and Mittal, Rajat and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Composition of Randomized Query Complexity and Approximate Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{63:1--63:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.63},
  URN =		{urn:nbn:de:0030-drops-188883},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.63},
  annote =	{Keywords: Approximate degree, Boolean functions, Composition Theorem, Partial functions, Randomized Query Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.74
Karchmer-Wigderson Games for Hazard-Free Computation

Authors: Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth 2 that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.
Cite as

Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh. Karchmer-Wigderson Games for Hazard-Free Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 74:1-74:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ikenmeyer_et_al:LIPIcs.ITCS.2023.74,
  author =	{Ikenmeyer, Christian and Komarath, Balagopal and Saurabh, Nitin},
  title =	{{Karchmer-Wigderson Games for Hazard-Free Computation}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{74:1--74:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.74},
  URN =		{urn:nbn:de:0030-drops-175775},
  doi =		{10.4230/LIPIcs.ITCS.2023.74},
  annote =	{Keywords: Hazard-free computation, monotone computation, Karchmer-Wigderson games, communication complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.65
Rabbits Approximate, Cows Compute Exactly!

Authors: Balagopal Komarath, Anurag Pandey, and Nitin Saurabh

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that VF, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in VDet, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. We show that algebraic formulas can in fact be efficiently simulated by the determinant of tetradiagonal matrices, transforming the open problem into a problem about determinant of general matrices versus determinant of tetradiagonal matrices with just three non-zero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two non-zero diagonals or even tridiagonal matrices, thanks to Allender and Wang (Computational Complexity'16) which showed that the determinant of tridiagonal matrices cannot even compute simple polynomials like x_1 x_2 + x_3 x_4 + ⋯ + x_15 x_16. Our proof involves a structural refinement of the simulation of algebraic formulas by width-3 algebraic branching programs by Ben-Or and Cleve (SIAM Journal of Computing'92). The tetradiagonal matrices we obtain in our proof are also structurally very similar to the tridiagonal matrices of Bringmann, Ikenmeyer and Zuiddam (JACM'18) which showed that, if we allow approximations in the sense of geometric complexity theory, algebraic formulas can be efficiently simulated by the determinant of tridiagonal matrices of a very special form, namely the continuant polynomial. The continuant polynomial family is closely related to the Fibonacci sequence, which was used to model the breeding of rabbits. The determinants of our tetradiagonal matrices, in comparison, is closely related to Narayana’s cows sequences, which was originally used to model the breeding of cows. Our result shows that the need for approximation can be eliminated by using Narayana’s cows polynomials instead of continuant polynomials, or equivalently, shifting one of the outer diagonals of a tridiagonal matrix one place away from the center. Conversely, we observe that the determinant (or, permanent) of band matrices can be computed by polynomial-sized algebraic formulas when the bandwidth is bounded by a constant, showing that the determinant (or, permanent) of bandwidth k matrices for all constants k ≥ 2 yield VF-complete polynomial families. In particular, this implies that the determinant of tetradiagonal matrices in general and Narayana’s cows polynomials in particular yield complete polynomial families for the class VF.
Cite as

Balagopal Komarath, Anurag Pandey, and Nitin Saurabh. Rabbits Approximate, Cows Compute Exactly!. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.MFCS.2022.65,
  author =	{Komarath, Balagopal and Pandey, Anurag and Saurabh, Nitin},
  title =	{{Rabbits Approximate, Cows Compute Exactly!}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{65:1--65:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.65},
  URN =		{urn:nbn:de:0030-drops-168637},
  doi =		{10.4230/LIPIcs.MFCS.2022.65},
  annote =	{Keywords: Algebraic complexity theory, Algebraic complexity classes, Determinant versus permanent, Algebraic formulas, Algebraic branching programs, Band matrices, Tridiagonal matrices, Tetradiagonal matrices, Continuant, Narayana’s cow sequence, Padovan sequence}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.28
Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d

Authors: Rajesh Chitnis and Nitin Saurabh

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In the discrete k-Center problem, we are given a metric space (P,dist) where |P| = n and the goal is to select a set C ⊆ P of k centers which minimizes the maximum distance of a point in P from its nearest center. For any ε > 0, Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an (1+ε)-approximation algorithm for this problem in d-dimensional Euclidean space which runs in O(dn log k) + (k/ε)^{O (k^{1-1/d})}⋅ n^{O(1)} time. In this paper we show that their algorithm is essentially optimal: if for some d ≥ 2 and some computable function f, there is an f(k)⋅(1/ε)^{o (k^{1-1/d})} ⋅ n^{o (k^{1-1/d})} time algorithm for (1+ε)-approximating the discrete k-Center on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a d-dimensional constraint satisfaction problem (CSP) to discrete d-dimensional k-Center. This reduction has the property that there is a fixed value ε (depending on the CSP) such that the optimal radius of k-Center instances corresponding to satisfiable and unsatisfiable instances of the CSP is < 1 and ≥ (1+ε) respectively. Our claimed lower bound on the running time for approximating discrete k-Center in d-dimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG '14] for checking the satisfiability of the aforementioned d-dimensional CSP. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in n^{O (d⋅ k^{1-1/d})} time for discrete k-Center on n points in d-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some d ≥ 2 and some computable function f, there is an f(k)⋅n^{o (k^{1-1/d})} time exact algorithm for the discrete k-Center problem on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for d = 2 and was implicit in the work of Marx [IWPEC '06].
Cite as

Rajesh Chitnis and Nitin Saurabh. Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.SoCG.2022.28,
  author =	{Chitnis, Rajesh and Saurabh, Nitin},
  title =	{{Tight Lower Bounds for Approximate \& Exact k-Center in \mathbb{R}^d}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.28},
  URN =		{urn:nbn:de:0030-drops-160365},
  doi =		{10.4230/LIPIcs.SoCG.2022.28},
  annote =	{Keywords: k-center, Euclidean space, Exponential Time Hypothesis (ETH), lower bound}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.21
Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Authors: Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh

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

Abstract
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.
Cite as

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.CCC.2020.21,
  author =	{Bl\"{a}ser, Markus and Ikenmeyer, Christian and Mahajan, Meena and Pandey, Anurag and Saurabh, Nitin},
  title =	{{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{21:1--21:24},
  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.21},
  URN =		{urn:nbn:de:0030-drops-125733},
  doi =		{10.4230/LIPIcs.CCC.2020.21},
  annote =	{Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.45
Improved Bounds on Fourier Entropy and Min-Entropy

Authors: Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Given a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this paper we present three new contributions towards the FEI conjecture: ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs. iii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the min-entropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅?_{min}^⊕(f), where ?_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1-ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). iv) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.
Cite as

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45,
  author =	{Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald},
  title =	{{Improved Bounds on Fourier Entropy and Min-Entropy}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45},
  URN =		{urn:nbn:de:0030-drops-119062},
  doi =		{10.4230/LIPIcs.STACS.2020.45},
  annote =	{Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.12
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity

Authors: Diptarka Chakraborty, Debarati Das, Michal Koucký, and Nitin Saurabh

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
A quasi-Gray code of dimension n and length l over an alphabet Sigma is a sequence of distinct words w_1,w_2,...,w_l from Sigma^n such that any two consecutive words differ in at most c coordinates, for some fixed constant c>0. In this paper we are interested in the read and write complexity of quasi-Gray codes in the bit-probe model, where we measure the number of symbols read and written in order to transform any word w_i into its successor w_{i+1}. We present construction of quasi-Gray codes of dimension n and length 3^n over the ternary alphabet {0,1,2} with worst-case read complexity O(log n) and write complexity 2. This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasi-Gray codes of dimension n and length at least 2^n - 20n with worst-case read complexity 6+log n and write complexity 2. This complements a recent result by Raskin [Raskin '17] who shows that any quasi-Gray code over binary alphabet of length 2^n has read complexity Omega(n). Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Omega(n) worst-case barrier for space-optimal (non-redundant) quasi-Gray codes with constant number of writes. We obtain our results via a novel application of algebraic tools together with the principles of catalytic computation [Buhrman et al. '14, Ben-Or and Cleve '92, Barrington '89, Coppersmith and Grossman '75].
Cite as

Diptarka Chakraborty, Debarati Das, Michal Koucký, and Nitin Saurabh. Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.12,
  author =	{Chakraborty, Diptarka and Das, Debarati and Kouck\'{y}, Michal and Saurabh, Nitin},
  title =	{{Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.12},
  URN =		{urn:nbn:de:0030-drops-94750},
  doi =		{10.4230/LIPIcs.ESA.2018.12},
  annote =	{Keywords: Gray code, Space-optimal counter, Decision assignment tree, Cell probe model}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.493
Homomorphism Polynomials Complete for VP

Authors: Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.
Cite as

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh. Homomorphism Polynomials Complete for VP. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.FSTTCS.2014.493,
  author =	{Durand, Arnaud and Mahajan, Meena and Malod, Guillaume and de Rugy-Altherre, Nicolas and Saurabh, Nitin},
  title =	{{Homomorphism Polynomials Complete for VP}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.493},
  URN =		{urn:nbn:de:0030-drops-48665},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.493},
  annote =	{Keywords: algebraic complexity, graph homomorphism, polynomials, VP, VNP, completeness}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact