Search Results

Documents authored by Komarath, Balagopal

Document
DOI: 10.4230/LIPIcs.STACS.2024.31
On the Power of Border Width-2 ABPs over Fields of Characteristic 2

Authors: Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The celebrated result by Ben-Or and Cleve [SICOMP92] showed that algebraic formulas are polynomially equivalent to width-3 algebraic branching programs (ABP) for computing polynomials. i.e., VF = VBP₃. Further, there are simple polynomials, such as ∑_{i = 1}⁸ x_i y_i, that cannot be computed by width-2 ABPs [Allender and Wang, CC16]. Bringmann, Ikenmeyer and Zuiddam, [JACM18], on the other hand, studied these questions in the setting of approximate (i.e., border complexity) computation, and showed the universality of border width-2 ABPs, over fields of characteristic ≠ 2. In particular, they showed that polynomials that can be approximated by formulas can also be approximated (with only a polynomial blowup in size) by width-2 ABPs, i.e., VF ̅ = VBP₂ ̅. The power of border width-2 algebraic branching programs when the characteristic of the field is 2 was left open. In this paper, we show that width-2 ABPs can approximate every polynomial irrespective of the field characteristic. We show that any polynomial f with 𝓁 monomials and with at most t odd-power indeterminates per monomial can be approximated by 𝒪(𝓁⋅ (deg(f)+2^t))-size width-2 ABPs. Since 𝓁 and t are finite, this proves universality of border width-2 ABPs. For univariate polynomials, we improve this upper-bound from O(deg(f)²) to O(deg(f)). Moreover, we show that, if a polynomial f can be approximated by small formulas, then the polynomial f^d, for some small power d, can be approximated by small width-2 ABPs. Therefore, even over fields of characteristic two, border width-2 ABPs are a reasonably powerful computational model. Our construction works over any field.
Cite as

Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the Power of Border Width-2 ABPs over Fields of Characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.STACS.2024.31,
  author =	{Dutta, Pranjal and Ikenmeyer, Christian and Komarath, Balagopal and Mittal, Harshil and Nanoti, Saraswati Girish and Thakkar, Dhara},
  title =	{{On the Power of Border Width-2 ABPs over Fields of Characteristic 2}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31},
  URN =		{urn:nbn:de:0030-drops-197419},
  doi =		{10.4230/LIPIcs.STACS.2024.31},
  annote =	{Keywords: Algebraic branching programs, border complexity, characteristic 2}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.40
Finding and Counting Patterns in Sparse Graphs

