Copertina

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Guruswami, Venkatesan, Lyu, Xin, Yuan, Weiqiang
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Cryptography and Security Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Perfect Zero-Knowledge PCPs for #P
di: Gur, Tom, et al.
Pubblicazione: (2024)

Mind the Gap? Not for SVP Hardness under ETH!
di: Aggarwal, Divesh, et al.
Pubblicazione: (2025)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
di: Dolev, Shlomi
Pubblicazione: (2025)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
di: Kumar, Rajendra, et al.
Pubblicazione: (2018)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
di: Bennett, Huck, et al.
Pubblicazione: (2021)

The Planted Orthogonal Vectors Problem
di: Kühnemann, David, et al.
Pubblicazione: (2025)

On the instance optimality of detecting collisions and subgraphs
di: Ben-Eliezer, Omri, et al.
Pubblicazione: (2023)

The Price of Privacy For Approximating Max-CSP
di: Dharangutte, Prathamesh, et al.
Pubblicazione: (2026)

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
di: Lyu, Xin, et al.
Pubblicazione: (2024)

Average-Case Complexity of Quantum Stabilizer Decoding
di: Khesin, Andrey Boris, et al.
Pubblicazione: (2025)

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

Improved Lower Bound for Differentially Private Facility Location
di: Manurangsi, Pasin
Pubblicazione: (2024)

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

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

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
di: Ko, Young Kun
Pubblicazione: (2025)

Privately Estimating Black-Box Statistics
di: Steinke, Günter F., et al.
Pubblicazione: (2025)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
di: Golowich, Noah, et al.
Pubblicazione: (2024)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
di: Kothari, Robin, et al.
Pubblicazione: (2025)

The NISQ Complexity of Collision Finding
di: Hamoudi, Yassine, et al.
Pubblicazione: (2022)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
di: Dvijotham, Krishnamurthy, et al.
Pubblicazione: (2024)

InstaHide's Sample Complexity When Mixing Two Private Images
di: Huang, Baihe, et al.
Pubblicazione: (2020)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

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

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
di: Peter, Naty, et al.
Pubblicazione: (2023)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
di: Aggarwal, Divesh, et al.
Pubblicazione: (2020)

Private Learning of Littlestone Classes, Revisited
di: Lyu, Xin
Pubblicazione: (2025)

Private Synthetic Data Generation in Bounded Memory
di: Holland, Rayne, et al.
Pubblicazione: (2024)

Invertible Bloom Lookup Tables with Less Memory and Randomness
di: Fleischhacker, Nils, et al.
Pubblicazione: (2023)

Local Node Differential Privacy
di: Raskhodnikova, Sofya, et al.
Pubblicazione: (2026)

Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
di: Portella, Victor S., et al.
Pubblicazione: (2024)

Triangle Counting with Local Edge Differential Privacy
di: Eden, Talya, et al.
Pubblicazione: (2023)

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

High-Probability Bounds For Heterogeneous Local Differential Privacy
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2025)

Streaming approximation resistance of every ordering CSP
di: Singer, Noah G., et al.
Pubblicazione: (2021)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
di: Hillebrand, Quentin, et al.
Pubblicazione: (2024)

A Differentially Private Clustering Algorithm for Well-Clustered Graphs
di: He, Weiqiang, et al.
Pubblicazione: (2024)