Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428723 | Information Processing Letters | 2009 | 4 Pages |
Abstract
We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k22. We prove an exponential lower bound 2Ω(n/ck) for an explicit function over substantially smaller domain D of size about k2. Our function is a universal function of linear codes.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics