Sorting signed permutations by inversions in O(nlogn) time

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.

Modern machine learning (ML) models are capable of impressive performances. However, their prowess is not due only to the improvements in their architecture and training algorithms but also to a drastic increase in computational power used to train them.|S ...

Last-mile delivery in the logistics chain contributes to congestion in urban networks due to frequent stops. Crowd-shipping is a sustainable and low-cost alternative to traditional delivery but relies heavily on the availability of occasional couriers. In ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

Adiabatic quantum-flux parametron (AQFP) is an energy-efficient superconducting technology. Buffer and splitter (B/S) cells must be inserted to an AQFP circuit to meet the technology-imposed constraints on path balancing and fanout branching. These cells a ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

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

Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final siz ...

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

Sorting signed permutations by inversions in O(nlogn) time

Chat with Graph Search

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

A continuum approximation approach to the depot location problem in a crowd-shipping system

Formula Normalizations in Verification

Streaming and Matching Problems with Submodular Functions

Beyond Local Optimality of Buffer and Splitter Insertion for AQFP Circuits

Discrete Optimal Transport with Independent Marginals is #P-Hard

Approximate CVPp in time 2(0.802n)

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

The Role of Adaptivity in Source Identification with Time Queries

Hybrid Flock - Formation Control Algorithms