On uniform circuit complexity
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3571498 (Why is no real title available?)
- scientific article; zbMATH DE number 3594651 (Why is no real title available?)
- scientific article; zbMATH DE number 3592964 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- A characterization of the power of vector machines
- A unified approach to models of synchronous parallel machines
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Fast Parallel Matrix Inversion Algorithms
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- On Relating Time and Space to Size and Depth
- Parallelism in random access machines
- Pebbling with an auxiliary pushdown
- Relations Among Complexity Measures
- The complexity of the membership problem for some extensions of context-free languagest†
- The network complexity and the Turing machine complexity of finite functions
- The polynomial-time hierarchy
- Time Bounded Random Access Machines with Parallel Processing
- Time-space trade-offs in a pebble game
- Tree-size bounded alternation
Cited in
(only showing first 100 items - show all)- Prediction-preserving reducibility
- Arithmetizing uniform \(NC\)
- Root finding with threshold circuits
- Computing a context-free grammar-generating series
- Expander construction in \(\mathsf{VNC}^1\)
- Rounds versus time for the two person pebble game
- Reductions to graph isomorphism
- Complexity theory for splicing systems
- On the computational power of binary decision diagram with redundant variables.
- The complexity of ranking simple languages
- The equivalence of theories that characterize ALogTime
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- The enumerability of P collapses P to NC
- On the complexity of Szilard languages of regulated grammars
- Relations among parallel and sequential computation models
- Fine-grained cryptography revisited
- Advocating ownership
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- A very hard log-space counting class
- Constructing arrangements optimally in parallel
- Sublinear-time language recognition and decision by one-dimensional cellular automata
- Decompositions of nondeterministic reductions
- Embedding arbitrary Boolean circuits into fungal automata
- Some subclasses of context-free languages in NC^ 1
- Proofs of proximity for context-free languages and read-once branching programs
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Efficient parallel circuits and algorithms for division
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Space-bounded hierarchies and probabilistic computations
- A measure of relativized space which is faithful with respect to depth
- On the complexity of inducing categorical and quantitative association rules
- Multiplication, division, and shift instructions in parallel random access machines
- Bounded arithmetic for NC, ALogTIME, L and NL
- On some derivation mechanisms and the complexity of their Szilard languages
- Nondeterministic NC^1 computation
- Symmetries and the complexity of pure Nash equilibrium
- Evaluation of circuits over nilpotent and polycyclic groups
- Parallel pointer machines
- Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
- Ordered vertex removal and subgraph problems
- Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- On log-time alternating Turing machines of alternation depth k
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On the relative complexity of some languages in \(NC^ 1\)
- Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)
- Function-algebraic characterizations of log and polylog parallel time
- Reductions to Graph Isomorphism
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02
- A Characterization of NC k by First Order Functional Programs
- Local reduction
- Proofs of proximity for context-free languages and read-once branching programs
- Characterizing parallel hierarchies by reducibilities
- Circuits and expressions with nonassociative gates
- Interactive proof systems and alternating time-space complexity
- Reversals and alternation
- The complexity of computing maximal word functions
- Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
- On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
- Rudimentary reductions revisited
- Some results on uniform arithmetic circuit complexity
- On the synchronization of semi-traces
- Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
- Rounds versus time for the two person pebble game (extended abstract)
- Characterizing parallel time by type 2 recursions with polynomial output length
- Computation models and function algebras
- The Computational Complexity of Choice Sets
- Tradeoff lower lounds for stack machines
- On parallel hierarchies and R ki
- Parallel computation with threshold functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A characterization of alternating log time by ramified recurrence
- A note on some languages in uniform \(ACC^ 0\)
- Division in logspace-uniform NC
- The complexity of circuit value and network stability
- Upper bounds on recognition of a hierarchy of non-context-free languages
- Properties that characterize LOGCFL
- Parallel on-line parsing in constant time per word
- Nondeterministics circuits, space complexity and quasigroups
- Logspace verifiers, NC, and NP
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Effective entropies and data compression
- The effective entropies of some extensions of context-free languages
- Some classes of languages in \(NC^ 1\)
- Extensions to Barrington's M-program model
- The complexity of short two-person games
- On the complexity of the clone membership problem
- Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
- Extensional Uniformity for Boolean Circuits
- An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
- On uniformity within \(NC^ 1\)
- Array processing machines: an abstract model
- A recursion-theoretic characterisation of the positive polynomial-time functions
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- Boolean grammars
- On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
- Lower bounds against weakly-uniform threshold circuits
This page was built for publication: On uniform circuit complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1152951)
