Zobrazeno 1 - 10
of 54
pro vyhledávání: '"Sandon, Colin"'
In 1948, Shannon used a probabilistic argument to show the existence of codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, based on polynomial evaluations, con
Externí odkaz:
http://arxiv.org/abs/2411.13493
Can Transformers predict new syllogisms by composing established ones? More generally, what type of targets can be learned by such models from scratch? Recent works show that Transformers can be Turing-complete in terms of expressivity, but this does
Externí odkaz:
http://arxiv.org/abs/2406.06467
Autor:
Abbe, Emmanuel, Sandon, Colin
This paper shows that a class of codes such as Reed-Muller (RM) codes have vanishing bit-error probability below capacity on symmetric channels. The proof relies on the notion of `camellia codes': a class of symmetric codes decomposable into `camelli
Externí odkaz:
http://arxiv.org/abs/2312.04329
Autor:
Abbe, Emmanuel, Sandon, Colin
Reed-Muller codes were introduced in 1954, with a simple explicit construction based on polynomial evaluations, and have long been conjectured to achieve Shannon capacity on symmetric channels. Major progress was made towards a proof over the last de
Externí odkaz:
http://arxiv.org/abs/2304.02509
Glauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of social networks, computer vision and other domains. In this work, we int
Externí odkaz:
http://arxiv.org/abs/2302.10841
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algor
Externí odkaz:
http://arxiv.org/abs/2210.05893
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abbe, Fan, Wan
Externí odkaz:
http://arxiv.org/abs/2203.11847
We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt u
Externí odkaz:
http://arxiv.org/abs/2108.04190
Community detection is the problem of identifying community structure in graphs. Often the graph is modeled as a sample from the Stochastic Block Model, in which each vertex belongs to a community. The probability that two vertices are connected by a
Externí odkaz:
http://arxiv.org/abs/2107.06338
In this work, we study the computational complexity of determining whether a machine learning model that perfectly fits the training data will generalizes to unseen data. In particular, we study the power of a malicious agent whose goal is to constru
Externí odkaz:
http://arxiv.org/abs/2106.08393