Skew Circuits of Small Width

DOI10.1007/978-3-319-21398-9_16zbMath1465.68074OpenAlexW1201042245MaRDI QIDQ3196384

Nikhil Balaji, Nutan Limaye, Andreas Krebs

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://ora.ox.ac.uk/objects/uuid:8eae127f-8bde-41f3-a1ec-bebe2f154d8d

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On approximate majority and probabilistic time
• An impossibility gap between width-4 and width-5 permutation branching programs
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs

This page was built for publication: Skew Circuits of Small Width