Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Asymptotic spectra and their applications II

Jeroen Zuiddam
Member, School of Mathematics
October 16, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.

Asymptotic spectra and their applications I

Jeroen Zuiddam
Member, School of Mathematics
October 9, 2018
These two talks will introduce the asymptotic rank and asymptotic subrank of tensors and graphs - notions that are key to understanding basic questions in several fields including algebraic complexity theory, information theory and combinatorics.

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalized on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties.

Tensor rank

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
October 2, 2018
Tensors occur throughout mathematics. Their rank, defined in analogy with matrix rank, is however much more poorly understood, both from a structural and algorithmic viewpoints.

Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem.

Ehud Friedgut
The Weizmann Institute of Science
September 24, 2018

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed size k. A setting which many might consider no less natural, is considering the Boolean lattice of all subsets of {1,...,n} endowed with a product measure, and studying the structure and measure of maximal intersecting families.
 

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

Cody Murray
Massachusetts Institute of Technology
March 26, 2018

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit of only n^O(k^3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME[n^(log n)^O(1)]. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS'02] which only held for larger nondeterministic classes such as NEXP.