## Karthekeyan Chandrasekaran

### About

I am a Simons Postdoctoral Fellow in the Theory of Computation research group at Harvard University.

I completed my Ph.D. in Algorithms, Combinatorics, and Optimization (ACO) from Georgia Tech (2007-2012). My advisor was Prof. Santosh Vempala.

Email: k a r t h e [at] s e a s [dOt] h a r v a r d [dOt] e d u

### Research Interests

I am interested in optimization, integer programming, probabilistic methods and analysis, and randomized algorithms. Here is my CV.: New Approaches to Integer Programming. [pdf]**Thesis**

- College of Computing Dissertation Prize (Georgia Tech)

- Best Ph.D. Thesis Award, Sigma Xi Chapter of Georgia Tech

### Publications

- Finding Small Stabilizers for Unstable Graphs

(with Adrian Bock, Jochen Könemann, Britta Peis, Laura Sanitá)

(To appear in) Integer Programming and Combinatorial Optimization (IPCO '14), Jun 2014. - Faster Private Release of Marginals on Small Databases

(with Justin Thaler, Jonathan Ullman, Andrew Wan)

Innovations in Theoretical Computer Science (ITCS '14), Jan, 2014. [arXiv]| [Abstract]

We study the problem of answering k-way marginal queries on a database D in ({0,1}^d)^n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database's records x in {0,1}^d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time poly(n, min{ exp(d^{1-Omega(1/sqrt{k})}), exp(d / \log^{.99} d) } ) per query and answers any (adaptively chosen) sequence of poly(n) k-way marginal queries with error at most +/- .01 on every query, provided n >= d^{.51}. To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee for databases containing poly(d, k) records in time exp(o(d)). Our algorithm runs the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10) on a new approximate polynomial representation of the database.

We derive our representation for the database using techniques from approximation theory. More concretely, our representation uses approximations to the OR function by low-degree polynomials with coefficients of bounded L_1-norm. We derive our representation for the database by approximating the OR function restricted to low Hamming weight inputs using low-degree polynomials with coefficients of bounded L_1-norm. In doing so, we show new upper and lower bounds on the degree of such polynomials, which may be of independent approximation-theoretic interest. First, we construct a polynomial that approximates the d-variate OR function on inputs of Hamming weight at most k such that the degree of the polynomial is at most d^{1-Omega(1/sqrt{k})} and the L_1-norm of its coefficient vector is d^{0.01}. Then we show the following lower bound that exhibits the tightness of our approach: for any k = o(log d), any polynomial whose coefficient vector has L_1-norm poly(d) that pointwise approximates the d-variate OR function on all inputs of Hamming weight at most k must have degree d^{1-O(1/sqrt{k})}.

- Integer Feasibility of Random Polytopes

(with Santosh Vempala)

Innovations in Theoretical Computer Science (ITCS '14), Jan, 2014. [pdf]| [Abstract]

We study integer programming instances over polytopes P(A,b)={x:Ax<=b} where the constraint matrix A is random, i.e., its entries are i.i.d. Gaussian or, more generally, its rows are i.i.d. from a spherically symmetric distribution. The radius of the largest inscribed ball is closely related to the existence of integer points in the polytope. We show that for m=2^O(sqrt{n}), there exist constants c_0 < c_1 such that with high probability, random polytopes are integer feasible if the radius of the largest ball contained in the polytope is at least c_1sqrt{log(m/n)}; and integer infeasible if the largest ball contained in the polytope is centered at (1/2,...,1/2) and has radius at most c_0sqrt{log(m/n)}. Thus, random polytopes transition from having no integer points to being integer feasible within a constant factor increase in the radius of the largest inscribed ball. We show integer feasibility via a randomized polynomial-time algorithm for finding an integer point in the polytope.

Our main tool is a simple new connection between integer feasibility and linear discrepancy. We extend a recent algorithm for finding low-discrepancy solutions (Lovett-Meka, FOCS '12) to give a constructive upper bound on the linear discrepancy of random matrices. By our connection between discrepancy and integer feasibility, this upper bound on linear discrepancy translates to the radius lower bound that guarantees integer feasibility of random polytopes.

- Finding the most biased coin with fewest flips

(with Richard Karp) [arXiv]| [Abstract]

We study the problem of learning a most biased coin among a set of coins by tossing the coins adaptively. The goal is to minimize the number of tosses until we identify a coin i^* whose posterior probability of being most biased is at least 1-delta for a given delta. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy -- a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs tools from the field of Markov games.

- The Cutting Plane Method is Polynomial for Perfect Matchings

(with László Végh, Santosh Vempala)

IEEE Symposium on Foundations of Computer Science (FOCS '12), Oct 2012. [pdf]| [Abstract]

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.

***[With an appendix section giving a provably efficient combinatorial perfect matching algorithm in which all intermediate solutions are half-integral.]***

- Algorithms for Implicit Hitting Set Problems

(with Richard Karp, Erick Moreno-Centeno, Santosh Vempala)

ACM-SIAM Symposium on Discrete Algorithms (SODA '11), Jan 2011. [pdf]| [Abstract]

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.

- Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections

(with Navin Goyal, Bernhard Haeupler) [arXiv]| [Abstract]

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.

- Deterministic Algorithms for the Lovász Local Lemma

(with Navin Goyal, Bernhard Haeupler)

Preliminary version appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA '10), Jan 2010.

SIAM Journal on Computing, Vol. 42, Issue 6, 2013. [pdf]| [Abstract]

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.

- Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

(with Daniel Dadush, Santosh Vempala)

ACM-SIAM Symposium on Discrete Algorithms (SODA '10), Jan 2010. [pdf]| [Abstract]

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.

- Sampling s-Concave functions

(with Amit Deshpande, Santosh Vempala)

13th International Workshop on Randomization and Computation (RANDOM 2009), Aug 2009. [pdf]| [Abstract]

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.

- An Observation about Variations of the Diffie-Hellman Assumption

(with R. Bhaskar, S. V. Lokam, P. L. Montgomery, R. Venkatesan, Y. Yacobi)

Serdica Journal of Computing, Vol 3, No. 3, 2009. [pdf] |[Abstract]

We generalize the Strong Boneh-Boyen (SBB) signature scheme to sign vectors (GSBB). We show that if a particular average case reduction from SBB to GSBB exists, then the Strong Diffie-Hellman (SDH) and the Computational Diffie-Hellman (CDH) have the same worst case complexity.

- Vulnerabilities in Anonymous Credential Systems

(with R. Bhaskar, S. V. Lokam, P. L. Montgomery, R. Venkatesan, Y. Yacobi)

Electronic Notes in Theoretical Computer Science, Vol 197, No. 2, 2008. [pdf] |[Abstract]

We show the following:

(1) In existing anonymous credential revocation systems, the revocation authority can link the transactions of any user in a subset T of users in O(log T) fake failed sessions.

(2) A concern about the DLREP-I anonymous credentials system.