# Theory Seminar @ Computing Science, SFU

Theory Seminar series organized by theory group, Computing Science at SFU. We gratefully acknowledge the Pacific Institute of Mathematical Sciences for their generous funding.

## Details

### Venue & Time

The usual venue is the CS-Seminar room 9204 in TASC-1. The standard day/time of the seminar for the Fall'19 semester is Mondays from 11:30am to 12:30am.

### Mailing list

Our announcements/updates are sent out on the theory seminar mailing list at cs-theorysem@sfu.ca. If you would like to subscribe, please click the following link and sent us a mail : subscribe, or email Sajin Koroth at .

## Upcoming Talk

### September 23rd : A Boosting Tutorial via Game Theory - Marco Leandro Carmosino (PIMS Postdoctoral Fellow, SFU)

Abstract

This talk will give prove the correctness of simple boosting algorithms using basic game theory.

Boosting is a technique for using weak learning algorithms whose accuracy barely beats a coin toss to construct strong learning algorithms who have 99% accuracy. It is an ensemble method that creates a "committee" of weak hypotheses whose combination is extremely accurate. It has applications across learning, complexity theory, and mathematics.

The analysis via game theory will provide both a strong intuition for how boosting algorithms work, and deep connections to online learning and convex optimization.

## Future Talks

### September 30th : Faster k-SAT algorithms using biased-PPSZ - Uri Zwick (TAU)

Abstract

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k>=3. For k=3 we also improve on Herli's result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from $$1.308^n$$ to $$1.307^n$$.

Joint work with Thomas Dueholm Hansen, Haim Kaplan and Or Zamir.

## Past Talks

### September 16th : Learning models : connections between boosting, hard-core distributions, dense models, GAN, and regularity - Russell Impagliazzo (UCSD)

Abstract

A theme that cuts across many domains of computer science and mathematics is to find simple representations of complex mathematical objects such as graphs, functions, or distributions on data. These representations need to capture how the object interacts with a class of tests, and to approximately determine the outcome of these tests.

For example, a scientist is trying to find a mathematical model explaining observed data about some phenomenon, such as kinds of butterflies in a forest. A minimal criterion for success is that the model should accurately predict the results of future observations. When is this possible? This general situation arises in many contexts in computer science and mathematics. In machine learning, the object might be a distribution on data points, high dimensional real vectors, and the tests might be half-spaces. The goal would be to learn a simple representation of the data that determines the probability of any half-space or possibly intersections of half spaces. In computational complexity, the object might be a Boolean function or distribution on strings, and the tests are functions of low circuit complexity. In graph theory, the object is a large graph, and the tests are the cuts; the representation should determine approximately the size of any cut. In additive combinatorics, the object might be a function or distribution over a group, and the tests might be correlations with linear functions or polynomials.

This talk is to illustrate the connections between these various contexts. In particular, we'll show how to convert boosting algorithms into unsupervised learning algorithms similar to GANs. These algorithms produce dense models'' from seeing samples of a distribution, that are high entropy distributions that are indistinguishable from the samples by a class of tests. To illustrate the versatility of the techniques, we'll show direct applications to Fourier analysis of functions, leakage-resistant cryptography and graph theory.

We will then discuss how to implement the algorithms in question, and in particular, bounds on the sample complexity required to ensure generalization.

### July 4th : The challenge of broadcasting and a new graph sampling lemma - Valerie King (UVic)

Abstract

The problem of broadcasting in a distributed network is to transmit a single message from one node to every other node. We assume each node knows its neighbors, and communication is by message-passing. For many years, the simple flooding algorithm was considered optimal but this requires a transmission across every edge. Since 2015, we have made substantial progress on this problem. Monte Carlo algorithms, for synchronous and asynchronous networks can build a spanning tree (or minimum spanning tree) with a number of messages sublinear in the number of edges, for dense graphs. But Monte Carlo algorithms have a probability of error. Is a deterministic algorithm possible? In this talk I’ll focus on recent work about a simplified version of the problem. It has led to a surprising graph sampling lemma with potentially interesting applications.

This work will appear in FOCS 2019. This is joint work with Jacob Holm, Mikkel Thorup, Or Zamir, and Uri Zwick.

### June 20th : Toward a dichotomy for approximation of $$H$$-coloring : Akbar Rafiey (SFU)

Abstract

Given two (di)graphs $$G$$, $$H$$ and a cost function $$c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$$, in the minimum cost homomorphism problem, MinHOM($$H$$), we are interested in finding a homomorphism $$f:V(G)\to V(H)$$ (a.k.a $$H$$-coloring) that minimizes $$\sum\limits_{v\in V(G)}c(v,f(v))$$. The complexity of \emph{exact minimization} of this problem is well understood due to Hell and Rafiey 2012, and the class of digraphs $$H$$, for which the MinHOM($$H$$) is polynomial time solvable is a small subset of all digraphs.

