Karthekeyan Chandrasekaran
Assistant Professor, Department of Industrial and Enterprise Systems EngineeringAffiliate, Department of Computer Science
University of Illinois at UrbanaChampaign
Research Interests
Combinatorial optimization, integer programming, probabilistic methods and analysis, randomized algorithms.
Short Bio
Karthik Chandrasekaran is an Assistant Professor in the Department of Industrial and Enterprise Engineering and an Affiliate in the Department of Computer Science at the University of Illinois at UrbanaChampaign. He received his bachelor's in Computer Science from IIT Madras and Ph.D. in Algorithms, Combinatorics and Optimization (ACO) from Georgia Tech. Prior to joining UIUC, he was a Simons postdoctoral fellow in the Theory of Computation research group at Harvard University. Here is his CV.
Teaching
 IE 511: Integer Programming, Spring 2017
 IE 310 + IE 311: Operations Research, Fall 2016
 IE 310 + IE 311: Operations Research, Spring 2016
 IE 598: Combinatorial Optimization, Fall 2015
 IE 511: Integer Programming, Spring 2015
Students
 Chao Xu: PhD advisee (joint with Chandra Chekuri)
 Jingwen Jiang: Senior Thesis, Spring 2016 (currently PhD student at University of Chicago)
Publications
 Global and fixedterminal cuts in digraphs
(with Kristóf Bérczi, Tamás Király, Euiwoong Lee, Chao Xu) [arXiv] [Abstract]
The computational complexity of multicutlike problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of this phenomenon in two types of cut problems in directed graphs: double cut and bicut.
1. The fixedterminal edgeweighted double cut is known to be solvable efficiently. We show a tight approximability factor of 2 for the fixedterminal nodeweighted double cut. We show that the global nodeweighted double cut cannot be approximated to a factor smaller than 3/2 under the Unique Games Conjecture (UGC).
2. The fixedterminal edgeweighted bicut is known to have a tight approximability factor of 2. We show that the global edgeweighted bicut is approximable to a factor strictly better than 2, and that the global nodeweighted bicut cannot be approximated to a factor smaller than 3/2 under UGC.
3. In relation to these investigations, we also prove two results on undirected graphs which are of independent interest. First, we show NPcompleteness and a tight inapproximability bound of 4/3 for the nodeweighted 3cut problem. Second, we show that for constant k, there exists an efficient algorithm to solve the minimum {s,t}separating kcut problem.
Our techniques for the algorithms are combinatorial, based on LPs and based on enumeration of approximate mincuts. Our hardness results are based on combinatorial reductions and integrality gap instances.
 Largest Eigenvalue and Invertibility of Symmetric Matrix Signings
(with Charles Carlson, HsienChih Chang, Alexandra Kolla) [arXiv] [Abstract]
The spectra of signed matrices have played a fundamental role in social sciences, graph theory and control theory. They have been key to understanding balance in social networks, to counting perfect matchings in bipartite graphs, and to analyzing robust stability of dynamic systems involving uncertainties. More recently, the results of Marcus et al. have shown that an efficient algorithm to find a signing of a given adjacency matrix that minimizes the largest eigenvalue could immediately lead to efficient construction of Ramanujan expanders.
Motivated by these applications, we investigate natural spectral properties of signed matrices and address the computational problems of identifying signings with these spectral properties. Our main results are: (a) NPcompleteness of three problems: verifying whether a given matrix has a signing that is positive semidefinite/singular/has bounded eigenvalues, (b) a polynomialtime algorithm to verify whether a given matrix has a signing that is invertible, and (c) a polynomialtime algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible signing. We use combinatorial and spectral techniques; our main new tool is a combinatorial characterization of matrices with invertible signings that might be of independent interest. We use our characterization and classic structural results from matching theory to find a minimum increase in the support in order to obtain invertible signings.
 Additive Stabilizers for Unstable Graphs
