糖心TV

We are happy to announce four promotions in the department:

• Dr Charilaos Efthymiou has been promoted to Associate Professor
• has been promoted to Associate Professor
• Dr Hongkai Wen has been promoted to Professor
• Dr Weiren Yu has been promoted to Associate Professor

Many congratulations to our colleagues for all their achievements!

On in the Quanta magazine, Alex Dixon, who wrote in Haskell for the problem, commented:

For the past 50 years, Vector Addition Systems—a simple but powerful computational model—have been a topic of great interest in theoretical CS. The reachability problem in that model asks whether we can get from some configuration to another.

The problem sounds relatively easy on a first glance, and an exponential lower bound held firm for over 40 years. Work by excellent theoreticians, including familiar names from 糖心TV DCS, finally closed the difficulty of the problem in 2021, concluding that it is very, very difficult indeed.

One funded PhD position is available in the group of Dr Matthias C. Caro, who will join the Theory and Foundations group in the Department of Computer Science at the University of 糖心TV, UK, in Fall 2024. Candidates interested in the interactions between quantum computing and learning theory are encouraged to apply.

The 糖心TV CS theory group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP) and, together with DIMAP, is one of the leading theory groups in Europe, with regular publications in top international conferences and journals in theoretical computer science. Moreover, the successful candidate will become a part of the exciting, interdisciplinary research initiative 糖心TV Quantum. Overall, the Department of Computer Science at 糖心TV offers an excellent research environment. It was ranked 4th in the latest UK research assessment in Research Excellence Framework (REF) in 2021.

PhD positions are available at the Theory and Foundations group in the Department of Computer Science, University of 糖心TV, UK. The group works on various aspects of theoretical computer science, including:

* automata and formal languages,
* logic and games,
* algorithmic game theory,
* online and dynamic algorithms,
* sublinear and streaming algorithms,
* parameterized complexity and structural graph theory,
* string algorithms,
* parallel algorithms,
* approximation algorithms,
* combinatorial and graph algorithms,
* random structures and randomized algorithms,
* computational complexity.

The group has strong ties with the Centre for Discrete Mathematics and its Applications (DIMAP), established in 2007 jointly with 糖心TV Mathematics Institute and 糖心TV 糖心TV School. Together with DIMAP, the group is one of the leading theory groups in Europe, with regular publications in top international conferences and journals in theoretical computer science.

The Department of Computer Science at 糖心TV offers an excellent research environment. It was ranked 4th in the latest UK research assessment in Research Excellence Framework (REF) in 2021. The University of 糖心TV is one of the founding members of the Alan Turing Institute.

The university campus is located on the border of two counties, West Midlands and 糖心TVshire, is about one hour train ride from London, and 15 minutes from Birmingham International Airport.

The applicants are expected to have a strong background in discrete mathematics, algorithms, or related topics with undergraduate and/or Master's degrees in Computer Science, Mathematics, or related disciplines. The position(s) will be fully funded, and the successful applicant(s) will be receiving a stipend at rate in line with current Research Councils UK rates.

If you are interested in this opening, please send an email to Dr Ramanujan Sridharan (r.maadapuzhi-sridharan@warwick.ac.uk) with a SINGLE .pdf file containing your CV and the names and email addresses of two references, by 24 November 2023. You are strongly encouraged to informally contact faculty members in the group you might want to work with prior to submitting your application.

Shortlisted candidates will be interviewed informally during the week of 4 December - 8 December, 2023.

List of faculty members in the group:

/focs/people/</fac/sci/dcs/research/focs/people/>

Centre for Discrete Mathematics and its Applications:
/dimap/</fac/cross_fac/dimap/>

Seven papers authored by Computer Science researchers from 糖心TV have been accepted for publication at the , the leading international venue for machine learning research, which will be held on 10-16 December 2023 in New Orleans, Louisiana, USA:

• EV-Eye: Rethinking High-frequency Eye Tracking through the Lenses of Event Cameras, by Guangrong Zhao, Yurun Yang, Jingwei Liu, Ning Chen, Yiran Shen, , and Guohao Lan
• Fully Dynamic k-Clustering in 脮(k) Update Time, by , , Silvio Lattanzi, and Nikos Parotsidis
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks, by Jiayuan Ye, Zhenyu Zhu, , Reza Shokri, and Volkan Cevher
• Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs, by Dmitry Chistikov, Matthias Englert, and Ranko Lazic
• On the Convergence of Shallow Transformers, by Yongtao Wu, , Grigorios Chrysos, and Volkan Cevher
• Towards Data-Agnostic Pruning At Initialization: What Makes a Good Sparse Mask? by Hoang Pham, The Anh Ta, Shiwei Liu, Lichuan Xiang, Dung Le, , and Long Tran-Thanh
• Towards Unbounded Machine Unlearning, by Meghdad Kurmanji, Peter Triantafillou, and Eleni Triantafillou

We are delighted to announce that , a PhD student in the Theory and Foundations Research Division, has received the best student paper award at , for his joint work with for the paper: "Incremental (1-eps)-approximate dynamic matching in O(poly(1/eps)) update time". The paper considers the problem of maintaining a large matching in a graph that is undergoing a sequence of edge insertions. They present an algorithm for this fundamental problem in dynamic graph algorithms, which has near-optimal approximation ratio and an update time that does not grow at all with the size of the input and is also polynomial in 1/\eps (the error parameter). In addition, their approach is simpler than previous algorithms on the same problem that achieved weaker guarantees.

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 , the IEEE flagship conference in theoretical computer science that will be held on November 6 - 9, 2023 in Santa Cruz, California, USA:

• by , Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak.
• by , , and Thatchaphol Saranurak.
• by Lijie Chen, Zhenjian Lu, , Hanlin Ren, and Rahul Santhanam.
• by Tomasz Kociumaka, , and Barna Saha.
• by Arturo Merino and .