- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Fall 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 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
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B 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
In the basic model of communication complexity (Yao, 1979), Alice holds x, Bob holds y, and their goal is to compute a given function F(x,y) by communicating as few bits as possible. What elevates this model beyond its immediate appearances (communication networks, distributed systems) are several surprising connections to other seemingly unrelated areas of theoretical computer science and mathematics. I will discuss my PhD work in this area, with applications to circuit complexity, proof complexity, combinatorial optimisation (size of linear programming formulations), and graph theory (Alon-Saks-Seymour conjecture). A central theme in my research has been the introduction and application of several new Big Hammers, so-called "query-to-communication lifting" theorems. These new techniques have allowed me and my coauthors to resolve several fundamental open problems in communication complexity, some dating back to Yao's original 1979 paper that started the field.
Bio:
Mika Göös is a postdoctoral fellow in the Theory of Computing group at Harvard. He obtained his PhD from the University of Toronto (2016) under the supervision of Toniann Pitassi. He also holds an MSc from the University of Oxford (2011) and a BSc from Aalto University (2010). His research interests revolve around computational complexity theory.