Concept

Combinatorics

Related publications (53)

Enriching the Computational Toolbox for Organocatalysis

Organocatalysis has evolved significantly over the last decades, becoming a pillar of synthetic chemistry, but traditional theoretical approaches based on quantum mechanical computations to investigate reaction mechanisms and provide rationalizations of ca ...

EPFL2023

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

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformatio ...

EPFL2022

From Trees to Barcodes and Back Again:A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

Adélie Eliane Garin

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view.Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B involve ...

EPFL2022

Communication Complexity of Collision

Mika Tapani Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...

Leibniz-Zentrum für Informatik2022

Synthesis and direct assay of large macrocycle diversities by combinatorial late-stage modification at picomole scale

Christian Heinis, Gerardo Turcatti, Julien Bortoli Chapalay, Alessandro Angelini, Manuel Leonardo Merz, Sevan Mleh Habeshian, Jonathan Patrice Vesin, Mischa Schüttel, Ganesh Kumar Mothukuri, Gontran Sangouard, Cristina Diaz Perlas, Zsolt Bognár

Macrocycles have excellent potential as therapeutics due to their ability to bind challenging targets. However, generating macrocycles against new targets is hindered by a lack of large macrocycle libraries for high-throughput screening. To overcome this, ...

2022

Atomic length in Weyl groups

Thomas Gerber

We define a new statistic on Weyl groups called the atomic length and investigate its combinatorial and representation-theoretic properties. In finite types, we show a number of properties of the atomic length which are reminiscent of the properties of the ...

2022

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Oligomodal metamaterials with multifunctional mechanics

Aleksi Antoine Bossart

Mechanical metamaterials are artificial composites that exhibit a wide range of advanced functionalities such as negative Poisson's ratio, shape shifting, topological protection, multistability, extreme strength-to-density ratio, and enhanced energy dissip ...

NATL ACAD SCIENCES2021

Conditional gradient methods for stochastically constrained convex minimization

Volkan Cevher, Ya-Ping Hsieh, Ahmet Alacaoglu, Maria-Luiza Vladarean

We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, whi ...

2020

Graph Chatbot

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.