Copertina

The Planted Orthogonal Vectors Problem

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kühnemann, David, Polak, Adam, Rosen, Alon
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

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

Low-degree Security of the Planted Random Subgraph Problem
di: Bogdanov, Andrej, 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)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

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

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

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

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

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
di: Hu, Bingbing, et al.
Pubblicazione: (2024)

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

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

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

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

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)

Online Orthogonal Vectors Revisited
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
di: Alman, Josh, et al.
Pubblicazione: (2025)

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

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
di: Bogdanov, Andrej, et al.
Pubblicazione: (2025)

Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication
di: Mutluergil, Kemal, et al.
Pubblicazione: (2026)

Fine-Grained Privacy Guarantees for Coverage Problems
di: Dhulipala, Laxman, et al.
Pubblicazione: (2024)

Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy
di: Dong, Wei, et al.
Pubblicazione: (2024)

Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
di: Jain, Palak, et al.
Pubblicazione: (2024)

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

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

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

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

Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
di: Jain, Palak, et al.
Pubblicazione: (2023)

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

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)

On optimal distinguishers for Planted Clique
di: Nagda, Ansh, et al.
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Decentralized Privacy Preservation for Critical Connections in Graphs
di: Li, Conggai, et al.
Pubblicazione: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
di: Garg, Sumegha, et al.
Pubblicazione: (2026)

PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
di: Asi, Hilal, et al.
Pubblicazione: (2025)

A Classical Quadratic Speedup for Planted $k$XOR
di: Gupta, Meghal, et al.
Pubblicazione: (2025)

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