Cover Image

Reasonable Bounds for Combinatorial Lines of Length Three

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhangale, Amey, Khot, Subhash, Liu, Yang P., Minzer, Dor
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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)

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

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
by: Bhangale, Amey, et al.
Published: (2023)

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

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

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

The Lens of Abelian Embeddings
by: Minzer, Dor
Published: (2026)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

A Distance Amplification Lemma for Monotonicity
by: Minzer, Dor
Published: (2025)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

Characterizing Direct Product Testing via Coboundary Expansion
by: Bafna, Mitali, et al.
Published: (2023)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

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

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

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

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

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
by: Minzer, Dor, et al.
Published: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
by: Nagda, Ansh, et al.
Published: (2026)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Chernoff Bounds and Reverse Hypercontractivity on HDX
by: Dikstein, Yotam, et al.
Published: (2024)

Bounded degree QBF and positional games
by: Oijid, Nacim
Published: (2024)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
by: Nagda, Ansh, et al.
Published: (2025)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Product Mixing in Compact Lie Groups
by: Ellis, David, et al.
Published: (2024)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
by: Hou, Jianfeng, et al.
Published: (2024)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

Forest Covers and Bounded Forest Covers
by: Gaur, Daya Ram, et al.
Published: (2024)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
by: Alrabiah, Omar, et al.
Published: (2024)