Thoughts on theoretical computer science and research life.

Greedy algorithm optimizing submodular functions
Mar 3, 2023
Continuing with the theme of combinatorial optimization and approximate algorithms, Stephen presented a simple approximate greedy algorithm for optimizing monotone, submodular set functions. Continue Reading ❯

Approximate algorithms for metric traveling salesman
Feb 24, 2023
Brian presented on combinatorial optimization, specifically, some approximation algorithms for the (metric) traveling salesman problem. Continue Reading ❯

Sampling a Gaussian Markov random field on a torus
Feb 17, 2023
For Valentine’s day, Stephen talked about efficient algorithms for sampling a stationary random field defined on a torus. Sugartopped flour tori will be provided. Continue Reading ❯

MyAnimeList affinity attack
Feb 10, 2023
Stephen talked about past work on efficiently recovering private data from the anime tracking website through queries against an affinity oracle. Continue Reading ❯

Checkpoints in reversemode automatic differentiation
Feb 3, 2023
Stephen talked about automatic differentiation (autodiff) techniques including finite differencing, forwardmode autodiff, and reversemode autodiff, the last of which is also commonly known as “backpropagation”. Continue Reading ❯

Auction design
Jan 27, 2023
Brian gave an introduction to auction design, a key topic in algorithmic game theory. Continue Reading ❯

Information theory
Jan 20, 2023
Stephen talked about information theory, particularly about which distributions maximize information. Continue Reading ❯

First meeting
Jan 13, 2023
We held our first meeting of the semester tonight, giving an overview of the club, went over some games, and tried a few more puzzles. Continue Reading ❯

The probabilistic method
Dec 2, 2022
For the last meeting of the semester, Brian covered the probabilistic method, a creative and popular proof technique in combinatorics. Continue Reading ❯

Thanksgiving break
Nov 25, 2022
We didn’t have a meeting this week. Happy Thanksgiving! Continue Reading ❯

Preconditioned gradient descent
Nov 18, 2022
Stephen lectured on different forms of preconditioning gradient descent including the natural gradient and Newton’s method for convex problems. Continue Reading ❯

Symmetric methods
Nov 11, 2022
Brian presented on symmetric encryption algorithms and their related attacks. Continue Reading ❯

Iterative methods and gradient descent
Nov 4, 2022
Stephen lectured on iterative methods for solving linear systems, fixed point methods, and gradient descent. Continue Reading ❯

Fun and interesting probability topics
Oct 28, 2022
Brian covered an assortment of fun and interesting topics from probability, including linearity of expectation, random walks, Bayes theorem, and maybe more if time permits. Continue Reading ❯

Introduction to linear programming
Oct 21, 2022
Today Suhas introduced linear programming. Continue Reading ❯

Probability donut problem session
Oct 14, 2022
We had a donut 🍩 session featuring a problem set on some of the topics we previously covered. Continue Reading ❯

Basic probability
Oct 7, 2022
We covered basic probability in preparation for a future donut problem session. Continue Reading ❯

RSA cryptography
Sep 30, 2022
Brian presented on RSA cryptography along with some of its mathematical background. Continue Reading ❯

Cholesky factorization
Sep 23, 2022
Stephen presented on his research: exploiting the interplay between statistical inference and numerical linear algebra to derive faster algorithms for Gaussian elimination/the Cholesky factorization. Continue Reading ❯

Secretary problem
Sep 16, 2022
For today’s meeting, Brian presented on the Secretary Problem, a classic example from optimal stopping and online algorithms. Continue Reading ❯

Communication complexity
Sep 9, 2022
Suhas presented on communication complexity (which sounds scarier than it is). Continue Reading ❯

First meeting
Sep 2, 2022
We held our first meeting of the semester tonight, giving an overview of the club, went over the game from the CoC Club Fair, and tried a few more puzzles. Continue Reading ❯

Optimal Transport
Apr 25, 2022
Arvind gave a talk about optimal transport. Continue Reading ❯

Probability Problem Session
Apr 18, 2022
Tonight we’re did a miniproblem session, with some topics mostly inspired from last week’s game night. Continue Reading ❯

Probability Game Night
Apr 4, 2022
On Monday night we had a gambling Probability Game Night! Continue Reading ❯

Secret Sharing Schemes
Apr 4, 2022
Today Brian talked about secret sharing schemes. Continue Reading ❯

