Théorie de la complexité (informatique théorique)

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (30)

Generalized Bradley-Terry Models for Score Estimation from Paired Comparisons

Sadegh Farhadkhani, Oscar Jean Olivier Villemaud, Julien René Pierre Fageot, Le Nguyen Hoang

Many applications, e.g. in content recommendation, sports, or recruitment, leverage the comparisons of alternatives to score those alternatives. The classical Bradley-Terry model and its variants have been widely used to do so. The historical model conside ...

AAAI Press2024

Scalable Quantum Algorithms for Noisy Quantum Computers

Julien Sebastian Gacon

Quantum computing not only holds the potential to solve long-standing problems in quantum physics, but also to offer speed-ups across a broad spectrum of other fields. Access to a computational space that incorporates quantum effects, such as superposition ...

EPFL2024

Post-correction of Historical Text Transcripts with Large Language Models: An Exploratory Study

Frédéric Kaplan, Maud Ehrmann, Matteo Romanello, Emanuela Boros, Sven-Nicolas Yoann Najem

The quality of automatic transcription of heritage documents, whether from printed, manuscripts or audio sources, has a decisive impact on the ability to search and process historical texts. Although significant progress has been made in text recognition ( ...

Association for Computational Linguistics2024

Modular segmentation, spatial analysis and visualization of volume electron microscopy datasets

Martin Weigert

Volume electron microscopy is the method of choice for the in situ interrogation of cellular ultrastructure at the nanometer scale, and with the increase in large raw image datasets generated, improving computational strategies for image segmentation and s ...

Nature Portfolio2024

Why computational complexity may set impenetrable barriers for epistemic reductionism

Michael Herzog, Christian Sachse, Adrien Christophe Doerig

According to physicalism, everything is physical or metaphysically connected to the physical. If physicalism were true, it seems that we should - in principle - be able to reduce the descriptions and explanations of special sciences to physical ones, for e ...

Springer2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Siam Publications2023

Attenuated Self-Interference Synchrophasor Estimation: the SOGI Interpolated DFT

Mario Paolone, Cesar Garcia Veloso

In this paper, a synchrophasor estimation (SE) algorithm is presented to simultaneously comply with the requirements for the P and M phasor measurement unit (PMU) performance classes. The method employs a second-order generalized integrator (SOGI) quadratu ...

IEEE2023

Homothetic Tube Model Predictive Control With Multi-Step Predictors

Giancarlo Ferrari Trecate, Danilo Saccani, Melanie Nicole Zeilinger

We present a robust model predictive control (MPC) framework for linear systems facing bounded parametric uncertainty and bounded disturbances. Our approach deviates from standard MPC formulations by integrating multi-step predictors, which provide reduced ...

Ieee-Inst Electrical Electronics Engineers Inc2023

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

2023

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Colin Neil Jones, Yuning Jiang, Yingzhao Lian, Xinliang Dai

This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...

IEEE2023

Page 2 sur 2