The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable \poly(n)-clause CNF formula F that has at least ≥ 2^n satisfying assignments, runs in time \[ n^{\tilde{O}(\log\log n)^2} \] for ≥ \ge 1/\polylog(n) and outputs...
A weight-t halfspace} is a Boolean function f(x)=\sign(w_1 x_1 + … + w_n x_n - θ) where each w_i is an integer in \{-t,\dots,t\}. We give an explicit pseudorandom generator that δ-fools any intersection of k weight-t halfspaces with seed length \poly(\log n, \log k,t,1/δ). In particular, our result gives an explicit PRG that fools any intersection of any...
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d -- 1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size...
We consider the problem of testing whether an unknown Boolean function f : { -- 1, 1}n ⇆ { -- 1, 1} is monotone versus ε-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an Ω(n1/5) lower bound on the query complexity of any non-adaptive two-sided...
In this work, we study the parity complexity measures pCmin[f] and PDT[f]. Pcmin[f] is the parity kill number of f, the fewest number of parities on the input variables one has to fix in order to "kill" f, i.e. To make it constant. PDT[f] is the depth of the shortest emph{parity decision tree} which computes f. These complexity measures have in recent years become increasingly important...
We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first non-trivial universal upper bounds on approximability by DNFs: \begin{itemize} \item Every Boolean...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.