On Sub-determinants and the Diameter of Polyhedra

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.

This paper rethinks Sharpness-Aware Minimization (SAM), which is originally formulated as a zero-sum game where the weights of a network and a bounded perturbation try to minimize/maximize, respectively, the same differentiable loss. We argue that SAM shou ...

It is well-known that for any integral domain R, the Serre conjecture ring R(X), i.e., the localization of the univariate polynomial ring R[X] at monic polynomials, is a Bezout domain of Krull dimension

Self-attention mechanisms and non-local blocks have become crucial building blocks for state-of-the-art neural architectures thanks to their unparalleled ability in capturing long-range dependencies in the input. However their cost is quadratic with the nu ...

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

The diffusion strategy for distributed learning from streaming data employs local stochastic gradient updates along with exchange of iterates over neighborhoods. In Part I [3] of this work we established that agents cluster around a network centroid and pr ...

Driven by the need to solve increasingly complex optimization problems in signal processing and machine learning, there has been increasing interest in understanding the behavior of gradient-descent algorithms in non-convex environments. Most available wor ...

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

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

We study discretizations of polynomial processes using finite state Markov processes satisfying suitable moment matching conditions. The states of these Markov processes together with their transition probabilities can be interpreted as Markov cubature rul ...

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

The Ring Learning with Errors (RLWE) problem has become one of the most widely used cryptographic assumptions for the construction of modern cryptographic primitives. Most of these solutions make use of power-of-two cyclotomic rings mainly due to its simpl ...

The diffusion strategy for distributed learning from streaming data employs local stochastic gradient updates along with exchange of iterates over neighborhoods. In this work we establish that agents cluster around a network centroid in the mean-fourth sen ...

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

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

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

A nonnegative matrix factorization (NMF) can be computed efficiently under the separability assumption, which asserts that all the columns of the given input data matrix belong to the cone generated by a (small) subset of them. The provably most robust met ...

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

We consider integer programming problems max {c^Tx : A x = b, l

Let F-p be a prime field of order p > 2, and let A be a set in F-p with very small size in terms of p. In this note, we show that the number of distinct cubic distances determined by points in A x A satisfies vertical bar(A - A)(3) + (A - A)(3 vertical bar ...

On Sub-determinants and the Diameter of Polyhedra

Chat with Graph Search

Improving SAM Requires Rethinking its Optimization Formulation

The multivariate Serre conjecture ring

Linear Complexity Self-Attention With 3rd Order Polynomials

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Distributed Learning in Non-Convex Environments-Part II: Polynomial Escape From Saddle-Points

Distributed Learning in Non-Convex Environments-Part I: Agreement at a Linear Rate

New Results in Integer and Lattice Programming

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Markov cubature rules for polynomial processes

The electric autonomous dial-a-ride problem

Multiquadratic Rings and Walsh-Hadamard Transforms for Oblivious Linear Function Evaluation

Polynomial Escape-Time From Saddle Points In Distributed Non-Convex Optimization

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

On some problems related to 2-level polytopes

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

A Fast Gradient Method for Nonnegative Sparse Regression With Self-Dictionary

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Faster Algorithms for Integer Programs with Block Structure

Four-Variable Expanders Over The Prime Fields