Imagen de Portada

Locally Sampleable Uniform Symmetric Distributions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kane, Daniel M., Ostuni, Anthony, Wu, Kewen
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Symmetric Distributions from Shallow Circuits
por: Kane, Daniel M., et al.
Publicado: (2025)

Locality Bounds for Sampling Hamming Slices
por: Kane, Daniel M., et al.
Publicado: (2024)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
por: Grier, Daniel, et al.
Publicado: (2025)

Hard-to-Sample Distributions from Robust Extractors
por: Byramji, Farzan, et al.
Publicado: (2026)

On the Advantage of Adaptivity for Sampling with Cell Probes
por: Byramji, Farzan, et al.
Publicado: (2026)

Corners in Quasirandom Groups via Sparse Mixing
por: Jaber, Michael, et al.
Publicado: (2024)

Refuting approaches to the log-rank conjecture for XOR functions
por: Hatami, Hamed, et al.
Publicado: (2023)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
por: Grier, Daniel, et al.
Publicado: (2026)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
por: Guruswami, Venkatesan, et al.
Publicado: (2025)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
por: Li, Zeyong
Publicado: (2023)

Quasipolynomial bounds for the corners theorem
por: Jaber, Michael, et al.
Publicado: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

(Sub)Exponential Quantum Speedup for Optimization
por: Leng, Jiaqi, et al.
Publicado: (2025)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
por: Hitchcock, John M.
Publicado: (2026)

Symmetric Algebraic Circuits and Homomorphism Polynomials
por: Dawar, Anuj, et al.
Publicado: (2025)

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

Computing the Elementary Symmetric Polynomials in Positive Characteristics
por: Orzel, Ian
Publicado: (2025)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
por: Agarwal, Sanyam, et al.
Publicado: (2026)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
por: Bortolotti, Alex, et al.
Publicado: (2025)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
por: Aivasiliotis, Panagiotis, et al.
Publicado: (2025)

Symmetric quantum computation
por: Castro-Silva, Davi, et al.
Publicado: (2025)

Upper Bounds for Symmetric Approximate Bounded Indistinguishability
por: Williamson, Christopher
Publicado: (2026)

Rigorous Implications of the Low-Degree Heuristic
por: Hsieh, Jun-Ting, et al.
Publicado: (2026)

Towards Uniform Certification in QBF
por: Chew, Leroy, et al.
Publicado: (2022)

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

Symmetric Proofs in the Ideal Proof System
por: Dawar, Anuj, et al.
Publicado: (2025)

Uniformity within Parameterized Circuit Classes
por: Hegeman, Steef, et al.
Publicado: (2025)

Optimal Lower Bounds for Symmetric Modular Circuits
por: Pago, Benedikt
Publicado: (2026)

The Optimal Approximation Factor in Density Estimation
por: Bousquet, Olivier, et al.
Publicado: (2019)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
por: Ghosh, Abheek, et al.
Publicado: (2024)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
por: Barto, Libor, et al.
Publicado: (2026)

Relaxed Local Correctability from Local Testing
por: Kumar, Vinayak M., et al.
Publicado: (2023)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
por: Grigorescu, Elena, et al.
Publicado: (2025)

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

Spectral Lower Bounds for Local Search
por: Brânzei, Simina, et al.
Publicado: (2024)

Distribution-Free Proofs of Proximity
por: Aaronson, Hugo, et al.
Publicado: (2023)

Hypercontractivity on HDX II: Symmetrization and q-Norms
por: Hopkins, Max
Publicado: (2024)

Parameterized Algorithms for Editing to Uniform Cluster Graph
por: Gaikwad, Ajinkya, et al.
Publicado: (2024)

Parameterized Local Search for Max $c$-Cut
por: Garvardt, Jaroslav, et al.
Publicado: (2024)

Research on Combat Mission Configuration of Unmanned Aerial Vehicle Maritime Reconnaissance Based on Particle Swarm Optimization Algorithm
por: Peng Dong, et al.
Publicado: (2024)