Communication complexity and lower bounds on multilective computations
Branching programs provide lower bounds on the area of VLSI circuits
Hierarchy of reversal bounded one-way multicounter machines
On the number of monotonic functions from two-valued logic to -valued logic
Reversals-space-parallelism tradeoffs for language recognition
Communication Complexity and Lower Bounds on Multilective Computations
Communication complexity of two-party (multiparty) protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious, semilective computations are usually transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one...
Zerotesting bounded one-way multicounter machines
Page 1