Cover Image

Improved Condensers for Chor-Goldreich Sources

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Goodman, Jesse, Li, Xin, Zuckerman, David
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

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

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

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

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

On the Existence of Seedless Condensers: Exploring the Terrain
by: Chattopadhyay, Eshan, et al.
Published: (2023)

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

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

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

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

The Complexity of Finding Missing Answer Repairs
by: Comer, Jesse, et al.
Published: (2026)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

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

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

Improving the Leading Constant of Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

An Improved Construction of Variety-Evasive Subspace Families
by: Andrews, Robert, et al.
Published: (2026)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

Condensing and Extracting Against Online Adversaries
by: Chattopadhyay, Eshan, et al.
Published: (2024)

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

Regular Functions on Formal-Analytic Arithmetic Surfaces
by: Goodman, Samuel
Published: (2025)

Mistake-bounded online learning with operation caps
by: Geneson, Jesse, et al.
Published: (2025)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
by: Mao, Xinyu, et al.
Published: (2024)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

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

Improved quantum data analysis
by: Bădescu, Costin, et al.
Published: (2020)

Improved Debordering of Waring Rank
by: Shpilka, Amir
Published: (2025)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Reverse-Robust Computation with Chemical Reaction Networks
by: Kini, Ravi, et al.
Published: (2026)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Improved Lower Bounds for QAC0
by: Joshi, Malvika Raj, et al.
Published: (2025)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
by: Dingel, David, et al.
Published: (2024)

Complexity of adaptive testing in scenarios defined extensionally
by: Rodriguez, Ismael, et al.
Published: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Complexity analysis and practical resolution of the data classification problem with private characteristics
by: Pantoja, David, et al.
Published: (2026)

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)