6 papers · 1 filter
Hypergraph Samplers: Typical and Worst Case Behavior
Vedat Levi Alev, Uriya A. First
We study the utility and limitations of using -uniform hypergraphs () in the context of error reduction for randomized algorithms for deci…
Expanderizing Higher Order Random Walks
Vedat Levi Alev, Shravas Rao
We study a variant of the down-up and up-down walks over an -partite simplicial complex, which we call expanderized higher order random walks -- where the sequence of updated co…
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 through operations such as -XOR applied to "local views" of codewords of , according t…
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…
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 (-CSPs) on instances satisfying certain expansion properties, when viewed as…
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 , partitions into…