Cover Image

Symmetric Distributions from Shallow Circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kane, Daniel M., Ostuni, Anthony, Wu, Kewen
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Locally Sampleable Uniform Symmetric Distributions
by: Kane, Daniel M., et al.
Published: (2024)

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

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

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

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

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

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

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

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

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

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

Classical Simulability of Quantum Circuits with Shallow Magic Depth
by: Zhang, Yifan, et al.
Published: (2024)

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
by: Grilo, Alex Bredariol, et al.
Published: (2024)

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

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

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

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

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

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
by: Zhang, Zhihan, et al.
Published: (2024)

Learning and Generating Mixed States Prepared by Shallow Channel Circuits
by: Hu, Fangjun, et al.
Published: (2026)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

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

Optimal Depth-Three Circuits for Inner Product
by: Gurumukhani, Mohit, et al.
Published: (2026)

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

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

Arithmetic Circuits with Division
by: Sacher, Silas Cato
Published: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

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

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

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Simple Circuit Extensions for XOR in PTIME
by: Carmosino, Marco, et al.
Published: (2025)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

Circuits and Backdoors: Five Shades of the SETH
by: Lampis, Michael
Published: (2024)

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

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)