Concept

Réduction polynomiale

Publications associées (31)

Isogeny Problems with Level Structure

Given two elliptic curves and the degree of an isogeny between them, finding the isogeny is believed to be a difficult problem—upon which rests the security of nearly any isogeny-based scheme. If, however, to the data above we add information about the beh ...

2024

Implementing water recirculation in a novel portable plasma-activated water reactor enhances antimicrobial effect against Escherichia coli

Ivo Furno, Alan Howling, Fabio Avino, Rita Agus, Brayden Graham Myers, Lorenzo Ibba

The need for sustainable and reliable decontamination methods is driven by concerns regarding antibiotic resistance, as well as environmental and cost -efficiency challenges associated with traditional methods. Plasmaactivated water (PAW) holds significant ...

Elsevier Science Sa2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

High-Density Immobilization of TCEP on Silica Beads for Efficient Disulfide Reduction and Thiol Alkylation in Peptides

Christian Heinis

Tris-(2-carboxyethyl)phosphine (TCEP) linked to agarose beads is widely used for reducing disulfide bridges in proteins and peptides. The immobilization of TCEP on beads allows efficient removal after reduction to prevent its reaction with alkylating reage ...

2023

Tensor-Based Numerical Method For Stochastic Homogenization

Quentin Olivier Martin Ayoul--Guilmard

This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...

SIAM PUBLICATIONS2022

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

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

SIAM Publications2023

Efficient lattice Green's function method for bounded domain problems

William Curtin, Max Ludwig Hodapp, Ankit Gupta

The lattice Green's function method (LGFM) is the discrete counterpart of the continuum boundary element method and is a natural approach for solving intrinsically discrete solid mechanics problems that arise in atomistic-continuum coupling methods. Here, ...

Wiley2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

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

EPFL2022

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Flow Time Scheduling and Prefix Beck-Fiala

Ola Nils Anders Svensson, Lars Rohwedder

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bound ...

ASSOC COMPUTING MACHINERY2022

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Automating cutting planes is NP-hard

Mika Tapani Göös

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It is -hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, ...

ACM2021

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

ASSOC COMPUTING MACHINERY2021

Bayesian Decision Making in Groups is Hard

Jan Hazla

We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior be ...

INFORMS2021

Vessel scheduling with pilotage and tugging considerations

Michel Bierlaire

This paper considers vessel scheduling with pilotage and tugging constraints in berthing operations with channel restrictions at seaports. To our knowledge, pilotage and tugging requirements have not been simultaneously considered in the literature. This w ...

PERGAMON-ELSEVIER SCIENCE LTD2021

Perceptual Quality of Point Clouds with application to Compression

Evangelos Alexiou

Modern information technologies and human-centric communication systems employ advanced content representations for richer portrayals of the real world. The newly adopted imaging modalities offer additional information cues and permit the depiction of real ...

EPFL2021

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Source Term Estimation Algorithms for Gas Sensing Mobile Robots

Faezeh Rahbar

Localizing sources of airborne chemicals with mobile sensing systems finds applications in various crucial and perilous situations, such as safety and security investigation for detecting explosives or illegal drugs, search and rescue operations to locate ...

EPFL2021

A note on the integrality gap of the configuration LP for restricted Santa Claus

Lars Rohwedder

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to pl ...

ELSEVIER2020