O(blog)

Thoughts on theoretical computer science and research life.

RSS

• 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. Sugar-topped 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 reverse-mode automatic differentiation

  Feb 3, 2023

  Stephen talked about automatic differentiation (autodiff) techniques including finite differencing, forward-mode autodiff, and reverse-mode 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 mini-problem 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 hands-on 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/problem-session on cryptography let by Neil. Continue Reading ❯

• Primitive Recursion and Gödel Incompleteness

  Mar 15, 2021

  We had a special grad-student 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 (breadth-first search, short-cycle 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, NP-hardness (as well as briefly what it means to be in NP, NP-Hard, 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 (Halloween-themed) 🎃 problem session led by Arvind today. Continue Reading ❯

• Context Free Grammars

  Oct 26, 2020

  Atul gave a talk about context-free 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 max-flow min-cut theorem and its proof, the Ford-Fulkerson 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 COVID-19, Big-O 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 ❯

• Min-Max Optimization

  Mar 2, 2020

  Arvind gave a talk on min-max 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 ❯

• Lattice-based Cryptography

  Feb 3, 2020

  Neil Thistlethwaite gave a talk on Lattice-based 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: Big-O 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 Zero-Knowledge

  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 error-correction 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 Multi-Armed 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

  egg Continue Reading ❯

• 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 light-hearted 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 ❯