In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM($$H$$) is not approximable if $$H$$ contains a \emph{digraph asteroidal triple (DAT)}. We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM($$H$$) when $$H$$ is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a \emph{conservative semi-lattice polymorphism} or \emph{min-ordering}), and $$k$$-arc digraphs (digraphs with an \emph{extended min-ordering}). Specifically, we show that:

a) \textbf{Dichotomy for Graphs:} MinHOM($$H$$) has a $$2|V(H)|$$-approximation algorithm if graph $$H$$ admits a \emph{conservative majority polymorphims} (i.e. $$H$$ is a \emph{bi-arc graph}), otherwise, it is inapproximable; b) MinHOM($$H$$) has a $$|V(H)|^2$$-approximation algorithm if $$H$$ is a bi-arc digraph; c) MinHOM($$H$$) has a $$|V(H)|^2$$-approximation algorithm if $$H$$ is a $$k$$-arc digraph.

In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of $$H$$. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs $$H$$, where MinHOM($$H$$) admits a constant factor approximation algorithm that is independent of $$|V(H)|$$.

Join work with Arash Rafiey and Tiago Santos

### June 6th : Revenue optimization for correlated bidders via sampling - Hu Fu

Abstract

Correlation among buyers' valuations enables a revenue maximizing seller to fully extract the social surplus, with no money left to the buyers. This was shown in a classic work by Cremer and McLean. The model has been criticized for allowing arbitrary dependence of the mechanism on the prior: any uncertainty on the prior disrupts the mechanism. We examine this criticism from a learning point of view. We allow uncertainty on the prior but grant the seller sample access from the true prior, and study the number of samples that suffice for surplus extraction. We give precise bounds on the number of samples needed, which show that surplus extraction needs much less information than learning the prior itself. In a sense, this is because the buyers "collaborate" in the learning, driven by their incentives. Our upper bound on the number of samples is by an algebraic argument.

### May 23rd : Counting (with) homomorphisms - Radu Curticapean

Abstract

We survey results on counting graph homomorphisms, a simple yet comprehensive framework that unifies various graph-theoretic counting problems, sometimes in unexpected ways.

In the central problem for this framework, there are some objects on the left and some objects on the right. The objects on the left stand in relationships, as specified by a graph L. Likewise, the objects on the right share relationships specified by a graph R. A homomorphism f from L to R is a function that maps the left objects to the right objects such that present relationships are preserved: If uv is an edge in L, then its image f(u)f(v) is required to be an edge in R.

Given L and R as input, counting homomorphisms from L to R is #P-complete, and thus at least NP-hard: The problem can express counting proper 3-colorings of graphs (by taking L as input and fixing R to a triangle) or counting cliques of a desired size (by fixing L to a complete graph and taking R as the input, assuming R has no self-loops). We study how the complexity of this problem varies under more general restrictions on L and R:

• Concerning restrictions on R, Dyer and Greenhill proved a dichotomy for the complexity of counting homomorphisms to fixed graphs R almost 20 years ago: The problem is #P-complete unless R has a very simple structure. We revisit their result, sketching a new and simplified proof that also gives tight lower bounds under the exponential-time hypothesis ETH.

• Concerning restrictions on L, it is clear that counting homomorphisms is polynomial-time solvable for every fixed L. A result by Marx shows that, assuming ETH, the exponent of optimal algorithms is essentially the treewidth of L. We survey how the complexity of counting general small subgraph patterns can be understood by first expressing them as homomorphism counting problems and then using bounds on the complexity of the relevant homomorphism problems.

While the settings of counting homomorphisms from fixed L or to fixed R may seem very different, we observe that they are both governed by the same connections between complexity-theoretic and algebraic properties of graph homomorphisms.

Based on joint works with Hubie Chen, Holger Dell, and Daniel Marx.

### May 16th : Near-optimal sample complexity bounds for learning mixtures of Gaussians - Chris Liaw

Abstract

Estimating distributions from observed data is a fundamental task in statistics that has been studied for over a century. We consider such a problem where the distribution is a mixture of k Gaussians in $$\mathbb{R}^d$$. The objective is density estimation: given i.i.d. samples from the (unknown) distribution, produce a distribution whose total variation distance from the unknown distribution is at most $$\epsilon$$. We prove that $$Θ(kd^2/\epsilon^2)$$ samples are necessary and sufficient for this task, suppressing logarithmic factors. This improves both the known upper bound and lower bound for this problem.

This is joint work with Hassan Ashtiani, Shai Ben-David, Nick Harvey, Abbas Mehrabian, and Yaniv Plan.

### April 25th : Anti-Concentration in most directions - Anup Rao

Abstract

