Thoughts on theoretical computer science and research life.

The Word Problem for Groups & Unsolvability
Feb 25, 2019
Long time member Eric Zhu is giving a talk on group theory and how it relates to complexity! It will cover the word representation problem along with its connections to undecidability. Here is an abstract : Continue Reading ❯

Interactive Proofs and ZeroKnowledge
Feb 18, 2019
This meeting will be a talk on zero knowledge proofs by the chair of the school of computer science, Dr. Lance Fortnow (also Theory Club’s advisor)! Continue Reading ❯

Probabilistic Method Problem Session
Feb 11, 2019
This meeting is on the probabilistic method problem session in the spirit of Valentine’s day. We went over some interesting bounds on dominating sets and Hamiltonian cycles in tournaments that can be easily derived from the probabilistic method. Check out the slides here : https://drive.google.com/open?id=1hS_qSnxrXiyniuuNBTNTTGG3ar1lO2Ztyr0veeKRuk Continue Reading ❯

Distance Preservers
Feb 4, 2019
This meeting will be a talk on sparse distance preservers of graphs given by Greg Bodwin. Continue Reading ❯

Donut Problem Session
Jan 14, 2019
First meeting of the semester was a problem session! We had donuts as well as a few very interesting problems about discrete structures, probability, and set theory. The slides for the problem session are here Continue Reading ❯

Deletion Codes
Dec 3, 2018
For our final meeting of the semester, we had professor Venkat Guruswami present a talk on deletion codes, a subset of errorcorrection codes. Thank you to everyone who came to Big O this semester! We’ll see you next year! Continue Reading ❯

Oracles in Complexity Theory
Nov 26, 2018
A guest appearance by our faculty talks coordinator DeVon, we had an introduction to oracles. Additionally, he talked about Bounded Error Quantum Polynomial Time (BQP) vs. Polynomial Hierarchy (PH) and barriers to proofs in complexity theory. The slides are here. Continue Reading ❯

Happy Ending Problem
Nov 19, 2018
This week, Sherry gave a lecture/problem session on the Happy Ending Problem, a popular field of mathematics created by P. Erdös, G. Szekeres, and E. Klein. This problem is very interesting for its connections to Ramsey theory. Her main reference is this website. Continue Reading ❯

Markov Chain Monte Carlo Methods
Nov 12, 2018
Yet another faculty talk, this week we had and introduction to Markov Chain Monte Carlo methods by Dr. Eric Vigoda! MCMC methods are super useful in approximating the size #P to count sets, the volume of hard to calculate integrals, and more. Continue Reading ❯

Spectral Algorithms
Nov 5, 2018
We had another faculty talk this week, about how graphs, linear algebra, and algorithms come together in Spectral Algorithms by Dr. Richard Peng. Here is the full abstract: Continue Reading ❯

Spooky Problem Session
Oct 29, 2018
Happy Halloween! We had an adeptly themed problem session led by Arvind this week! You can find the problems here. Continue Reading ❯

The MultiArmed Bandit Problem
Oct 22, 2018
We had our first faculty talk by Dr. Jacob Abernethy today! Dr. Abernethy recently joined GT as part of the theoretical CS department. He currently teaches CS 4540 (Advanced Algorithms) and Graduate ML Theory. His talk was on the multiarmed bandit problem and more generally, solving zerosum games without the iid requirements that are prevalent in much of ML theory today. Click here to learn more about Dr. Abernethy (and his juggling skills). Continue Reading ❯

Silly Talks
Oct 15, 2018
Thank you to everyone who presented for silly talks today! For the proof that the moon is fake, click here. Continue Reading ❯

Provable Security and Cryptocurrency
Oct 1, 2018
We had our first student talk this week by Abrahim Ladha on Provable Security and Cryptocurrency. Slides are here along with his references below. If you would like to know more about Abrahim, he has a website here. Continue Reading ❯

Information Theoretic Message Authentication
Sep 17, 2018
Our student talks coordinator Daniel gave our first student talk of the semester on message authentication in the information theoretic setting. Slides are here. If you are interested in giving a student talk at any point in the semester, please contact one of the officers. We welcome all talks even slightly related to theoretical computer science! Continue Reading ❯

Number Theory Problem Session
Sep 10, 2018
This meeting, we had a problem session on various number theory topics, led by Shyamal. The problems were (very) loosely related to the career fair, and were based on this CodeChef lecture here. Continue Reading ❯

Introduction to Computer Vision Workshop
Sep 4, 2018
We had our second meeting on Tuesday this week because of Labor Day, and instead of a talk, we had a workshop in preparation for the Home Depot Deep Learning Hackathon. Arvind gave an introduction to the field of computer vision along with a simple Keras demo on the MNIST dataset. Slides for the workshop are here, and the code is here. Continue Reading ❯

Big O Fall 2018 First Meeting
Aug 27, 2018
Welcome to Big O: Theory Club! We had our first meeting where we introduced officers explained what Theory Club is all about. We also had a short problem session which you can find here, along with the other slides. Continue Reading ❯

Big O Officer Elections
Apr 6, 2018
Officer elections for next school year will be held on April 23rd. If you are interested in becoming an officer, fill our the following form: Continue Reading ❯

Easter Problem Session by Shyamal Patel
Mar 26, 2018

Markov Chain Monte Carlo Methods Talk by Sherry Sarkar
Mar 12, 2018
We had a talk on Monte Carlo Methods using Markov Chains by Sherry this week! Continue Reading ❯

Neural Network Complexity Talk by Santosh Vempala
Mar 5, 2018
We had a talk on Neural Network Complexity by professor Santosh Vempala this week! Continue Reading ❯

Zero Knowledge Proofs Problem Session by Sherry Sarkar
Feb 26, 2018
We had a problem session on zero knowledge proofs by Sherry this week! Continue Reading ❯

Catalan Shuffles Talk by Prasad Tetali
Feb 19, 2018
We had a talk on Catalan Shuffles by professor Prasad Tetali this week! Continue Reading ❯

Derandomization Talk by Shyamal Patel
Feb 12, 2018
We had a talk on derandomization by our workshop coordinator Shyamal! Continue Reading ❯

Silly Talks
Feb 5, 2018
We had silly talks from vaious students as a lighthearted introduction to the art of presenting! Continue Reading ❯

Group Isomorphisms Talk by Daniel Hathcock
Jan 22, 2018
We had a talk on introductory group theory and group isomorphisms for our first meeting of the semester! Continue Reading ❯

Machine Learning Theory Talk by Diptodip Deb
Mar 7, 2017
We had a talk on introductory machine learning theory (Bayesian Learning and Computational Learning Theory) this week! Continue Reading ❯

Problem Session
Oct 17, 2016
We had a problem session today! We have two combinatorics problems and one erasure correction problem. Continue Reading ❯

Hello
Oct 12, 2016
We can only see a short distance ahead, but we can see plenty there that needs to be done. ~ Alan Turing
Continue Reading ❯