Imagen de Portada

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Bhattacharya, Sreejata Kishor
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
por: Bhattacharya, Sreejata Kishor, et al.
Publicado: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
por: Bhattacharya, Sreejata Kishor, et al.
Publicado: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
por: Gryaznov, Svyatoslav, et al.
Publicado: (2024)

Recovery Reductions, Conjectures, and Barriers
por: Nareddy, Tejas, et al.
Publicado: (2025)

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

On the Keevash-Knox-Mycroft Conjecture
por: Gan, Luyining, et al.
Publicado: (2022)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
por: Kamath, Pritish, et al.
Publicado: (2026)

Classically Spoofing System Linear Cross Entropy Score Benchmarking
por: Tanggara, Andrew, et al.
Publicado: (2024)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
por: Mackenzie, Simon, et al.
Publicado: (2024)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
por: Biswas, Aniruddha, et al.
Publicado: (2022)

The Rank-Ramsey Problem and the Log-Rank Conjecture
por: Beniamini, Gal, et al.
Publicado: (2024)

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

A Quantum Unique Games Conjecture
por: Mousavi, Hamoon, et al.
Publicado: (2024)

Finite Variable Counting Logics with Restricted Requantification
por: Raßmann, Simon, et al.
Publicado: (2024)

Broadcasting under Structural Restrictions
por: Egami, Yudai, et al.
Publicado: (2025)

Tensor Hinted Mv Conjectures
por: Song, Zhao
Publicado: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
por: Baril, Ambroise, et al.
Publicado: (2024)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
por: Riazanov, Artur, et al.
Publicado: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
por: Hsieh, Jun-Ting, et al.
Publicado: (2024)

Random Permutations in Computational Complexity
por: Hitchcock, John M., et al.
Publicado: (2025)

The Randomness Deficiency Function and the Shift Operator
por: Epstein, Samuel
Publicado: (2023)

The Quasi-Polynomial Low-Degree Conjecture is False
por: Buhai, Rares-Darius, et al.
Publicado: (2025)

No Complete Problem for Constant-Cost Randomized Communication
por: Fang, Yuting, et al.
Publicado: (2024)

Hilbert Functions and Low-Degree Randomness Extractors
por: Golovnev, Alexander, et al.
Publicado: (2024)

Strongly Refuting Random CSP without Literals
por: Chan, Siu On, et al.
Publicado: (2026)

Direct Product Theorems for Randomized Query Complexity
por: Ben-David, Shalev, et al.
Publicado: (2025)

Pseudorandom unitaries are neither real nor sparse nor noise-robust
por: Haug, Tobias, et al.
Publicado: (2023)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
por: Hirahara, Shuichi, et al.
Publicado: (2024)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
por: Chew, Leroy, et al.
Publicado: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
por: Yung, Kingsley
Publicado: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
por: Gharibian, Sevag, et al.
Publicado: (2021)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
por: Weggemans, Jordi, et al.
Publicado: (2023)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
por: Bharadwaj, G V Sumukha, et al.
Publicado: (2024)

Proof of Hiding Conjecture in Gaussian Boson Sampling
por: Shou, Laura, et al.
Publicado: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
por: Chukhin, Nikolai, et al.
Publicado: (2024)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
por: Xu, Jeff
Publicado: (2024)

Restricted CSPs and F-free Digraph Algorithmics
por: Guzmán-Pro, Santiago, et al.
Publicado: (2025)

Lines in Every Direction with No ee-Random Points
por: Lutz, Neil, et al.
Publicado: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
por: Zhuk, Dmitriy
Publicado: (2024)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
por: Tulsiani, Madhur, et al.
Publicado: (2024)