Cover Image

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kamath, Pritish, Kumar, Ravi, Manurangsi, Pasin
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 Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
by: Epasto, Alessandro, et al.
Published: (2026)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Perfect sampling from rapidly mixing Markov chains
by: Göbel, Andreas, et al.
Published: (2024)

Tight Lower Bound for Multicolor Discrepancy
by: Manurangsi, Pasin, et al.
Published: (2025)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
by: Li, Zihan, et al.
Published: (2024)

Computational Hardness of Private Coreset
by: Ghazi, Badih, et al.
Published: (2026)

Denoising the US Census: Succinct Block Hierarchical Regression
by: Ghazi, Badih, et al.
Published: (2026)

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
by: Ghazi, Badih, et al.
Published: (2024)

Differentially Private Optimization with Sparse Gradients
by: Ghazi, Badih, et al.
Published: (2024)

On Computing Pairwise Statistics with Local Differential Privacy
by: Ghazi, Badih, et al.
Published: (2024)

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

Tight Lower Bounds for Block-Structured Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2024)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

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

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

Tight Fine-Grained Bounds for Direct Access on Join Queries
by: Bringmann, Karl, et al.
Published: (2022)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
by: Biswas, Aniruddha, et al.
Published: (2022)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

The Price of Justified Representation
by: Elkind, Edith, et al.
Published: (2021)

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

Private Hyperparameter Tuning with Ex-Post Guarantee
by: Ghazi, Badih, et al.
Published: (2025)

On Convex Optimization with Semi-Sensitive Features
by: Ghazi, Badih, et al.
Published: (2024)

How Unique is Whose Web Browser? The role of demographics in browser fingerprinting among US users
by: Berke, Alex, et al.
Published: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Recovery Reductions, Conjectures, and Barriers
by: Nareddy, Tejas, et al.
Published: (2025)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
by: Bhattacharya, Sreejata Kishor
Published: (2024)

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

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

Crosslingual Capabilities and Knowledge Barriers in Multilingual Large Language Models
by: Chua, Lynn, et al.
Published: (2024)