We will visit the world-famous Slocum Puzzle Collection.

We will then have a brunch (provided) followed by Prof. Stan Wagon's talk.

• Title: NP: Be Not Afraid
  Speaker: Stan Wagon, Macalester College
  Abstract: NP-hard problems are really hard. Yet there are many fascinating algorithms that allow solution of cases of such problems far beyond what one would expect. The traveling salesman problem is noteworthy, in that solutions are known for instances with many thousands of cities. Many graph theory problems are also notoriously difficult, such as finding a Hamiltonian cycle or finding the chromatic number or other graph parameters. By combining several algorithms (such as TSP and integer-linear programming (ILP)), one can often develop methods that are strong enough to allow investigation of thousands of cases, leading to new insights and conjectures.

  A very famous conjecture is that all vertex transitive graphs have a Hamiltonian cycle, except for five small examples. Investigations on Mathematica's graph database (7000 graphs) showed that much more might well be true: all vertex transitive graphs (with some small exceptions) appear to be Hamilton-connected and have Hamiltonian decompositions. Moving to a large database of 100,000 vertex transitive graphs yielded no failures.

  In the talk we will discuss such algorithms and also ILP and its use in diverse real-world applications. It is used to help match patients with donors in kidney-transplant databases. And recently I used it to help Macalester College and Beloit College assign students to classes; it easily outperforms manual techniques in general use.

1. Title: Very Large Provable Primes (Finding Very Large Prime Numbers)
   Speaker: Prof. Jeff Kinne, Indiana State University
   Abstract:Finding very large prime numbers is a challenge that has a long history. Although efficient randomized primality tests are in common use, these tests do not in general give a /proof/ of primality and the fastest deterministic tests remain impractical for numbers containing more than a few hundred digits. Very efficient deterministic primality tests have been devised for certain special classes of integers (e.g., the Mersenne numbers). Since the advent of electronic computers, these special-purpose tests have routinely been used to find the largest known provable prime numbers (the current record holder has about 17 million digits).

   In ongoing work, we have applied techniques to search for very large primes that come from a somewhat wider class than traditionally considered. In this talk, we survey previous work and our own results. We focus on giving a glimpse into the types of issues (both theoretical and practical) that arise in the research area.

2. Title: A New Push-Relabel Algorithm for the Max-Flow Problem
   Speaker: Rahul Mehta (High School Senior at the UChicago Lab School)
   Abstract: In this paper, we present a faster push-relabel algorithm for the maximum flow problem on bounded-degree networks with $n$ vertices and $m$ arcs. We show how to compute a maximum flow in $O(mn)$ time. This matches the results of Orlin's algorithm, which runs in $O(mn + m^{31/16} \log^2 n)$ time on general networks (and $O(mn)$ time on bounded-degree networks). Our main result is improving on the generic push-relabel algorithm (Goldberg \& Tarjan, 1988) by reducing the number of nonsaturating pushes to $O(mn)$ across all scaling phases. This improvement is reached by a novel combination of Ahuja and Orlin's excess scaling method and Orlin's compact flow networks (STOC `13). A major contribution of this paper is demonstrating that the compact networks technique can be extended to the push-relabel family of algorithms. Moreover, we show that an extension of our result to general networks would imply an algorithm that runs in $O(mn)$ time, when $m = O(n^{2-\epsilon})$. An algorithm incorporating some or all of our techniques may be a promising avenue towards an $O(mn)$-time algorithm for all edge densities. (Says Rahul: "I did this work over the summer and it was supervised by Prof. Janos Simon of U of C.")

More details will be posted here shortly.