Publication

Extended Formulations from Communication Protocols in Output-Efficient Time

Publications associées (36)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Safe Motion Planning against Multimodal Distributions Based on a Scenario Approach

Maryam Kamgarpour

We present the design of a motion planning algorithm that ensures safety for an autonomous vehicle. In particular, we consider a multimodal distribution over uncertainties; for example, the uncertain predictions of future trajectories of surrounding vehicl ...

2022

Tropical Ehrhart Theory and Tropical Volume

Matthias Schymura, Georg Peter Loho

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

2019

On some problems related to 2-level polytopes

Manuel Francesco Aprile

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

EPFL2018

On 2-Level Polytopes Arising In Combinatorial Settings

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

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

SIAM PUBLICATIONS2018

Non-Normal Very Ample Polytopes - Constructions and Examples

Michal Lason

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

Taylor & Francis Inc2017

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

Springer2017

On vertices and facets of combinatorial 2-level polytopes

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

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

Springer2016

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

Nisheeth Vishnoi

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

Elsevier Science Bv2016

Detecting nanoscale vibrations as signature of life

Giovanni Dietler, Sandor Kasas, Giovanni Longo, Francesco Simone Ruggeri, Petar Stupar

The existence of life in extreme conditions, in particular in extraterrestrial environments, is certainly one of the most intriguing scientific questions of our time. In this report, we demonstrate the use of an innovative nanoscale motion sensor in life-s ...

National Academy of Sciences2015

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

Friedrich Eisenbrand

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

Springer2013