The Complexity of Renaming

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.

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

The rapid development of wearable biomedical systems now enables real-time monitoring of electroencephalography (EEG) signals. Acquisition of these signals relies on electrodes. These systems must meet the design challenge of selecting an optimal set of el ...

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In this paper, we propose an analytical stochastic dynamic programming (SDP) algorithm to address the optimal management problem of price-maker community energy storage. As a price-maker, energy storage smooths price differences, thus decreasing energy arb ...

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. ...

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 ...

Modern digital connectivity has necessitated the creation of robust methods for securely storing and transferring data. At the heart of all security infrastructure is the random number generator (RNG). While random numbers find use in a variety of applicat ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

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 ...

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 ...

Characterizing the genetic structure of large cohorts has become increasingly important as genetic studies extend to massive, increasingly diverse biobanks. Popular methods decompose individual genomes into fractional cluster assignments with each cluster ...

Quantum random number generators (QRNGs) are a burgeoning technology used for a variety of applications, including modern security and encryption systems. Typical methods exploit an entropy source combined with an extraction or bit generation circuit in or ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Tensor trains are a versatile tool to compress and work with high-dimensional data and functions. In this work we introduce the streaming tensor train approximation (STTA), a new class of algorithms for approximating a given tensor ' in the tensor train fo ...

Electric vehicle charging facilities offer their capacity constrained electric charge and parking to users for a fee. As electric vehicle adoption grows, so too does the potential for excessive resource utilization. In this paper, we study how prices set b ...

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

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 ...

The Complexity of Renaming

Chattez avec Graph Search

Planetary-Scale Byzantine Fault Tolerance

Orthologic with Axioms

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

FETCH: A Fast and Efficient Technique for Channel Selection in EEG Wearable Systems

A ride time-oriented scheduling algorithm for dial-a-ride problems

Energy Management of Price-Maker Community Energy Storage by Stochastic Dynamic Programming

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Results on Sparse Integer Programming and Geometric Independent Sets

Modelling and design of CMOS SPAD sensors for quantum random number generation

Approximation Algorithms for Allocation and Network Design

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

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Neural ADMIXTURE for rapid genomic clustering

A 3.3-Gb/s SPAD-Based Quantum Random Number Generator

Better Trees for Santa Claus

STREAMING TENSOR TRAIN APPROXIMATION

Resource aware pricing for electric vehicle charging

Minimum Cost Intervention Design for Causal Effect Identification

Unambiguous DNFs and Alon-Saks-Seymour

On Semi-Algebraic Proofs and Algorithms