Cover Image

On the Existence of Seedless Condensers: Exploring the Terrain

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chattopadhyay, Eshan, Gurumukhani, Mohit, Ringach, Noam
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Two-Sided Lossless Expanders in the Unbalanced Setting
by: Chattopadhyay, Eshan, et al.
Published: (2024)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
by: Chattopadhyay, Eshan, et al.
Published: (2025)

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

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

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

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)

Optimal Depth-Three Circuits for Inner Product
by: Gurumukhani, Mohit, et al.
Published: (2026)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)

Improved Condensers for Chor-Goldreich Sources
by: Goodman, Jesse, et al.
Published: (2024)

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

On the Existence of Anomalies, The Reals Case
by: Epstein, Samuel
Published: (2023)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2025)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
by: Chattopadhyay, Arkadev, et al.
Published: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

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

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)

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

Experiments, Computability, and the Existence of Physical Functions
by: Castillo, Isaac Pérez
Published: (2026)

Existence and nonexistence of commutativity gadgets for entangled CSPs
by: Culf, Eric, et al.
Published: (2025)

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)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)

Accessible Quantum Correlations Under Complexity Constraints
by: Yángüez, Álvaro, et al.
Published: (2026)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
by: Dutta, Suman, et al.
Published: (2021)

Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments
by: Horn, Laryssa, et al.
Published: (2025)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
by: Beniamini, Gal, et al.
Published: (2025)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
by: Çivril, Ali
Published: (2023)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Two-State Spin Systems with Negative Interactions
by: Fei, Yumou, et al.
Published: (2023)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

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

Corrigendum: PLS is contained in PLC
by: Ishizuka, Takashi
Published: (2023)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)