Computer science

Computer Science covers a wide variety of topics related to computers. Both theoretical and practical fields of computer science are covered under this tag.

There have been 12 completed talks and 28 topic suggestions tagged with computer science.

There are many subfields of computer science, including:

Related Tags

Completed Talks

Expander Graphs

Delivered by Frieda Rong on Wednesday November 29, 2017

In this talk, we’ll study graphs which are “sparse” yet “highly connected”. Known as expanders, these graphs exhibit interesting properties which can be viewed from a rich array of analytic, combinatorial, and probabilistic perspectives. Contributions of expanders range from the proof of important results in complexity theory to derandomization of algorithms to the construction of robust networks and cryptographic hash functions. We’ll see one application to coding theory, where expanders can be used to provide asymptotically “good” error-correcting codes with linear time encoding and decoding.

Prerequisites: linear algebra (familiarity with eigenvalues and eigenvectors).

Automatic sequences

Delivered by Laindon Burnett on Wednesday October 25, 2017

This talk will begin with a brief overview behind the theory of words in mathematics as well as the theory of finite automata in theoretical computer science. After this, we will define what an automatic sequence is, prove some fundamental theorems about them, and investigate some of their more intriguing properties. The majority of information presented comes from the text “Automatic Sequences: Theory, Applications, Generalisations” by Jean-Paul Allouche and the University of Waterloo's own Jeffrey Shallit, from the department of Computer Science.

The speaker has provided a PDF document covering the same content as this talk.

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.

Total Functional Programming

Delivered by Adam Hofmann on Friday March 3, 2017

Total functional programming is a paradigm of functional programming with the additional restriction that all functions must be total; that is, every function is defined for every element of its domain.

The immediate benefits of total functional programming are clear; every function in a total language is guaranteed to terminate and not cause a runtime error. This talk will cover the basics of writing and understanding functions that are total, as well as benefits that come from having totality.

Also in the scope of this talk is the major trade offs of total functional programming, including Turing completeness and things like input and output that seem unattainable. This is accompanied by strategies to write functions with non-trivial proofs of termination such that totality is guaranteed and verifiable by the interpreter.

General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme

Delivered by Zihao Zhu on Friday February 17, 2017

As more and more sensitive data gets digitized, there is a need to ensure privacy and reliability of the data, especially in the face of adversarial parties who attempt to corrupt or unwanted access to sensitive secrets.

In many instances such as online gambling, bidding, and even Google's targeted advertisements, a client wants to be able to take inputs from multiple sources (for example, auction bids) and produce an output (for example, the highest bidder) without revealing any information about the other inputs. We will use such scenarios as well as more cryptography related ones in order to motivate Multi-Party Computation as a method to compute on encrypted data. With MPC, we will quickly see it's limitations with unsecure channels and first develop secret sharing schemes (specifically linear secret sharing schemes) such as Shamir's scheme, and soon after, verifiable secret sharing schemes.

We will introduce the different types of adversarial structures and explore both the robustness and limitations of secret sharing schemes against them.

Finally, we will show that all Linear Secret Sharing Schemes can be constructed to be verifiable. We will explore the consequences of this and discuss techniques in their construction.

Prereqs: Math136 used in proofs

A summary of this talk is available here.

Bitcoin and the Blockchain

Delivered by Ben Zhang on Friday February 17, 2017

In this talk, we will learn about the principles behind the Double Spend Problem, the Blockchain, and explore the various ways this technology is being used today.

Transferring money in the physical world is easy. However, the transfer of virtual currency is not as easy to validate. The Double Spend Problem has long stood in the way of a free (libre et gratis) virtual currency, and the world found a need for a third party (usually in the form of large banks) to validate all virtual transactions.