Abstract. I will discuss a recent proof giving anti-concentration bounds for the inner product of two independent random vectors. For example, we show that if A, B are subsets of the cube $$\{±1\}^n$$ with $$|A| · |B| \geq 2^{1.01n}$$, and $$X \in A$$ and $$Y \in B$$ are sampled independently and uniformly, then the inner product $$<X,Y>$$ takes on any fixed value with probability at most $$O( 1/ \sqrt{n} )$$. Extending Hal´asz work, we prove stronger bounds when the choices for $$x$$ are unstructured. I will discuss some applications of these results to communication complexity.

Joint work with Amir Yehudayoff.

### April 18th : Circuit Lower Bounds for MCSP from Local Pseudorandom Generator - Zhenjian Lu

Abstract

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $$f$$ can be computed by a Boolean circuit of size at most $$\theta$$, for a given parameter $$\theta$$. Understanding the exact complexity of MCSP is an important open problem in computational complexity theory. In this talk, I will talk about lower bounds for computing MCSP in some weak/restricted computational models. In particular, I will discuss some new and improved lower bounds for MCSP under several restricted circuit models including Boolean formulas, constant-depth circuits, and branching programs. These lower bounds for MCSP essentially match the best-known lower bounds for any explicit function/problem in these models.

Joint work with Mahdi Cheraghchi (Imperial College London), Valentine Kabanets (Simon Fraser University), and Dimitrios Myrisiotis (Imperial College London).

### April 11th : A PTAS for approximating the genus of dense graphs - Bojan Mohar

Abstract

Approximating the genus of graphs is one of the challenging open problems in approximation algorithms. Following our FOCS 2018 work, the speaker will show that for dense graphs the genus can be approximated with a PTAS of quadratic time complexity.

This is joint work with Yifan Jing.

### April 4th : Circuit lower bounds for the Min Circuit Size Problem - Valentine Kabanets

Abstract

The Minimum Circuit Size Problem (MCSP) is a problem to decide the minimum circuit complexity of a boolean function given by its truth table. More precisely, given a 2^n-bit string T (representing all the values of some boolean function f on n variables), and a parameter s>0, one needs to decide if there is a circuit of size at most s that computes f. While MCSP is easily seen to be in NP (guess a circuit of size s and then check if it computes f), it is still unknown if MCSP is NP-complete. In fact, Leonid Levin (co-discoverer of NP-completeness) delayed his NP-completeness paper in the 1970s because he tried to prove that MCSP is NP-complete, but could not. The question whether MCSP is NP-complete remains open today.

MCSP is a meta-computational problem that has applications to a number of areas of theoretical computer science: circuit complexity, cryptography, computational learning, proof complexity, and more. Since around 2015, there has been an increased interest in MCSP, with many research papers coming out in the past couple of years.

In this talk, I will present some very recent results on the circuit complexity of MCSP against several restricted circuit models, which essentially match the known state-of-the-art circuit lower bounds known today for explicit boolean functions. In particular, I will show that MCSP requires exponential-size circuits of constant depth, with AND, OR, NOT, and PARITY gates (of unbounded fanin), i.e., the circuit class AC^0[2]. I will also talk about almost-cubic lower bounds against boolean formulas with AND, OR, and NOT gates (de Morgan formulas).

No prior background in circuit complexity will be assumed for this talk. It is aimed to be understandable by first-year graduate students interested in theoretical computer science.

(Based on the joint works with A. Golovnev, R. Ilango, R. Impagliazzo, A. Kolokolova and A. Tal, as well as M. Cheraghchi, Z. Lu, and D. Myrisiotis.)

### March 28th : Another problem with variants on either side of the P vs. NP divide - Leonid Chindelevitch

Talk slides

Abstract

In our computer science classes we learn about several problems with variants crossing the boundary between P and NP: edge cover vs. vertex cover, 2-SAT vs. 3-SAT, LP vs. ILP, min-cut vs. max-cut. In this talk we focus on yet another such problem, motivated by genomics. It is the problem of finding the rank median of three permutation matrices. On the positive side, we show that if the median is allowed to be rational, then we can find it in O(n^w) time, where w is the matrix multiplication exponent. On the negative side, we show that if the median must be a permutation, the problem is not only NP-hard, but also APX-hard. We conclude with some open questions and directions for future work.

### March 14th : Probabilistic Checking against Non-Signaling Strategies from Linearity Testing - Igor Shinkar

Abstract

Non-signaling strategies are collections of distributions with certain non-local correlations that have been studied recently in the context of delegation of computation. In this talk I will discuss a recent result showing that the classical PCP construction of [ALMSS'92] is sound against non-signaling strategies. As part of the proof, we study the problem of linearity testing [BLR'93] in the non-signaling setting, and prove that any no-signaling strategy that passes the linearity test with high probability must be close to a “quasi-distribution” over linear functions. Quasi-distributions generalize the notion of probability distributions over functions by allowing negative probabilities, while at the same time requiring that “local views” follow standard distributions (with non-negative probabilities).

Joint work with Alessandro Chiesa and Peter Manohar (UC Berkeley).