Cover Image

Bounds for Hardness Condensation in the Query Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kayal, Chandrima, Mittal, Rajat, Nalli, Sai Soumya, Paraashar, Manaswi, Polisetty, Karthikeya, Sarma, Jayalal, Saurabh, Nitin
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Testing Isomorphism of Boolean Functions over Finite Abelian Groups
by: Datta, Swarnalipa, et al.
Published: (2025)

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Almost-catalytic Computation
by: Bisoyi, Sagar, et al.
Published: (2024)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Towards Parameterized Hardness on Maintaining Conjunctive Queries
by: Wang, Qichen
Published: (2026)

Lower Bounds for Conjunctive Query Evaluation
by: Mengel, Stefan
Published: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

Explicit Codes approaching Generalized Singleton Bound using Expanders
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
by: Lu, Jiaqi, et al.
Published: (2025)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
by: Mittal, Kunal
Published: (2025)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Biased Linearity Testing in the 1% Regime
by: Khot, Subhash, et al.
Published: (2025)

On the Existence of Seedless Condensers: Exploring the Terrain
by: Chattopadhyay, Eshan, et al.
Published: (2023)

Improved Condensers for Chor-Goldreich Sources
by: Goodman, Jesse, et al.
Published: (2024)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)