Cover Image

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Xin, Zhong, Yan
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Two-Source and Affine Non-Malleable Extractors for Small Entropy
by: Li, Xin, et al.
Published: (2024)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

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

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
by: Biswas, Ari, et al.
Published: (2025)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

Direct Product Primality Testing of Graphs is GI-hard
by: Calderoni, Luca, et al.
Published: (2020)

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

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Hard-to-Sample Distributions from Robust Extractors
by: Byramji, Farzan, et al.
Published: (2026)

Hardness of 4-Colourings G-Colourable Graphs
by: Avvakumov, Sergey, et al.
Published: (2025)

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

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

Deciding if a DAG is Interesting is Hard
by: De Carufel, Jean-Lou, et al.
Published: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

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

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

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
by: Cheng, Kuan, et al.
Published: (2026)

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds
by: Dhar, Manik, et al.
Published: (2022)

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

More efficient sifting for grid norms, and applications to multiparty communication complexity
by: Kelley, Zander, et al.
Published: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
by: Dikstein, Yotam, et al.
Published: (2023)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

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

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)