Algorithm

There have been 3 completed talks and 5 topic suggestions tagged with algorithm.

Related Tags

Completed Talks

A 3/2-approximation algorithm for the stable marriage problem with ties

Delivered by Felix Bauckholt on Wednesday October 4, 2017

I will introduce the Stable Marriage Problem, and its NP-complete cousin, the Stable Marriage Problem with ties. I will present a simplified version of Király’s 3/2-approximation algorithm, which archieves the best approximation ratio known.

The slides for this presentation are available.

Metric embeddings and dimensionality reduction

Delivered by Frieda Rong on Friday March 31, 2017

In this talk, we consider embeddings which preserve the pairwise distances of a set of points. It is often useful to find mappings from one high dimensional space to a lower dimensional space that preserve the geometry of the points. One source of applications is in streaming large amounts of data, for which storage is costly and/or impractical. However, the study of such embeddings has also inspired developments in the design of approximation algorithms and compressed sensing.

At the crux of the talk is the remarkable Johnson-Lindenstrauss lemma. This fundamental result shows that for Euclidean spaces, it is possible to achieve significant dimensionality reduction of a set of points while approximately preserving the pairwise distances. An elementary proof will be given, along with subsequent speed improvements with sparse projections and an interesting use of the Fourier transform. We will also discuss applications of the lemma to the fields mentioned above.

Bloom Filters and Other Probabilistic Data Structures

Delivered by Luthfi Mawarid on Friday March 3, 2017

With the advent of big data, the ability to process large volumes of data is becoming increasingly important. For instance, when dealing with large data sets, we may want to perform simple operations such as counting the number of unique elements or checking whether or not an element is present in the set. While there are deterministic data structures, such as hash tables, that can perform these quickly, the sheer size of the data involved makes their use largely impractical and unscalable.Instead, we may want to trade-off some accuracy in our answers in exchange for greater space efficiency and ease of parallelization. For this, we introduce the concept of probabilistic data structures.

In this talk, we will mainly focus on Bloom filters, which are commonly used to test set membership and speed up data access. We will explore its main use cases, its implementation details, and the mathematics behind it. If time permits, I will also talk about the count min-sketch, used for frequency counting, and/or the HyperLogLog counter, used for cardinality estimation.

This talk will assume basic knowledge of probability.

Talk Suggestions

Complexity of Matrix Multiplication

Volker Strassen showed that $n^3$ matrix multiplication was not optimal in 1969. Since then, new algorithms such as Coppersmith-Winograd have further improved the time complexity of matrix multiplication. It is conjectured that matrix multiplication is possible in $O(n^{2+ɛ})$ for any $ɛ>0$, however small. This is one of the few remaining open problems in finite-dimensional linear algebra.

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

algebra algorithm computational mathematics computer science group theory linear algebra open problem

Galois Field Arithmetic

A Galois field is a finite field and are used in a variety of applications, including in classical coding theory and cryptography algorithms. This topic studies how to efficiently optimize arithmetic in such fields.

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

algebra algorithm computer science cryptography efficiency field theory

Gillespie Algorithm

The Gillespie Algorithm for stochastic equations is used heavily in a number of fields of applied mathematics, in particular computational systems biology.

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

algorithm applied mathematics biology computational biology computational mathematics computer science differential equation probability stochastic equation

The Joy of Factoring

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

algorithm computer science cryptography number theory quantum algorithm

Wilf zeilberg method to computer verify combinatorial identities

One of the most exciting mathematical discoveries in the early 1990s was the Wilf-Zeilberger (WZ) algorithm that can be used for proving, evaluating, and discovering identities involving hypergeometric terms automatically by computer. And unlike computerized proof techniques in other areas, the computerized proofs generated by this method provides a certificate for the validity of a combinatorial identity, called a WZ-pair.

Required Background: Combinatorics at the level of Math 249, Calculus at the level of Math 147.

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

algorithm combinatorics computer algebra