In 2008, a mysterious individual known as Satoshi Nakamoto published a paper titled "Bitcoin: A Peer-to-Peer Electronic Cash System" which describes a system for virtual transactions to be validated through the distributed computing power of the community. The system, known as the Blockchain, uses hashing and non-deterministic mathematics to protect itself from Double Spending attacks. Nakamoto's paper led to the creation of free online currencies such Bitcoin, Litecoin, and Ethereum, which are used in marketplaces today.

Prerequisite Information: Middle school math.

Quantum Computing

Delivered by Michael Pang on Friday February 10, 2017

Introduction to quantum computing. We start off by tackling a classical problem via deterministic and probabilistic computation and then motivate a quantum model of computation. Along the way we lay out some of the mathematics needed to describe quantum computation and how it corresponds to key concepts in quantum mechanics such as interference and superposition.

Reinforcement Learning in Games

Delivered by Agastya Kalra on Friday October 21, 2016

Category Theory

Delivered by Luthfi Mawarid on Friday October 21, 2016

This talk will cover the very basics of Category Theory, motivated by simple examples using the category of sets. I will then introduce some applications to other areas of mathematics, such as linear algebra and programming language theory.

Types and Object-Oriented Programming

Delivered by Nikita Kapustin on Friday October 14, 2016

I'll be talking about how to use basic types like sets and functions to construct other types and use them to represent objects.

Talk Suggestions

Abstraction in Technical Computing

Scientists, mathematicians, and engineers have an increasing need to write efficient computer programs but they tend to use specific languages for technical computing like Matlab or Mathematica rather than general purpose languages. The suggested reference discusses the properties a general purpose language would need to be able to also handle technical computing – one possibility for allowing efficient technical computing involves a powerful type system and dispatch system to enable generic, staged, and higher-order programming.

Required Background: First year CS at the level of CS 135 and 136.

Possible reference materials for this topic include

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

Tech Talks computer science first year friendly polymorphism programming language type theory

Automated Verification of Computational Systems

It was realized in the 1960s that mathematical logic provides a suitable language to formulate properties of programs. This idea was formalized by Hoare who developed Hoare logic as a means to prove program correctness. However, this technique didn't apply directly to concurrent programs. An alternative approach called Temporal Logic was proposed by Amir Pneuli in 1977 which did provide a means to reason about concurrent programs. This topic studies this and then delves into the fundamental ideas behind model checking.

Required Background: Basics of computer science at the level of CS 146, Logic at the level of CS 245.

Possible reference materials for this topic include

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

computer science logic model checking

Completeness, Incompleteness, and Turing Machines

This topic studies the connection between Gödel’s incompleteness theorems and turing machines and how each implies the other

Possible reference materials for this topic include

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

computability computer science incompleteness logic theoretical computer science turing machine

Complex Event Processing Systems

The ever-increasing amount of information that needs to be processed has led to the development of Complex Event Processing systems such as Apache Storm or Twitter Heron. These systems distribute a workload over many machines in a cluster, and offer both efficiency and fault-tolerance.

Possible reference materials for this topic include

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

Tech Talks computer science data science distributed system first year friendly parallel computing statistics

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

Constructive Mathematics

Constructive mathematics, or mathematics without the law of the excluded middle, is becoming more popular thanks to connections with computer science, category theory, and topology. Its logical foundations may be initially difficult to grasp for those used to a classical system.

Possible reference materials for this topic include

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

computability computer science constructive mathematics logic philosophy topology type theory

Conway’s Game of Life

Possible reference materials for this topic include

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

automaton cellular automaton computer science first year friendly recreational mathematics theoretical computer science

Curry–Howard–Lambek Correspondence

Possible reference materials for this topic include

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

category theory computer science logic

Dealing with Missing Data

Data are rarely perfect. Robust data science tools must have ways to deal with missing data. However, this is not always easy. A balance must be struck between performance and convenience.

Possible reference materials for this topic include

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

Tech Talks computer science data science efficiency first year friendly statistics

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

Geographic Authentication Schemes

