Turan-type problems and probabilistic methods in extremal combinatorics

这项建议涉及极值和概率组合学的研究。广义地说，极值组合学解决了组合对象的大小的存在和理论界限，并施加了某些局部限制。许多重要的问题，虽然陈述简单和吸引人，但往往代表了数学中更普遍的现象，并导致许多意想不到的和有用的应用在其他领域。例如，扩展图和Ramanujan图的主题对编码、复杂性和信息论产生了重大影响。这些问题还导致了新的理论方法，其中最引人注目的例子可能是著名数学家保罗·鄂尔多斯开创的概率方法。极值组合方法导致构造用于纠正数据传输中的错误的新的和更有效的代码，减少了蒙特卡罗算法所需的比特数，例如用于素性测试的随机算法。事实上，最近用于素性测试的确定性算法的惊人突破与之前的随机算法高度相关，这些算法早已存在。在我的提案中，我计划进一步研究理论和实际应用，包括矩阵乘法的时间复杂性问题，二次筛型整数分解算法，以及其他数学领域的问题。在数学上，这项工作涉及泛函分析、射影几何、谱图理论、编码理论和算法。虽然这些悬而未决的问题很重要，但通过将概率和组合技术与一些新思想结合起来，一些重大的进展是可能的。组合数学位于许多现代运算的核心，如数字安全、网络搜索和可靠的数据传输。例如，用于定性网络搜索的大型数字数组的乘法--这些矩阵往往有数十亿行和列；RSA密码系统，它是现代数字安全的基础，它强烈地基于这样一种信念：整数的因式分解是困难的；最后，在嘈杂或不可靠的信道上传输数据是编码理论的核心，人们试图设计新的消息编码方法，以便即使消息在传输过程中受到干扰，接收者仍然可以很高概率地找出原始消息是什么。构造这样好的纠错码的主要因素之一是存在称为扩展图的组合对象。使用这些对象的显式结构和变体，以及基本的概率参数，可以以最佳方式压缩消息，使得接收者有极好的机会弄清楚原始消息是什么。具有这种极值性质的图的构造是所提出的研究的基础。此外，研究人员计划使用组合和概率技术来解决矩阵乘法和整数因式分解问题，这两个问题都是上面列出的具体例子的核心。研究人员计划对上述组合和概率方法的实际和理论应用进行研究。

This proposal concerns research in extremal and probabilistic combinatorics. Broadly speaking, extremal combinatorics addresses the existence of and theoretical bounds on the sizes of combinatorial objects with certain local restrictions imposed. Many of the important problems, while simple to state and attractive, are often representative of more general phenomena in mathematics, and lead to many unexpected and useful applications in other areas. For example, the topics of expander graphs and Ramanujan graphs have had a major impact on coding, complexity and information theory. These problems also lead to new theoretical methods, perhaps the most remarkable instance of which is the probabilistic method pioneered by the renowned mathematician Paul Erdos. Extremal combinatorial methods lead to the construction of new and more efficient codes for correcting errors in data transmission, the reduction of the number of bits required for Monte-Carlo algorithms, such as randomized algorithms for primality testing. In fact, the spectacular recent breakthrough of a deterministic algorithm for primality testing is highly connected to preceding randomized algorithms which were long known to exist. In my proposal I plan to study further theoretical and practical applications, including the problem of time-complexity of matrix multiplication, quadratic sieve-type integer factoring algorithms, and questions in other areas of mathematics. In mathematics, this work has implications in functional analysis, projective geometry, spectral graph theory, coding theory, and algorithms. While these open problems are important and clearly difficult, some major inroads are possible by combining probabilistic and combinatorial techniques with some new ideas.Combinatorial mathematics lies at the heart of many modern-day operations, such as digital security, web searching, and reliable data transmission. Examples include multiplication of large arrays of numbers for qualitative web searches -- these matrices tend to have billions of rows and columns; the RSA cryptosystem, which underpins much of modern digital security, and is based strongly on the belief that factoring integers is difficult; finally, transmission of data over noisy or unreliable channels is at the core of coding theory, where one attempts to design novel ways of encoding a message so that even if the message is perturbed in transmission, the receiver can still figure out with high probability what the original message was. One of the major ingredients for constructing such good error-correcting codes is the existence of combinatorial objects known as expander graphs. Using explicit constructions and variants of these objects, together with basic probabilistic arguments, one can compress a message in an optimal way such that the receiver has an excellent chance of figuring out what the original message was. Constructions of graphs with such extremal properties is fundamental to the proposed research. In addition, the researcher plans to use combinatorial and probabilistic techniques to approach the problems of matrix multiplication and integer factoring, both of which are central to the concrete examples listed above. The researcher plans to investigate both the practical and theoretical applications of the above-mentioned combinatorial and probabilistic methods.