Computer Science News

We are pleased to announce that Dr Teddy Cunningham has been awarded a Faculty of Science, Engineering, and Medicine (SEM) PhD Thesis Prize. Each year, the SEM Faculty funds a prize for the best PhD/EngD thesis entered into the competition. Each department nominates a winner out of the applications received after a judging process as determined by the Faculty.

Teddy’s thesis is titled “Generating and Sharing Differentially Private Spatio-Temporal Data Using Real-World Knowledge”, and was supervised by Prof Hakan Ferhatosmanoglu. The thesis includes solutions for sharing trajectory data using local differential privacy, and incorporating constraints and relationships of data records into differential privacy that improves their utility while preserving the theoretical privacy guarantees. An example application is using road network information for improving the quality of privately shared location datasets.

Researchers from the Systems and Security theme, Department of Computer Science have created a new spin-out company, SEEV Technologies Ltd, to build end-to-end (E2E) verifiable e-voting systems for future elections. An E2E verifiable voting system allows every voter to verify that their vote is properly cast-as-intended, recorded-as-cast and tallied-as-recorded while preserving the voter's privacy. SEEV (self-enforcing e-voting) is a new paradigm of E2E voting technology that enables voters to fully verify the tallying integrity of an election without needing any trustworthy tallying authority, hence the system is "self-enforcing".

This joint spin-out from the University of Warwick and Newcastle University is built on an ERC-funded starting grant ("Self-Enforcing E-Voting System: Trustworthy Election in Presence of Corrupt Authorities", No. 306994, PI: Professor Feng Hao) initially hosted at Newcastle University and later transferred to the University of Warwick. The company is co-founded by Professor Feng Hao and Dr Siamak Shandahshti (co-inventors), and led by Dr Stewart Hefferman (CEO). SEEV has been prototyped and successfully tested in several trials in the past, supported by an ERC Proof of Concept grant (No. 677124), a Royal Society International collaboration award (CA\R1\180226), and an Innovate UK Cybersecurity Academic Startup Accelerator Programme (CASAP). SEEV Technologies Ltd has received seed funding from Oxford-based Global Initiative to build SEEV systems for real-world elections.

A University of Warwick press release is here.

Edgaras Purauskas, Technician in the Department of Computer Science received the Warwick Technician Commitment Award for Outstanding Achievement. Edgaras was one of two recipients of these inaugural awards, which received over 40 nominations campus wide. Edgaras had a number of nominations for his "consistently exceptional work" and his "deep understanding of computer systems, software, and hardware". Many congratulations Edgaras and thank you for your extraordinary efforts!

Five papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023), the IEEE flagship conference in theoretical computer science that will be held on November 6 - 9, 2023 in Santa Cruz, California, USA:

• "Chasing positive bodies" by Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak.
• "Dynamic (1+epsilon)-approximate matching size in truly sublinear update time" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
• "Polynomial-time pseudodeterministic construction of primes" by Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.
• "Approximating edit distance in the fully dynamic model" by Tomasz Kociumaka, Anish Mukherjee, and Barna Saha.
• "Traversing combinatorial 0/1-polytopes via optimization" by Arturo Merino and Torsten Mütze.

We are happy to announce that Dr Gihan Mudalige and Dr Victor Sanchez have both been promoted to Professor from 1st August 2023.

Many congratulations to our colleagues for all their achievements!

Professor Edmund Rolls is pleased to announce the publication of his 16th book, Rolls,E.T. (2023) Brain Computations and Connectivity. Oxford University Press: Oxford. Open Access.

Brain Computations and Connectivity provides a computational framework for understanding brain function in health and disease. The book also describes many discoveries on the computational functions of many brain regions.

The book includes research performed with many members of the Department of Computer Science including Professor Jianfeng Feng. The Gatsby Foundation is thanked for a grant towards the cost of enabling this book to be Open Access. A link to the book is available here.

Henry Sinclair-Banks, a PhD student in the the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP), has won a Best Paper Award at ICALP 2023, the 50th EATCS International Colloquium on Automata, Languages and Programming. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS).

Henry's paper, co-authored with researchers from Germany and Poland: Marvin Künnemann, Filip Mazowiecki, Lia Schütze, and Karol Węgrzycki, addresses the coverability problem in vector addition systems (VASS), a well-known model of concurrent systems. Coverability is an algorithmic problem for the verification of "safety properties": whether the system always avoids a set of bad states. Henry and his co-authors determine how much time is required to solve this problem in the worst case. They develop an algorithm that improves upon the state of the art that has stood for forty years. They also prove that, in several settings, it is impossible to decide coverability substantially faster, unless there is also a faster algorithm for a classic problem such as Boolean satisfiability (SAT) and finding cycles of fixed length in graphs.

In total, 5 Warwick papers will appear at this year's ICALP:

• Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti, "The complexity of Presburger arithmetic with power or powers",
• Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra, "Optimal (degree+1)-coloring in congested clique",
• Charilaos Efthymiou and Weiming Feng, "On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)",
• Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Węgrzycki, "Coverability in VASS revisited: Improving Rackoff's bound to obtain conditional optimality",
• Konstantinos Zampetakis and Charilaos Efthymiou, "Broadcasting with random matrices".

This July's ICALP will be the 50th edition of the conference.