Cover Image

Hard-to-Sample Distributions from Robust Extractors

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Byramji, Farzan, Kane, Daniel M., Morris, Jackson, Ostuni, Anthony
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Advantage of Adaptivity for Sampling with Cell Probes
by: Byramji, Farzan, et al.
Published: (2026)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Locally Sampleable Uniform Symmetric Distributions
by: Kane, Daniel M., et al.
Published: (2024)

Locality Bounds for Sampling Hamming Slices
by: Kane, Daniel M., et al.
Published: (2024)

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

Corners in Quasirandom Groups via Sparse Mixing
by: Jaber, Michael, et al.
Published: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

New Pseudorandom Generators and Correlation Bounds Using Extractors
by: Kumar, Vinayak M.
Published: (2025)

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)

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

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

Extractors for Polynomial Sources over $\mathbb{F}_2$
by: Chattopadhyay, Eshan, et al.
Published: (2023)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
by: Grier, Daniel, et al.
Published: (2026)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

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

Leakage-Resilient Extractors against Number-on-Forehead Protocols
by: Chattopadhyay, Eshan, et al.
Published: (2025)

Free Fermion Distributions Are Hard to Learn
by: Nietner, Alexander
Published: (2023)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

Nearly-Linear Time Seeded Extractors with Short Seeds
by: Doron, Dean, et al.
Published: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

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

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

Higher Hardness Results for the Reconfiguration of Odd Matchings
by: Dorfer, Joseph
Published: (2026)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

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

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

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

Hardness of Quantum Distribution Learning and Quantum Cryptography
by: Hiroka, Taiga, et al.
Published: (2025)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
by: Casteigts, Arnaud, et al.
Published: (2026)