Taking the Derivative of a Type
Mar 28, 2022
Ohad presented on type stuff (like taking the derivative of a type). Continue Reading ❯

Interior Point Methods for Linear Programming
Mar 14, 2022
Arvind gave a talk about linear programs, LP duality, and how to solve LP’s using interior point methods. Continue Reading ❯

Formal Security in Cryptography
Mar 7, 2022
Today Neil talked about a variety of (symmetric) cryptography topics and formal security models for them. Continue Reading ❯

Cholesky Factorization by Gaussian Process Regression
Feb 28, 2022
Today Stephen talked about ongoing research: how the interplay between numerical linear algebra, statistical inference, and information theory can be exploited to yield better algorithms for classic problems in scientific computing. Continue Reading ❯

Geometric Folding Algorithms
Feb 21, 2022
Today I (Alvin) talked about some past research I’ve done, where we reduced a counting problem in origami into a graph coloring problem (I’ll be bringing some handson paper to play around with 👀). Continue Reading ❯

Valentine's Day Problem Session
Feb 14, 2022
Today will be a Valentine’s Day themed Problem Session (some problems about games and algorithms), so yes that means there’ll be donuts 😍 🍩. Continue Reading ❯

Machine Learning Theory
Feb 7, 2022
Today Neil talked about ML theory (but better this time). Continue Reading ❯

Cache Complexity
Jan 31, 2022
Today Suhas talked about cache complexity. Continue Reading ❯

Maximum Matching
Jan 24, 2022
To kick things off, Suhas gave the first meeting of the spring semester on maximum matchings. Continue Reading ❯

Quantum Computing
Nov 29, 2021
Today Suhas held a lecture (with a few problems on the side) on quantum computing. Continue Reading ❯

Probabilistic Method Problem Session Continued
Nov 22, 2021
Tonight we are just going to continue working on last week’s problem session, keep it lowkey since it’s Thanksgiving week after all. Continue Reading ❯

Probabilistic Method Problem Session
Nov 15, 2021
As mentioned last week, today’s meeting is going to be a problem session guided by Alvin based around the Probabilistic Method. Continue Reading ❯

Probabilistic Method
Nov 8, 2021
Today Neil and Alvin talked about the probabilistic method. Continue Reading ❯

Statistical Machine Learning
Nov 1, 2021
Tonight Neil talked about some basic statistical ML / results in ML theory! Continue Reading ❯

Approximation Algorithms for Metric Traveling Salesman
Oct 25, 2021
Tonight Alvin talked about Approximation Algorithms, specifically for the Metric Traveling Salesman Problem (metric TSP). Continue Reading ❯

NP and quantum computing
Oct 18, 2021
Suhas talked bout NP and connections to quantum computing. Continue Reading ❯

Secretary Problem
Oct 4, 2021
Tonight Alvin gave talk on The Secretary Problem (also known as the Marriage Problem 😳), one classic example of an Online Algorithm. Continue Reading ❯

Doughnut Problem Session on Cryptography
Sep 27, 2021
Tonight we’re going to have a 🍩 DONUT 🍩 PROBLEM 🍩 SESSION 🍩 on more cryptography guided by Neil! Continue Reading ❯

RSA cryptography
Sep 20, 2021
Neil lectured on topics in cryptography (probably mostly RSA). Continue Reading ❯

Communication Complexity
Sep 13, 2021
Suhas gave a talk on Communication Complexity. Continue Reading ❯

Fun with Probability and Expectation
Sep 6, 2021
We had a problem session on probability and expectation. Continue Reading ❯

Incompressibility Method
Apr 12, 2021
Abrahim Ladha gave a talk about the incompressibility method. Continue Reading ❯

Origami as Graph Coloring
Apr 5, 2021
Alvin talked about turning an origami problem into a graph coloring problem. Continue Reading ❯

Graph coloring
Mar 29, 2021
Arvind gave a talk about graph coloring (and some results for the problem based on spectral graph theory). Continue Reading ❯

RSA cryptography problem session
Mar 22, 2021
Tonight we had a hybrid lecture/problemsession on cryptography let by Neil. Continue Reading ❯

Primitive Recursion and Gödel Incompleteness
Mar 15, 2021
We had a special gradstudent guest speaker, Abrahim Ladha, give a talk on primitive recursion and Gödel incompleteness. Continue Reading ❯

