Concept

Cramér's conjecture

Related publications (33)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Nisheeth Vishnoi

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ1 with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough n, there is an n-point negative ...

Association for Computing Machinery2015

Affine congruences and rational points on a certain cubic surface

Pierre Francis André Le Boudec

We establish estimates for the number of solutions of certain affine congruences. These estimates are then used to prove Manin's conjecture for a cubic surface split over Q whose singularity type is D-4. This improves on a result of Browning and answers a ...

Mathematical Science Publ2014

Optimal asymptotic bounds for spherical designs

Maryna Viazovska

In this paper we prove the conjecture of Korevaar and Meyers: for each N≥cdtd, there exists a spherical t-design in the sphere Sd consisting of N points, where cd is a constant depending only on d. ...

2013

Proof of a conjecture by Gazeau et al. using the Gould-Hopper polynomials

Olivier Lévêque

We provide here some probabilistic interpretations of the generalized binomial distributions proposed by Gazeau et al. ["Generating functions for generalized binomial distributions," J. Math. Phys. 53, 103304 (2012)]. In the second part, we prove the "stro ...

Amer Inst Physics2013

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013

Tight Bounds on the Redundancy of Huffman Codes

Ali Kakhbod

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman c ...

Ieee-Inst Electrical Electronics Engineers Inc2012

Quantum fluctuations of one-dimensional free fermions and Fisher-Hartwig formula for Toeplitz determinants

We revisit the problem of finding the probability distribution of a fermionic number of one-dimensional spinless free fermions on a segment of a given length. The generating function for this probability distribution can be expressed as a determinant of a ...

2011

Conway's conjecture for monotone thrackles

János Pach

A drawing of a graph in the plane is called a thrackle if every pair of edges meet precisely once, either at a common vertex or at a proper crossing. According to Conway's conjecture, every thrackle has at most as many edges as vertices. We prove this conj ...

Mathematical Association of America2011

Holography from conformal field theory

The locality of bulk physics at distances below the AdS length scale is one of the remarkable aspects of AdS/CFT duality, and one of the least tested. It requires that the AdS radius be large compared to the Planck length and the string length. In the CFT ...

Springer2009

A new REM conjecture

Véronique Gayrard

We introduce here a new universality conjecture for levels of random Hamiltonians, in the same spirit, as the local REM conjecture made by S. Mertens and H. Bauke. We establish our conjecture for a wide class of Gaussian and non-Gaussian Hamiltonians, whic ...

Birkhauser Boston, C/O Springer-Verlag, Service Center, 44 Hartz Way, Secaucus, Nj 07096-2491 Usa2008