Yury Makarychev

SODA Conference 2025 Conference Paper

Constraint Satisfaction Problems with Advice

• Suprovat Ghoshal
• Konstantin Makarychev
• Yury Makarychev

SODA Conference 2024 Conference Paper

Higher-Order Cheeger Inequality for Partitioning with Buffers

• Konstantin Makarychev
• Yury Makarychev
• Liren Shan
• Aravindan Vijayaraghavan

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G = ( V, E ). The buffered expansion of a set S ⊆ V with a buffer B ⊆ V \ S is the edge expansion of S after removing all the edges from set S to its buffer B. An ɛ -buffered k -partitioning is a partitioning of a graph into disjoint components P i and buffers B i, in which the size of buffer B i for P i is small relative to the size of P i: | B i | ≤ ɛ| P i |. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets P i with buffers B i. Let be the buffered expansion of the optimal ɛ -buffered k -partitioning, then for every δ > 0, where λ [(1 + δ) k is the [(1 + δ) k -th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the “square-root loss” that is present in the standard Cheeger inequalities (even for k = 2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.

STOC Conference 2024 Conference Paper

Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes

• Yury Makarychev
• Naren Sarayu Manoj
• Max Ovsiankin

We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.

SODA Conference 2022 Conference Paper

Approximating Fair Clustering with Cascaded Norm Objectives

• Eden Chlamtac
• Yury Makarychev
• Ali Vakilian

We introduce the ( p, q )-Fair Clustering problem. In this problem, we are given a set of points P and a collection of different weight functions W. We would like to find a clustering which minimizes the ℓ q -norm of the vector over W of the ℓ p -norms of the weighted distances of points in P from the centers. This generalizes various clustering problems, including Socially Fair k -Median and k -Means, and is closely connected to other problems such as Densest k -Subgraph and Min k -Union. We utilize convex programming techniques to approximate the ( p, q )-Fair Clustering problem for different values of p and q. When p ≥ q, we get an O ( k ( p – q )/(2 pq ) ), which nearly matches a k Ω(( p – q ) / ( pq )) lower bound based on conjectured hardness of Min k -Union and other problems. When q ≥ p, we get an approximation which is independent of the size of the input for bounded p, q, and also matches the recent O ((log n /(log log n )) 1/ p )-approximation for ( p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).

ICML Conference 2021 Conference Paper

Local Correlation Clustering with Asymmetric Classification Errors

• Jafar Jafarov
• Sanchit Kalhan
• Konstantin Makarychev
• Yury Makarychev

In the Correlation Clustering problem, we are given a complete weighted graph $G$ with its edges labeled as “similar" and “dissimilar" by a noisy binary classifier. For a clustering $\mathcal{C}$ of graph $G$, a similar edge is in disagreement with $\mathcal{C}$, if its endpoints belong to distinct clusters; and a dissimilar edge is in disagreement with $\mathcal{C}$ if its endpoints belong to the same cluster. The disagreements vector, $\disagree$, is a vector indexed by the vertices of $G$ such that the $v$-th coordinate $\disagree_v$ equals the weight of all disagreeing edges incident on $v$. The goal is to produce a clustering that minimizes the $\ell_p$ norm of the disagreements vector for $p\geq 1$. We study the $\ell_p$ objective in Correlation Clustering under the following assumption: Every similar edge has weight in $[\alpha\mathbf{w}, \mathbf{w}]$ and every dissimilar edge has weight at least $\alpha\mathbf{w}$ (where $\alpha \leq 1$ and $\mathbf{w}>0$ is a scaling parameter). We give an $O\left((\nicefrac{1}{\alpha})^{\nicefrac{1}{2}-\nicefrac{1}{2p}}\cdot \log\nicefrac{1}{\alpha}\right)$ approximation algorithm for this problem. Furthermore, we show an almost matching convex programming integrality gap.

ICML Conference 2020 Conference Paper

Correlation Clustering with Asymmetric Classification Errors

• Jafar Jafarov
• Sanchit Kalhan
• Konstantin Makarychev
• Yury Makarychev

In the Correlation Clustering problem, we are given a weighted graph $G$ with its edges labelled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge $e$ has weight $w_e \in [ \alpha w, w ]$ and every "dissimilar" edge $e$ has weight $w_e \geq \alpha w$ (where $\alpha \leq 1$ and $w > 0$ is a scaling parameter). We give a $(3 + 2 \log_e (1/\alpha))$ approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of $\Omega(\log 1/\alpha)$.

STOC Conference 2019 Conference Paper

Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering

• Konstantin Makarychev
• Yury Makarychev
• Ilya P. Razenshteyn

Consider an instance of Euclidean k -means or k -medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O (log( k /ε) / ε 2 )-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k -clustering with the distances raised to the p -th power for any constant p .

STOC Conference 2018 Conference Paper

Nonlinear dimension reduction via outer Bi-Lipschitz extensions

• Sepideh Mahabadi
• Konstantin Makarychev
• Yury Makarychev
• Ilya P. Razenshteyn

We introduce and study the notion of *an outer bi-Lipschitz extension* of a map between Euclidean spaces. The notion is a natural analogue of the notion of *a Lipschitz extension* of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f ′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a *prioritized* variant of the Johnson–Lindenstrauss lemma: given a set of points X ⊂ ℝ d of size N and a permutation (”priority ranking”) of X , there exists an embedding f of X into ℝ O (log N ) with distortion O (loglog N ) such that the point of rank j has only O (log 3 + ε j ) non-zero coordinates – more specifically, all but the first O (log 3+ε j ) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O (loglog j ). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in ℜ d , there exists a *terminal* dimension reduction embedding of ℝ d into ℝ d ′ , where d ′ = O (log N /ε 4 ), which preserves distances || x − y || between points x ∈ X and y ∈ ℝ d , up to a multiplicative factor of 1 ± ε. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.

SODA Conference 2017 Conference Paper

Algorithmic and Hardness Results for the Hub Labeling Problem

• Haris Angelidakis
• Yury Makarychev
• Vsevolod Oparin

STOC Conference 2017 Conference Paper

Algorithms for stable and perturbation-resilient problems

• Haris Angelidakis
• Konstantin Makarychev
• Yury Makarychev

We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. In this paper, we give improved algorithms for stable instances of various clustering and combinatorial optimization problems. We also prove several hardness results. We first give an exact algorithm for 2-perturbation resilient instances of clustering problems with natural center-based objectives. The class of clustering problems with natural center-based objectives includes such problems as k -means, k -median, and k -center. Our result improves upon the result of Balcan and Liang (2016), who gave an algorithm for clustering 1+√≈2.41 perturbation-resilient instances. Our result is tight in the sense that no polynomial-time algorithm can solve (2ε)-perturbation resilient instances of k -center unless NP = RP , as was shown by Balcan, Haghtalab, and White (2016). We then give an exact algorithm for (2-2/ k )-stable instances of Minimum Multiway Cut with k terminals, improving the previous result of Makarychev, Makarychev, and Vijayaraghavan (2014), who gave an algorithm for 4-stable instances. We also give an algorithm for (2-2/ k +ς)-weakly stable instances of Minimum Multiway Cut. Finally, we show that there are no robust polynomial-time algorithms for n 1-ε -stable instances of Set Cover, Minimum Vertex Cover, and Min 2-Horn Deletion (unless P = NP ).

SODA Conference 2017 Conference Paper

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

• Eden Chlamtac
• Michael Dinitz
• Yury Makarychev

In the Minimum k -Union problem (M k U) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural problem, it has received surprisingly little attention: the only known approximation algorithm is an due to [Chlamtac et al APPROX’16]. This problem can also be viewed as the bipartite version of the Small Set Vertex Expansion problem (SSVE), which we call the Small Set Bipartite Vertex Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes to minimize their vertex expansion, has not been as well studied as its edge-based counterpart Small Set Expansion (SSE), but has recently received significant attention, e. g. [Louis-Makarychev APPROX ‘15]. However, due to the connection to Unique Games and hardness of approximation the focus has mostly been on sets of size k = Ω( n ), while we focus on the case of general k, for which no polylogarithmic approximation is known. We improve the upper bound for this problem by giving an η 1/4 + ∊ approximation for SSBVE for any constant ∊ > 0. Our algorithm follows in the footsteps of Densest k -Subgraph (DkS) and related problems, by designing a tight algorithm for random models, and then extending it to give the same guarantee for arbitrary instances. Moreover, we show that this is tight under plausible complexity conjectures: it cannot be approximated better than O ( n 1/4 ) assuming an extension of the so-called “Dense versus Random” conjecture for DkS to hypergraphs. In addition to conjectured hardness via our reduction, we show that the same lower bound is also matched by an integrality gap for a super-constant number of rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for the natural SDP relaxation. Finally, we note that there exists a simple bicriteria approximation for the more general SSVE problem (where no non-trivial approximations were known for general k ).

SODA Conference 2017 Conference Paper

Robust algorithms with polynomial loss for near-unanimity CSPs

• Víctor Dalmau
• Marcin Kozik
• Andrei A. Krokhin
• Konstantin Makarychev
• Yury Makarychev
• Jakub Oprsal

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for CSP is called robust if it outputs an assignment satisfying a (1 — g(∊))-fraction of constraints on any (1 — ∊)-satisfiable instance, where the loss function g is such that g( ∊ ) → 0 as ∊ → 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g ) have been characterised by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(∊) = O ((loglog(1/ ∊))/log(1/ ∊)). It is natural to ask when a better loss can be achieved: in particular, polynomial loss g(∊) = O (∊ 1/ k ) for some constant k. In this paper, we consider CSPs with a constraint language having a near- unanimity polymorphism. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalisation of Un ique Ga mes with a fixed domain and 2-Sa t. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for CSP.

FOCS Conference 2015 Conference Paper

Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

• Konstantin Makarychev
• Yury Makarychev
• Yuan Zhou 0007

We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear equations. To obtain our results, we prove a new Bonami-type inequality for the Efron -- Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.

SODA Conference 2014 Conference Paper

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut

• Konstantin Makarychev
• Yury Makarychev
• Aravindan Vijayaraghavan

STOC Conference 2014 Conference Paper

Constant factor approximation for balanced cut in the PIE model

• Konstantin Makarychev
• Yury Makarychev
• Aravindan Vijayaraghavan

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters L and R of equal size. Let G be an arbitrary graph on V with no edges between L and R . Let E random be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in L and in R ). Then we say that G+E random is a graph with permutation-invariant random edges.

NeurIPS Conference 2013 Conference Paper

The Power of Asymmetry in Binary Hashing

• Behnam Neyshabur
• Nati Srebro
• Russ Salakhutdinov
• Yury Makarychev
• Payman Yadollahpour

When approximating binary similarity using the hamming distance between short binary hashes, we shown that even if the similarity is symmetric, we can have shorter and more accurate hashes by using two distinct code maps. I. e. ~by approximating the similarity between $x$ and $x'$ as the hamming distance between $f(x)$ and $g(x')$, for two distinct binary codes $f, g$, rather than as the hamming distance between $f(x)$ and $f(x')$.

SODA Conference 2012 Conference Paper

Approximation algorithms and hardness of the k -route cut problem

• Julia Chuzhoy
• Yury Makarychev
• Aravindan Vijayaraghavan
• Yuan Zhou 0007

STOC Conference 2012 Conference Paper

Approximation algorithms for semi-random partitioning problems

• Konstantin Makarychev
• Yury Makarychev
• Aravindan Vijayaraghavan

In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real-world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser.

FOCS Conference 2011 Conference Paper

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games

• Alexandra Kolla
• Konstantin Makarychev
• Yury Makarychev

In this paper, we study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an ε-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1 - ε)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1 - δ) fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is Ω̃(log k)). Our result holds only for ε less than some absolute constant. We prove that if ε ≥ 1/2, then the problem is hard in one of the models, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1 - ε)-satisfiable semi-random instance and (ii) the instance is at most δ-satisfiable (for every δ >; 0); the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1 - ε)-satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1 - δ)-satisfiable instances if ε >; cδ (for some absolute constant c).

