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.
Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.
The approximate degree of a Boolean function f: {-1, 1}^n ↦ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits.Specifically, we show how to transform any Boolean function f with approximate...
For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the ℓp norm (CVP_p) over rank n lattices cannot be solved in 2^(1-≥) n time for any constant ≥ 0 unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to almost all values of p ≥ 1, not including the even integers. This comes...
We present a new distributed} model of probabilistically checkable proofs (PCP). A satisfying assignment x ∊ \{0,1\}^n to a CNF formula \phi is shared between two parties, where Alice knows x_1, \dots, x_{n/2, Bob knows x_{n/2+1},\dots,x_n, and both parties know \phi. The goal is to have Alice and Bob jointly write a PCP that x satisfies \phi, while exchanging little or no information....
We study the computational complexity of short sentences in Presburger arithmetic (SHORT-PA). Here by short we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integer coefficients involved in the linear inequalities. We prove that satisfiability of SHORT-PA sentences with m+2 alternating quantifiers is SigmaP_m-complete...
We study the classic k-median and k-means clustering objectives in the beyond-worst-case scenario. We consider three well-studied notions of structured data that aim at characterizing real-world inputs:• Distribution Stability (introduced by Awasthi, Blum, and Sheffet, FOCS 2010)• Spectral Separability (introduced by Kumar and Kannan, FOCS 2010)• Perturbation Resilience...
Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+≥ilon, a ratio that is known to be tight with respect to such methods.We overcome this barrier...
We describe a general technique that yields the first Statistical Query lower bounds} fora range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the problems of (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown Gaussian distribution. For each of these problems, we show a super-polynomial...
We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of this problem, we are given samples from a uniform mixture of k standard spherical Gaussians with means mu_1,...,mu_k in R^d, and the goal is to estimate the means up to accuracy δ using poly(k,d, 1/δ)...
We prove a lower bound on the size of a small depth Frege refutation of the Tseitin contradiction on the grid. We conclude that polynomial size such refutations must use formulas of almost logarithmic depth.
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics and is a benchmark for satisfiability algorithms. We show that when k = Θ(log n), any Cutting Planes refutation for random k-SAT requires exponential size in the interesting regime where the number of clauses guarantees that the formula is unsatisfiable...
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.