This is the home page for NYU's Computer Science Theory seminar, hosted jointly by the Courant Theoretical Computer Science Group and the Tandon Algorithms and Foundations Group.
Time and Location:
Thursday, 11AM
Warren Weaver Hall
251 Mercer Street
Room 202
You can sign up for the Theory Seminar mailing list here. For more information, or if you would like to invite a speaker or give a talk, please contact Christopher Musco.
Fall 2022
Sept. 22
 Vladimir Podolskii (NYU)
 ConstantDepth Sorting Networks [+]

Abstract: We consider sorting networks that are constructed from comparators of arity k>2. That is, in our setting the arity of the comparators — or, in other words, the number of inputs that can be sorted at the unit cost — is a parameter. We study its relationship with two other parameters — n, the number of inputs, and d, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for majority functions from majority gates of lower fanin.
We obtain the first lower bounds on the arity of constantdepth sorting networks. More precisely, we consider sorting networks of depth d up to 4, and determine the minimal k for which there is such a network with comparators of arity k. For depths d=1, 2 we observe that k=n. For d=3 we show that k=n/2. For d=4 the minimal arity becomes sublinear: k=\Theta(n^{2/3}). This contrasts with the case of majority circuits, in which k=O(n^{2/3}) is achievable already for depth d=3.
Joint work with Natalia DobrokhotovaMaikova and Alexander Kozachinskiy: https://eccc.weizmann.ac.il/report/2022/116/
Bio: Vladimir Podolskii defended his PhD thesis in 2009 in Moscow State University. His research areas are computational complexity, tropical algebra, applications of complexity theory to databases augmented with logical theories. Until recently he worked in Steklov Mathematical Institute (Moscow) and HSE University (Moscow).
Sept. 29
 Sepehr Assadi (Rutgers)
 Deterministic Graph Coloring in the Streaming Model [+]

Abstract: Recent breakthroughs in graph streaming have led to the design of singlepass semistreaming algorithms for various graph coloring problems such as (Δ+1)coloring, Δcoloring, degeneracycoloring, coloring trianglefree graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work.
In this talk, we will discuss our recent result that fully resolves this question: there is no deterministic singlepass semistreaming algorithm that given a graph G with maximum degree Δ, can output a proper coloring of G using any number of colors which is subexponential in Δ. The proof is based on analyzing the multiparty communication complexity of a related communication game using elementary random graph theory arguments.
Based on joint work with Andrew Chen (Cornell) and Glenn Sun (UCLA): https://arxiv.org/abs/2109.14891A.
Oct. 6
 Peng Zhang (Rutgers)
 Hardness Results for Weaver's Discrepancy Problem [+]
 Abstract: Marcus, Spielman, and Srivastava (Annals of Mathematics, 2015) solved the KadisonSinger Problem by proving a strong form of Weaver’s discrepancy conjecture. They showed that for all \(\alpha > 0\) and all lists of vectors of norm at most \(\sqrt{\alpha}\) whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most \(\sqrt{8 \alpha} + 2 \alpha\). Besides its relation to the KadisonSinger problem, Weaver’s discrepancy problem has applications in graph sparsification and randomized experimental design. In this talk, we will prove that it is NPhard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least \(k \sqrt{\alpha}\), for some absolute constant \(k > 0\). Thus, it is NPhard to construct a signing that is a constant factor better than that guaranteed to exist. This result is joint work with Daniel Spielman.
Oct. 13
 Dominik Kempa (Stony Brook)
 TBA [+]
 Abstract: TBA
Oct. 18
(this is a Tuesday!)
(this is a Tuesday!)
 Yuval Rabani (Hebrew University of Jerusalem )
 New Results in Online Computing [+]

