Skew circuits of small width

DOI10.1007/978-3-319-21398-9_16MaRDI QIDQ3196384zbMATHOpenAlexFDO

Authors Nikhil Balaji, A. Krebs, Nutan Limaye

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

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

Recommendations

• Skew circuits of small width
• scientific article; zbMATH DE number 36617
• Circuits on cylinders
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

Cites work

• scientific article; zbMATH DE number 3353170 (Why is no real title available?)
• scientific article; zbMATH DE number 3197115 (Why is no real title available?)
• An impossibility gap between width-4 and width-5 permutation branching programs
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On approximate majority and probabilistic time

Cited in

(1)

• Skew circuits of small width

This page was built for publication: Skew circuits of small width

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