Emptiness problems for integer circuits

DOI10.4230/LIPICS.MFCS.2017.33zbMATH Open1441.68064OpenAlexW2775642327MaRDI QIDQ5111247FDOQ5111247

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

Recommendations

• Emptiness problems for integer circuits
• The complexity of membership problems for circuits over sets of integers
• Mathematical Foundations of Computer Science 2004
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• The complexity of membership problems for circuits over sets of natural numbers

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Decision Procedure for the First Order Theory of Real Addition with Order
• The decision problem for exponential diophantine equations
• PRIMES is in P
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of membership problems for circuits over sets of natural numbers
• The difference and truth-table hierarchies for NP
• The complexity of membership problems for circuits over sets of integers
• Arithmetic Circuits: A survey of recent results and open questions
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Relationships among $PL$, $\#L$, and the determinant
• Title not available (Why is that?)
• The computational complexity of logical theories
• Progress on Polynomial Identity Testing - II
• Title not available (Why is that?)
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Integer circuit evaluation is PSPACE-complete
• Title not available (Why is that?)
• Equivalence problems for circuits over sets of natural numbers
• Satisfiability of algebraic circuits over sets of natural numbers
• Progress on Polynomial Identity Testing-II
• Dominoes and the complexity of subclasses of logical theories
• Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
• Functions Definable by Arithmetic Circuits
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Title not available (Why is that?)
• Emptiness Problems for Integer Circuits

Cited In (5)

• Title not available (Why is that?)
• Emptiness Problems for Integer Circuits
• A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction
• Balance problems for integer circuits
• Emptiness problems for integer circuits

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111247)