Publications associées à Réduction polynomiale

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, Leonardo Zampieri

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

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

2023

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, Mikhail Makarov, Jakab Tardos

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