This seminar will use a broad interpretation of "CS theory," including but not limited to algorithms, complexity, discrete mathematics, experimental algorithms, logic, and cryptography. The series typically hosts external speakers 2-3 times per semester, with a preferred day/time decided in consultation with active participants each academic year.

We often develop algorithms for a Real RAM model of computation, which has 3 unbounded quantities: the number of steps allowed (so we minimize big-O asymptotic bounds on running time), the number of memory cells (so we also bound space), and the number of bits in each cell (which we tacitly agree not to abuse). Liotta, Preparata, and Tomassia [LPT99] suggested Degree-driven analysis of algorithms: minimizing degrees of predicates can spark creativity in algorithm design to produce new that are more robust when implemented in floating point. In this talk we consider neutron tracking, in a form suggested by David Greisheimer of Bettis labs: Given a CAD model of nuclear reactor in a hierarchical Constructive Solid Geometry (CSG) representation, with unions and intersections of geometric primitives bounded by quadratic surfaces specified by floating point coefficients, track the materials pierced by a point moving in a straight line. A straightforward attempt to follow the point through surfaces can have surprising results – they have seen neutrons get stuck in a model (which makes a physicist rather nervous, since the code violates basic conservation laws.) Analysis of the degrees of the geometric operations used reveals why, and suggests changing the problem to tracking line segments, where we apply geometric rounding to the segment endpoints. By doing so, we can continue to use fast floating-point arithmetic, but give guarantees on both geometric and topological properties (e.g., every neutron entering a bounded region must also exit). This is work with David Millman and Michael Deakin.

**August 22, 2018**, 10:30 am:** Lalla Mouatadid**, University of Toronto. * Graph Searches on Structured Families of Graphs.*

**September 17, 2018**, 10:30 am:** Jack Snoeyink**, UNC Chapel Hill. * Changing the problem: Robust geometric computations for neutron tracking.*

**Fall 2018**, TBD:** Nina Fefferman**, University of Tennessee, Knoxville. * TBA.*

- 2018-2019
- 2017-2018
- The Theory Seminar was on leave in 2016-17 due to the birth of Tristan Sullivan.
- 2015-2016
- 2014-2015
- 2013-2014

To subscribe to the theory seminar announcement mailing list, send an email message to the NCSU list server at mj2@lists.ncsu.edu with "SUBSCRIBE cstheoryseminar" in the body of the message (not the subject line).