Abstract: We prove new bounds, mostly lower bounds, on the competitive ratio of a few online problems, including the \(k\)server problem and other related problems. In particular:
1. The randomized competitive ratio of the \(k\)server problem is at least \(\Omega(\log^2 k)\) in some metric spaces. This refutes the longstanding randomized \(k\)server conjecture that the competitive ratio is \(O(\log k)\) in all metric spaces.
2. Consequently, there is a lower bound of \(\Omega(\log^2 n)\) on the competitive ratio of metrical task systems in some \(n\)point metric spaces, refuting an analogous conjecture that in all \(n\)point metric spaces the competitive ratio is \(O(\log n)\). This lower bound matches asymptotically the best previously known universal upper bound.
3. The randomized competitive ratio of traversing width\(w\) layered graphs is \(\Theta(w^2)\). The lower bound improves slightly the previously best lower bound. The upper bound improves substantially the previously best upper bound.
4. The \(k\)server lower bounds imply improved lower bounds on the competitive ratio of distributed paging and metric allocation.
5. The universal lower bound on the randomized competitive ratio of the \(k\)server problem is \(\Omega(\log k)\). Consequently, the universal lower bound for \(n\)point metrical task systems is \(\Omega(\log n)\). These bounds improve the previously known universal lower bounds, and they match asymptotically existential upper bounds.
The talk is based on two papers which are both joint work with Sebastien Bubeck and Christian Coester: Shortest paths without a map, but with an entropic regularizer (the upper bound in 3, to appear in FOCS 2022) The randomized \(k\)server conjecture is false! (all the lower bounds, manuscript)
Oct. 27
 Jessica Sorrell (University of Pennsylvania)
 TBA [+]
 Abstract: TBA
Nov. 10
 Huacheng Yu (Princeton University)
 TBA [+]
 Abstract: TBA
Nov. 17
 Sophie Huiberts (Columbia University)
 TBA [+]
 Abstract: TBA
Dec. 1
 Roei Tell (Institute for Advanced Study/DIMACS)
 TBA [+]
 Abstract: TBA
Dec. 8
 Michael Chapman (NYU)
 TBA [+]
 Abstract: TBA
Spring 2019
May 21
 Jeroen Zuiddam (IAS)
 The asymptotic spectrum of graphs: duality for Shannon capacity [+]
 Abstract: We give a dual description of the Shannon capacity of graphs. The Shannon capacity of a graph is the rate of growth of the independence number under taking the strong power, or in different language, it is the maximum rate at which information can be transmitted over a noisy communication channel. Our dual description gives Shannon capacity as a minimization over the "asymptotic spectrum of graphs", which as a consequence unifies previous results and naturally gives rise to new questions. Besides a gentle introduction to the asymptotic spectrum of graphs we will discuss, if time permits, Strassen's general theory of "asymptotic spectra" and the asymptotic spectrum of tensors.
May 16
 Omri Weinstein (Columbia University)
 Data Structure Lower Bounds imply Rigidity [+]

Abstract: I will talk about new connections between arithmetic data structures, circuit lower bounds and pseudorandomness. As the main result, we show that static data structure lower bounds in the group (linear) model imply semiexplicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t ω(log^2 n) on the cellprobe complexity of linear data structures in the group model, even against arbitrarily small linear space (s = (1+ε)n), would already imply a semiexplicit (P^NP) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy, and Yekhanin, 2009). Our result further asserts that polynomial (t n^δ) data structure lower bounds against nearmaximal space, would imply superlinear circuit lower bounds for logdepth linear circuits (which would close a fourdecade open question). In the succinct space regime (s = n+o(n)), we show that any improvement on current cellprobe lower bounds in the linear model would also imply new rigidity bounds. Our main result relies on a new connection between the inner and outer dimensions of a matrix (Paturi and Pudlak, 2006), and on a new worsttoaverage case reduction for rigidity, which is of independent interest.
Based mostly on joint work with Zeev Dvir (Princeton) and Alexander Golovnev (Harvard).
May 2
 Noah StephensDavidowitz (MIT)
 SETHhardness of coding problems [+]

