Author name cluster

Ali Kemal Sinop

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Fairness and Optimality in Routing

Sreenivas Gollapudi
Kostas Kollias
Alkmini Sgouritsa
Ali Kemal Sinop

We study the existence of almost fair and near-optimal solutions to a routing problem as defined in the seminal work of Rosenthal [41]. We focus on the setting where multiple alternative routes are available for each potential request (which corresponds to a potential user of the network). This model captures a collection of diverse applications such as packet routing in communication networks, routing in road networks with multiple alternative routes, and the economics of transportation of goods. Our proposed centralized routes have provable guarantees in terms of both the total cost and fairness concepts such as approximate envy-freeness. We employ and appropriately combine tools from algorithmic game theory and fair division. Our results apply on two distinct models: the splittable case where the request is split among the selected paths (e. g. , routing a fleet of trucks) and the unsplittable case where the request is assigned to one of its designated paths (e. g. , a single user request). Finally, we conduct an empirical analysis to test the performance of our approach against simpler baselines using the real world road network of New York City.

PDF

ICML Conference 2023 Conference Paper

Exphormer: Sparse Transformers for Graphs

Hamed Shirzad
Ameya Velingker
Balaji Venkatachalam
Danica J. Sutherland
Ali Kemal Sinop

Graph transformers have emerged as a promising architecture for a variety of graph learning and representation tasks. Despite their successes, though, it remains challenging to scale graph transformers to large graphs while maintaining accuracy competitive with message-passing networks. In this paper, we introduce Exphormer, a framework for building powerful and scalable graph transformers. Exphormer consists of a sparse attention mechanism based on two mechanisms: virtual global nodes and expander graphs, whose mathematical characteristics, such as spectral expansion, pseduorandomness, and sparsity, yield graph transformers with complexity only linear in the size of the graph, while allowing us to prove desirable theoretical properties of the resulting transformer models. We show that incorporating Exphormer into the recently-proposed GraphGPS framework produces models with competitive empirical results on a wide variety of graph datasets, including state-of-the-art results on three datasets. We also show that Exphormer can scale to datasets on larger graphs than shown in previous graph transformer architectures.

Details

SODA Conference 2016 Conference Paper

How to Round Subspaces: A New Spectral Clustering Algorithm

Ali Kemal Sinop

