DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2024.25

Depth-3 Circuit Lower Bounds for k-OV

Authors: Tameem Choudhury and Karteek Sreenivasaiah

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

Abstract

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples A and B of n Boolean vectors, each of dimension d, decide if there exist vectors u ∈ A, and v ∈ B, such that u and v are orthogonal. This problem, and its generalization k-OV defined analogously for k tuples, are central problems in the area of fine-grained complexity. One of the major conjectures in fine-grained complexity is that k-OV cannot be solved by a randomised algorithm in n^{k-ε}poly(d) time for any constant ε > 0. In this paper, we are interested in unconditional lower bounds against k-OV, but for weaker models of computation than the general Turing Machine. In particular, we are interested in circuit lower bounds to computing k-OV by Boolean circuit families of depth 3 of the form OR-AND-OR, or equivalently, a disjunction of CNFs. We show that for all k ≤ d, any disjunction of t-CNFs computing k-OV requires size Ω((n/t)^k). In particular, when k is a constant, any disjunction of k-CNFs computing k-OV needs to use Ω(n^k) CNFs. This matches the brute-force construction, and for each fixed k > 2, this is the first unconditional Ω(n^k) lower bound against k-OV for a computation model that can compute it in size O(n^k). Our results partially resolve a conjecture by Kane and Williams [Daniel M. Kane and Richard Ryan Williams, 2019] (page 12, conjecture 10) about depth-3 AC⁰ circuits computing 2-OV. As a secondary result, we show an exponential lower bound on the size of AND∘OR∘AND circuits computing 2-OV when d is very large. Since 2-OV reduces to k-OV by projections trivially, this lower bound works against k-OV as well.

Cite as

Tameem Choudhury and Karteek Sreenivasaiah. Depth-3 Circuit Lower Bounds for k-OV. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{choudhury_et_al:LIPIcs.STACS.2024.25,
  author =	{Choudhury, Tameem and Sreenivasaiah, Karteek},
  title =	{{Depth-3 Circuit Lower Bounds for k-OV}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-197359},
  doi =		{10.4230/LIPIcs.STACS.2024.25},
  annote =	{Keywords: fine grained complexity, k-OV, circuit lower bounds, depth-3 circuits}
}

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}
}

Search Results

Documents authored by Sreenivasaiah, Karteek

Depth-3 Circuit Lower Bounds for k-OV

Abstract

Cite as

Graph Pattern Polynomials

Abstract

Cite as

Thanks for your feedback!

Could not send message