Imagen de Portada

Simple general magnification of circuit lower bounds

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Atserias, Albert, Müller, Moritz
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

From Gödel incompleteness to the consistency of circuit lower bounds
por: Atserias, Albert, et al.
Publicado: (2026)

Hard Clique Formulas for Resolution
por: Atserias, Albert
Publicado: (2026)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
por: Atserias, Albert, et al.
Publicado: (2024)

Quantum circuit lower bounds in the magic hierarchy
por: Parham, Natalie
Publicado: (2025)

The Proof Analysis Problem
por: Arteche, Noel, et al.
Publicado: (2025)

Exponential lower bound via exponential sums
por: Bhattacharjee, Somnath, et al.
Publicado: (2026)

Depth lower bounds in Stabbing Planes for combinatorial principles
por: Dantchev, Stefan, et al.
Publicado: (2021)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
por: Goubault-Larrecq, Aliénor, et al.
Publicado: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
por: Gordeev, Lev, et al.
Publicado: (2026)

On the consistency of stronger lower bounds for NEXP
por: Thapen, Neil
Publicado: (2025)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
por: Wu, Hao
Publicado: (2024)

Optimising quantum circuits is generally hard
por: van de Wetering, John, et al.
Publicado: (2023)

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

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
por: Agarwal, Avantika, et al.
Publicado: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
por: Ron-Zewi, Noga, et al.
Publicado: (2024)

A quasi-optimal lower bound for skew polynomial multiplication
por: Chen, Qiyuan, et al.
Publicado: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
por: Geniet, Colin, et al.
Publicado: (2026)

A note on quantum lower bounds for local search via congestion and expansion
por: Brânzei, Simina, et al.
Publicado: (2024)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

Clifford testing: algorithms and lower bounds
por: Hinsche, Marcel, et al.
Publicado: (2025)

Optimal lower bounds for quantum state tomography
por: Scharnhorst, Thilo, et al.
Publicado: (2025)

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

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
por: Hsieh, Min-Hsiu, et al.
Publicado: (2024)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)

Rice-like complexity lower bounds for Boolean and uniform automata networks
por: Goubault-Larrecq, Aliénor, et al.
Publicado: (2024)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
por: Chen, Zitan
Publicado: (2023)

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

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

An unconditional lower bound for the active-set method on the hypercube
por: Disser, Yann, et al.
Publicado: (2025)

On the Complexity of Target Set Selection in Simple Geometric Networks
por: Dvořák, Michal, et al.
Publicado: (2023)

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

IQP circuits for 2-Forrelation
por: Buzet, Quentin, et al.
Publicado: (2026)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
por: Lichter, Moritz, et al.
Publicado: (2024)

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

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

Complexity and hardness of random peaked circuits
por: Zhang, Yuxuan
Publicado: (2025)

Fast simulation of planar Clifford circuits
por: Gosset, David, et al.
Publicado: (2020)

Incompressibility and spectral gaps of random circuits
por: Chen, Chi-Fang, et al.
Publicado: (2024)

On estimating the entropy of shallow circuit outputs
por: Gheorghiu, Alexandru, et al.
Publicado: (2020)

An unconditional lower bound for the active-set method in convex quadratic maximization
por: Bach, Eleon, et al.
Publicado: (2025)