(with Corinna Gottschalk, Jochen Könemann, Britta Peis, Daniel Schmand, Andreas Wierz) [arXiv] [Abstract]
Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with nonempty core. They are also the graphs that induce a network bargaining game with a balanced solution. A graph with weighted edges is called stable if the maximum weight of an integral matching equals the cost of a minimum fractional weighted vertex cover. If a graph is not stable, it can be stabilized in different ways. Recent papers have considered the deletion or addition of edges and vertices in order to stabilize a graph. In this work, we focus on a finegrained stabilization strategy, namely stabilization of graphs by fractionally increasing edge weights.
We show the following results for stabilization by minimum weight increase in edge weights (min additive stabilizer): (i) Any approximation algorithm for min additive stabilizer that achieves a factor of O(V^(1/24eps)) for eps>0 would lead to improvements in the approximability of densestksubgraph. (ii) Min additive stabilizer has no o(logV) approximation unless NP=P. Results (i) and (ii) together provide the first superconstant hardness results for any graph stabilization problem. On the algorithmic side, we present (iii) an algorithm to solve min additive stabilizer in factorcritical graphs exactly in polytime, (iv) an algorithm to solve min additive stabilizer in arbitrarygraphs exactly in time exponential in the size of the Tutte set, and (v) a polytime algorithm with approximation factor at most O(sqrt(V)) for a superclass of the instances generated in our hardness proofs.
 Local Testing for Membership in Lattices
