Epsilon

Résumé

Epsilon (capitale Ε, minuscule ε ; en grec έψιλον), est la lettre de l'alphabet grec, précédée par delta et suivie par zêta. Dérivée de la lettre he x12px de l'alphabet phénicien, elle est l'ancêtre des lettres E et Ɛ (epsilon) de l'alphabet latin, et des lettres Е et Є de l'alphabet cyrillique et de leurs formes diacritées ou culbutées. Usage Grec En grec ancien, epsilon représente, suivant les dialectes, la voyelle mi-fermée antérieure non arrondie courte , sa forme longue ou la voyelle mi-ouverte antérieure non arrondie longue . En grec moderne, elle représente la voyelle mi-fermée antérieure non arrondie . Dans le système de numération grecque, epsilon vaut 5. Sciences

En mathématiques : ** ε est la notation traditionnelle (francophone) du majorant de l'écartement de la fonction dans la définition formelle de la continuité. ** Plus généralement, ε est utilisé pour désigner de petits nombres, relativement au contexte. ** ε est parfois dans

Source officielle

À 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

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Mohsen Ghaffari, Slobodan Mitrovic

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum vertex cover, for any n-vertex graph and any constant epsilon > 0. These improve the state of the art as follows: Our MIS algorithm leads to a simple O(log log A)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the (O) over tilde(root log Delta)-round algorithm of Ghaffari [PODC'17]. Our O(log log(2) n)-round (1 + epsilon)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 log n)-round (1 + epsilon)-approximation algorithm of Czumaj et al. [STOC'18] and O(log log n)-round (1 + epsilon) approximation algorithm of Assadi et al. [arXiv'17]. Our O(log log n)-round (2 + epsilon)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)-approximation of Assadi et al. [arXiv'17].

ASSOC COMPUTING MACHINERY2018

Chargement

Bounds on multiscalar CFTs in the epsilon expansion

Matthijs Jan Hogervorst

We study fixed points with N scalar fields in 4 - epsilon dimensions to leading order in epsilon using a bottom-up approach. We do so by analyzing O(N) invariants of the quartic coupling lambda(ijkl) that describes such CFTs. In particular, we show that lambda(iijj) and lambda ijkl2 are restricted to a specific domain, refining a result by Rychkov and Stergiou. We also study averages of one-loop anomalous dimensions of composite operators without gradients. In many cases, we are able to show that the O(N) fixed point maximizes such averages. In the final part of this work, we generalize our results to theories with N complex scalars and to bosonic QED. In particular we show that to leading order in epsilon, there are no bosonic QED fixed points with N < 183 flavors.

SPRINGER2021

Chargement

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C is an element of X, it holds that Sigma(x is an element of S) w(x).d(z) (x, C) is an element of (1 +/- epsilon) . Sigma(x is an element of X) d(z) (x, C). We present an efficient algorithm that constructs an epsilon-coreset for the (k, z)-clustering problem in M(X, d), where the size of the coreset only depends on the parameters k, z, epsilon and the doubling dimension ddim(M). To the best of our knowledge, this is the first efficient epsilon-coreset construction of size independent of vertical bar X vertical bar for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of M(X, d) and the shattering dimension (or VC-dimension) of the range space induced by the distance d. Such a relation is not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small (1 +/- epsilon)-distortion of the distance function d (the distorted distance is called the smoothed distance function), the shattering dimension can be upper bounded by O(epsilon(-O(ddim(M)))). For the purpose of coreset construction, the above bound does not suffice as it only works for unweighted spaces. Therefore, we introduce the notion of tau-error probabilistic shattering dimension, and prove a (drastically better) upper bound of O(ddim(M).log(1/epsilon)+log log 1/tau) for the probabilistic shattering dimension for weighted doubling metrics. As it turns out, an upper bound for the probabilistic shattering dimension is enough for constructing a small coreset. We believe the new relation between doubling and shattering dimensions is of independent interest and may find other applications. Furthermore, we study robust coresets for (k, z)-clustering with outliers in a doubling metric. We show an improved connection between alpha-approximation and robust coresets. This also leads to improvement upon the previous best known bound of the size of robust coreset for Euclidean space [Feldman and Langberg, STOC 11]. The new bound entails a few new results in clustering and property testing. As another application, we show constant-sized (epsilon, k, z)-centroid sets in doubling metrics can be constructed by extending our coreset construction. Prior to our result, constant-sized centroid sets for general clustering problems were only known for Euclidean spaces. We can apply our centroid set to accelerate the local search algorithm (studied in [Friggstad et al., FOCS 2016]) for the (k, z)-clustering problem in doubling metrics.

IEEE COMPUTER SOC2018

Chargement