In distributed computing, the notion of extension-based proofs classifies the proof technique in which one demonstrates the impossibility of solving a task in a wait-free manner by constructing an infinite execution. One such example is the famous impossibility proof of the consensus task. In recent years, it was shown that there are tasks with known impossibility results, where the proof of such results are out of reach by any extension-based proof. In a previous talk, using a combinatorial argument, I demonstrated the impossibility of solving approximate agreement on graphs that satisfies certain "impossibility conditions". We will continue our discussion on approximate agreement tasks and show that there is no extension-based impossibility proof of solving approximate agreement on any connected graph.

A b-frugal coloring of a graph is a proper coloring where no color appears more than b times in any neighborhood. The concept was first introduced by Hind, Molloy, and Reed in 1997. For a general graph with a maximum degree D, Molloy and Reed (2009) showed that there exists an O(log D / log log D)-frugal coloring using D+1 colors. The girth of a graph is the length of the shortest cycle in the graph. Kim (1995) proved that for any graph with girth at least five, its chromatic number is upper-bounded by (1 + o(1)) D / ln D. A natural question to ask is whether there exists an O(log D)-frugal coloring of graphs with girth at least five using (1 + o(1)) D / ln D colors. In this talk, I will demonstrate how to use the semi-random method, together with the Lovász Local Lemma, Talagrand's inequality, etc., to prove the existence of an O(log^2 D)-frugal coloring. The proof is an extension of Kim's proof as presented in the graph coloring book by Molloy and Reed.

In this talk, we give a brief introduction to one of the most important methods for bounding stochastic processes: chaining. We will derive a few fundamental results in chaining, including Dudley's bound, the generic chaining bound, and the majorizing measure theorem for Gaussian processes.

Have you ever said to yourself: "Cauchy Schwarz is perfect right now if only the inequality went the other way"? Well, in-fact it can! In this talk we will work through the conditions in which a Cauchy converse exists and its derivation. We follow an excerpt from The Cauchy Schwarz Master Class by Steele.

Given a graph, how long does it take to decompose this graph into a collection of short cycles? While a almost linear time(m^{1 + o(1)}) solution is known, it is open as to if this problem has a near linear time(m\polylog{m}) solution. In this talk, I will give a description of the relatively simple combinatorial algorithm that achieves almost linear time, talk about the classes of problem that are known to solve the short cycle decomposition if solved, as well as give a brief overview of the various uses of this subroutine.

Concentration of measure states that in many instances, a random variable will take on a value close to its mean with high probability. It has become an important tool used in probability and theoretical computer science. Levy's Lemma describes concentration of measure for the uniform spherical measure, and has become important for applications of the probabilistic method in quantum information theory. We will state and prove Levy's lemma, and use Levy's lemma to show the existence of highly entangled subspaces of large dimension.

Last month Hunter released a preprint which gives a construction for 3-AP-free sets. This represents the first improvement in the highest-order term of the lower bound since Behrend in 1946. In this seminar I'll present the elegant construction of Behrend as well as a different way of looking at Behrend's construction by Green and Wolf. I'll then show what needs to be changed to get the improvement shown by Hunter and, if time permits, discuss some of the details of the new paper.

A map f:{0,1}^n -> {0,1}^n has locality t if every output bit of f depends only on t input bits. We call an expander a Local Expander if it is a bounded-degree expander graph on 2^n nodes such that maps of constant locality can compute the neighbors of a node. I will discuss the results in [Viola Wigderson 18], where the authors explicitly construct such graphs with locality "one"! They also give a construction of 3-regular bipartite Ramanujan Graphs with constant locality. After these, I will talk about the construction of [Batra Saxena Shringi 23], which gives construction for bipartite Ramanujan graphs of degree q+1 with constant locality, for any prime power q.

One goal of TSS is to help people understand classic papers in theoretical computer science. Yao's millionaires' problem was introduced in 1982. The problem discusses that two millionaires want to figure out who is richer without revealing the exact amount of money they have. The problem is generalized to the problem of secure two-party computation. Two parties, Alice and Bob, want to jointly compute a function $f$, but they do not want to leak their private input or any information other than the final result to the other party. [Yao '86] presented a constant-round protocol for securely computing any two-party functionality. The protocol is secure against semi-honest adversaries and is based on a cryptography primitive called oblivious transfer (OT). This talk will be based on [Lindell-Pinkas '06'], a well-written paper that gives a clear explanation and proof of the garbled circuit.

Fair Division problems look at how to fairly divide a set of items among many agents with different utility functions. This involves defining formal notions of what it means for an allocation to be 'Fair', and designing algorithms that allocate the items in a way that meets these notions. This talk will explore the model of Temporal Fair Division, where items from a set are allocated in batches over a number of days. In this model, fairness properties are not only concerned about the total allocation over the set of items being fair, but are also concerned about the fairness of the partial allocations of items at any point in time. This talk will look at the possibilities, impossibilities, and open questions in the Temporal Fair Division model.

I will describe 3 well-known string searching algorithms: Knuth-Morris-Pratt algorithm, Aho-Corasick algorithm and Manacher's Algorithm. The KMP algorithm is the first linear time algorithm for searching a pattern string in a text string, and the AC algorithm is an extension of the KMP algorithm for the case where there are multiple pattern strings. Manacher's algorithm is a very elegant linear time algorithm for finding the longest palindromic substring.

I will talk about some error correcting code constructions obtained by evaluating polynomials. I'll show a variant of the classic Reed Muller codes and proof some properties about the code. Along the way I'll prove a slight generalization of the Schwartz-Zippel lemma, and a slight generalization of GMD decoding.