:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Liu, Yang P., Lovett, Shachar, Mittal, Kunal
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2602.09290
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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

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

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

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

On Efficient Computation of DiRe Committees
di: Relia, Kunal
Pubblicazione: (2024)

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

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

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

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

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

Game Derandomization
di: Epstein, Samuel
Pubblicazione: (2024)

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

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

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

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

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

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

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

Parallel Play Saves Quantifiers
di: Carmosino, Marco, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

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

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

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