- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Spring 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2023 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Thursday, October 12, 2023 - 11:45 to 12:45
B11 Kimball Hall and via Zoom https://cornell.zoom.us/j/97728839889?pwd=UEwwS0o1Ym9ROGttWCtJbFBmalVpdz09&from=addon
Host:
Eshan Chattopadhyay
Categories:
Please note the Colloquium talk will be held in B11 Kimball Hall and via Zoom
Abstract:
Data compression is a key concept in computer science, relevant in contexts such as data storage and transmission, learnability of patterns from data, and complexity theory. In particular, in complexity theory, a Boolean function is considered hard if its truth table cannot be compressed by Boolean circuits.
But how difficult is it to estimate the inherent compressibility of a string?
This question is the focus of a thriving research program in "meta-complexity", ie., the complexity of complexity (since incompressibility can be considered as a measure of the complexity of a string). I will discuss various recent results connecting this question to fundamental results and directions in areas such as learning theory, cryptography, complexity lower bounds, and Gödel-type incompleteness phenomena in computer science.
Bio:
Rahul Santhanam is a Professor of Computer Science at Oxford and a Tutorial Fellow at Magdalen College. He obtained a Ph.D. in Computer Science from the University of Chicago in 2005, working under the supervision of Prof. Lance Fortnow and Prof. Janos Simon. After postdoctoral stints at Simon Fraser University and the University of Toronto, he joined the University of Edinburgh as a Lecturer in Computer Science in 2008. He was promoted to Reader in 2013 and moved to Oxford in 2016. In 2013, he was awarded the ERC Consolidator Grant ALUnif on "Algorithms and Lower Bounds: A Unified Approach", which he held from March 2014 until August 2019.