Search Results

Documents authored by Sreenivasaiah, Karteek

Document
DOI: 10.4230/LIPIcs.MFCS.2025.17
Sensitivity and Query Complexity Under Uncertainty

Authors: Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, and Karteek Sreenivasaiah

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output "unknown" only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang’s celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.
Cite as

Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, and Karteek Sreenivasaiah. Sensitivity and Query Complexity Under Uncertainty. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{benson_et_al:LIPIcs.MFCS.2025.17,
  author =	{Benson, Deepu and Komarath, Balagopal and Mande, Nikhil and Nalli, Sai Soumya and Sarma, Jayalal and Sreenivasaiah, Karteek},
  title =	{{Sensitivity and Query Complexity Under Uncertainty}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.17},
  URN =		{urn:nbn:de:0030-drops-241240},
  doi =		{10.4230/LIPIcs.MFCS.2025.17},
  annote =	{Keywords: CREW-PRAM, query complexity, decision trees, sensitivity, hazard-free extensions}
}
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}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact