The Centre for Discrete Mathematics and its Applications (DIMAP)
Lead Research Organisation:
University of Warwick
Department Name: Computer Science
Abstract
Discrete Mathematics plays an essential role in modelling the natural world (e.g., the genome) and the technological world (e.g., the internet), and in designing efficient solutions such as gene-sequencing algorithms and internet routing protocols. It is well known that the UK has a serious lack of capacity in this increasingly important area. This has been highlighted in three International Reviews (Computer Science, Mathematics and OR) and by independent industry reports such as that from the Smith Institute. Discrete Mathematics is a fundamentally multi-disciplinary activity. The close connections among algorithmic work being done primarily in computer science departments, combinatorial work primarily in mathematics departments, and optimisation work primarily in OR research groups in business schools, strongly suggest that the lack of capacity in these inter-related areas will be best addressed by developing a new centre with a unified, collaborative strategy. The EPSRC Science and Innovation scheme, focussing on both the interface of mathematics and computer science, and the fundamentals of operational research, reinforces this view. We propose to enhance capacity in this area substantially by founding the Centre for Discrete Mathematics and its Applications, rooted in three internationally recognised departments at the University of Warwick: Computer Science, Mathematics and the Business School. The key deliverables resulting from an initial investment of 3.62M from EPSRC/HEFCE, combined with substantial and continuing support by the University, will be:o a strong multi-disciplinary research centre in the adjacent new Computer Science and Mathematics buildings, directed by an Executive Team of Profs M Paterson FRS, AM Stuart, B Chen and Dr LA Goldberg supporting an internationally competitive programme of research in discrete modelling, algorithmic analysis and operational research;o the recruitment of three new lecturers, one in each department, on attractive terms and with permanent contracts to ensure highest quality appointments; o the recruitment of a new professor in Discrete Mathematics and its Applications in Algorithms within the Department of Computer Science;o an ongoing stream of postdoctoral RA's, building from an initial group of four to be recruited under the EPSRC/HEFCE grant;o a training strategy comprising: - a doctoral training centre offering 4-year PhD's. Two new students would be recruited each year for 5 years under the EPSRC/HEFCE grant, with others funded through CASE awards and the DTA programme; - a new stream within the 4-year Computer Science MEng degree with modules from mathematics and OR and focussing on discrete mathematics;o an Industrial Affiliates Programme, for industrial and other users to communicate their needs within the discrete mathematics area, and to collaborate with the Centre in developing solutions and transferring knowledge;o the development of collaborations, rooted in discrete maths, involving researchers at other UK universities.Strong management by the Executive Team will ensure that the Centre delivers impact through high quality research advancing knowledge in discrete mathematics, algorithms, and fundamentals of operational research and giving a significant boost to UK industry, capacity by increasing the UK's production of trained researchers in this area, sustainability by securing the long-term future through research and training, knowledge transfer via the usual publication routes and the Industrial Affiliates Programme, and timeliness by ensuring that projected schedules are met to address the UK's current problems. The added value from this Award would arise from the opportunity to focus and coordinate the excellent research currently undertaken across three departments.
Publications
Tiskin A
(2013)
Fast Distance Multiplication of Unit-Monge Matrices
in Algorithmica
Bampis E
(2013)
Energy Efficient Scheduling and Routing via Randomized Rounding
Fearnley J
(2013)
Automata, Languages, and Programming
Bienkowski M
(2013)
Automata, Languages, and Programming
Adamaszek M
(2013)
Clique complexes and graph powers
in Israel Journal of Mathematics
Czumaj A
(2013)
(1 + e)-Approximation for Facility Location in Data Streams
Dabrowski K
(2013)
New results on maximum induced matchings in bipartite graphs and beyond
in Theoretical Computer Science
Demri S
(2013)
The covering and boundedness problems for branching vector addition systems
in Journal of Computer and System Sciences
Fearnley J
(2013)
Reachability in Two-Clock Timed Automata is PSPACE-complete
Hatami H
(2013)
On the number of pentagons in triangle-free graphs
in Journal of Combinatorial Theory, Series A
Englert M
(2012)
Considering Suppressed Packets Improves Buffer Management in Quality of Service Switches
in SIAM Journal on Computing
Dabrowski K
(2012)
Colouring vertices of triangle-free graphs without forests
in Discrete Mathematics
Czumaj A
(2012)
Finding cycles and trees in sublinear time
in Random Structures & Algorithms
Adamaszek M
(2012)
Splittings of independence complexes and the powers of cycles
in Journal of Combinatorial Theory, Series A
Adamaszek M
(2012)
Comparing minimal simplicial models
in Journal of Homotopy and Related Structures
CZUMAJ A
(2012)
APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN
in International Journal of Foundations of Computer Science
Adamaszek A
(2012)
An O (log k )-competitive algorithm for generalized caching
Adamaszek M
(2012)
Dense flag triangulations of 3-manifolds via extremal graph theory
Berenbrink P
(2012)
Multiple-choice balanced allocation in (almost) parallel
Allen P
(2012)
Turánnical hypergraphs
in Random Structures & Algorithms
Adamaszek A
(2012)
Optimal online buffer scheduling for block devices
HATAMI H
(2012)
Non-Three-Colourable Common Graphs Exist
in Combinatorics, Probability and Computing
Karanikolas N
(2011)
Solution to Exchanges 9.1 puzzle borrowing as cheaply as possible
in ACM SIGecom Exchanges
Goldberg P
(2011)
Algorithms - ESA 2011
Allen P
(2011)
Filling the gap between Turán's theorem and Pósa's conjecture
in Journal of the London Mathematical Society
Allen P
(2011)
A density Corrádi-Hajnal theorem
in Electronic Notes in Discrete Mathematics
Adamaszek A
(2011)
Automata, Languages and Programming
Adamaszek M
(2011)
On a lower bound for the connectivity of the independence complex of a graph
in Discrete Mathematics
Adamaszek A
(2011)
Almost tight bounds for reordering buffer management
Aziz H
(2011)
False-Name Manipulations in Weighted Voting Games
in Journal of Artificial Intelligence Research
Czumaj A
(2011)
Planar Graphs: Random Walks and Bipartiteness Testing
ADAMASZEK A
(2011)
PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
in International Journal of Foundations of Computer Science
Adamaszek A
(2011)
Uniqueness of Graph Square Roots of Girth Six
in The Electronic Journal of Combinatorics
Adamaszek M
(2011)
Extremal problems related to Betti numbers of flag complexes
Czumaj A
(2011)
Fast message dissemination in random geometric networks
in Distributed Computing
Adamaszek M
(2010)
Testing Monotone Continuous Distributions on High-dimensional Real Cubes
Christofides D
(2010)
Hamilton cycles in dense vertex-transitive graphs
Krusche P
(2010)
Parallel Processing and Applied Mathematics
Bodlaender H
(2010)
Treewidth computations I. Upper bounds
in Information and Computation
Adamaszek M
(2010)
Topology and subsets - the story of a theorem
Czumaj A
(2010)
Algorithms - ESA 2010
Adamaszek M
(2010)
Property Testing
Chakrabort S
(2010)
Two-phase algorithms for the parametric shortest path problem
Adamaszek A
(2010)
Large-Girth Roots of Graphs
in SIAM Journal on Discrete Mathematics
Fearnley J
(2010)
SOFSEM 2010: Theory and Practice of Computer Science
Czumaj A
(2010)
Selfish Traffic Allocation for Server Farms
in SIAM Journal on Computing
Czumaj A
(2010)
Encyclopedia of Machine Learning
Description | DIMAP - which is the research centre funded by this EPSRC project - is a very successful research centre that enhanced Warwick's and UK's reputation in mathematical and computer science communities in the UK, in Europe, and around the world. It promotes cutting edge research in discrete mathematics and combinatorics, theoretical aspects of computer science, and mathematical aspects of operations research. Its positive impact on the UK mathematics scene has been cited in the International Reviews of Mathematical Sciences 2010 and DIMAP is widely recognized as a UK centre of excellence in algorithms. Since its creation in 2007, DIMAP has become a recognised brand name in the mathematical and computer science communities around the world. Its excellent research environment - thanks to its renowned academic staff and its scientific activities - made DIMAP an excellent place to work at and visit. Largely thanks to DIMAP, Warwick has succeeded in several high profile appointments, like Dr Coja-Oghlan (ERC winner), Prof Cormode (ERC winner), Dr Georgakopoulos (ERC winner), Prof Král (ERC winner)', Prof Pikhurko (ERC winner), Dr Räcke, Prof Sviridenko, doubling the number of Warwick academic staff in core DIMAP areas. Most of DIMAP key members have significant individual research grants (which is not necessarily a UK standard in theoretical areas as those in the focus of DIMAP), including several ERC grants, many EPSRC grants, Royal Society Wolfson Merit Awards, etc. Grant income of DIMAP members together with the excellent research environment in DIMAP and its reputation, allowed DIMAP to maintain a steady number of high quality postdocs and PhD students. It's extremely unlikely that these things could have happened without DIMAP. DIMAP's research activities, like its extensive programme of scientific seminars and international workshops and conferences, have brought to the UK and to Warwick many leading researchers from around the world, including Turing Award winners, Nevanlinna Prize winners, Gödel Prize winners, European Prize in Combinatorics winners, etc. DIMAP has also played key role in establishing in October 2008 a new BSc degree course Discrete Mathematics, offered jointly by the Department of Computer Science and the Warwick Mathematics Institute. Current total number of students is over 100 across all years. |
Exploitation Route | The funding allowed the UK to enhance its international standing in discrete mathematics, theoretical computer science, and mathematical aspects of OR. We believe that this will have a positive long-term impact on the UK research in these areas and beyond, and will allow the UK to be one of the most world best centres of excellence in the very hot areas on the interface of mathematics, computer science, and operational research. |
Sectors | Digital/Communication/Information Technologies (including Software) Other |
URL | http://www2.warwick.ac.uk/dimap/ |