Publication

A scalable and oblivious atomicity assertion

Publications associées (31)

Results on Sparse Integer Programming and Geometric Independent Sets

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Proofs, Circuits, and Communication

Mika Tapani Göös

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

2022

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

Alessandro Chiesa, Siqi Liu

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs. ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

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

On Semi-Algebraic Proofs and Algorithms

Mika Tapani Göös

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

FANOK: Knockoffs in Linear Time

Quentin Rebjock

We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large-scale feature selection problems. Identifying the knockoff distribution requires solving a large-scale semidefinite progra ...

SIAM PUBLICATIONS2021

Tree in Tree: from Decision trees to Decision Graphs

Mahsa Shoaran, Bingzhao Zhu

Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional dec ...

Curran Associates, Inc, (NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems)2021

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

Giovanni De Micheli, Heinz Riener, Siang-Yun Lee

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...

IEEE2021

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

Privacy-Preserving Federated Analytics using Multiparty Homomorphic Encryption

David Jules Froelicher

Analyzing and processing data that are siloed and dispersed among multiple distrustful stakeholders is difficult and can even become impossible when the data are sensitive or confidential. Current data-protection and privacy regulations highly restrict the ...

EPFL2021

A method for faster application of process integration techniques in retrofit situations

Tuong-Van Nguyen

Numerous process integration techniques were proved to be highly effective for identifying and estimating potential energy savings in the industry. However, they require high time and effort to collect and analyse process data. As a result, they do not con ...

ELSEVIER SCI LTD2021

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Fast Transformers with Clustered Attention

François Fleuret, Angelos Katharopoulos, Apoorv Vyas

Transformers have been proven a successful model for a variety of tasks in sequence modeling. However, computing the attention matrix, which is their key component, has quadratic complexity with respect to the sequence length, thus making them prohibitivel ...

2020

mu RAI: Securing Embedded Systems with Return Address Integrity

Mathias Josef Payer

Embedded systems are deployed in security critical environments and have become a prominent target for remote attacks. Microcontroller-based systems (MCUS) are particularly vulnerable due to a combination of limited resources and low level programming whic ...

INTERNET SOC2020

On Vacuous and Non-Vacuous Generalization Bounds for Deep Neural Networks

Konstantinos Pitas

Deep neural networks have been empirically successful in a variety of tasks, however their theoretical understanding is still poor. In particular, modern deep neural networks have many more parameters than training data. Thus, in principle they should over ...

EPFL2020

Adaptive Streaming in Interactive Multiview Video Systems

Pascal Frossard, Laura Toni, Xue Zhang, Yao Zhao

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize addition ...

2019

Graph fragmentation problem: analysis and synthesis

Manuel Francesco Aprile, Pablo Romero Gómez

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...

WILEY2019

SoK: Shining Light on Shadow Stacks

Mathias Josef Payer, Xiangyu Zhang

Control-Flow Hijacking attacks are the dominant attack vector against C/C++ programs. Control-Flow Integrity (CFI) solutions mitigate these attacks on the forward edge, i.e., indirect calls through function pointers and virtual calls. Protecting the backwa ...

IEEE COMPUTER SOC2019

Construction of Polar Codes With Sublinear Complexity

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

Numerical methods for option pricing: polynomial approximation and high dimensionality

Francesco Statti

Options are some of the most traded financial instruments and computing their price is a central task in financial mathematics and in practice. Consequently, the development of numerical algorithms for pricing options is an active field of research. In gen ...

EPFL2019