2024 / 01 / 17 |
Extension-based proofs and the impossibility of approximate agreement on graphs [show abstract] 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.
|
Jason Liu |
2024 / 01 / 24 |
Frugal Colouring of Graphs with Girth At Least Five [show abstract][slides] 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. |
Ziyang Jin |
2024 / 01 / 31 |
Stochastic Processes and Chaining[show abstract] 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. |
Yibin Zhao |
2024 / 02 / 07 |
Cauchy Converse[show abstract] 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. |
Lily Li |
2024 / 02 / 14 |
Short Cycle Decomposition[show abstract] 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. |
Lawrence Li |
2024 / 02 / 21 |
Levy's Lemma, with Applications in Quantum Information[show abstract] 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. |
Adrian She |
2024 / 02 / 28 |
3-AP-free sets: Behrend, Green-Wolf, and Hunter[show abstract] 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. |
Morgan Shirley |
2024 / 03 / 06 |
Construction of One-Local Expanders and Constant Locality Ramanujan Graphs[show abstract] 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. |
Devansh Shringi |
2024 / 03 / 13 |
Yao's Garbled Circuits and Some Primitives in Cryptography[show abstract] 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. |
Ziyang Jin |
2024 / 03 / 20 |
Temporal Fair Division[show abstract] 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. |
Ben Cookson |
2024 / 03 / 27 |
String Searching Algorithms[show abstract] 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. |
Haohua Tang |
2024 / 04 / 03 |
Polynomial Evaluation Codes[show abstract] 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. |
Harry Sha |
2024 / 04 / 10 |
Selecting Representative Committees with Ranked Preferences[show abstract] In the committee selection problem, we are given n voters who have ranked preferences over m candidates, and we want to select a committee of k candidates. One goal in the literature is to identify representative committees, where as many voters (and groups of voters) as possible are represented by the committee. In this talk, we will discuss a representation axiom called (local) stability and its probabilistic generalization termed stable lotteries [Aziz et al. 2017, Cheng et al. 2020]. Our goal is to prove the existence of stable lotteries for ranked preferences using von Neumann's minimax theorem, which is a result of Cheng, Jiang, Munagala, and Wang (EC'19).
|
Soroush Ebadian |
2024 / 04 / 24 |
Distortion in metric matching with ordinal preferences[show abstract] Suppose that we have n agents and n items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their matched items is as small as possible. However, instead of having direct access to distances in the metric, we only have each agent’s ranking of the items in order of distance. Given this limited information, what is the minimum possible worst-case
approximation ratio (known as the distortion) that a matching mechanism can guarantee?
I’ll show why a simple mechanism like Serial Dictatorship gets exponential distortion and then go over the proof of Anari et al. to show how we can achieve O(n^2) distortion with a deterministic mechanism.
|
Mohamad Latifian |
2024 / 05 / 01 |
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach[show abstract] This work explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting.
Our main results are 1) an $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed Poincaré inequality $\mathsf{dist}^{\mathsf{mono}}_2(f)^2 \le C\, \mathbb{E}[|\nabla^- f|^2]$, where the "directed gradient" operator $\nabla^-$ measures the local violations of monotonicity of $f$.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.
|
Renato Ferreira Pinto Junior |
2024 / 05 / 08 |
Spectral sparsification of Eulerian digraphs: Faster and Sparser[show abstract] Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems [Peng-Song'22]. In this talk, we give a brief overview of new techniques and advancements for this question. In particular, we consider (1) leveraging matrix discrepancy theory for better sparsity, (2) bypassing specific graph structures (short cycles) using electrical circulations, and (3) regulating circulations using effective resistance partitioning introduced by [Alev-Anari-Lau-Oveis Gharan'18]. This talk is based on works with Jambulapati, Sachdeva, Sidford, Thudi, and Tian.
|
Yibin Zhao |