:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Liu, Yang P., Lovett, Shachar, Mittal, Kunal
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2602.09290
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
by: Bhangale, Amey, et al.
Published: (2025)

Corners in Quasirandom Groups via Sparse Mixing
by: Jaber, Michael, et al.
Published: (2024)

Parallel Repetition for $3$-Player XOR Games
by: Bhangale, Amey, et al.
Published: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
by: Chattopadhyay, Arkadev, et al.
Published: (2025)

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

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

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

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

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

On Efficient Computation of DiRe Committees
by: Relia, Kunal
Published: (2024)

Superposition detection and QMA with non-collapsing measurements
by: Bassirian, Roozbeh, et al.
Published: (2024)

Pseudorandomness of Expander Walks via Fourier Analysis on Groups
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

Computational Complexity of Game Boy Games
by: Tirmazi, Hayder, et al.
Published: (2024)

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

Game Derandomization
by: Epstein, Samuel
Published: (2024)

A complexity phase transition at the EPR Hamiltonian
by: Marwaha, Kunal, et al.
Published: (2026)

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

Work-Efficient Parallel Counting via Sampling
by: Liu, Hongyang, et al.
Published: (2024)

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

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

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
by: Mohammad, Noor Islam S.
Published: (2026)

Parallel Play Saves Quantifiers
by: Carmosino, Marco, et al.
Published: (2024)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Quantum Merlin-Arthur with an internally separable proof
by: Bassirian, Roozbeh, et al.
Published: (2024)

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

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
by: Guruswami, Venkatesan, et al.
Published: (2021)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
by: Mao, Xinyu, et al.
Published: (2024)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
by: MIT Hardness Group, et al.
Published: (2024)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
by: Mittal, Tushant, et al.
Published: (2024)

Correction to “The Spread of Information in Virtual Communities”
Published: (2025)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)