Computer Science News
6 papers accepted to FOCS 2024
Six papers from the Theory and Foundations Research Group and the Centre for Discrete Mathematics and Its Applications (DIMAP) have been accepted to the , the flagship conference in theoretical computer science that will be held on October 27 - 30, 2024 in Chicago, USA:
- "" by Lijie Chen, Jiatu Li and .
- "" by , Din Carmon, , Shay Solomon and Tianyi Zhang.
- "Fully Dynamic k-Clustering with Fast Update Time and Small Recourse" by , , Naveen Garg, Silvio Lattanzi and Nikos Parotsidis.
- "The Tractability Border of Reachability in Simple Vector Addition Systems with States" by Dmitry Chistikov, Wojciech Czerwi艅ski, 艁ukasz Orlikowski, Filip Mazowiecki, Henry Sinclair-Banks and Karol W臋grzycki.
- "Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications" by Shuichi Hirahara, and Mikito Nanashima.
- "On the Complexity of Avoiding Heavy Elements" by , , Hanlin Ren and Rahul Santhanam.
Breakthrough result on the power of memory in computation
A published by , a postdoctoral researcher in the Theory and Foundations (FoCS)Link opens in a new window research group and the Centre for Discrete Mathematics and its Applications (DIMAP)Link opens in a new window, has disproved a longstanding conjecture on the limitations of space-bounded computation.
For many years it had been believed that a function, known as Tree Evaluation, would be the key to separating two fundamental classes of problems: those computable quickly (P), and those computable in low space (L). Mertz, along with of Toronto, builds on their earlier work to show a low-space algorithm for Tree Evaluation, thus refuting this belief. In particular, their technique has attracted attention for shedding new light on the power of space-bounded computation, suggesting novel approaches to age-old questions in complexity theory. They show that space can be used in surprising ways, with the same memory serving many simultaneous purposes.
The paper, which Mertz will present at the , has been invited to the special issue of for the conference. STOC is the main conference of the Association of Computing Machinery (ACM) and one of the two premier venues for theoretical computer science, with only the top results being invited for publication in the special issue.
Mertz has also presented this work at many venues, including the Institute for Advanced Study (IAS), Columbia University, Oxford University, 海角社区 (, McGill University, and others.
Seven papers accepted to ICML 2024
Seven papers authored by Computer Science researchers from 海角社区 have been accepted for publication at the , one of the top three global venues for machine learning research, which will be held on 21-27 July 2024 in Vienna, Austria:
- Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPs, by Stelios Triantafyllou, Aleksa Sukovic, , and Goran Radanovic
- Dynamic Facility Location in High Dimensional Euclidean Spaces, by , Gramoz Goranci, Shaofeng Jiang, Yi Qian, and Yubo Zhang (Accepted as a spotlight, among the top 13 percent of all accepted papers)
- High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization, by Yihang Chen, , Taiji Suzuki, and Volkan Cevher
- Revisiting character-level adversarial attacks, by Elias Abad Rocamora, Yongtao Wu, , Grigorios Chrysos, and Volkan Cevher
- Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences, by Andi Nika, , Parameswaran Kamalaruban, Georgios Tzannetos, Goran Radanovic, and Adish Singla
- To Each (Textual Sequence) Its Own: Improving Memorized-Data Unlearning in Large Language Models, by George-Octavian B膬rbulescu and Peter Triantafillou
- Towards Neural Architecture Search through Hierarchical Generative Modeling, by Lichuan Xiang, 艁ukasz Dudziak, Mohamed Abdelfattah, Abhinav Mehrotra, Nicholas Lane, and
Latest academic promotions
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!
An Easy-Sounding Problem Yields Numbers Too Big for Our Universe
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 海角社区 DCS, finally closed the difficulty of the problem in 2021, concluding that it is very, very difficult indeed.
PhD position in Quantum Learning Theory at the University of 海角社区, UK (Application deadline: January 1, 2024)
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 海角社区, UK, in Fall 2024. Candidates interested in the interactions between quantum computing and learning theory are encouraged to apply.
The 海角社区 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 海角社区 Quantum. Overall, the Department of Computer Science at 海角社区 offers an excellent research environment. It was ranked 4th in the latest UK research assessment in Research Excellence Framework (REF) in 2021.
PhD positions at the University of 海角社区, UK (Application deadline: 24 November, 2023)
PhD positions are available at the Theory and Foundations group in the Department of Computer Science, University of 海角社区, 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 海角社区 Mathematics Institute and 海角社区 海角社区 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 海角社区 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 海角社区 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 海角社区shire, 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/>