Quadratic time-space lower bounds for computing natural functions with a random oracle
© Dylan M. McKay and Richard Ryan Williams. We define a model of size-S R-way branching programs with oracles that can make up to S distinct oracle queries over all of their possible inputs, and generalize a lower bound proof strategy of Beame [SICOMP 1991] to apply in the case of random oracles. Th...
| Format: | Article |
|---|---|
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137452 |