This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:group:seminars:20110722 [2011/07/18 11:04] maatouk |
en:group:seminars:20110722 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 17: | Line 17: | ||
| Boolean randomized oblivious branching programs computing GIP-MAP, a variation of the generalized inner product problem that can be computed in time n and space O(\og^2 n) by a | Boolean randomized oblivious branching programs computing GIP-MAP, a variation of the generalized inner product problem that can be computed in time n and space O(\og^2 n) by a | ||
| deterministic Boolean branching program. | deterministic Boolean branching program. | ||
| + | |||
| These are also the first lower bounds for randomized oblivious branching programs computing explicit functions that apply for T=omega(n log n). They also show that any simulation of general branching programs by randomized oblivious ones requires either | These are also the first lower bounds for randomized oblivious branching programs computing explicit functions that apply for T=omega(n log n). They also show that any simulation of general branching programs by randomized oblivious ones requires either | ||
| a superlogarithmic increase in time or an exponential increase in space. | a superlogarithmic increase in time or an exponential increase in space. | ||