A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a k -partition such that the subspace corresponding to the span of its indicator vectors is close to the original subspace in spectral norm with OPT being the minimum possible (OPT ≤ 1 always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a k -partition closer than o ( k · OPT). We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest k -partition in a graph where each cluster have expansion at most φ k provided φ k ≤ O ( Λ k +1 ) where Λ k +1 is the ( k + 1) st eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required φ k < O ( Λ k +1 / k ).

Details

SODA Conference 2013 Conference Paper

Approximating Non-Uniform Sparsest Cut Via Generalized Spectra

Venkatesan Guruswami
Ali Kemal Sinop

We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any ε, δ ∊ (0, 1), given cost and demand graphs with edge weights respectively, we can find a set T ⊆ V with at most times the optimal non-uniform sparsest cut value, in time 2 r / (δε) poly( n ) provided Λ r ≥ Φ*/(1 − δ). Here Λ r is the r 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; C ( T, V \ T ) (resp. D ( T, V \ T )) is the weight of edges crossing the ( T, V \ T ) cut in cost (resp. demand) graph and Φ* is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the r 'th smallest eigenvalue of the normalized Laplacian playing the role of Λ r ( G ) in the latter two cases. Our proof is based on an ℓ 1 -embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting ℓ 1 -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [9] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.

Details

FOCS Conference 2013 Conference Paper

Towards a Better Approximation for Sparsest Cut?

Sanjeev Arora
Rong Ge 0001
Ali Kemal Sinop

We give a new (1 + ε)-approximation for SPARSEST CUT problem on graphs where small sets expand significantly more than the sparsest cut (expansion of sets of size n/r exceeds that of the sparsest cut by a factor √log n log r, for some small r; this condition holds for many natural graph families). We give two different algorithms. One involves Guruswami-Sinop rounding on the level-r Lasserre relaxation. The other is combinatorial and involves a new notion called Small Set Expander Flows (inspired by the expander flows of [1]) which we show exists in the input graph. Both algorithms run in time 2 O(r) poly(n). We also show similar approximation algorithms in graphs with genus g with an analogous local expansion condition. This is the first algorithm we know of that achieves (1 + ε)-approximation on such general family of graphs.

Details

FOCS Conference 2012 Conference Paper

Faster SDP Hierarchy Solvers for Local Rounding Algorithms

Venkatesan Guruswami
Ali Kemal Sinop

Convex relaxations based on different hierarchies of linear/semi-definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of rounds r in the hierarchy, though the complexity of solving (or even writing down the solution for) the r'th level program grows as n Ω(r) where n is the input size. In this work, we observe that many of these algorithms are based on local rounding procedures that only use a small part of the SDP solution (of size n O(1) 2 O(r) instead of n Ω(r) ). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to n O(1) 2 O(r) time algorithms to obtain the same guarantees in many cases as the earlier n O(r) time algorithms based on r rounds of the Lasserre hierarchy. In particular, guarantees based on O(log n) rounds can be realized in polynomial time. For instance, one can (i) get O(1/λ r ) approximations for graph partitioning problems such as minimum bisection and small set expansion in n O(1) 2 O(r) time, where λ r is the r'th smallest eigenvalue of the graph's normalized Laplacian; (ii) a similar guarantee in n O(1) k O(r) for Unique Games where k is the number of labels (the polynomial dependence on k is new); and (iii) find an independent set of size Ω(n) in 3-colorable graphs in (n2 r ) O(1) time provided λ n-r <; 17/16. We develop and describe our algorithm in a fairly general abstract framework. The main technical tool in our work, which might be of independent interest in convex optimization, is an efficient ellipsoid algorithm based separation oracle for convex programs that can output a certificate of infeasibility with restricted support. This is used in a recursive manner to find a sequence of consistent points in nested convex bodies that “fools” local rounding algorithms.

Details

SODA Conference 2012 Conference Paper

Optimal column-based low-rank matrix reconstruction

Venkatesan Guruswami
Ali Kemal Sinop

We prove that for any real-valued matrix X ∊ ℝ m × n, and positive integers r ≥ k, there is a subset of r columns of X such that projecting X onto their span gives a -approximation to best rank- k approximation of X in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in O ( rnm ω log m ) arithmetic operations where ω is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in O ( rnm 2 ) arithmetic operations.

Details

FOCS Conference 2011 Conference Paper

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

Venkatesan Guruswami
Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global lin- ear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time n O(r/ε2) with approximation ratio (1+ε)/min{1, λ r }, where λ r is the r'th smallest eigenvalue of the normalized graph Laplacian L. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply (1 + O(ε)) factor approximation in time n O(r*/ε2) where r* is the number of eigenvalues of L smaller than 1 - ε. This perhaps gives some indication as to why even showing mere APX-hardness for these problems has been elusive, since the reduction must produce graphs with a slowly growing spectrum (and classes like planar graphs which are known to have such a spectral property often admit good algorithms owing to their nice structure). For Unique Games, we give a factor (1 + (2+ε)/λ r ) approximation for minimizing the number of unsatisfied constraints in n O(r/ε) time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than 1 + o(1).

Details

SODA Conference 2011 Conference Paper

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Venkatesan Guruswami
Ali Kemal Sinop

We prove almost tight hardness results under randomized reductions for finding independent sets in bounded degree graphs and hypergraphs that admit a good coloring. Our specific results include the following (where Δ, a constant, is a bound on the degree, and n is the number of vertices): NP-hardness of finding an independent set of size larger than in a 2-colorable r-uniform hypergraph for each fixed r ≥ 4. A simple algorithm is known to find independent sets of size in any r -uniform hypergraph of maximum degree Δ. Under a combinatorial conjecture on hypergraphs, the (log Δ) 1/( r –1) factor in our result is necessary. Conditional hardness of finding an independent set with more than vertices in a k -colorable (with k ≥ 7) graph for some absolute constant c ≤ 4, under Khot's 2-to-1 Conjecture. This suggests the near-optimality of Karger, Motwani and Sudan's graph coloring algorithm which finds an independent set of size in k -colorable graphs. Conditional hardness of finding independent sets of size in almost 2-colorable 3-uniform hypergraphs, under Khot's Unique Games Conjecture. This suggests the optimality of the known algorithms to find an independent set of size in 2-colorable 3-uniform hypergraphs. Conditional hardness of finding an independent set of size more than in r -uniform hypergraphs that contain an independent set of size n (1 − O (log r/r )) assuming the Unique Games Conjecture.

Details