3 papers
cs.CC2026
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 …
cs.CC2025
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…
cs.CC2024
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…