Abstract: We show that, assuming a common conjecture in complexity theory, there are "no nontrivial algorithms" for the two most important problems in coding theory: the Nearest Codeword Problem (NCP) and the Minimum Distance Problem (MDP). Specifically, for any constant \eps > 0, there is no N^{1\eps}time algorithm for codes with N codewords. In fact, the NCP result even holds for a family of codes with a single code of each cardinality, and our hardness result therefore also applies to the preprocessing variant of the problem.
These results are inspired by earlier work showing similar results for the analogous lattice problems (joint works with three other NYU alums: Huck Bennett and Sasha Golovnev and with Divesh Aggarwal), but the proofs for coding problems are far simpler. As in those works, we also prove weaker hardness results for approximate versions of these problems (showing that there is no N^{o(1)}time algorithm in this case).
Based on joint work with Vinod Vaikuntanathan.
Apr. 11
 LiYang Tan (Stanford University)
 A highdimensional LittlewoodOfford inequality [+]
 Abstract: We prove a new LittlewoodOffordtype anticoncentration inequality for mfacet polytopes, a highdimensional generalization of the classic LittlewoodOfford theorem. Our proof draws on and extends techniques from Kane's bound on the boolean average sensitivity of mfacet polytopes. Joint work with Ryan O'Donnell and Rocco Servedio; manuscript available at https://arxiv.org/abs/1808.04035.
Mar. 21
 Sahil Singla (Princeton)
 The Byzantine Secretary Problem [+]
 Abstract: In the classical secretary problem, a sequence of n elements arrive in a uniformly random order. The goal is to maximize the probability of selecting the largest element (or to maximize the expected value of the selected item). This model captures applications like online auctions, where we want to select the highest bidder. In many such applications, however, one may expect a few outlier arrivals that are adversarially placed in the arrival sequence. Can we still select a large element with good probability? Dynkin’s popular 1/esecretary algorithm is sensitive to even a single adversarial arrival: if the adversary gives one large bid at the beginning of the stream, the algorithm does not select any element at all. In this work we introduce the Byzantine Secretary problem where we have two kinds of elements: green (good) and red (bad). The green elements arrive uniformly at random. The reds arrive adversarially. The goal is to find a large green element. It is easy to see that selecting the largest green element is not possible even when a small fraction of the arrival is red, i.e., we cannot do much better than random guessing. Hence we introduce the secondmax benchmark, where the goal is to select the secondlargest green element or better. This dramatically improves our results. We study both the probabilitymaximization and the valuemaximization settings. For probabilitymaximization, we show the existence of a good randomized algorithm, using the minimax principle. Specifically, we give an algorithm for the known distribution case, based on trying to guess the secondmax in hindsight, and using this estimate as a good guess for the future. For valuemaximization, we give an explicit poly log^∗ n competitive algorithm, using a multilayered bucketing scheme that adaptively refines our estimates of secondmax as we see more elements. For the multiple secretary problem, where we can pick up to r secretaries, we show constant competitiveness as long as r is large enough. For this, we give an adaptive thresholding algorithm that raises and lowers thresholds depending on the quality and the quantity of recently selected elements.
Mar. 14
 Mert Saglam (University of Washington)
 Near logconvexity of heat and the kHamming distance problem [+]
 Abstract: We answer a 1982 conjecture of Erdős and Simonovits about the growth of number ofkwalks in a graph, which incidentally was studied even earlier by Blakley and and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of thekHamming distance isΩ(k log k)and that consequently any property tester forklinearity requires Ω(k log k)queries.
Jan. 24
 Mika Göös (IAS)
 Adventures in Monotone Complexity and TFNP [+]
 Abstract: *Separations:* We introduce a monotone variant of XORSAT and show it has exponential monotone circuit complexity. Since XORSAT is in NC^2, this improves qualitatively on the monotone vs. nonmonotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite fields. These results can be interpreted as separating subclasses of TFNP in communication complexity. *Characterizations:* We show that the communication (resp. query) analogue of PPA (subclass of TFNP) captures span programs over F_2 (resp. Nullstellensatz degree over F_2). Previously, it was known that communication FP captures formulas (KarchmerWigderson, 1988) and that communication PLS captures circuits (Razborov, 1995). Joint work with Pritish Kamath, Robert Robere, and Dmitry Sokolov.