Publication

Partial Recovery Bounds for the Sparse Stochastic Block Model

Publications associées (31)

Equivariant Neural Architectures for Representing and Generating Graphs

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

EPFL2023

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

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

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

WikiArtVectors: Style and Color Representations of Artworks for Cultural Analysis via Information Theoretic Measures

Bhargav Srinivasa Desikan

With the increase in massive digitized datasets of cultural artefacts, social and cultural scientists have an unprecedented opportunity for the discovery and expansion of cultural theory. The WikiArt dataset is one such example, with over 250,000 high qual ...

MDPI2022

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

A Functional Perspective on Information Measures

Amedeo Roberto Esposito

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Other ...

EPFL2022

A numerical algorithm based on probing to find optimized transmission conditions

Tommaso Vanzan

Optimized Schwarz Methods (OSMs) are based on optimized transmission conditions along the interfaces between the subdomains. Optimized transmission conditions are derived at the theoretical level, using techniques developed in the last decades. The hypothe ...

Springer-Verlag2023

Holistic, Efficient, and Real-time Cleaning of Heterogeneous Data

Styliani Asimina Giannakopoulou

Data cleaning has become an indispensable part of data analysis due to the increasing amount of dirty data. Data scientists spend most of their time preparing dirty data before it can be used for data analysis. Existing solutions that attempt to automate t ...

EPFL2021

Non-Wilson-Fisher kinks of O(N) numerical bootstrap: From the deconfined phase transition to a putative new family of CFTs

Ning Su

It is well established that the O(N) Wilson-Fisher (WF) CFT sits at a kink of the numerical bounds from bootstrapping four point function of O(N) vector. Moving away from the WF kinks, there indeed exists another family of kinks (dubbed non-WF kinks) on th ...

2021

Feedback and Common Information: Bounds and Capacity for Gaussian Networks

Erixhen Sula

Network information theory studies the communication of information in a network and considers its fundamental limits. Motivating from the extensive presence of the networks in the daily life, the thesis studies the fundamental limits of particular network ...

EPFL2021

Dynamic Balanced Graph Partitioning

Georg Stefan Schmid, Andreas Loukas

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to servi ...

SIAM Publications2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

The Almost-Sure Asymptotic Behavior Of The Solution To The Stochastic Heat Equation With Levy Noise

Carsten Hao Ye Chong

We examine the almost-sure asymptotics of the solution to the stochastic heat equation driven by a Levy space-time white noise. When a spatial point is fixed and time tends to infinity, we show that the solution develops unusually high peaks over short tim ...

INST MATHEMATICAL STATISTICS2020

A conformal dispersion relation: correlations from absorption

Din Carmi

We introduce the analog of Kramers-Kronig dispersion relations for correlators of four scalar operators in an arbitrary conformal field theory. The correlator is expressed as an integral over its "absorptive part", defined as a double discontinuity, times ...

Springer Nature2020

Jamming with Tunable Roughness

Matthieu Wyart, Carolina Brito Carvalho dos Santos

We introduce a new model to study the effect of surface roughness on the jamming transition. By performing numerical simulations, we show that for a smooth surface, the jamming transition density and the contact number at the transition point both increase ...

AMER PHYSICAL SOC2020

Adaptive algorithms for two fluids flows with anisotropic finite elements and order two time discretizations

Samuel Dubuis

This thesis is devoted to the derivation of a posteriori error estimates for the numerical approximation of fluids flows separated by a free surface. Based on these estimates, error indicators are introduced and adaptive algorithms are proposed to solve th ...

EPFL2020

Random time step probabilistic methods for uncertainty quantification in chaotic and geometric numerical integration

Assyr Abdulle, Giacomo Garegnani

A novel probabilistic numerical method for quantifying the uncertainty induced by the time integration of ordinary differential equations (ODEs) is introduced. Departing from the classical strategy to randomize ODE solvers by adding a random forcing term, ...

2020

An adaptive algorithm for the transport equation with time dependent velocity

Marco Picasso, Samuel Dubuis

An a posteriori error estimate is derived for the approximation of the transport equation with a time dependent transport velocity. Continuous, piecewise linear, anisotropic finite elements are used for space discretization, the Crank-Nicolson scheme schem ...

2020

On Maintaining Linear Convergence of Distributed Learning and Optimization Under Limited Communication

Na Li, Hossein Shokri Ghadikolaei

In distributed optimization and machine learning, multiple nodes coordinate to solve large problems. To do this, the nodes need to compress important algorithm information to bits so that it can be communicated over a digital channel. The communication tim ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020