Imagen de Portada

Average-Case Reductions for $k$-XOR and Tensor PCA

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bresler, Guy, Harbuzova, Alina
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity Cryptography and Security Probability Statistics Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
por: Bresler, Guy, et al.
Publicado: (2025)

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
por: Bangachev, Kiril, et al.
Publicado: (2024)

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

Pseudorandom Permutations from Random Reversible Circuits
por: He, William, et al.
Publicado: (2024)

Cryptographic Hardness of Score Estimation
por: Song, Min Jae
Publicado: (2024)

Private measures, random walks, and synthetic data
por: Boedihardjo, March, et al.
Publicado: (2022)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
por: Fu, Daniel, et al.
Publicado: (2026)

Infinitely divisible privacy and beyond I: resolution of the $s^2=2k$ conjecture
por: Pandey, Aaradhya, et al.
Publicado: (2025)

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
por: Herman, Tal, et al.
Publicado: (2024)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
por: Lou, Mengqi, et al.
Publicado: (2025)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
por: R., Abhishek Hegade K., et al.
Publicado: (2025)

An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
por: Düngler, Johanna, et al.
Publicado: (2025)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
por: Gamarnik, David, et al.
Publicado: (2023)

Computational lower bounds for multi-frequency group synchronization
por: Kireeva, Anastasia, et al.
Publicado: (2024)

Fast computational deep thermalization
por: Chakraborty, Shantanav, et al.
Publicado: (2025)

More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
por: Gretta, Lucas, et al.
Publicado: (2024)

Nearly-Linear Time Seeded Extractors with Short Seeds
por: Doron, Dean, et al.
Publicado: (2024)

Graph Quasirandomness for Hypothesis Testing of Stochastic Block Models
por: Bangachev, Kiril, et al.
Publicado: (2025)

Tensor cumulants for statistical inference on invariant distributions
por: Kunisky, Dmitriy, et al.
Publicado: (2024)

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

Secret Sharing on Superconcentrator
por: Li, Yuan
Publicado: (2023)

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
por: Bangachev, Kiril, et al.
Publicado: (2024)

Symmetric Perceptrons, Number Partitioning and Lattices
por: Vafa, Neekon, et al.
Publicado: (2025)

Safety Analysis in the NGAC Model
por: Tan, Brian, et al.
Publicado: (2025)

Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents
por: Brice, Léonard, et al.
Publicado: (2024)

Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
por: Bresler, Guy, et al.
Publicado: (2025)

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
por: Bangachev, Kiril, et al.
Publicado: (2024)

The computational two-way quantum capacity
por: Meyer, Johannes Jakob, et al.
Publicado: (2026)

Computational relative entropy
por: Meyer, Johannes Jakob, et al.
Publicado: (2025)

Generalized one-way function and its application
por: Yin, Hua-Lei
Publicado: (2024)

Hardness Amplification for (Sparse) LPN
por: Aggarwal, Divesh, et al.
Publicado: (2026)

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code
por: Leverett, Eireann, et al.
Publicado: (2026)

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
por: Otsuji, Taisei, et al.
Publicado: (2026)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
por: Bhattiprolu, Vijay, et al.
Publicado: (2024)

New constructions of pseudorandom codes
por: Ghentiyala, Surendra, et al.
Publicado: (2024)

Leakage-Resilient Extractors against Number-on-Forehead Protocols
por: Chattopadhyay, Eshan, et al.
Publicado: (2025)

Efficient derandomization of differentially private counting queries
por: Ghentiyala, Surendra
Publicado: (2025)

Characterizing the Distinguishability of Product Distributions through Multicalibration
por: Marcussen, Cassandra, et al.
Publicado: (2024)

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
por: Ren, Hanlin, et al.
Publicado: (2025)

Differentially Private Compression and the Sensitivity of LZ77
por: Blocki, Jeremiah, et al.
Publicado: (2025)