The mixing time of the Dikin walk in a polytope-A simple proof

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We study mixing and diffusion properties of passive scalars driven by generic rough shear flows. Genericity is here understood in the sense of prevalence, and (ir)regularity is measured in the Besov-Nikolskii scale B\alpha 1,\infty, \alpha \in (0,1). We pr ...

Proximal splitting methods are standard tools for nonsmooth optimization. While primal-dual methods have become very popular in the last decade for their flexibility, primal methods may still be preferred for two reasons: acceleration schemes are more effe ...

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

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 ...

Nowadays, the production in fine chemical and pharmaceutical industry is mostly carried out in large scale batch reactors having typically dimensions of a few meters to satisfy the demand of the market. Even though this technology has been widely used and ...

It is shown that 2-dimensional subdivisions can be made regular by moving their vertices within parallel 1-dimensional spaces. As a consequence, any 2-dimensional subdivision is projected from the boundary complex of a 4-polytope. ...

We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposit ...

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

To every d-dimensional polytope P with centrally symmetric facets one can assign a “subway map” such that every line of this “subway” contains exactly the facets parallel to one of the ridges of P. The belt diameter of P is the maximum number of subway lin ...

This paper studies the problem of learning under both large datasets and large-dimensional feature space scenarios. The feature information is assumed to be spread across agents in a network, where each agent observes some of the features. Through local co ...

We cast the under-determined convolutive speech separation as sparse approximation of the spatial spectra of the mixing sources. In this framework we compare and contrast the major practical algorithms for structured sparse recovery of speech signal. Speci ...

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arisi ...

In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes ...

The kinetics of hydration of cementitious materials is sensitive to the mixing procedure. High shear mixing conditions lead to an increase in the kinetics of hydration at early age compared to low shearing conditions such as hand mixing. In this study the ...

We answer several questions posed by Beck, Cox, Delgado, Gubeladze, Haase, Hibi, Higashitani, and Maclagan in [Cox et al. 14, Question 3.5 (1),(2), Question 3.6], [Beck et al. 15, Conjecture 3.5(a),(b)], and [Hasse et al. 07, Open question 3 (a),(b) p. 231 ...

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. ...

Mixing is an essential part of chemical processes. In the present work, homogeneous mixing at relatively high throughput for a single microchannel (of 1-18 mL/min) was investigated in microchannels with different dimensions, cross sections and mixing eleme ...

The objective of this paper is to study a special family of Minkowski sums, that is of polytopes relatively in general position. We show that the maximum number of faces in the sum can be attained by this family. We present a new linear equation that is sa ...

We show that for any concave polygon that has no parallel sides and for any k, there is a k-fold covering of some point set by the translates of this polygon that cannot be decomposed into two coverings. Moreover, we give a complete classification of open ...

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 mixing time of the Dikin walk in a polytope-A simple proof

Chat with Graph Search

MIXING FOR GENERIC ROUGH SHEAR FLOWS

Yapa: Accelerated Proximal Algorithm For Convex Composite Problems

New Results in Integer and Lattice Programming

Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Heat Management for Process Intensification of Fast Exothermic Reactions in Microstructured Reactors

Weakly regular subdivisions

Tropical Ehrhart Theory and Tropical Volume

Extended Formulations from Communication Protocols in Output-Efficient Time

Belt distance between facets of space-filling zonotopes

Supervised Learning Under Distributed Features

Computational Methods For Structured Sparse Component Analysis of Convolutive Speech Mixtures

On 2-Level Polytopes Arising In Combinatorial Settings

On some problems related to 2-level polytopes

Effect of mixing on the early hydration of alite and OPC systems

Non-Normal Very Ample Polytopes - Constructions and Examples

Extension complexity of stable set polytopes of bipartite graphs

Mixing efficiency and energy consumption for five generic microchannel designs

A linear equation for Minkowski sums of polytopes relatively in general position

Indecomposable Coverings with Concave Polygons

On vertices and facets of combinatorial 2-level polytopes