Organizer: Blair D. Sullivan

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. Please sign up for our mailing list (directions at the bottom of this page) to receive notification of all talks, times, and locations.


Next Talk:

Rescheduled due to Hurricane Florence!

Jack Snoeyink, UNC Chapel Hill
Monday October 1, 2018: Time EBII-3211

Changing the problem: Robust geometric computations for neutron tracking
Abstract:
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.

Scheduled Talks for 2018-19 Academic Year

Watch this space! More speakers to be confirmed soon!

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.


Sponsors: The 2018-2019 seminars have been made possible thanks to support from Eastman Chemical, the ePartners program, and the NC State Engineering Foundation, and the Gordon and Betty Moore Foundation's Data-Driven Discovery Program.


Previous Seminars (with abstracts)


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).