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 show that hard sets S for NP must have exponential density, i.e. |S=n| ges 2nepsi for some isin > 0 and infinitely many n, unless coNP sube NP/poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n1-isin queries. In addition we study the instance complexity o/NP- hard problems and show that hard sets also have an exponential amount of instances...
We prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. Our result answers a question of Alekhnovich and Razborov, who proved that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable 2-approximation algorithm unless every problem...
We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant mu Gt 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 - (log n)-mu fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm...
We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n1+isin for every isin>0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields,...
This paper shows a complete upward collapse in the Polynomial Hierarchy (PH) if for ZPP, two queries to a SAT oracle is equivalent to one query. That is, ZPPSAT[1] = ZPPSAT||[2] rArr ZPPSAT[1] = PH. These ZPP machines are required to succeed with probability at least 1/2 + 1/p(n) on inputs of length n for some polynomial p(n). This result builds upon recent work by Tripathi who showed a collapse of...
This paper has two main focal points. We first consider an important class of machine learning algorithms - large margin classifiers, such as support vector machines. The notion of margin complexity quantifies the extent to which a given class of functions can be learned by large margin classifiers. We prove that up to a small multiplicative constant, margin complexity is equal to the inverse of discrepancy...
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let Repsiv(f) and Dmuepsiv(f) denote the randomized and mu-distributional communication complexities off, respectively (e a small constant). Yao's well-known minimax principle states that Repsiv(f) = maxmu{Dmuepsiv(f)}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the...
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity,...
We show that disjointness requires randomized communication Omega(n1/(k+1)/22k) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (log n/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2nOmega(1) lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial...
We revisit the computational power of constant width polynomial size planar nondeterministic branching programs. We show that they are capable of computing any function computed by a Pi2 o CC0 o AC0 circuit in polynomial size. In the quasipolynomial size setting we obtain a characterization of ACC0 by constant width planar non-deterministic branching programs.
We show that tree-like OBDD proofs of unsatisfiability require an exponential increase (s rarr 2sOmega(1)) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase (s rarr 22(logs)Omega(1)) in proof size to simulate Res (O(log n)). The "OBDD proof system" that we consider has lines that are ordered...
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.