Skip to main content

CS Theory Seminar

Ivan Hu: Lifting Polynomial Complexity Measures Using Error-Correcting Codes. *Note different location for this week 6631*

Event Details

Date
Friday, September 18, 2026
Time
1-2 p.m.
Location
Description

Abstract: Lifting is the process of taking a function that is hard for a weak computational model and transforming it into a function that is hard for a stronger computational model. In this talk, we describe a lift that takes any polynomial with many terms and produces a polynomial that is hard for the model of read-once algebraic branching programs. We also describe the consequences for factor complexity, which asks if there are polynomials of low complexity with factors of high complexity.


 

Cost
Free
Contact
Accessibility

We value inclusion and access for all participants and are pleased to provide reasonable accommodations for this event. Please call 646-670-2527 (text only) to make a disability-related accommodation request. Reasonable effort will be made to support your request.

Tags