14 citations · 22 across the 6 of their papers we have counts for
7 papers
New and Improved Concrete Lower Bounds for Orthogonal Vectors
Tameem Choudhury, Nutan Limaye, Karteek Sreenivasaiah +1
The Orthogonal Vectors Problem (OV) takes as input two sets each containing -dimensional Boolean vectors, and outputs if and only if there exists …
Sensitivity and Query Complexity under Uncertainty
Deepu Benson, Balagopal Komarath, Nikhil Mande +3
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 inp…
Query Complexity with Unknowns
Nikhil S. Mande, Karteek Sreenivasaiah
We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with ``unknown''. The query algorithm is…
Graph Pattern Polynomials
Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah
We study the time complexity of induced subgraph isomorphism problems where the pattern graph is fixed. The earliest known example of an improvement over trivial algorithms is by I…
A Fixed-Depth Size-Hierarchy Theorem for AC via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2
We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC circuits; in particular, for fixed , the class of uniform AC for…
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen +3
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows th…
Small Depth Proof Systems
Andreas Krebs, Nutan Limaye, Meena Mahajan +1
A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof syst…