Concept

Computational complexity

Publications associées (1 000)

Efficient Preparation of Cyclic Quantum States

Giovanni De Micheli, Fereshte Mozafari Ghoraba

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...

IEEE2022

Information Retrieval Under Network Uncertainty: Robust Internet Ranking

Ralf Seifert, Anna Timonina-Farkas

Internet ranking algorithms play a crucial role in information technologies and numerical analysis due to their efficiency in high dimensions and wide range of possible applications, including scientometrics and systemic risk in finance (SinkRank, DebtRank ...

INFORMS2022

Towards Verifiable, Generalizable and Efficient Robust Deep Neural Networks.

Chen Liu

In the last decade, deep neural networks have achieved tremendous success in many fields of machine learning.However, they are shown vulnerable against adversarial attacks: well-designed, yet imperceptible, perturbations can make the state-of-the-art deep ...

EPFL2022

Towards coupling conventional with high-fidelity fuel behavior analysis tools

Andreas Pautz, Carlo Fiorina, Alessandro Scolaro, Edoardo Luciano Brunetto

Multi-dimensional fuel performance codes have the potential to enhance the understanding of complex phenomena affecting fuel integrity, but their application is often limited by the high computational cost. Recognizing that many multi-dimensional aspects s ...

PERGAMON-ELSEVIER SCIENCE LTD2022

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

IEEE2022

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...

EPFL2022

A Prony-based approach for accelerating the lightning electromagnetic fields computation above a perfectly conducting ground

Marcos Rubinstein

Lightning strikes can seriously affect the reliability and availability of electrical infrastructures. The computation of lightning-electromagnetic fields represents one of the most crucial steps in the evaluation of the induced effects; thus, having at di ...

2022

Deep learning accelerated prediction of the permeability of fibrous microstructures

Véronique Michaud, Baris Çaglar, Guillaume Clément Broggi

Permeability of fibrous microstructures is a key material property for predicting the mold fill times and resin flow path during composite manufacturing. In this work, we report an efficient approach to predict the permeability of 3D microstructures from d ...

2022

Fast and accurate decoding of finger movements from ECoG through Riemannian features and modern machine learning techniques

Mahsa Shoaran, Bingzhao Zhu

Objective. Accurate decoding of individual finger movements is crucial for advanced prosthetic control. In this work, we introduce the use of Riemannian-space features and temporal dynamics of electrocorticography (ECoG) signal combined with modern machine ...

IOP Publishing Ltd2022

Controlling the Complexity and Lipschitz Constant improves Polynomial Nets

Volkan Cevher, Grigorios Chrysos, Fabian Ricardo Latorre Gomez

While the class of Polynomial Nets demonstrates comparable performance to neural networks (NN), it currently has neither theoretical generalization characterization nor robustness guarantees. To this end, we derive new complexity bounds for the set of Coup ...

2022

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search