# Seminars & Colloquia Calendar

## On-Line Algorithms and Reverse Mathematics

#### Seth Harris (Cornell)

Location: ** Hill 705**

Date & time: Monday, 16 April 2018 at 5:00PM - 6:00PM

Abstract: Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence \(\bar{a}\) and Bob responds with a sequence \(\bar{b}\) with no knowledge of Alice's future requests. A problem P is solvable by an on-line algorithm if Bob has a winning strategy in this game, where Bob wins the game if (\(\bar{a}, \bar{b}\)) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is on-line colorable if Bob has a winning strategy in this game. Given a problem P, the corresponding sequential problem SeqP asserts the existence of an infinite sequence of solutions to P. We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in the axiom systems RCA\(_0\), WKL\(_0\), and ACA\(_0\).

This is joint work with Francois Dorais.

R. Shapiro Organizer's Page

Eilidh McKemmie -Charles Weibel Organizer's Page

Narek Hovsepyan and Ewerton Rocha Vieira Organizer's page

Ziming Shi, Sagun Chanillo, Xiaojun Huang, Chi Li, Jian Song Seminar website Old seminar website

Sepehr Assadi Seminar webpage

Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage

Robert Dougherty-Bliss and Doron Zeilberger --> homepage

Paul Feehan, Daniel Ketover, Natasa Sesum Organizer's webpage

Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage

Hong Chen Seminar webpage

Fanxin Wu and Nkhalo Malawo Organizer's website

James Holland; Organizer website

Organizers: Maxime Van de Moortel and Avy Soffer. Organizer's Page

Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum Organizer's Webpage

Organizer: Luochen Zhao

Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song Organizer's Page

Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage

Simon Thomas website

Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page

Joel Lebowitz, Michael Kiessling

Yanyan Li, Dennis Kriventsov Organizer's Webpage

Alex V. Kontorovich, Vlada Sedláček seminar website

Stephen D. Miller

Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum

Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page

Fioralba Cakoni Seminar webpage

Organizer's webpage: Organizer's webpage

For information on the Statistical Mechanics Conference, visit HERE

- Show events from all categories

## Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

*Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.*