Skew circuits of small width
DOI10.1016/J.TCS.2017.03.013zbMATH Open1433.68136OpenAlexW2602492787MaRDI QIDQ2173307FDOQ2173307
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
Recommendations
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)
Cites Work
- Word Problems Solvable in Logspace
- Boolean function complexity. Advances and frontiers.
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Characterizing Valiant's algebraic complexity classes
- Parity, circuits, and the polynomial-time hierarchy
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for Width Two Branching Programs
- On Relating Time and Space to Size and Depth
- Finite monoids and the fine structure of NC 1
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Log Depth Circuits for Division and Related Problems
- Title not available (Why is that?)
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Title not available (Why is that?)
- On approximate majority and probabilistic time
- Nonuniform ACC circuit lower bounds
- Circuit Definitions of Nondeterministic Complexity Classes
- An impossibility gap between width-4 and width-5 permutation branching programs
Cited In (1)
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)
