Skew circuits of small width

DOI10.1016/J.TCS.2017.03.013MaRDI QIDQ2173307zbMATHOpenAlexFDO

Authors Nikhil Balaji, A. Krebs, Nutan Limaye

Publication date 22 April 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsparitybranching programsBarrington's theoremskew circuits

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
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 36617
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• scientific article; zbMATH DE number 4047115

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
• Boolean function complexity. Advances and frontiers.
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Characterizing Valiant's algebraic complexity classes
• Circuit Definitions of Nondeterministic Complexity Classes
• Finite monoids and the fine structure of NC ¹
• Log Depth Circuits for Division and Related Problems
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nonuniform ACC circuit lower bounds
• On Relating Time and Space to Size and Depth
• On approximate majority and probabilistic time
• Parity, circuits, and the polynomial-time hierarchy
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Word Problems Solvable in Logspace

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 Q2173307)