The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...
We study the mixing time of the Dikin walk in a polytope a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing ti ...
2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number ...
The well-known "necklace splitting theorem" of Alon (1987) asserts that every k-colored necklace can be fairly split into q parts using at most t cuts, provided k(q - 1)
Let P be a set of n > d points in for d >= 2. It was conjectured by Zvi Schur that the maximum number of (d-1)-dimensional regular simplices of edge length diam(P), whose every vertex belongs to P, is n. We prove this statement under the condition that any ...
We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological space ...
Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same ...
Let Isom(H^n) be the group of isometries of the n-dimensional real hyperbolic space. We first classify all continuous non-elementary actions of on the infinite-dimensional real hyperbolic space. We then prove the existence of a continuous family of non-iso ...
This paper features two main contributions. On the one hand, it gives an impressive survey on the progress on the diameter problem, including the breakthrough of the author with his disproof of the Hirsch conjecture among many other recent results. On the ...
A faithful (unit) distance graph in R-d is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph in Rd ...
A diameter graph in is a graph whose set of vertices is a finite subset of and whose set of edges is formed by pairs of vertices that are at diameter apart. This paper is devoted to the study of different extremal properties of diameter graphs in and on a ...
Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room’s response. Can you hear the shape of the room? Some people can do it naturally, but can we design computer algorithms that hear rooms? We show how to com ...
