Copertina

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Garg, Abhibhav, Oliveira, Rafael, Sengupta, Akash Kumar
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
di: Garg, Abhibhav, et al.
Pubblicazione: (2025)

An Improved Construction of Variety-Evasive Subspace Families
di: Andrews, Robert, et al.
Pubblicazione: (2026)

Hilbert's Nullstellensatz is in the Counting Hierarchy
di: Andrews, Robert, et al.
Pubblicazione: (2026)

An exposition of recent list-size bounds of FRS Codes
di: Garg, Abhibhav, et al.
Pubblicazione: (2025)

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

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

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
di: Bharadwaj, G V Sumukha, et al.
Pubblicazione: (2024)

Lower Bounds for Approximate Sign Rank
di: Bindua, Riju, et al.
Pubblicazione: (2026)

Query Lower Bounds for Correlation Clustering under Memory Constraints
di: Garg, Sumegha, et al.
Pubblicazione: (2026)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
di: Alman, Josh, et al.
Pubblicazione: (2025)

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

Program Synthesis is $Σ_3^0$-Complete
di: Kim, Jinwoo
Pubblicazione: (2024)

Learning depth-3 circuits via quantum agnostic boosting
di: Arunachalam, Srinivasan, et al.
Pubblicazione: (2025)

Newman's theorem via Carathéodory
di: Li, Yaqiao, et al.
Pubblicazione: (2024)

Constant-depth circuits for polynomial GCD over any characteristic
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

Modular composition & polynomial GCD in the border of small, shallow circuits
di: Andrews, Robert, et al.
Pubblicazione: (2025)

New Pseudorandom Generators and Correlation Bounds Using Extractors
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
di: Kothari, Pravesh K., et al.
Pubblicazione: (2024)

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

A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization
di: Harary, Marc
Pubblicazione: (2025)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
di: Kamath, Pritish, et al.
Pubblicazione: (2026)

Hardness of clique approximation for monotone circuits
di: Błasiok, Jarosław, et al.
Pubblicazione: (2025)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
di: Daskin, Ammar
Pubblicazione: (2024)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
di: Ivanov, Sergiu, et al.
Pubblicazione: (2024)

Simple general magnification of circuit lower bounds
di: Atserias, Albert, et al.
Pubblicazione: (2025)

Range Avoidance in Boolean Circuits via Turan-type Bounds
di: Kuntewar, Neha, et al.
Pubblicazione: (2025)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
di: Junchi, Ma, et al.
Pubblicazione: (2024)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
di: Antonelli, Melissa, et al.
Pubblicazione: (2026)

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

The Complexity of Tensor Rank
di: Schaefer, Marcus, et al.
Pubblicazione: (2016)

Strong Inapproximability for a Promise Rank Problem
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2026)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
di: Krokhin, Andrei, et al.
Pubblicazione: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
di: Beniamini, Gal, et al.
Pubblicazione: (2024)

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
di: Chen, Lijie, et al.
Pubblicazione: (2025)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
di: Meir, Or
Pubblicazione: (2023)

Affine Rank Minimization is ER Complete
di: Majumdar, Angshul
Pubblicazione: (2026)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
di: Byramji, Farzan, et al.
Pubblicazione: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

The power of quantum circuits in sampling
di: Blanc, Guy, et al.
Pubblicazione: (2025)