SODA Conference 2011 Conference Paper

On Graph Crossing Number and Edge Planarization

• Julia Chuzhoy
• Yury Makarychev
• Anastasios Sidiropoulos

Given an n -vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with O(log 2 n ). ( n + OPT) crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Planarization problem on graph G, then we can efficiently find a drawing of G with at most poly( d ) · k · ( k + OPT) crossings, where d is the maximum degree in G. This result implies an O ( n · poly( d ) · log 3/2 n )-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k -apex and bounded-genus graphs.

FOCS Conference 2011 Conference Paper

The Grothendieck Constant is Strictly Smaller than Krivine's Bound

• Mark Braverman
• Konstantin Makarychev
• Yury Makarychev
• Assaf Naor

The classical Grothendieck constant, denoted K G, is equal to the integrality gap of the natural semidefinite relaxation of the problem of computing max {Σ i-1 m Σ j=1 n a ij ε i δ j: {ε i } i=1 m, {δ j } j=1 n ⊆{-1, 1} } a generic and well-studied optimization problem with many applications. Krivine proved in 1977 that KG ≤ 2log (1+√2)/π and conjectured that his estimate is sharp. We obtain a sharper Grothendieck inequality, showing that KG o >; 0. Our main contribution is conceptual: despite dealing with a binary rounding problem, random 2-dimensional projections combined with a careful partition of ℝ 2 in order to round the projected vectors, beat the random hyperplane technique, contrary to Krivine's long-standing conjecture.

