Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Principe des tiroirs

Résumé

En mathématiques, le principe des tiroirs de Dirichlet, affirme que, sans perte de généralité, si n chaussettes sont rangées dans m

Source officielle

https://fr.wikipedia.org/wiki/Principe_des_tiroirs

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (4)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (9)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (13)

Afficher plus

Séances de cours associées

Chargement

Scalable Bias-Resistant Distributed Randomness

Bryan Alexander Ford, Nicolas Gailly, Linus Gasser, Philipp Svetolik Jovanovic, Ismail Khoffi, Eleftherios Kokoris Kogias

Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

Ieee2017

Chargement

We introduce the

N\times N

random matrices

X_{j,k}=\exp\left(2\pi i \sum_{q=1}^d\ \omega_{j,q} k^q\right) \quad \text{with } \{\omega_{j,q}\}_{\substack{1\leq j\leq N\\ 1\leq q\leq d}} \text{ i.i.d. random variables},

and

d

a fixed integer. We prove that the distribution of their singular values converges to the local Marchenko-Pastur law at scales

N^{-\theta_d}

for an explicit, small

\theta_d>0

, as long as

d\geq 18

. To our knowledge, this is the first instance of a random matrix ensemble that is explicitly defined in terms of only

O(N)

random variables exhibiting a universal local spectral law. Our main technical contribution is to derive concentration bounds for the Stieltjes transform that simultaneously take into account stochastic and oscillatory cancellations. Important ingredients in our proof are strong estimates on the number of solutions to Diophantine equations (in the form of Vinogradov's main conjecture recently proved by Bourgain-Demeter-Guth) and a pigeonhole argument that combines the Ward identity with an algebraic uniqueness condition for Diophantine equations derived from the Newton-Girard identities.

2020

Chargement

Complex index refraction tomography with sub ?/6-resolution

Yann Jérôme Michel Pascal Cotte, Christian Depeursinge, Nicolas Pavillon

The present invention discloses a method to improve the image resolution of a microscope. This improvement is based on the mathematical processing of the complex field computed from the measurements with a microscope of the wave emitted or scattered by the specimen. This wave is, in a preferred embodiment, electromagnetic or optical for an optical microscope, but can be also of different kind like acoustical or matter waves. The disclosed invention makes use of the quantitative phase microscopy techniques known in the sate of the art or to be invented. In a preferred embodiment, the complex field provided by Digital Holographic Microscopy (DHM), but any kind of microscopy derived from quantitative phase microscopy: modified DIC, Shack- Hartmann wavefront analyzer or any analyzer derived from a similar principle, such as multi-level lateral shearing interferometers or common-path interferometers, or devices that convert stacks of intensity images (transport if intensity techniques: TIT) into quantitative phase image can be used, provided that they deliver a comprehensive measure of the complex scattered wavefield. The hereby-disclosed method delivers superresolution microscopic images of the specimen, i.e. images with a resolution beyond the Rayleigh limit of the microscope. It is shown that the limit of resolution with coherent illumination can be improved by a factor of 6 at least. It is taught that the gain in resolution arises from the mathematical digital processing of the phase as well as of the amplitude of the complex field scattered by the observed specimen. In a first embodiment, the invention teaches how the experimental observation of systematically occurring phase singularities in phase imaging of sub-Rayleigh distanced objects can be exploited to relate the locus of the phase singularities to the sub-Rayleigh distance of point sources, not resolved in usual diffraction limited microscopy. In a second, preferred imbodiment, the disclosed method teaches how the image resolution is improved by complex deconvolution. Accessing the object's scattered complex field - containing the information coded in the phase - and deconvolving it with the reconstructed complex transfer function (CTF) is at the basis of the disclosed method. In a third, preferred imbodiment, it is taught how the concept of "Synthetic Coherent Transfer Function" (SCTF), based on Debye scalar or Vector model includes experimental parameters of MO and how the experimental Amplitude Point Spread Functions (APSF) are used for the SCTF determination. It is also taught how to derive APSF from the measurement of the complex field scattered by a nanohole in a metallic film. In a fourth imbodiment, the invention teaches how the limit of resolution can be extended to a limit of ?/6 or smaller based angular scanning. In a fifth imbodiment, the invention teaches how the presented method can generalized to a tomographic approach that ultimately results in super-resolved 3D refractive index reconstruction.

2011

Chargement

We introduce the

N\times N

random matrices

X_{j,k}=\exp\left(2\pi i \sum_{q=1}^d\ \omega_{j,q} k^q\right) \quad \text{with } \{\omega_{j,q}\}_{\substack{1\leq j\leq N\\ 1\leq q\leq d}} \text{ i.i.d. random variables},

and

d

a fixed integer. We prove that the distribution of their singular values converges to the local Marchenko-Pastur law at scales

N^{-\theta_d}

for an explicit, small

\theta_d>0

, as long as

d\geq 18

. To our knowledge, this is the first instance of a random matrix ensemble that is explicitly defined in terms of only

O(N)

2020

Complex index refraction tomography with sub ?/6-resolution

Yann Jérôme Michel Pascal Cotte, Christian Depeursinge, Nicolas Pavillon

2011