Buchumschlag

Biased Linearity Testing in the 1% Regime

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Khot, Subhash, Mittal, Kunal
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
von: Bhangale, Amey, et al.
Veröffentlicht: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
von: S., Karthik C., et al.
Veröffentlicht: (2021)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: IV
von: Bhangale, Amey, et al.
Veröffentlicht: (2023)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
von: Mittal, Kunal
Veröffentlicht: (2025)

An Invariance Principle for the Multi-slice, with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2021)

On Approximability of Satisfiable $k$-CSPs: VI
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

Parallel Repetition for $3$-Player XOR Games
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
von: Mittal, Tushant, et al.
Veröffentlicht: (2024)

Isomorphism Testing of Rooted Trees in Linear Time
von: Lindeberg, Anna
Veröffentlicht: (2024)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
von: Datta, Swarnalipa, et al.
Veröffentlicht: (2023)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
von: Komarath, Balagopal, et al.
Veröffentlicht: (2026)

On Optimal Testing of Linearity
von: Arora, Vipul, et al.
Veröffentlicht: (2024)

Superposition detection and QMA with non-collapsing measurements
von: Bassirian, Roozbeh, et al.
Veröffentlicht: (2024)

On Efficient Computation of DiRe Committees
von: Relia, Kunal
Veröffentlicht: (2024)

Approximate Degree Composition for Recursive Functions
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2024)

On query complexity measures and their relations for symmetric functions
von: Mittal, Rajat, et al.
Veröffentlicht: (2021)

A complexity phase transition at the EPR Hamiltonian
von: Marwaha, Kunal, et al.
Veröffentlicht: (2026)

On the Complexity of Decoded Quantum Interferometry
von: Marwaha, Kunal, et al.
Veröffentlicht: (2025)

Bounds for Hardness Condensation in the Query Model
von: Kayal, Chandrima, et al.
Veröffentlicht: (2026)

Parity Tests with Ties
von: Kupfer, Ron
Veröffentlicht: (2026)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
von: Erhardt, Alexander, et al.
Veröffentlicht: (2025)

Relations between monotone complexity measures based on decision tree complexity
von: Byramji, Farzan, et al.
Veröffentlicht: (2024)

New Direct Sum Tests
von: Westover, Alek, et al.
Veröffentlicht: (2024)

Linear Planar 3-SAT and Its Applications in Planning
von: Desbois, Victorien, et al.
Veröffentlicht: (2025)

Local Correction of Linear Functions over the Boolean Cube
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2024)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
von: Arvind, V., et al.
Veröffentlicht: (2022)

Low-Degree Testing Over Grids
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2023)

On Matrix Multiplication and Polynomial Identity Testing
von: Andrews, Robert
Veröffentlicht: (2022)

Explicit Codes approaching Generalized Singleton Bound using Expanders
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2025)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
von: Ketkov, Sergey S., et al.
Veröffentlicht: (2025)

Quantum Merlin-Arthur with an internally separable proof
von: Bassirian, Roozbeh, et al.
Veröffentlicht: (2024)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
von: Fu, Honghao, et al.
Veröffentlicht: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
von: Ramya, C., et al.
Veröffentlicht: (2025)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
von: Yamakami, Tomoyuki
Veröffentlicht: (2017)