Users often choose passwords that are easy to remember but also easy to guess. Both textual and graphical passwords have failed to provide a viable solution to this usability-security tension. It thus remains a critical challenge in password research to design an authentication scheme that is resilient to guessing attacks while offering good memorability.

Possible reference materials for this topic include

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

computer science encryption human-computer interaction security

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

Hindley–Milner Type System

Possible reference materials for this topic include

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

computer science type theory

IEEE 754-2008: Floating Point Arithmetic

Most programming languages provide a floating-point type. What is floating point, and how does it work? What caveats should programmers be aware of?

Possible reference materials for this topic include

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

Tech Talks computational mathematics computer science first year friendly floating point number

Lindenmeyer systems

Originally developed to model plant growth, L-systems are a logical approach to various scientific questions, as well as one of many ways to generate artistically pleasing fractals.

Possible reference materials for this topic include

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

art biology botany computability computer science fractal logic theoretical computer science

P vs. NP

Possible reference materials for this topic include

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

computability computational complexity computer science open problem theoretical computer science

Predicate Dispatch

Possible reference materials for this topic include

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

computer science polymorphism

Presburger Arithmetic

Possible reference materials for this topic include

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

computability computational complexity computer science logic theoretical computer science

Protein Structure Prediction

Possible reference materials for this topic include

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

biology chemistry computer science optimization

Purely Functional Data Structures

Persistent (or purely function) data structures are those whose operations do not mutate the existing data structure, but rather create a new data structure that might share some state. These data structures are useful because there is no need to copy memory; rather the data structure can be shared among multiple objects. Techniques for making these data structures fast, memory-efficient, or real-time are an active area of research in functional programming.

Possible reference materials for this topic include

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

computer science data structure functional programming

Queueing Theory

Queueing theory is the mathematical study of waiting lines, or queues. In queueing theory, a model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

Possible reference materials for this topic include

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

computer science optimization

Separating Words Problem

Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.

Possible reference materials for this topic include

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

automaton computer science open problem theoretical computer science

Sparse Matrices

Sparse matrices are frequently used in scientific and numerical computation. How do they work? What new findings have there been? Speakers are encouraged to specialize this broad topic to a particular subfield of interest.

Possible reference materials for this topic include

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

algebra computational mathematics computer science linear algebra

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

Tropical geometry and Computational Biology

Tropical geometry is a combinatorial shadow of algebraic geometry, offering new polyhedral tools to compute invariants of algebraic varieties. It is based on tropical algebra, where the sum of twonumbers is their minimum and the product is their sum. This turnspolynomials into piecewise-linear functions, and their zero sets into polyhedralcomplexes.

Possible reference materials for this topic include

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

algebra algebraic geometry applied mathematics biology computational biology computer science geometry

Understanding LLVM

The LLVM Compiler Infrastructure Project now powers a wide variety of software, including major programming languages including Rust and Julia, as well as compilers for the popular C and C++ programming languages. Understanding how LLVM works, and being able to read some LLVM bytecode, is extremely useful for optimizing code.

Possible reference materials for this topic include

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

Tech Talks compiler computer science efficiency first year friendly programming language

Unique Games Conjecture

The Unique Games Conjecture, if true, implies that many problems that lack exact polynomial time solutions also lack approximate polynomial time solutions. It was formulated by Subhash Khot in 2002 and is still unsolved.

Possible reference materials for this topic include

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

computational complexity computer science open problem theoretical computer science

Zero-Cost Abstraction

Computer science is, fundamentally, about abstraction and efficiency. A programmer would rather use high-level bricks to build a product than worry about low-level details. Regrettably, the use of high-level bricks often comes at a cost in efficiency, forcing programmers to worry about low-level details. Recently, many programming languages have begun to stress the importance of zero-cost abstractions: ways to construct high-level bricks with zero efficiency cost.

Possible reference materials for this topic include

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

Tech Talks abstraction computer science efficiency first year friendly