Unifying lower bounds for algebraic machines, semantically

DOI10.1016/j.ic.2024.105232MaRDI QIDQ6647768

Ulysse Léchine, Luc Pellissier, Thomas Seiller

Publication date: 3 December 2024

Published in: Information and Computation (Search for Journal in Brave)

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interaction graphs: graphings
• The maximum flow problem is log space complete for P
• Specified precision polynomial root isolation is in NC
• Topological entropy for noncompact spaces
• \(\ell^2\) invariants of equivalence relations and groups
• Cost of equivalence relations and groups
• Algebrization
• Nonuniform ACC Circuit Lower Bounds
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• Trees and amenable equivalence relations
• Computational complexity of parametric linear programming
• Lower bounds for algebraic decision trees
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Lower Bounds in a Parallel Model without Bit Operations
• Interaction Graphs
• Interaction Graphs
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Implementing geometric complexity theory: on the separation of orbit closures via symmetries
• Topological Entropy
• Paths, Trees, and Flowers
• The Product Theorem for Topological Entropy
• The complexity of theorem-proving procedures
• On the Betti Numbers of Real Varieties
• Natural proofs
• Decision tree complexity and Betti numbers

This page was built for publication: Unifying lower bounds for algebraic machines, semantically