This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:group:seminars:20110722 [2011/06/01 14:13] maatouk created |
en:group:seminars:20110722 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | page | + | ---- dataentry seminar ---- |
| + | date_dt : 2011-07-22 | ||
| + | title : Time-space tradeoffs for randomized oblivious branching programs | ||
| + | speaker : Widad Machmouchi | ||
| + | affiliation : University of Washington | ||
| + | time : 16h15 | ||
| + | room : BC 129 | ||
| + | table : seminars | ||
| + | =================== | ||
| + | template:datatemplates:seminar | ||
| + | ----------------------- | ||
| + | |||
| + | |||
| + | ==== 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 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 | ||
| + | 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 | ||
| + | a superlogarithmic increase in time or an exponential increase in space. | ||