Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.

Sai Soumya Nalli

dblp:429/1629 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
1since 2021 · last 2026
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › query complexity
block sensitivity
1.012026
Bounds for Hardness Condensation in the Query Model · CCC 2026
Computational complexity › structural complexity
hardness condensation
1.012026
Bounds for Hardness Condensation in the Query Model · CCC 2026
Computational complexity
query complexity
1.012026
Bounds for Hardness Condensation in the Query Model · CCC 2026
Computational complexity › query complexity › decision tree complexity
randomized query complexity
1.012026
Bounds for Hardness Condensation in the Query Model · CCC 2026

Methods — techniques the papers use, named apart from their topics

restriction · 1.0lossy condensation · 1.0
YearPublicationVenuePosition
2026 Bounds for Hardness Condensation in the Query Model
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.
Chandrima Kayal, Rajat Mittal 0001, Sai Soumya Nalli, Manaswi Paraashar, Karthikeya Polisetty, Jayalal Sarma, Nitin Saurabh
CCC3