Cover Image

Biased Linearity Testing in the 1% Regime

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Khot, Subhash, Mittal, Kunal
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

On Approximability of Satisfiable k-CSPs: V
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable k-CSPs: IV
by: Bhangale, Amey, et al.
Published: (2023)

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

An Invariance Principle for the Multi-slice, with Applications
by: Braverman, Mark, et al.
Published: (2021)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
by: Bhangale, Amey, et al.
Published: (2024)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
by: Liu, Yang P., et al.
Published: (2026)

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

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

Isomorphism Testing of Rooted Trees in Linear Time
by: Lindeberg, Anna
Published: (2024)

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

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

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

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

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

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

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

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

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

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

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

Parity Tests with Ties
by: Kupfer, Ron
Published: (2026)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
by: Erhardt, Alexander, et al.
Published: (2025)

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

New Direct Sum Tests
by: Westover, Alek, et al.
Published: (2024)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

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

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
by: Arvind, V., et al.
Published: (2022)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

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

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

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
by: Fu, Honghao, et al.
Published: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

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