- We study the problem of learning the most biased coin among a set of coins by tossing the coins adaptively. The goal is to minimize the number of tosses to identify a coin i* such that prob{coin i* is most biased} is at least 1-\delta\ for any given \delta>0. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of tosses, to learn a most biased coin. The problem is equivalent to finding the best arm in the multi-armed bandit problem using adaptive strategies. Dar et al. (2002) and Mannor and Tsitsiklis (2004) show upper and lower bounds matching up to constant factors on the number of coin tosses for several underlying settings of the bias probabilities. For a class of such settings we bridge the constant factor gap by giving an optimal adaptive strategy -- a strategy that performs the best possible action under any given history of outcomes. For any given history, tossing the coin chosen by our strategy minimizes the expected number of tosses needed to learn a most biased coin. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem.

- We consider random integer programs defined by linear constraints whose normal vectors are chosen independently from any spherically symmetric distribution. We show that with high probability, a program defined by O(n) constraints has an integer solution provided the corresponding polytope contains a ball whose radius is larger than a universal constant. For a polytope with m constraints in n-dimensional space, with n < m < 2^O(sqrt(n)) , a ball of radius about Omega(log (2m/n)) suffices. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. Our work provides a connection between integer programming and discrepancy of set systems - in particular, we use the entropy technique from Spencer's classical result on discrepancy of set systems and build on Bansal's recent algorithm for finding low-discrepancy solutions efficiently.

- The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (Padberg and Rao, Grotschel and Holland, Lovasz and Plummer, Trick, Fischetti and Lodi), and its convergence has been an open question. We prove that the cutting plane approach using Edmonds' blossom inequalities converges in polynomial time for the minimum-cost perfect matching problem. Our main insight is an LP-based method to retain/drop cuts. This careful cut retention procedure leads to a sequence of intermediate linear programs with a linear number of constraints whose optima are half-integral and supported by a disjoint union of odd cycles and edges. This structural property of the optima is instrumental in finding violated blossom inequalities (cuts) in linear time. Further, the number of cycles in the support of the half-integral optima acts as a potential function to show efficient convergence to an integral solution.

- Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n-(1/p) log np(1-o(1)) with probability at least 3/4 for the random graph G(n,p) (the smallest feedback vertex set is of size n-(2/p) log np(1 + o(1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.

- Lovasz Local Lemma (LLL) is a powerful result in probability theory that is often used for non-constructive existence proofs of combinatorial structures. A prominent application is to k-CNF formulas, where LLL implies that if every clause in a formula shares variables with at most d<=2^k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment in this setting was given by Moser. Subsequently Moser and Tardos gave a general algorithmic framework for LLL and a randomized algorithm to construct the structures guaranteed by LLL. In this paper we address the main problem left open by Moser and Tardos of derandomizing this algorithm efficiently. Our algorithm works in the general framework of Moser--Tardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for k-CNF formulas, for any epsilon in (0, 1) we give a deterministic algorithm that finds a satisfying assignment for any k-CNF formula with m clauses and d<=2^k/(1+epsilon) /e in time \tilde{O}(m^(2(1+1/{lower case epsilon})). This improves upon the deterministic algorithms of Moser and of Moser-Tardos with running times m^(Omega(k^2)) and m^(Omega(k/epsilon)) which are superpolynomial for k = omega(1) and upon other previous algorithms which work only for d<=2^(k/16)/e. Our algorithm is the first deterministic algorithm that works in the general framework of Moser--Tardos. Lastly we show how to obtain an NC, i.e., fully parallel, algorithm for the same setting.

- Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard.

- Efficient sampling, integration and optimization algorithms for logconcave functions rely on the good isoperimetry of these functions. We extend this to show that -1/(n-1)-concave functions have good isoperimetry, and moreover, using a characterization of functions based on their values along every line, we prove that this is the largest class of functions with good isoperimetry in the spectrum from concave to quasi-concave. We give an efficient sampling algorithm based on a random walk for -1/(n-1)-concave probability densities satisfying a smoothness criterion, which includes heavy-tailed densities such as the Cauchy density. In addition, the mixing time of this random walk for Cauchy density matches the corresponding best known bounds for logconcave densities.

- We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees satisfiability under the assumption that every two clauses share at most alpha variables. More formally, we call these formulas alpha-intersecting and define, for example, a threshold mu_i(k,alpha) for the number of clause intersection pairs i, such that every alpha-intersecting k-CNF formula in which at most mu_i(k,alpha) pairs of clauses share a variable is satisfiable and there exists an unsatisfiable alpha-intersecting k-CNF formula with mu_m(k,alpha) such intersections. We provide a lower bound for these thresholds based on the Lovasz Local Lemma and a nearly matching upper bound by constructing an unsatisfiable k-CNF to show that mu_i(k,alpha) = Theta(2^{k(2+1/alpha)})$. Similar thresholds are determined for the number of variables (mu_n = Theta(2^{k/alpha})) and the number of clauses (mu_m = Theta(2^{k(1+(1/alpha))})) (see [Scheder08] for an earlier but independent report on this threshold). Our upper bound construction gives a family of unsatisfiable formula that achieve all four thresholds simultaneously.