Demo Data from VLDB 2026 / reviewers in the wild / expert
Karthikeya Polisetty
dblp:429/0331
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2026
—ORCID · none
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › query complexity
block sensitivity |
1.0 | 1 | 2026 | Bounds for Hardness Condensation in the Query Model · CCC 2026 |
Computational complexity › structural complexity
hardness condensation |
1.0 | 1 | 2026 | Bounds for Hardness Condensation in the Query Model · CCC 2026 |
Computational complexity
query complexity |
1.0 | 1 | 2026 | Bounds for Hardness Condensation in the Query Model · CCC 2026 |
Computational complexity › query complexity › decision tree complexity
randomized query complexity |
1.0 | 1 | 2026 | 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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Bounds for Hardness Condensation in the Query ModelabstractFor 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 |
CCC | 5 |