CS Theory Seminar
Ivan Hu: Lifting Polynomial Complexity Measures Using Error-Correcting Codes. *Note different location for this week 6631*
Event Details
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.
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.