Constant Depth Reducibility
From MaRDI portal
Recommendations
- Computational depth and reducibility
- Computational depth and reducibility
- Relating polynomial time to constant depth
- The isomorphism conjecture for constant depth reductions
- Publication:4934278
- Mathematical Foundations of Computer Science 2004
- A reducibility for the dot-depth hierarchy
- On the consistency of depth functionals
- Depth and Toomer's invariant
- Intrinsic Reducibilities
Cited in
(91)- Symmetries and the complexity of pure Nash equilibrium
- Bounded-depth, polynomial-size circuits for symmetric functions
- One-way functions and circuit complexity
- Limits on the power of concurrent-write parallel machines
- Parallel computation with threshold functions
- Efficient parallel circuits and algorithms for division
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On the relative complexity of some languages in \(NC^ 1\)
- On the computational efficiency of symmetric neural networks
- Linear-size constant-depth polylog-threshold circuits
- Some notes on threshold circuits, and multiplication in depth 4
- The complexity of the parity function in unbounded fan-in, unbounded depth circuits
- An arithmetic model of computation equivalent to threshold circuits
- Learning in parallel
- The graph of multiplication is equivalent to counting
- The invariant problem for binary string structures and the parallel complexity theory of queries
- Regular languages in \(NC\)
- Multiplication, division, and shift instructions in parallel random access machines
- The complexity of computing symmetric functions using threshold circuits
- Circuit depth relative to a random oracle
- Computing with discrete multi-valued neurons
- Extensions to Barrington's M-program model
- Threshold circuits of small majority-depth
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- The complexity of computing maximal word functions
- Analog computation via neural networks
- On ACC
- A note on neural sorting networks with O(1) time complexity
- Queries with arithmetical constraints
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- On the relative power of reduction notions in arithmetic circuit complexity
- A frame for general divide-and-conquer recurrences
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- The complexity of planarity testing
- A note on logspace optimization
- Designing checkers for programs that run in parallel
- New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust
- Equivalence classes and conditional hardness in massively parallel computations
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- Threshold circuits of bounded depth
- Parallelizing time with polynomial circuits
- A note on some languages in uniform \(ACC^ 0\)
- On uniformity within \(NC^ 1\)
- The complexity of searching implicit graphs
- Parity, circuits, and the polynomial-time hierarchy
- The Computational Complexity of Choice Sets
- Extensions of an idea of McNaughton
- scientific article; zbMATH DE number 3936520 (Why is no real title available?)
- Parallel complexity of algebraic operations
- Some results on uniform arithmetic circuit complexity
- Faster all-pairs shortest paths via circuit complexity
- The complexity of searching succinctly represented graphs
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- scientific article; zbMATH DE number 7359421 (Why is no real title available?)
- From circuit complexity to faster all-pairs shortest paths
- The complexity class θp2: Recent results and applications in AI and modal logic
- On small depth threshold circuits
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- Does looking inside a circuit help?
- Correctness of linear logic proof structures is NL-complete
- Feasible Depth
- Counting classes: Thresholds, parity, mods, and fewness
- A lower bound for primality
- On the complexity of some problems on groups input as multiplication tables
- On the coincidence of complexity classes BPC and \(\text{TC}^0 \)
- The isomorphism conjecture for constant depth reductions
- On the parallel parameterized complexity of MaxSAT variants
- Circuit complexity before the dawn of the new millennium
- Computationally hard problems for logic programs under answer set semantics
- The expressiveness of a family of finite set languages
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Computing functions with parallel queries to NP
- Methods for proving completeness via logical reductions
- On the power of small-depth threshold circuits
- The \(\text{AC}^0\)-complexity of visibly pushdown languages
- Root finding with threshold circuits
- A new minimax theorem for randomized algorithms
- The descriptive complexity of graph neural networks
- \#SAT-algorithms for classes of threshold circuits based on probabilistic rank
- A first-principles theory of slow thinking and active perception
- The \(\mathsf{AC}^0\)-complexity of visibly pushdown languages
- The exact complexity of projective image matching
- In-place algorithms for computing a largest clique in geometric intersection graphs
- Non-uniform automata over groups
- The parallel complexity of two problems on concurrency
- The binary network flow problem is logspace complete for P
- Polynomial size \(\Omega\)-branching programs and their computational power
- The complexity of propositional implication
This page was built for publication: Constant Depth Reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3325043)
