Institute of Information Science, Academia Sinica

Settling the Approximation Ratio of Boolean Max-2CSP in the Streaming Model
Chi-Ning Chou (Harvard University)

Abstract:
Constraint Satisfaction Problem (CSP)is one of the central computational problems studied in complexity theory. In this work,we focus on the streaming model where the input is a sequence of constraints and the goal is to approximate the maximum number of satisfied constraints using space as small as possible.
Unlike the traditional setting,there have been very few results in the streaming model. A recent line of works culminating in [Kapralov-Krachun, STOC 2019]shows that $(1/2+[@BackSlash]epsilon)$-approximation for Max-CUT requires $[@BackSlash]Omega(n)$ space while there is a trivial 1/2-approximation using $O([@BackSlash]log n)$ space. However,the knowledge of the right approximation ratio for other boolean 2CSP in the streaming model remain elusive. Specifically,prior to this work,there is a 2/5-approximation for Max-DICUT while the hardness side only refutes 1/2-approximation [Guruswami-Velingker-Velusamy, APPROX-RANDOM 2017].
In this work,we show that,surprisingly,the right approximation ratio for Max-DICUT in the streaming model is 4/9. Furthermore,we settle down the right approximation ratios for all the boolean 2CSP in the streaming model. The techniques we are using are random samplings and reductions from the distributional implicit hidden matching problem (DIHP).
This is a joint work with Sasha Golonev and Santhoshini Velusamy.

ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
Brabeeba Wang (Massachusetts Institute of Technology)

Abstract:
Oja's rule [Oja, Journal of mathematical biology 1982] is a well-known biologically-plausible algorithm using a Hebbian-type synaptic update rule to solve streaming principal component analysis (PCA). Computational neuroscientists have known that this biological version of Oja's rule converges to the top eigenvector of the covariance matrix of the input in the limit. However, prior to this work, it was open to prove any convergence rate guarantee. In this work, we give the first convergence rate analysis for the biological version of Oja's rule in solving streaming PCA. Moreover, our convergence rate matches the information theoretical lower bound up to logarithmic factors and outperforms the state-of-the-art upper bound for streaming PCA. Furthermore, we develop a novel framework inspired by ordinary differential equations (ODE) to analyze general stochastic dynamics. The framework abandons the traditional step-by-step analysis and instead analyzes a stochastic dynamic in one-shot by giving a closed-form solution to the entire dynamic. The one-shot framework allows us to apply stopping time and martingale techniques to have a flexible and precise control on the dynamic. We believe that this general framework is powerful and should lead to effective yet simple analysis for a large class of problems with stochastic dynamics.

Lunch