Authors: Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover Õ(m³)-time, constant-space algorithms for cycles of length at most 11 and Õ(m²)-time, polynomial-space algorithms for paths of length at most 10.
Cite as

Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia. Finding and Counting Patterns in Sparse Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.STACS.2023.40,
  author =	{Komarath, Balagopal and Kumar, Anant and Mishra, Suchismita and Sethia, Aditi},
  title =	{{Finding and Counting Patterns in Sparse Graphs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.40},
  URN =		{urn:nbn:de:0030-drops-176921},
  doi =		{10.4230/LIPIcs.STACS.2023.40},
  annote =	{Keywords: Subgraph Detection and Counting, Homomorphism Polynomials, Treewidth and Treedepth, Matchings}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.83
Monotone Arithmetic Complexity of Graph Homomorphism Polynomials

Authors: Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials.
Cite as

Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.ICALP.2022.83,
  author =	{Komarath, Balagopal and Pandey, Anurag and Rahul, Chengot Sankaramenon},
  title =	{{Monotone Arithmetic Complexity of Graph Homomorphism Polynomials}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.83},
  URN =		{urn:nbn:de:0030-drops-164245},
  doi =		{10.4230/LIPIcs.ICALP.2022.83},
  annote =	{Keywords: Homomorphism polynomials, Monotone complexity, Algebraic complexity, Graph algorithms, Fine-grained complexity, Fixed-parameter algorithms and complexity, Treewidth, Pathwidth, Treedepth, Graph homomorphisms, Algebraic circuits, Algebraic branching programs, Algebraic formulas}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.18
Graph Pattern Polynomials

Authors: Markus Bläser, Balagopal Komarath, and Karteek Sreenivasaiah

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

Abstract
Given a host graph G and a pattern graph H, the induced subgraph isomorphism problem is to decide whether G contains an induced subgraph that is isomorphic to H. We study the time complexity of induced subgraph isomorphism problems when the pattern graph is fixed. Nesetril and Poljak gave an O(n^{k omega}) time algorithm that decides the induced subgraph isomorphism problem for any 3k vertex pattern graph (the universal algorithm), where omega is the matrix multiplication exponent. Improvements are not known for any infinite pattern family. Algorithms faster than the universal algorithm are known only for a finite number of pattern graphs. In this paper, we show that there exists infinitely many pattern graphs for which the induced subgraph isomorphism problem has algorithms faster than the universal algorithm. Our algorithm works by reducing the pattern detection problem into a multilinear term detection problem on special classes of polynomials called graph pattern polynomials. We show that many of the existing algorithms including the universal algorithm can also be described in terms of such a reduction. We formalize this class of algorithms by defining graph pattern polynomial families and defining a notion of reduction between these polynomial families. The reduction also allows us to argue about relative hardness of various graph pattern detection problems within this framework. We show that solving the induced subgraph isomorphism for any pattern graph that contains a k-clique is at least as hard detecting k-cliques. An equivalent theorem is not known in the general case. In the full version of this paper, we obtain new algorithms for P_5 and C_5 that are optimal under reasonable hardness assumptions. We also use this method to derive new combinatorial algorithms - algorithms that do not use fast matrix multiplication - for paths and cycles. We also show why graph homomorphisms play a major role in algorithms for subgraph isomorphism problems. Using this, we show that the arithmetic circuit complexity of the graph homomorphism polynomial for K_k - e (The k-clique with an edge removed) is related to the complexity of many subgraph isomorphism problems. This generalizes and unifies many existing results.
Cite as

Markus Bläser, Balagopal Komarath, and Karteek Sreenivasaiah. Graph Pattern Polynomials. 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. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.FSTTCS.2018.18,
  author =	{Bl\"{a}ser, Markus and Komarath, Balagopal and Sreenivasaiah, Karteek},
  title =	{{Graph Pattern Polynomials}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{18:1--18:13},
  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.18},
  URN =		{urn:nbn:de:0030-drops-99172},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.18},
  annote =	{Keywords: algorithms, induced subgraph detection, algebraic framework}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.622
Pebbling, Entropy and Branching Program Size Lower Bounds

Authors: Balagopal Komarath and Jayalal M. N. Sarma

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced in (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, 2012). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this context, we consider a restriction of non-deterministic thrifty branching programs called bitwise-independence. We show that any bitwise-independent non-deterministic thrifty branching program solving BT_2(h,k) must have at least 1/2 k^{h/2} states. Prior to this work, lower bounds were known for general branching programs only for fixed heights h=2,3,4 (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, 2012). Our lower bounds are also tight (up to a factor of k), since the known (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, 2012) non-deterministic thrifty branching programs for this problem of size O(k^{h/2+1}) are bitwise-independent. We prove our results by associating a fractional pebbling strategy with any bitwise-independent non-deterministic thrifty branching program solving the Tree Evaluation Problem. Such a connection was not known previously even for fixed heights. Our main technique is the entropy method introduced by Jukna and Zak (S. Jukna and S. Žák, 2003) originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam, 2012) for deterministic branching programs for Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any k-way deterministic branching program solving Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.
Cite as

Balagopal Komarath and Jayalal M. N. Sarma. Pebbling, Entropy and Branching Program Size Lower Bounds. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 622-633, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.STACS.2013.622,
  author =	{Komarath, Balagopal and Sarma, Jayalal M. N.},
  title =	{{Pebbling, Entropy and Branching Program Size Lower Bounds}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{622--633},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.622},
  URN =		{urn:nbn:de:0030-drops-39709},
  doi =		{10.4230/LIPIcs.STACS.2013.622},
  annote =	{Keywords: Pebbling, Entropy Method, Branching Programs, Size Lower Bounds.}
}
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 Imprint Privacy Contact