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 14: | Line 14: | ||
| ==== abstract ==== | ==== abstract ==== | ||
| We prove a time-space tradeoff lower bound of T = Omega(n log(n/S) log log(n/S)) for randomized oblivious branching programs to compute 1GAP, also known as the pointer jumping problem, a problem for which there is a simple deterministic time n and space O(log n) RAM (random access machine) algorithm. | We prove a time-space tradeoff lower bound of T = Omega(n log(n/S) log log(n/S)) for randomized oblivious branching programs to compute 1GAP, also known as the pointer jumping problem, a problem for which there is a simple deterministic time n and space O(log n) RAM (random access machine) algorithm. | ||
| - | |||
| We give a similar time-space tradeoff of T = Omega(n log(n/S) log log(n/S)) for | We give a similar time-space tradeoff of T = Omega(n log(n/S) log log(n/S)) for | ||
| 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 | ||