Vedat Levi Alev

activity

20172026

collaborators

9 papers

math.CO2026

Faster Mixing for Triangulations via Transport Flows

Vedat Levi Alev, Daniel Frishberg, Michail Sarantis +1

We prove an $O (n^{2})$ bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n + 2)$ -…

cs.DS2026

Hypergraph Samplers: Typical and Worst Case Behavior

Vedat Levi Alev, Uriya A. First

We study the utility and limitations of using $k$ -uniform hypergraphs $H = ([n], E)$ ( $n \geq poly (k)$ ) in the context of error reduction for randomized algorithms for deci…

cs.DS2024

Expanderizing Higher Order Random Walks

Vedat Levi Alev, Shravas Rao

We study a variant of the down-up and up-down walks over an $n$ -partite simplicial complex, which we call expanderized higher order random walks -- where the sequence of updated co…

cs.DM2023

Sequential Sweeps and High Dimensional Expansion

Vedat Levi Alev, Ori Parzanchevski

It is well known that the spectral gap of the down-up walk over an $n$ -partite simplicial complex (also known as Glauber dynamics) cannot be better than $O (1/ n)$ due to natural obs…

cs.DS2020

List Decoding of Direct Sum Codes

Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana +2

We consider families of codes obtained by "lifting" a base code $C$ through operations such as $k$ -XOR applied to "local views" of codewords of $C$ , according t…

cs.DS2020

Improved Analysis of Higher Order Random Walks and Applications

Vedat Levi Alev, Lap Chi Lau

The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. Ou…

cs.DS2019

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders

Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani

We consider the problem of approximately solving constraint satisfaction problems with arity $k > 2$ ( $k$ -CSPs) on instances satisfying certain expansion properties, when viewed as…

cs.DS2017

Graph Clustering using Effective Resistance

Vedat Levi Alev, Nima Anari, Lap Chi Lau +1

We design a polynomial time algorithm that for any weighted undirected graph $G = (V, E,\vecc w)$ and sufficiently large $δ > 1$ , partitions $V$ into…

cs.DS2017

Approximating Unique Games Using Low Diameter Graph Decomposition

Vedat Levi Alev, Lap Chi Lau

We design approximation algorithms for Unique Games when the constraint graph admits good low diameter graph decomposition. For the $Max2Lin_{k}$ problem in $K_{r}$ -minor free gr…