Purdue Computer Science Hosts Midwest Theory Day

Writer(s): Jesica Hollinger

The Purdue Department of Computer Science recently hosted the 65th Midwest Theory Day at the Richard and Patricia Lawson Computer Science Building. Theory Day

The Midwest Theory Day is a biannual tradition among computer science theory researchers at academic institutions in the Midwest.  The event provides an opportunity for faculty and graduate students to interact, share ideas, and initiate collaborations. Purdue has been a frequent host of the event – most recently in 2006.

More than 45 researchers registered for the event, representing academic and research institutions, including University of Illinois at Urbana-Champaign, Indiana University, Toyota Technological Institute at Chicago, Northwestern University, Indiana State University, and Notre Dame University.

Department Head and Professor, Sunil Prabhakar, expressed the benefit to both Purdue and the CS Department in hosting the event.

“Our department is pleased to host Theory Day—an invaluable event, where we can gather for a day of interaction, discussion, and interesting presentations,” Prabhakar said.

Chris Peikert, Associate Professor at Georgia Institute of Technology, was this year’s invited speaker. Peikert is a leading researcher in the area of lattice-based cryptography. The topic of his talk was “Cryptography from Rings” and discussed one of the main cryptographic problems used in ring-based cryptography called “learning with errors over rings”.  He explained the theoretical evidence for its hardness and connection to algebraic “ideal lattices” and outlined some of the versatile and powerful encryption schemes that can be based upon it.

Eight additional participants gave presentations on various topics in the area of theoretical computer science, including:

  • Shi Li, Toyota Technological Institute at Chicago, “Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach” 
  • Danny Chen, Notre Dame University, “Stories of Clustering in Applications and Theory”
  • Shashank Agrawal, University of Illinois at Champaign Urbana, “Explicit Non-Malleable Codes Resistant to Permutations”
  • Vivek Madan, University of Illinois at Urbana-Champaign, “Centrality of Trees of Capacitated k-Center”
  • Jeremy Kun, University of Illinois at Chicago, “Resilient Coloring and Other Combinatorial Problems”
  • Sam Taggart, Northwestern University, “The Approximate Optimality of Simple Auctions”
  • Peng Zhang, Purdue University, “Optimal Query Complexity for Estimating the Trace of a Matrix”
  • Erfan Sadeqi Azer, Indiana University, “Palindrome Recognition in the Streaming Model”

The event was organized by Elena Grigorescu and Yi Wu, two faculty members of Purdue's Computer Science Department. For a complete program of the event and abstracts of the talks, visit the Midwest Theory web site.  The next meeting is expected to be scheduled in early December at a Chicago-area institution.