Graphs problem session
Mar 8, 2021
We had a problem session guided by Arvind on graphs. Continue Reading ❯

Randomized Algorithms
Mar 1, 2021
Arvind gave a talk about randomized algorithms. Continue Reading ❯

Modular Arithmetic and Cryptography
Feb 22, 2021
Tonight, Neil lectured on modular arithmetic and cryptography. Continue Reading ❯

Graph Algorithms
Feb 15, 2021
Arvind gave a talk about graph algorithms (breadthfirst search, shortcycle decompositions, and (if time permits) random contractions). Continue Reading ❯

Probability and Randomized Algorithms Problem Session
Feb 8, 2021
This week, we had a problem session guided by Arvind involving probability and randomized algorithms. Continue Reading ❯

Game Theory
Feb 1, 2021
Neil gave a lecture on Game Theory (simultaneous and sequential games, extended form, Nash equilibrium, best responses, rational choice, and other topics). Continue Reading ❯

Randomized Algorithms
Jan 25, 2021
Happy new year! Arvind gave a talk on randomized algorithms (planned topics: randomized sorting, Karger’s min cut algorithm). Continue Reading ❯

Traveling Salesman Problem
Nov 16, 2020
Neil gave a talk on the Traveling Salesman Problem (TSP), including the problem itself, NPhardness (as well as briefly what it means to be in NP, NPHard, etc.), the DP algorithm for exact TSP, some variants, and approximation algorithms. Continue Reading ❯

Cryptography
Nov 9, 2020
Neil gave a talk on cryptography (including topics like number theory and RSA). Continue Reading ❯

SpOoOky Problem Session
Nov 2, 2020
We had a SpOoOky (Halloweenthemed) 🎃 problem session led by Arvind today. Continue Reading ❯

Context Free Grammars
Oct 26, 2020
Atul gave a talk about contextfree grammars, along with LL(1) grammars and predictive parsers. Continue Reading ❯

Convex Optimization
Oct 19, 2020
Arvind gave a talk on convex optimization. Continue Reading ❯

skribbl.io Break
Oct 5, 2020
Today we took our minds off school and midterms by playing skribbl.io! Continue Reading ❯

October problem session
Oct 5, 2020
We are having our first problem session tonight at 6:30 pm. Hope to see you there! Continue Reading ❯

Provable Security and Cryptographic Proofs
Sep 28, 2020
Abrahim Ladha gave a talk on provable security and cryptographic proofs. Continue Reading ❯

Network Flows
Sep 21, 2020
Arvind gave a talk about network flows today (including the maxflow mincut theorem and its proof, the FordFulkerson Algorithm, and applications). Continue Reading ❯

Statistical Foundations of ML
Sep 14, 2020
Neil gave a talk about statistical foundations of ML theory (including topics like regression and maximum likelihood estimators). Continue Reading ❯

Graphs and Graph Algorithms
Aug 31, 2020
Today, Alvin gave an introductory talk about graphs and graph algorithms (including topics such as the definition of a graph, the handshake lemma, and the graph isomorphism problem). Continue Reading ❯

Intro to Theory Club
Aug 24, 2020
We kicked off the fall semester with our first meeting! Continue Reading ❯

Differential privacy
Mar 30, 2020
Despite COVID19, BigO Theory Club is continuing to run remotely! Continue Reading ❯

Acyclic orientations
Mar 9, 2020
Daniel gave a talk about acyclic orientations. Continue Reading ❯

Graduate Schule Dinner
Mar 3, 2020
We had a dinner event, where undergrad students could discuss and learn about the life of a typical graduate student. Continue Reading ❯

MinMax Optimization
Mar 2, 2020
Arvind gave a talk on minmax optimization. Continue Reading ❯

Crypto Problem Session
Feb 24, 2020
We had an interesting set of crypto problems! This session was run by Neil Thistlethwaite. Continue Reading ❯

Origami
Feb 17, 2020
Alvin Chiu gave a talk on his research (related to origami). Continue Reading ❯

Random matrices
Feb 10, 2020
Benjamin Bray (graduated from GT with a masters in Computer Science) gave a talk on Random Matrices. Continue Reading ❯

