TALK    [MERL Seminar Series 2025] Petar Veličković presents talk titled Amplifying Human Performance in Combinatorial Competitive Programming

Date & Time:

Wednesday, February 26, 2025; 11:00 AM

Abstract:

Recent years have seen a significant surge in complex AI systems for competitive programming, capable of performing at admirable levels against human competitors. While steady progress has been made, the highest percentiles still remain out of reach for these methods on standard competition platforms such as Codeforces. In this talk, I will describe and dive into our recent work, where we focussed on combinatorial competitive programming. In combinatorial challenges, the target is to find as-good-as-possible solutions to otherwise computationally intractable problems, over specific given inputs. We hypothesise that this scenario offers a unique testbed for human-AI synergy, as human programmers can write a backbone of a heuristic solution, after which AI can be used to optimise the scoring function used by the heuristic. We deploy our approach on previous iterations of Hash Code, a global team programming competition inspired by NP-hard software engineering problems at Google, and we leverage FunSearch to evolve our scoring functions. Our evolved solutions significantly improve the attained scores from their baseline, successfully breaking into the top percentile on all previous Hash Code online qualification rounds, and outperforming the top human teams on several. To the best of our knowledge, this is the first known AI-assisted top-tier result in competitive programming.

Speaker:

Petar Veličković
Google DeepMind

Petar Veličković is a Senior Staff Research Scientist at Google DeepMind, Affiliated Lecturer at the University of Cambridge, and an Associate of Clare Hall, Cambridge. He holds a PhD in Computer Science from the University of Cambridge (Trinity College), obtained under the supervision of Pietro Liò. Petar’s research concerns aligning neural networks to (classical) computation, to assess and improve their out-of-distribution generalisation ability. Particularly, Petar focusses on neural algorithmic reasoning (featured in VentureBeat), graph representation learning and categorical and geometric deep learning (a topic he has co-written a proto-book about). For Petar’s contributions, he is recognised as an ELLIS Scholar in the Geometric Deep Learning Program. Petar is the first author of Graph Attention Networks—a popular convolutional layer for graphs—and Deep Graph Infomax—a popular self-supervised learning pipeline for graphs (featured in ZDNet). His research has been used in substantially improving travel-time predictions in Google Maps (featured in Endgadget, VentureBeat, CNET, The Verge and ZDNet), guiding intuition of mathematicians towards new top-tier theorems and conjectures (featured in Nature, Science, Quanta Magazine, New Scientist, The Independent, Sky News, The Sunday Times, la Repubblica and The Conversation), the first full AI system for tactical suggestions in association football (featured in Financial Times, The Athletic, The Economist, New Scientist, Wired, MIT Technology Review, The Verge and El País), and the first AI-assisted top-percentile result in competitive programming.

MERL Host:

Anoop Cherian

Research Areas:

Artificial Intelligence, Computer Vision, Machine Learning