Loading...
Please wait, while we are loading the content...
Similar Documents
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds (2015)
| Content Provider | CiteSeerX |
|---|---|
| Author | Golovnev, Alexander Kulikov, Alexander S. |
| Abstract | In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n, k, s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show that if a Boolean function f is a |
| File Format | |
| Publisher Date | 2015-01-01 |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