(with Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu)
Foundations of Software Technology and Theoretical Computer Science (FSTTCS '16), Dec 2016. [arXiv] [Abstract]
Motivated by the structural analogies between point lattices and linear errorcorrecting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in latticebased communication, and cryptography. Apart from establishing the conceptual foundations of lattice testing, our results include the following:
1. We demonstrate upper and lower bounds on the query complexity of local testing for the wellknown family of code formula lattices. Furthermore, we instantiate our results with code formula lattices constructed from ReedMuller codes, and obtain nearlytight bounds.
2. We show that in order to achieve low query complexity, it is sufficient to design onesided nonadaptive canonical tests. This result is akin to, and based on an analogous result for errorcorrecting codes due to BenSasson et al. (SIAM J. Computing 35(1) pp 121).
 Deciding Orthogonality in ConstructionA Lattices
(with Venkata Gandikota, Elena Grigorescu)
Foundations of Software Technology and Theoretical Computer Science (FSTTCS '15), Dec 2015. [arXiv] [Abstract]
Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is wellknown that CVP can be easily solved in lattices that have an orthogonal basis if the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NPcomplete or in P.
In this work, we focus on the orthogonality decision problem for a wellknown family of lattices, namely Construction A lattices. These are lattices of the form C+qZ^n, where C is an errorcorrecting qary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction A that have an orthogonal basis. This characterization leads to an efficient algorithm solving the orthogonality decision problem, which also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem in general.
 On the Expansion of GroupBased Lifts
(with Naman Agarwal, Alexandra Kolla, Vivek Madan) [arXiv] [Abstract]
A klift of an nvertex base graph G is a graph H on n x k vertices, where each vertex v of G is replaced by k vertices v_1,...,v_k and each edge (u,v) in G is replaced by a matching representing a bijection pi_{uv} so that the edges of H are of the form (u_i,v_{pi_{uv}(i)}). Lifts have been studied as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are:
1. There is a constant c_1 such that for every k>= 2^{c_1nd}, there does not exist an abelian klift H of any nvertex dregular base graph with H being almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most O(sqrt{d}) in magnitude). This can be viewed as an analogue of the wellknown noexpansion result for abelian Cayley graphs.
2. A uniform random lift in a cyclic group of order k of any nvertex dregular base graph G, with the nontrivial eigenvalues of the adjacency matrix of G bounded by lambda in magnitude, has the new nontrivial eigenvalues also bounded by lambda+O(sqrt{d}) in magnitude with probability 1ke^{Omega(n/d^2)}. In particular, there is a constant c_2 such that for every k<=2^{c_2n/d^2}, there exists a lift H of every Ramanujan graph in a cyclic group of order k with H being almost Ramanujan. We use this fact to design a quasipolynomial time algorithm to construct almost Ramanujan expanders deterministically.
The existence of expanding lifts in cyclic groups of order k=2^{Oh(n/d^2)} can be viewed as a lower bound on the order k_0 of the largest abelian group that produces expanding lifts. Our two results show that the lower bound closely matches the upper bound for k_0 (upto a factor of d^3 in the exponent), thus suggesting a threshold phenomenon.
 Towards Constructing Ramanujan Graphs Using Shift Lifts
(with Ameya Velingker) [arXiv] [Abstract]
In a breakthrough work, MarcusSpielmanSrivastava recently showed that every dregular bipartite Ramanujan graph has a 2lift that is also dregular bipartite Ramanujan. As a consequence, a straightforward iterative bruteforce search algorithm leads to the construction of a dregular bipartite Ramanujan graph on N vertices in time 2^O(dN). Shift klifts studied by AgarwalKollaMadan lead to a natural approach for constructing Ramanujan graphs more efficiently. The number of possible shift klifts of a dregular nvertex graph is k^(nd/2). Suppose the following holds for k=2^{\Omega(n)}:
There exists a shift klift that maintains the Ramanujan property of dregular bipartite graphs on n vertices for all n. (*)
Then, by performing a similar bruteforce search, one would be able to construct an Nvertex bipartite Ramanujan graph in time 2^O(dlog^2 N). Furthermore, if (*) holds for all k>=2, then one would obtain an algorithm that runs in poly(N^d) time. In this work, we take a first step towards proving (*) by showing the existence of shift klifts that preserve the Ramanujan property in dregular bipartite graphs for k=3, 4.
 Finding Small Stabilizers for Unstable Graphs
(with Adrian Bock, Jochen Könemann, Britta Peis, Laura Sanità)
Preliminary version appeared in Integer Programming and Combinatorial Optimization (IPCO '14), Jun 2014.
Mathematical Programming, Series B, Dec 2014.  Finding a Most Biased Coin with Fewest Flips
(with Richard Karp)
Conference on Learning Theory (COLT '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 kway marginal queries on a database D in ({0,1}^d)^n, while preserving differential privacy. The answer to a kway 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^{1Omega(1/sqrt{k})}), exp(d / \log^{.99} d) } ) per query and answers any (adaptively chosen) sequence of poly(n) kway 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 nontrivial worstcase 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 lowdegree polynomials with coefficients of bounded L_1norm. We derive our representation for the database by approximating the OR function restricted to low Hamming weight inputs using lowdegree polynomials with coefficients of bounded L_1norm. In doing so, we show new upper and lower bounds on the degree of such polynomials, which may be of independent approximationtheoretic interest. First, we construct a polynomial that approximates the dvariate OR function on inputs of Hamming weight at most k such that the degree of the polynomial is at most d^{1Omega(1/sqrt{k})} and the L_1norm 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_1norm poly(d) that pointwise approximates the dvariate OR function on all inputs of Hamming weight at most k must have degree d^{1O(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 polynomialtime 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 lowdiscrepancy solutions (LovettMeka, 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.
 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 minimumcost perfect matching problem. Our main insight is an LPbased 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 halfintegral 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 halfintegral 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 halfintegral.]***
 Algorithms for Implicit Hitting Set Problems
(with Richard Karp, Erick MorenoCenteno, Santosh Vempala)
ACMSIAM 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 online 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(1o(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 polynomialsized 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 kCNF 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 kCNF formula that guarantees satisfiability under the assumption that every two clauses share at most alpha variables. More formally, we call these formulas alphaintersecting and define, for example, a threshold mu_i(k,alpha) for the number of clause intersection pairs i, such that every alphaintersecting kCNF formula in which at most mu_i(k,alpha) pairs of clauses share a variable is satisfiable and there exists an unsatisfiable alphaintersecting kCNF 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 kCNF 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 ACMSIAM 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 nonconstructive existence proofs of combinatorial structures. A prominent application is to kCNF 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 MoserTardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for kCNF formulas, for any epsilon in (0, 1) we give a deterministic algorithm that finds a satisfying assignment for any kCNF 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 MoserTardos 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 MoserTardos. 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)
ACMSIAM Symposium on Discrete Algorithms (SODA '10), Jan 2010. [pdf] [Abstract]
Starshaped 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 starshaped 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 starshaped 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 starshaped sets is NPhard.
 Sampling sConcave functions
(with Amit Deshpande, Santosh Vempala)
13th International Workshop on Randomization and Computation (RANDOM '09), 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/(n1)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 quasiconcave. We give an efficient sampling algorithm based on a random walk for 1/(n1)concave probability densities satisfying a smoothness criterion, which includes heavytailed 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 DiffieHellman 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 BonehBoyen (SBB) signature scheme to sign vectors (GSBB). We show that if a particular average case reduction from SBB to GSBB exists, then the Strong DiffieHellman (SDH) and the Computational DiffieHellman (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 DLREPI anonymous credentials system.

PhD Thesis:
New Approaches to Integer Programming. [pdf]