Mathematics is embracing theoretical computer science. This year’s Joint Mathematics Meetings showcased the field with awards and talks, including one from School of Computer Science Professor Dana Randall.

Randall was greatly honored to be invited to give this talk, her second invited address at the annual math conference, which more than 6,000 people attended in January.

“In addition, theoretical computer science was really well represented among speakers,” Randall said. “There’s now a broader interest in our field. It really is remarkable because last year there wasn’t anyone.”

Randall also hosted a special session with Arizona State’s Professor Andrea Richa on emergent phenomena in discrete models. Emergent phenomena are phase transitions, or a microscopic change in a parameter that creates a macroscopic change to a system, such as water to ice or unmagnetized to magnetized.

Sampling algorithms used in random generation also experience phase transitions. When some parameter of the system is modified, they can change abruptly from being efficient to inefficient. In effect, the algorithm breaks down.

Understanding the limitations of some sampling algorithms can lead theoretical computer scientists to find alternative faster algorithms. One path forward is harnessing these emerging phenomena to an advantage through distributed algorithms, or algorithms that do not have a central coordinator and run on distributed systems.

Randall, Richa, and School of Physics Associate Professor Daniel Goldman have been exploring this through programming smarticles, or tiny robots that cannot function well on their own but can accomplish tasks collectively.

“Each particle has local rules but no global puppeteer, but interesting collective behavior can happen by using emergent phenomena,” Randall said.

If a smarticle is put on a table, it will wiggle its arms around but stay still, but if a few are placed together, they start jostling and then move as a swarm. In effect, the smarticles are responding to their environment and adjusting parameters accordingly, which can change the phase of the entire system.

The researchers are trying to understand what are the minimal computational requirements to achieve compression. Then they determine if the collective behavior can become more sophisticated and complicated. To do so, they are building a simple distributed algorithm that exhibits this complicated behavior.

The possibilities of emergent phenomena were explored during the session. Theoretical computer scientists applied the concept to DNA, neural algorithms, graph coloring, and more.

 Theoretical computer science is finding more connections everywhere, and it’s especially nice to see it highlighted at a big math conference.