1 |
On the Erdös-Turán conjecture and related resultsXiao, Stanley Yao January 2011 (has links)
The Erdös-Turán Conjecture, posed in 1941 in, states that if a subset B of natural numbers is such that every positive integer n can be written as the sum of a bounded number of terms from B, then the number of such representations must be unbounded as n tends to infinity. The case for h = 2 was given a positive answer by Erdös in 1956. The case for arbitrary h was given by Erdös and Tetali in 1990. Both of these proofs use the probabilistic method, and so the result only shows the existence of such bases but such bases are not given explicitly. Kolountzakis gave an effective algorithm that is polynomial with respect to the digits of n to compute such bases. Borwein, Choi, and Chu showed that the number of representations cannot be bounded by 7. Van Vu showed that the Waring bases contain thin sub-bases. We will discuss these results in the following work.
|
2 |
On the Erdös-Turán conjecture and related resultsXiao, Stanley Yao January 2011 (has links)
The Erdös-Turán Conjecture, posed in 1941 in, states that if a subset B of natural numbers is such that every positive integer n can be written as the sum of a bounded number of terms from B, then the number of such representations must be unbounded as n tends to infinity. The case for h = 2 was given a positive answer by Erdös in 1956. The case for arbitrary h was given by Erdös and Tetali in 1990. Both of these proofs use the probabilistic method, and so the result only shows the existence of such bases but such bases are not given explicitly. Kolountzakis gave an effective algorithm that is polynomial with respect to the digits of n to compute such bases. Borwein, Choi, and Chu showed that the number of representations cannot be bounded by 7. Van Vu showed that the Waring bases contain thin sub-bases. We will discuss these results in the following work.
|
3 |
On Semi-definite Forms in AnalysisKlambauer, Gabriel 03 1900 (has links)
Using the representation theory of positive definite sequences some propositions in additive number theory are obtained and H. Bohr's approximation theorem is deduced. A unified approach to theorems by S. Bochner, S, N, Bernstein and H. Hamburger is discussed and some operator versions of numerical moment problems are studied. The Appendix contains comments to J. von Neumann's spectral theorem for self-adjoint operators in Hilbert space. / Thesis / Doctor of Philosophy (PhD)
|
4 |
Extração de aleatoriedade a partir de fontes defeituosas / Randomness extraction from weak random sourcesDellamonica Junior, Domingos 27 March 2007 (has links)
Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\". / Recently, Barak et al. (2004) constructed explicit deterministic extractors and dispersers (these are polynomial-time computable functions) with much better parameters than what was known before. We introduce the concepts involved in such a construction and mention some of its applications; in particular, we describe how it is possible to obtain much better bounds for the bipartite Ramsey problem (a very hard problem) using the machinery developed in that paper. We also present some original results that improve on these constructions. They are inspired by the work of Anup Rao (2005) and uses the recent breakthrough of Jean Bourgain (2005) in obtaining 2-source extractors that break the \"1/2-barrier\".
|
5 |
Extração de aleatoriedade a partir de fontes defeituosas / Randomness extraction from weak random sourcesDomingos Dellamonica Junior 27 March 2007 (has links)
Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\". / Recently, Barak et al. (2004) constructed explicit deterministic extractors and dispersers (these are polynomial-time computable functions) with much better parameters than what was known before. We introduce the concepts involved in such a construction and mention some of its applications; in particular, we describe how it is possible to obtain much better bounds for the bipartite Ramsey problem (a very hard problem) using the machinery developed in that paper. We also present some original results that improve on these constructions. They are inspired by the work of Anup Rao (2005) and uses the recent breakthrough of Jean Bourgain (2005) in obtaining 2-source extractors that break the \"1/2-barrier\".
|
Page generated in 0.0463 seconds