:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Kamath, Pritish, Kumar, Ravi, Manurangsi, Pasin
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2604.06590
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

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

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

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

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

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

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

Computational Hardness of Private Coreset
di: Ghazi, Badih, et al.
Pubblicazione: (2026)

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

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

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

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

The Price of Justified Representation
di: Elkind, Edith, et al.
Pubblicazione: (2021)

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

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

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

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

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

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

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

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

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

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

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

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

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Scalable DP-SGD: Shuffling vs. Poisson Subsampling
di: Chua, Lynn, et al.
Pubblicazione: (2024)

PREM: Privately Answering Statistical Queries with Relative Error
di: Ghazi, Badih, et al.
Pubblicazione: (2025)

How Private are DP-SGD Implementations?
di: Chua, Lynn, et al.
Pubblicazione: (2024)

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

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

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

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

Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning
di: Chua, Lynn, et al.
Pubblicazione: (2024)

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

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

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

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

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

Recovery Reductions, Conjectures, and Barriers
di: Nareddy, Tejas, et al.
Pubblicazione: (2025)