Date: 2025/12/11 15:30-17:30
Location: 博理館 101 演講廳
Speaker: Prof. Salil Vadhan (Harvard University)
Abstract:
I will describe a new course "Introduction to Algorithms and their Limitations," which we have developed at Harvard over the past five years, focusing on some of its innovative features: *An integration of content that has traditionally been separated into different algorithms and theory of computation courses, which provides pedagogical benefits for both topics; *A focus on modelling, abstraction, and conceptual tools such as reductions, over clever or technical problemsolving. This allows this course to be more accessible than our stand-alone algorithms and theory of computation courses, which can be taken subsequently for a more in-depth treatment. *A novel type of active learning exercise, where students are paired and one is tasked with interactively explaining a proof that they have just studied to their classmate. I will also share some musings on why the skills developed in such a course may be increasingly important in a world where AI is able to take on many code- and proof-writing tasks.
Title: Reliable Hash Functions in Computing
Date: 2025/12/11 15:30-17:30
Location: 博理館 101 演講廳
Speaker: Prof. Mikkel Thorup (University of Copenhagen)
Abstract:
Randomized algorithms are often enjoyed for their simplicity. However, if too simple hash functions are used, then the results are no longer reliable. Here we survey how simple hashing schemes based on tabulation are reliable, providing unexpectedly strong guarantees. The simplest is simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of c characters and we have precomputed character tables h1, ..., hq mapping characters to random hash values. A key x = (x1, ..., xc) is hashed to h1[x1] ⊕ h2[x2]..... ⊕ hc[xc]. This scheme is very fast with character tables in cache. While simple tabulation is not even 4- independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. We shall also discuss the power of more advanced tabulation hashing techniques.