Cover Image

Condensing and Extracting Against Online Adversaries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chattopadhyay, Eshan, Gurumukhani, Mohit, Ringach, Noam, Servedio, Rocco
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity 68Q87 F.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

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

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Analysis of multivariate symbol statistics in primitive rational models
by: Goldwurm, Massimiliano, et al.
Published: (2026)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
by: Koiran, Pascal, et al.
Published: (2022)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Graded Monad Coalgebras for Continuous-Time Transition Systems
by: Di Lavore, Elena, et al.
Published: (2026)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by: Filmus, Yuval, et al.
Published: (2020)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

A study of distributional complexity measures for Boolean functions
by: Köhler-Schindler, Laurin, et al.
Published: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)