Publications related to New Graph Algorithms via Polyhedral Techniques

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.

Planted matching problems on random hypergraphs

Lenka Zdeborová, Anshul Toshniwal, Gabriele Sicuro

We consider the problem of inferring a matching hidden in a weighted random k-hypergraph. We assume that the hyperedges' weights are random and distributed according to two different densities conditioning on the fact that they belong to the hidden matchin ...

2022

fGOT: Graph Distances Based on Filters and Optimal Transport

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Giovanni Chierchia

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Approximate CVPp in time 2(0.802n)

Friedrich Eisenbrand, Moritz Andreas Venzin

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

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

On Polynomial Algorithms for Normalizing Formulas

Viktor Kuncak, Simon Guilloud, Mario Bucev

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

2022

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...

ASSOC COMPUTING MACHINERY2021

New Graph Algorithms via Polyhedral Techniques

Graph Chatbot

Chat with Graph Search

Planted matching problems on random hypergraphs

fGOT: Graph Distances Based on Filters and Optimal Transport

Sketches, metrics and fast algorithms

Approximate CVPp in time 2(0.802n)

On Polynomial Algorithms for Normalizing Formulas

The Role of Adaptivity in Source Identification with Time Queries

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Spectral Hypergraph Sparsifiers of Nearly Linear Size

A PCP Theorem for Interactive Proofs and Applications

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

The Role of Adaptivity in Source Identification with Time Queries

Approximate CVPp in time 2(0.802n)

fGOT: Graph Distances Based on Filters and Optimal Transport

On Polynomial Algorithms for Normalizing Formulas

Planted matching problems on random hypergraphs

Sketches, metrics and fast algorithms

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Spectral Hypergraph Sparsifiers of Nearly Linear Size

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

A PCP Theorem for Interactive Proofs and Applications