Summary
Combinatorial Construction is a mathematical challenge with many applications. Examples include the construction of networks that are very sparse but highly connected, or codes that can correct many transmission errors with little overhead in communication costs. For a general class of combinatorial objects, and some desirable property, the fundamental question in Combinatorial Construction is to demonstrate the existence of an object with the property, preferably via an explicit algorithmic construction. Thus it is ubiquitous in Computer Science, including applications to expanders, sorting networks, distributed communication, data storage, codes, cryptography and derandomisation. In popular culture it appears as the unsolved `lottery problem' of determining the minimum number of tickets that guarantee a prize. In a recent preprint I prove the Existence Conjecture for combinatorial designs, via a new method of Randomised Algebraic Constructions; this result has already attracted considerable attention in the mathematical community. The significance is not only in the solution of a problem posed by Steiner in 1852, but also in the discovery of a powerful new method, that promises to have many further applications in Combinatorics, and more widely in Mathematics and Theoretical Computer Science. I am now poised to resolve many other problems of combinatorial construction.
Unfold all
/
Fold all
More information & hyperlinks
| Web resources: | https://cordis.europa.eu/project/id/647678 |
| Start date: | 01-01-2016 |
| End date: | 30-06-2021 |
| Total budget - Public funding: | 1 706 729,00 Euro - 1 706 729,00 Euro |
Cordis data
Original description
Combinatorial Construction is a mathematical challenge with many applications. Examples include the construction of networks that are very sparse but highly connected, or codes that can correct many transmission errors with little overhead in communication costs. For a general class of combinatorial objects, and some desirable property, the fundamental question in Combinatorial Construction is to demonstrate the existence of an object with the property, preferably via an explicit algorithmic construction. Thus it is ubiquitous in Computer Science, including applications to expanders, sorting networks, distributed communication, data storage, codes, cryptography and derandomisation. In popular culture it appears as the unsolved `lottery problem' of determining the minimum number of tickets that guarantee a prize. In a recent preprint I prove the Existence Conjecture for combinatorial designs, via a new method of Randomised Algebraic Constructions; this result has already attracted considerable attention in the mathematical community. The significance is not only in the solution of a problem posed by Steiner in 1852, but also in the discovery of a powerful new method, that promises to have many further applications in Combinatorics, and more widely in Mathematics and Theoretical Computer Science. I am now poised to resolve many other problems of combinatorial construction.Status
CLOSEDCall topic
ERC-CoG-2014Update Date
27-04-2024
Images
No images available.
Geographical location(s)
