Name
Abstract | ||
|---|---|---|
We use the techniques of Karchmer and Widgerson [KW90] to derive strong lower boundson the expected parallel time to compute boolean functions by circuits. By average time, wemean the time needed on a self-timed circuit, a model introduced recently by Jakoby, Reischuk,and Schindelhauer, [JRS94] in which gates compute their output as soon as it is determined(possibly by a subset of the inputs to the gate).More precisely, we show that the average time needed to compute a boolean function on... |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-60313-1_137 | ESA |
Keywords | Field | DocType |
circuit complexity~ parallel time~ communication complex- ity,average communication complexity,lower bounds,average circuit depth,communication complexity,lower bound,circuit complexity,boolean function | Boolean function,Discrete mathematics,Average-case complexity,Combinatorics,Boolean circuit,Parameterized complexity,Circuit complexity,Communication complexity,Arithmetic circuit complexity,Worst-case complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-60313-1 | 2 | 0.52 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Codenotti | 1 | 619 | 49.92 |
| Peter Gemmell | 2 | 675 | 108.87 |
| Janos Simon | 3 | 368 | 50.45 |