Emptiness Problems for Integer Circuits

DOI10.4230/LIPIcs.MFCS.2017.33zbMath1441.68064OpenAlexW2775642327MaRDI QIDQ5111247

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

Publication date: 26 May 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2017.html#BarthBDGMT17

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)

Related Items (5)

A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction ⋮ Emptiness problems for integer circuits ⋮ Unnamed Item ⋮ Emptiness Problems for Integer Circuits ⋮ Balance problems for integer circuits

Cites Work

• 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 computational complexity of logical theories
• 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
• Progress on Polynomial Identity Testing-II
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Arithmetic Circuits: A survey of recent results and open questions
• Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
• Functions Definable by Arithmetic Circuits
• 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
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• 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