Inside Our Program
Program Events

Events

  • Apr
    22

    CS Seminar: On the Hardness of Learning Regular Expressions (Lev Reyzin)

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    Wednesday / CS Seminar
    April 22 / 12:00 PM
    Hybrid / Mudd 3514

    Speaker
    Lev Reyzin, University of Illinois Chicago

    Talk Title
    On the Hardness of Learning Regular Expressions

    Abstract

    "Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computational hardness of improperly learning regular expressions in the PAC model and with membership queries. We show that PAC learning is hard even under the uniform distribution on the hypercube, and also prove hardness of distribution-free learning with membership queries. Furthermore, if regular expressions are extended with complement or intersection, we establish hardness of learning with membership queries even under the uniform distribution. We emphasize that these results do not follow from existing hardness results for learning DFAs or NFAs, since the descriptive complexity of regular languages can differ exponentially between DFAs, NFAs, and regular expressions.

    This work is joint with Idan Attias, Nati Srebro, and Gal Vardi"

    Biography
    Lev Reyzin is a Professor of Mathematics, Statistics, and Computer Science at the University of Illinois Chicago and Co-Director of the IDEAL Institute. He works on the theory of machine learning, data science, and artificial intelligence. Prior to UIC, Reyzin was a Simons Postdoctoral Fellow at Georgia Tech and an NSF Computing Innovation Fellow at Yahoo! Research. Reyzin received his Ph.D. on an NSF doctoral fellowship from Yale under Dana Angluin and his bachelor’s degree from Princeton. He is currently the Chair of the Steering Committee for the ALT conference and the Editor-in-Chief of Mathematics of Data, Learning, and Intelligence. He has also served as a General Chair for FOCS 2024, the Program Chair for ISAIM 2020, and a Program Chair for ALT 2017. His work has earned awards at ICML, COLT, and AISTATS and has received extensive funding.

    Research Areas/Interests: theory of machine learning, data science, and artificial intelligence

    ---
    Zoom Link
    Panopto Link

    more less

    TIME Wednesday, April 22, 2026 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Apr
    6

    ME/CS/HCI Seminar- Faez Ahmed

    McCormick - Mechanical Engineering (ME)

    3:00 PM 1-350, Ford Motor Company Engineering Design Center

    EVENT DETAILS

    TIME Monday, April 6, 2026 at 3:00 PM - 4:00 PM

    LOCATION 1-350, Ford Motor Company Engineering Design Center    map it

    ADD TO CALENDAR

    CONTACT Jeremy Wells    jeremywells@northwestern.edu EMAIL

    CALENDAR McCormick - Mechanical Engineering (ME)

  • Apr
    13

    CS Seminar: Arindam Banerjee

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Monday, April 13, 2026 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Apr
    25

    MS in Information Technology (MSIT) In Person Class Visit Information Session

    MS in Information Technology (MSIT) Program

    11:00 AM McCormick Education Center STE 1400

    EVENT DETAILSmore info

    TIME Saturday, April 25, 2026 at 11:00 AM - 12:30 PM

    LOCATION McCormick Education Center STE 1400   

    ADD TO CALENDAR

    CONTACT Svetlana Korzeniowski    msit@northwestern.edu EMAIL

    CALENDAR MS in Information Technology (MSIT) Program

  • Apr
    27

    CS Seminar: Tushar Chandra

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Monday, April 27, 2026 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Apr
    29

    CS Seminar: Bill Fefferman

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Wednesday, April 29, 2026 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • May
    1

    MS in Information Technology (MSIT) Online Information Session

    MS in Information Technology (MSIT) Program

    12:00 PM

    EVENT DETAILSmore info

    TIME Friday, May 1, 2026 at 12:00 PM - 1:00 PM

    ADD TO CALENDAR

    CONTACT Svetlana Korzeniowski    msit@northwestern.edu EMAIL

    CALENDAR MS in Information Technology (MSIT) Program

  • May
    4

    CS Seminar: Moon Duchin

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Monday, May 4, 2026 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)