FOCS Conference 2010 Conference Paper

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability

• Konstantin Makarychev
• Yury Makarychev

We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k/log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log 2 k/log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we obtain a lower bound of Ω (√log k/ log log k) for flow sparsifiers and a lower bound of Ω( √g k/ log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist Õ(√log k) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than Ω̃(√log k) would imply a negative answer to this question.

STOC Conference 2010 Conference Paper

Subgraph sparsification and nearly optimal ultrasparsifiers

• Alexandra Kolla
• Yury Makarychev
• Amin Saberi
• Shang-Hua Teng

We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph W k such that G+W k is a good spectral sparsifer of G+W. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on G and W such that a good sparsifier exists and give a polynomial-time algorithm to find the sparsifer. As an application of our technique, we show that for each positive integer k, every n-vertex weighted graph has an (n-1+k)-edge spectral sparsifier with relative condition number at most n/k log n, ~O(log log n) where ~O() hides lower order terms. Our bound nearly settles a question left open by Spielman and Teng about ultrasparsifiers. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.

STOC Conference 2009 Conference Paper

Integrality gaps for Sherali-Adams relaxations

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

We prove strong lower bounds on integrality gaps of Sherali-Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive n δ rounds of lift and project. For MAX CUT and Vertex Cover, these show that even n δ rounds of Sherali-Adams do not yield a better than 2-ε approximation. The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. We develop a conceptually simple geometric approach to constructing Sherali-Adams gap examples via constructions of consistent local SDP solutions. This geometric approach is surprisingly versatile. We construct Sherali-Adams gap examples for Unique Games based on our construction for MAX CUT together with a parallel repetition like procedure. This in turn allows us to obtain Sherali-Adams gap examples for any problem that has a Unique Games based hardness result (with some additional conditions on the reduction from Unique Games). Using this, we construct 2-ε gap examples for Maximum Acyclic Subgraph that rules out any family of linear constraints with support at most n δ .

SODA Conference 2007 Conference Paper

A divide and conquer algorithm for d -dimensional arrangement

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

FOCS Conference 2007 Conference Paper

Local Global Tradeoffs in Metric Embeddings

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

Suppose that every k points in a metric space X are D-distortion embeddable into lscr 1. We give upper and lower bounds on the distortion required to embed the entire space X into lscr 1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into lscr 1 with distortion O(D times log(|X|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from I. For D = 1 + delta we give a lower bound of Omega(log(|X|/k/ log( 1/delta)); and for D = 1, we give a lower bound of Omega( log |X|/(log k +log log | X|)). Our bounds significantly improve on the results of Arora, Jjovdsz, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

SODA Conference 2007 Conference Paper

Near-optimal algorithms for maximum constraint satisfaction problems

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

FOCS Conference 2007 Conference Paper

On the Advantage over Random for Maximum Acyclic Subgraph

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

In this paper we present a new approximation algorithm for the Max Acyclic Subgraph problem. Given an instance where the maximum acyclic subgraph contains 1/2 + delta fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Omega(delta/ log n) fraction of all edges.

SODA Conference 2006 Conference Paper

Directed metrics and directed graph partitioning problems

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

FOCS Conference 2006 Conference Paper

How to Play Unique Games Using Embeddings

• Eden Chlamtac
• Konstantin Makarychev
• Yury Makarychev

In this paper we present a new approximation algorithm for unique games. For a unique game with n vertices and k states (labels), if a (1 - epsiv) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(epsiv radic(log n log k)) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size

STOC Conference 2006 Conference Paper

Near-optimal algorithms for unique games

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. It has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. Thus, proving or refuting this conjecture is an important goal. We present significantly improved approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1-ε fraction of all constraints, our algorithms satisfy roughly k -ε/(2-ε) and 1- O(√εlog k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.

STOC Conference 2005 Conference Paper

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

• Amit Agarwal
• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

We give O(√log n)-approximation algorithms for the MIN UNCUT, MIN 2CNF DELETION, DIRECTED BALANCED SEPERATOR, and DIRECTED SPARSEST CUT problems. The previously best known algorithms give an O(log n)-approximation for MIN UNCUT [9], DIRECTED BALANCED SEPERATOR [17], DIRECTED SPARSEST CUT [17], and an O(log n log log n)-approximation for MIN 2CNF DELETION [14].We also show that the integrality gap of an SDP relaxation of the MINIMUM MULTICUT problem is Ω(log n).

STOC Conference 2005 Conference Paper

Quadratic forms on graphs

• Noga Alon
• Konstantin Makarychev
• Yury Makarychev
• Assaf Naor

We introduce a new graph parameter, called the Grothendieck constant of a graph G =( V,E ), which is defined as the least constant K such that for every A : E →R,sup f:V→S |V|-1 Σ (u,v) ∈ E A(u,v) · ‹f(u),f(v)› ≤ K sup f:V→(-1,+1) Σ (u,v)∈ E A(u,v) · f(u)f(v).The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑ u,v ∈ E A ( u,v ) f ( v over all f : V →-1,1, which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O (log θḠ)) where θ(Ḡ) is the Lovász Theta Function of the complement of G , which is always smaller than the chromatic number of G . This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G . We also show that the maximum possible integrality gap is always at least Ω(log ω( G )), where Ω(G) is the clique number of G . In particular it follows that the maximum possible integrality gap for the complete graph on n Θ vertices with no loops is ⏷(log n ). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is ⏷(log n ). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.