Latticebased Cryptography
Feb 3, 2020
Neil Thistlethwaite gave a talk on Latticebased Cryptography. Continue Reading ❯

Panel  REU's and Research
Jan 27, 2020
The officers had a panel about how to get into Theory CS Research and about applying to Research Experience for Undergrads (REU Summer Programs) and getting recommendations / applying to graduate school. Continue Reading ❯

Spring 2020 First Meeting  Fake Proofs
Jan 13, 2020
We had a fun meeting today, with the officers giving fake proofs. Continue Reading ❯

Minimum Circuit Size Problem by Dylan McKay, the Founder of Theory Club!
Nov 20, 2019
Dylan gave a talk about the Minimum Circuit Size Problem and about the Complexity Theory research that he is currently working on at MIT. Continue Reading ❯

Faculty Lecture with Dr. Ernie Croot
Nov 18, 2019
We had Dr. Ernie Croot give a lecture on relating to his very recent paper: On a Class of Sums with Unexpectedly High Cancellation, and its Applications Continue Reading ❯

Halloween Party
Oct 28, 2019
We had our Halloween special event lead by Alvin Chiu. Continue Reading ❯

Workshop 6: Linear Programming
Oct 21, 2019
Shyamal Patel gave a talk on linear programming. Continue Reading ❯

Workshop 5: Graphs
Oct 7, 2019
Arvind Ramaswami gave a workshop on Graph Theory. Continue Reading ❯

Workshop 4: Cryptography
Sep 30, 2019
Daniel Hathcock gave a talk about Cryptography. Continue Reading ❯

Workshop 3: BigO and Memesorts
Sep 16, 2019
Neil Thistlethwaite gave a talk on analyzing algorithms of sorting algorithms. Continue Reading ❯

Interesting Properties of Convex Sets
Sep 16, 2019
Sherry Sarkar gave a talk at today’s meeting about convexity. Continue Reading ❯

Big O Fall 2019 Intro Workshops
Sep 10, 2019
We had our intro workshops this week! Continue Reading ❯

Big O Fall 2019 First Meeting
Aug 26, 2019
Welcome to Big O: Theory Club! We had our first meeting where we introduced officers explained what Theory Club is all about. Continue Reading ❯

TSP Approximation Algorithms and Linear Program Basics
Apr 15, 2019
This meeting is in preparation for the TSP lecture series ARC will be holding from April 23rd to April 25th. Continue Reading ❯

Elections
Apr 8, 2019
We’ll be electing new officers and talking about future Continue Reading ❯

Randomized Algorithms Problem Session
Apr 1, 2019
Today, we had donuts and a randomized algorithms problem session! Continue Reading ❯

Chromatic Polynomials by Daniel Hathcock
Mar 25, 2019
Daniel Hathcock gave a talk on the interesting properties of the chromatic polynomials of graphs! Continue Reading ❯

Algebraic Combinatorics by Daniel Hathcock and Sherry Sarkar
Mar 11, 2019
Daniel and Sherry gave a talk on partially ordered sets and the Sperner property. Continue Reading ❯

Sturm Sequences by Shyamal Patel
Mar 5, 2019
Shyamal Patel gave a talk on Sturm sequences and their usefulness in finding roots of polynomials. Continue Reading ❯

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! 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. 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. 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. Continue Reading ❯

Oracles in Complexity Theory
Nov 26, 2018
A guest appearance by our faculty talks coordinator DeVon, we had an introduction to oracles. 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. 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! 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. Continue Reading ❯

Spooky Problem Session
Oct 29, 2018
Happy Halloween! We had an adeptly themed problem session led by Arvind this week! Continue Reading ❯

The MultiArmed Bandit Problem
Oct 22, 2018
We had our first faculty talk by Dr. Jacob Abernethy today! Continue Reading ❯

Silly Talks
Oct 15, 2018
Thank you to everyone who presented for silly talks today! 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. 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. Continue Reading ❯

Number Theory Problem Session
Sep 10, 2018
This meeting, we had a problem session on various number theory topics, led by Shyamal. 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. 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 and explained what Theory Club is all about. Continue Reading ❯

Big O Officer Elections
Apr 6, 2018
Officer elections for next school year will be held on April 23rd. 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
Welcome to Georgia Tech’s Big O Theory Club! More things incoming (hopefully) soon. Continue Reading ❯