Tue 11 Mar 14:00: The Algebraic Circuit-Based Approach to Proof Complexity
Proof complexity is one of the central approaches to the fundamental hardness problems in complexity theory. In recent years, significant efforts have been made to bridge the gap between algebraic and proof complexity through a relatively transparent reduction from algebraic circuit-size lower bounds to proof-size lower bounds. In this talk, I will discuss state-of-the-art lower bounds in proof complexity that leverage the algebraic circuit-based approach, establishing it as a new tool that also draws on ideas from existing techniques—such as feasible interpolation, random restrictions, width-size tradeoffs, and lifting. I will also highlight some imminent open problems and potential challenges in this direction.
- Speaker: Iddo Tzamaret (Imperial)
- Tuesday 11 March 2025, 14:00-15:00
- Venue: Computer Laboratory, William Gates Building, Room SS03.
- Series: Algorithms and Complexity Seminar; organiser: Tom Gur.
Thu 15 May 17:00: Title to be confirmed
=== Hybrid talk ===
Join Zoom Meeting https://cam-ac-uk.zoom.us/j/87143365195?pwd=SELTNkOcfVrIE1IppYCsbooOVqenzI.1
Meeting ID: 871 4336 5195
Passcode: 541180
- Speaker: Andrei Popescu (University of Sheffield)
- Thursday 15 May 2025, 17:00-18:00
- Venue: MR14 Centre for Mathematical Sciences.
- Series: Formalisation of mathematics with interactive theorem provers ; organiser: Anand Rao Tadipatri.
Tue 04 Mar 13:10: Metaphysics as Communing with the Unknown: Crossing between Emmanuel Levinas and Karl Jaspers
Classical metaphysics, or the effort to arrive at justified true knowledge of ‘the metaphysical’, the ultimate causes or first principles of reality, has been subjected to a developing critique over the past three centuries. Discussions of scholars concerning the possibility of metaphysics has continued to grow in recent decades, with many proclaiming the end of metaphysics.
This talk will endeavour to articulate an alternative approach to metaphysical philosophizing, issuing from a comparison of two 20th century thinkers, Emmanuel Levinas and Karl Jaspers. This alternative approach to engaging with the metaphysical is distinguished by an acceptance of the inability to arrive at final knowledge of such matters, but holds that thinking about the ‘deepest’ aspects of reality, in which we have our ideations regularly surpassed in a process of unending learning, can offer an alternative, personally and spiritually transformative value, in which we can come to playful, ‘just communion’ with the mystery of being, manifesting as the desire for wonderment.
- Speaker: Connor Hayes
- Tuesday 04 March 2025, 13:10-14:00
- Venue: Richard King room, Darwin College.
- Series: Darwin College Humanities and Social Sciences Seminars; organiser: Dr Amelia Hassoun.
Thu 06 Mar 13:00: RO-FIGS: Efficient and Expressive Tree-Based Ensembles for Tabular Data NOTE unusual date
Tree-based models are often robust to uninformative features and can accurately capture non-smooth, complex decision boundaries. Consequently, they often outperform neural network-based models on tabular datasets at a significantly lower computational cost. Nevertheless, the capability of traditional tree-based ensembles to express complex relationships efficiently is limited by using a single feature to make splits. To improve the efficiency and expressiveness of tree-based methods, we propose Random Oblique Fast Interpretable Greedy-Tree Sums (RO-FIGS). RO-FIGS builds on Fast Interpretable Greedy-Tree Sums, and extends it by learning trees with oblique or multivariate splits, where each split consists of a linear combination learnt from random subsets of features. This helps uncover interactions between features and improves performance. The proposed method is suitable for tabular datasets with both numerical and categorical features. We evaluate RO-FIGS on 22 real-world tabular datasets, demonstrating superior performance and much smaller models over other tree- and neural network-based methods. Additionally, we analyse their splits to reveal valuable insights into feature interactions, enriching the information learnt from SHAP summary plots, and thereby demonstrating the enhanced interpretability of RO-FIGS models. The proposed method is well-suited for applications, where balance between accuracy and interpretability is essential.
NOTE unusual date
- Speaker: Urška Matjašec (University of Cambridge)
- Thursday 06 March 2025, 13:00-14:00
- Venue: Lecture Theatre 2, Computer Laboratory, William Gates Building.
- Series: Artificial Intelligence Research Group Talks (Computer Laboratory); organiser: Mateja Jamnik.
Wed 05 Mar 13:30: Lifting in special linear groups
Given an element in SL_n(Z/qZ), what is the smallest element of SL_n(Z) that projects to it? In a joint work with Amitay Kamber, we proved that a lift with entries bounded by O(q^2 log q) always exists, and that the exponent 2 is best possible. In the first half of the talk, I will explain how this problem is related to bounding the diameter of the Ramanujan graphs of Lubotzky, Phillips and Sarnak, and to Sarnak’s golden gates in quantum computing. In the second half of the talk, I will talk about the proof that the exponent 2 is best possible. This uses some tools from additive combinatorics.
- Speaker: Péter Varjú (University of Cambridge)
- Wednesday 05 March 2025, 13:30-15:00
- Venue: MR4, CMS.
- Series: Discrete Analysis Seminar; organiser: Julia Wolf.
Wed 15 Oct 15:00: tbc
Abstract not available
- Speaker: Professor Filipe Cabreiro, University of Cologne, Germany
- Wednesday 15 October 2025, 15:00-16:00
- Venue: MRC MBU, Level 7 Lecture Theatre, The Keith Peters Building, CB2 0XY.
- Series: MRC Mitochondrial Biology Unit Seminars; organiser: Lisa Arnold.
Mon 15 Sep 11:00: LMB Seminar - Title TBC
Abstract not available
- Speaker: Alan Brown, Harvard Medical School
- Monday 15 September 2025, 11:00-12:00
- Venue: In person in the Max Perutz Lecture Theatre (CB2 0QH) and via Zoom link https://mrc-lmb-cam-ac-uk.zoom.us/j/99625598840?pwd=tiFsd5DQ5nqRyGefhp24MlXakfaa9L.1.
- Series: MRC LMB Seminar Series; organiser: Scientific Meetings Co-ordinator.
Thu 16 Oct 13:00: Seminars in Cancer
Abstract not available
- Speaker: Steffi Oesterreich, University of Pittsburgh
- Thursday 16 October 2025, 13:00-14:00
- Venue: CRUK CI Lecture Theatre.
- Series: Cancer Research UK Cambridge Institute (CRUK CI) Seminars in Cancer; organiser: Kate Davenport.
Wed 01 Oct 15:00: tbc
tbc
- Speaker: Professor Irene Miguel-Aliaga, The Francis Crick Institute
- Wednesday 01 October 2025, 15:00-16:00
- Venue: MRC MBU, Level 7 Lecture Theatre, The Keith Peters Building, CB2 0XY.
- Series: MRC Mitochondrial Biology Unit Seminars; organiser: Lisa Arnold.
Mon 29 Sep 11:00: LMB Seminar - Title TBC
Abstract not available
- Speaker: Hiroaki Suga - The University of Tokyo
- Monday 29 September 2025, 11:00-12:00
- Venue: In person in the Max Perutz Lecture Theatre (CB2 0QH) and via Zoom link https://mrc-lmb-cam-ac-uk.zoom.us/j/96488916942?pwd=BpCGRwD8hD8ec89yfaJ0yKPmV3o6lv.1.
- Series: MRC LMB Seminar Series; organiser: Scientific Meetings Co-ordinator.
Mon 07 Jul 11:00: LMB Seminar - Title TBC
Abstract not available
- Speaker: Marileen Dogterom - TU Delft, Delft University of Technology
- Monday 07 July 2025, 11:00-12:00
- Venue: In person in the Max Perutz Lecture Theatre (CB2 0QH) and via Zoom link https://mrc-lmb-cam-ac-uk.zoom.us/j/95584842300?pwd=V2DAKEE0bQXA4bbbSUryiRPELlhmzP.1.
- Series: MRC LMB Seminar Series; organiser: Scientific Meetings Co-ordinator.