Imagen de Portada

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bharadwaj, G V Sumukha, Raja, S
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

Deterministic Depth-4 PIT and Normalization
por: Guo, Zeyu, et al.
Publicado: (2025)

Polynomial-Time PIT from (Almost) Necessary Assumptions
por: Andrews, Robert, et al.
Publicado: (2025)

Black-Box PWPP Is Not Turing-Closed
por: Hubáček, Pavel
Publicado: (2026)

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

Are Depth-2 Regular Expressions Hard to Intersect?
por: Ascone, Rocco, et al.
Publicado: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
por: Göös, Mika, et al.
Publicado: (2023)

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

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
por: Garg, Abhibhav, et al.
Publicado: (2025)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
por: Andrews, Robert, et al.
Publicado: (2024)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
por: Shpilka, Amir, et al.
Publicado: (2026)

Thermodynamic Signature of Logical Depth in Quantum Circuits
por: Ibnouhsein, Issam
Publicado: (2025)

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

Black-Box Crypto is Useless for Pseudorandom Codes
por: Garg, Sanjam, et al.
Publicado: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
por: Kumar, Mrinal, et al.
Publicado: (2024)

An Algebraic Rigidity Framework for Order-Oblivious Deterministic Black-Box PIT of ROABPs
por: Singh, Shalender, et al.
Publicado: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
por: Arvind, V., et al.
Publicado: (2023)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
por: Lu, Jiaqi, et al.
Publicado: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
por: Chukhin, Nikolai, et al.
Publicado: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
por: Gryaznov, Svyatoslav, et al.
Publicado: (2024)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
por: Raz, Ran
Publicado: (2026)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
por: Drucker, Andrew, et al.
Publicado: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
por: Rajakumar, Joel, et al.
Publicado: (2024)

Pseudorandom bits for non-commutative programs
por: Lee, Chin Ho, et al.
Publicado: (2025)

Faster Mixing of Higher-Dimensional Random Reversible Circuits
por: Gay, William, et al.
Publicado: (2024)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
por: Xu, Jeff
Publicado: (2024)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
por: Kahanamoku-Meyer, Gregory D., et al.
Publicado: (2024)

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

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
por: Fefferman, Bill, et al.
Publicado: (2024)

Arithmetic Circuits with Division
por: Sacher, Silas Cato
Publicado: (2025)

Satisfiability of commutative vs. non-commutative CSPs
por: Bulatov, Andrei A., et al.
Publicado: (2024)

Random Circuit Sampling: Fourier Expansion and Statistics
por: Kalai, Gil, et al.
Publicado: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
por: Li, Xin, et al.
Publicado: (2024)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
por: Collins, Nathaniel A., et al.
Publicado: (2024)

Compression of Voxelized Vector Field Data by Boxes is Hard
por: Zhang, Simon
Publicado: (2025)

Circuits and Backdoors: Five Shades of the SETH
por: Lampis, Michael
Publicado: (2024)

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

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

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

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

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