On uniform circuit complexity
From MaRDI portal
Cites work
- 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
- 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?)
- 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)- Symmetries and the complexity of pure Nash equilibrium
- Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
- Space-bounded hierarchies and probabilistic computations
- Speedups of deterministic machines by synchronous parallel machines
- Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity
- Array processing machines: an abstract model
- On nondeterminism in parallel computation
- Parallel computation with threshold functions
- An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
- Decompositions of nondeterministic reductions
- Some subclasses of context-free languages in NC^ 1
- Efficient parallel circuits and algorithms for division
- A measure of relativized space which is faithful with respect to depth
- Subtree isomorphism is NC reducible to bipartite perfect matching
- Complexity theory of parallel time and hardware
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- On the relative complexity of some languages in \(NC^ 1\)
- The complexity of short two-person games
- Properties that characterize LOGCFL
- Arithmetizing uniform NC
- The complexity of computing the number of strings of given length in context-free languages
- Characterizing parallel hierarchies by reducibilities
- Rudimentary reductions revisited
- Expected parallel time and sequential space complexity of graph and digraph problems
- A model classifying algorithms as inherently sequential with applications to graph searching
- On the theory of average case complexity
- The complexity of circuit value and network stability
- Bounded arithmetic for NC, ALogTIME, L and NL
- A survey of space complexity
- Multiplication, division, and shift instructions in parallel random access machines
- Upper bounds on recognition of a hierarchy of non-context-free languages
- On iterated integer product
- A very hard log-space counting class
- Extensions to Barrington's M-program model
- Unambiguity of circuits
- On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Nondeterministic NC^1 computation
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- Parallel on-line parsing in constant time per word
- Nondeterministics circuits, space complexity and quasigroups
- The complexity of computing maximal word functions
- Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines
- Function-algebraic characterizations of log and polylog parallel time
- Space-efficient recognition of sparse self-reducible languages
- ALOGTIME and a conjecture of S. A. Cook
- Expressing uniformity via oracles
- Parallel evaluation of arithmetic circuits
- On parallel hierarchies and R_k^i
- Gap-languages and log-time complexity classes
- On the parallel complexity of loops
- Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
- Circuits and expressions with nonassociative gates
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Proofs of proximity for context-free languages and read-once branching programs
- Local reduction
- Evaluation of circuits over nilpotent and polycyclic groups
- Constructing arrangements optimally in parallel
- Separating NC along the \(\delta\) axis
- Computing a context-free grammar-generating series
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On the complexity of inducing categorical and quantitative association rules
- Boolean grammars
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
- Data independence of read, write, and control structures in PRAM computations
- A characterization of alternating log time by ramified recurrence
- On the complexity of the clone membership problem
- Expander construction in \(\mathrm{VNC}^1\)
- Parallel pointer machines
- Uniform proofs of ACC representations
- Parallelizing time with polynomial circuits
- On some derivation mechanisms and the complexity of their Szilard languages
- Complexity theory for splicing systems
- The enumerability of P collapses P to NC
- A note on some languages in uniform \(ACC^ 0\)
- An algebra and a logic for \(NC^ 1\)
- Boolean circuits versus arithmetic circuits
- On uniformity within \(NC^ 1\)
- Ranking and formal power series
- Rounds versus time for the two person pebble game
- Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
- Division in logspace-uniform NC
- The complexity of ranking simple languages
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- On the complexity of Szilard languages of regulated grammars
- The Computational Complexity of Choice Sets
- Proofs of proximity for context-free languages and read-once branching programs
- Local reductions
- A Characterization of NC k by First Order Functional Programs
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Recursion Schemata for NC k
- Extensional Uniformity for Boolean Circuits
- RelativizedNC
- Classifying the computational complexity of problems
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
- Some results on uniform arithmetic circuit complexity
- Adaptive logspace reducibility and parallel time
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)
