Emptiness problems for integer circuits

DOI10.1016/j.tcs.2020.03.023zbMath1441.68063OpenAlexW3016356945MaRDI QIDQ2182324

Dominik Barth, Christian Glaßer, Marc Technau, Titus Dose, Moritz Beck, Larissa Michler

Publication date: 23 May 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8064/

zbMATH Keywords

computational complexitypolynomial identity testinginteger expressionsinteger circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of membership problems for circuits over sets of integers
• Satisfiability of algebraic circuits over sets of natural numbers
• Dominoes and the complexity of subclasses of logical theories
• The decision problem for exponential diophantine equations
• The complexity of logical theories
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• The computational complexity of logical theories
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• PRIMES is in P
• Equivalence problems for circuits over sets of natural numbers
• The complexity of membership problems for circuits over sets of natural numbers
• Arithmetic Circuits: A survey of recent results and open questions
• Functions Definable by Arithmetic Circuits
• On the Complexity of Numerical Analysis
• Progress on Polynomial Identity Testing - II
• The difference and truth-table hierarchies for NP
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Relativization of questions about log space computability
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Parallel identity testing for skew circuits with big powers and applications
• Relationships among $PL$, $\#L$, and the determinant
• Emptiness Problems for Integer Circuits
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Integer circuit evaluation is PSPACE-complete

This page was built for publication: Emptiness problems for integer circuits