- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Spring 2025 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University / Cornell Tech - High School Programming Workshop and Contest 2025
- 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
- Robotics Ph. D. prgram
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Speaker
Monday, September 27, 2021 - 15:45 to 16:35
Streaming via Zoom
Host:
Eshan Chattopadhyay
Categories:
Reversing Color Coding
Abstract: In computational complexity it is often easier to prove hardness results for a colored version of a combinatorial or graph theoretic problem than its uncolored counterpart. Moreover, one can typically reduce from the uncolored version of a problem to its colored counterpart by a straightforward application of the celebrated color coding technique. Is the reduction in the reverse direction also possible?
In some interesting cases, such as the parameterized set intersection problem, such a reduction is highly non-trivial and this shall be the focus of the talk.
Joint work with Boris Bukh and Bhargav Narayanan.
Bio: Karthik C. S. is an Assistant Professor in the Department of Computer Science at Rutgers University. He received his Ph.D. in 2019 from Weizmann Institute of Science where he was advised by Irit Dinur. He has held postdoctoral appointments at Tel Aviv University (hosted by Amir Shpilka) and New York University (hosted by Subahsh Khot). He is broadly interested in complexity theory and geometry with emphasis on hardness of approximation, fine-grained complexity, and parameterized complexity.