Separating OR, SUM, and XOR circuits

DOI10.1016/j.jcss.2016.01.001zbMath1338.68102arXiv1304.0513OpenAlexW1650093283WikidataQ42264471 ScholiaQ42264471MaRDI QIDQ269494

Mika Göös, Matti Järvisalo, Petteri Kaski, Janne H. Korhonen, Mikko Koivisto, Magnus Gausdal Find

Publication date: 18 April 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.0513

zbMATH Keywords

rewritingBoolean arithmeticarithmetic circuitsidempotent arithmeticmonotone separations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Some remarks on Boolean sums
• On another Boolean matrix
• Which problems have strongly exponential complexity?
• Logic minimization techniques with applications to cryptology
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Norm-graphs and bipartite Turán numbers
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Cancellation-Free Circuits in Unbounded and Bounded Depth
• Finding Efficient Circuits for Ensemble Computation
• Linear Circuits over $\operatorname{GF}(2)$
• The Complexity of Satisfiability of Small Depth Circuits
• On the Evaluation of Powers and Monomials
• Communication Complexity
• Complexity of Linear Boolean Operators
• Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
• On the complexity of \(k\)-SAT