scientific article; zbMATH DE number 3257409

Cited in

(52)

Time-space trade-offs for branching programs
A lower bound for read-once-only branching programs
Entropy of contact circuits and lower bounds on their complexity
Meanders and their applications in lower bounds arguments
Tradeoffs for language recognition on alternating machines
On Nečiporuk's theorem for branching programs
Neither reading few bits twice nor reading illegally helps much
Size-depth tradeoff in non-monotone Boolean formulae
Discrete extremal problems
Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
Lower bounds for depth-restricted branching programs
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
A class of Boolean functions with linear combinational complexity
Lower bounds for the size of expressions for certain functions in d-ary logic
Hierarchy theorems for kOBDDs and kIBDDs
On the complexity of encoding in analog circuits
Efficient oblivious branching programs for threshold and mod functions
On uncertainty versus size in branching programs.
BDDs -- design, analysis, complexity, and applications.
Some observations on holographic algorithms
On the limits of gate elimination
Size-treewidth tradeoffs for circuits computing the element distinctness function
Normal Boolean functions
On the complexity of planar Boolean circuits
Circuit complexity of linear functions: gate elimination and feeble security
A quadratic lower bound for homogeneous algebraic branching programs
Mining circuit lower bound proofs for meta-algorithms
Lower bounds for restricted read-once parity branching programs
On the complexity of the marriage problem
A hierarchy result for read-once branching programs with restricted parity nondeterminism
Lower bounds on the complexity of real-time branching programs
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Small bias requires large formulas
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Circuit lower bounds for MCSP from local pseudorandom generators
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
On the meaning of works by V. M. Khrapchenko
Limitations of incremental dynamic programming
Algorithms and lower bounds for comparator circuits from shrinkage
Improving \(3N\) circuit complexity lower bounds
New lower bounds and hierarchy results for restricted branching programs
One-tape Turing machine and branching program lower bounds for MCSP
Linear-size Boolean circuits for multiselection
Towards stronger depth lower bounds
Pebbles and branching programs for tree evaluation
Towards a complexity theory of synchronous parallel computation
Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
On read-k projections of the determinant
On oblivious branching programs of linear length
Lower bounds to the complexity of symmetric Boolean functions
Entropy of operators or why matrix multiplication is hard for depth-two circuits
A nondeterministic space-time tradeoff for linear codes

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5545524)