Search Results

Documents authored by Nalli, Sai Soumya

Document
DOI: 10.4230/LIPIcs.CCC.2026.30
Bounds for Hardness Condensation in the Query Model

Authors: Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli, Manaswi Paraashar, Karthikeya Polisetty, Jayalal Sarma, and Nitin Saurabh

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
For any Boolean function f:{0,1}ⁿ → {0,1} with a complexity measure having value k ≪ n, is it possible to restrict the function f to Θ(k) variables while keeping the complexity preserved at Θ(k)? Instantiation of this question for the measure of circuit complexity of the Boolean function was shown to be related to circuit lower bounds (Buresh-Oppenheim and Santhanam, 2006). Variants of the above question were also shown to have connections to the log-rank conjecture in communication complexity (Hrubeš, 2024) and lower bounds in proof complexity (Razborov, 2016). In the context of communication and query complexity, this question was recently studied by Göös, Newman, Riazanov and Sokolov (2024). They showed, among other results, that query complexity cannot be condensed losslessly. In this work, we show that there exists a Boolean function f such that any restriction of f to O(ℳ(f)) variables has ℳ(⋅)-complexity at most Õ(ℳ(f)^{2/3}), where ℳ is one of block sensitivity (bs), fractional block sensitivity (fbs), certificate complexity (𝖢), deterministic query complexity (𝖣), zero-error randomized query complexity (𝖱₀), and AND (and OR)-decision tree query complexity. This improves upon the results of Göös, Newman, Riazanov, and Sokolov (2024) for 𝖣 and 𝖱₀, and in particular answers their open question about the condensation of block sensitivity. We complement the negative results on lossless condensation with positive results about lossy condensation. In particular, we show that for every Boolean function f there exists a restriction of f to O(ℳ(f)) variables such that its ℳ(⋅)-complexity is at least Ω(ℳ(f)^{1/2}), where ℳ ∈ {bs,fbs,𝖢,UC_{min},UC₁,UC,𝖣,deg̃,λ}. In addition, we show lossy condensation for randomized and quantum query complexity with a slightly smaller exponent.
Cite as

Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli, Manaswi Paraashar, Karthikeya Polisetty, Jayalal Sarma, and Nitin Saurabh. Bounds for Hardness Condensation in the Query Model. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2026.30,
  author =	{Kayal, Chandrima and Mittal, Rajat and Nalli, Sai Soumya and Paraashar, Manaswi and Polisetty, Karthikeya and Sarma, Jayalal and Saurabh, Nitin},
  title =	{{Bounds for Hardness Condensation in the Query Model}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.30},
  URN =		{urn:nbn:de:0030-drops-270722},
  doi =		{10.4230/LIPIcs.CCC.2026.30},
  annote =	{Keywords: Query Complexity, Decision Trees, Hardness Condensation}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact