Buchumschlag

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Goubault-Larrecq, Aliénor, Perrot, Kévin
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

Hardness of monadic second-order formulae over succinct graphs
von: Gamard, Guilhem, et al.
Veröffentlicht: (2023)

Directed st-connectivity with few paths is in quantum logspace
von: Apers, Simon, et al.
Veröffentlicht: (2024)

Complexity of Boolean automata networks under block-parallel update modes
von: Perrot, Kévin, et al.
Veröffentlicht: (2024)

Simple general magnification of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2025)

Exponential lower bound via exponential sums
von: Bhattacharjee, Somnath, et al.
Veröffentlicht: (2026)

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

Lower bounds for planar Arithmetic Circuits
von: Ramya, C., et al.
Veröffentlicht: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
von: Dantchev, Stefan, et al.
Veröffentlicht: (2021)

Timed Prediction Problem for Sandpile Models
von: Concha-Vega, Pablo, et al.
Veröffentlicht: (2025)

Just Previsions
von: Goubault-Larrecq, Jean
Veröffentlicht: (2026)

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

Semitopological Barycentric Algebras
von: Goubault-Larrecq, Jean
Veröffentlicht: (2025)

Quantum circuit lower bounds in the magic hierarchy
von: Parham, Natalie
Veröffentlicht: (2025)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
von: Concha-Vega, Pablo, et al.
Veröffentlicht: (2025)

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

Distributing Retractions, Weak Distributive Laws and Applications to Monads of Hyperspaces, Continuous Valuations and Measures
von: Goubault-Larrecq, Jean
Veröffentlicht: (2025)

Weak Distributive Laws between Monads of Continuous Valuations and of Non-Deterministic Choice
von: Goubault-Larrecq, Jean
Veröffentlicht: (2024)

Isomorphism Theorems between Models of Mixed Choice (Revised)
von: Goubault-Larrecq, Jean
Veröffentlicht: (2024)

On the Dynamics of Bounded-Degree Automata Networks
von: Aracena, Julio, et al.
Veröffentlicht: (2025)

Computational lower bounds for multi-frequency group synchronization
von: Kireeva, Anastasia, et al.
Veröffentlicht: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
von: Agarwal, Avantika, et al.
Veröffentlicht: (2024)

A quasi-optimal lower bound for skew polynomial multiplication
von: Chen, Qiyuan, et al.
Veröffentlicht: (2024)

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

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Clifford testing: algorithms and lower bounds
von: Hinsche, Marcel, et al.
Veröffentlicht: (2025)

Space-bounded online Kolmogorov complexity is additive
von: Bauwens, Bruno, et al.
Veröffentlicht: (2025)

On the complexity of freezing automata networks of bounded pathwidth
von: Goles, Eric, et al.
Veröffentlicht: (2025)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
von: Chen, Zherui, et al.
Veröffentlicht: (2024)

Optimal lower bounds for quantum state tomography
von: Scharnhorst, Thilo, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

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

Arithmetic Circuits with Division
von: Sacher, Silas Cato
Veröffentlicht: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

A universal bound on the space complexity of Directed Acyclic Graph computations
von: Bilardi, Gianfranco, et al.
Veröffentlicht: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Stone Duality for Preordered Topological Spaces
von: Goubault-Larrecq, Jean
Veröffentlicht: (2026)

On the Preservation of Projective Limits by Functors of Non-Deterministic, Probabilistic, and Mixed Choice
von: Goubault-Larrecq, Jean
Veröffentlicht: (2024)