Permutation groups and the complexity of Boolean functions
We shall study open questions regarding various complexity measures of Boolean functions (decision-tree complexity, sensitivity, property-testing complexity, etc.) in the context of groups of symmetries admitted by these functions.
Basic group theory (including Sylow's theorems, the Jordan-Hölder theorem, solvability), discrete probability, and a course in discrete mathematics or equivalent.
- Pooya Hatami, Raghav Kulkarni, Denis Pankratov: Variations on the sensitivity conjecture. Theory of Computing Library, Graduate Surveys 4 (2011)
- László Babai, Anandam Banerjee, Raghav Kulkarni, Vipul Naik: Evasiveness and the distribution of prime numbers. In: Proc. 27th STACS (2010)
- Jeff Kahn, Michael Saks, Dean Sturtevant: A topological approach to evasiveness. Combinatorica 4 (1984) 297-306
- Peter J. Cameron: Finite permutation groups and finite simple groups. Bull. London Math. Soc. 13 (1981) 1-22
- László Babai: On the automorphism groups of strongly regular graphs I. In: Proc. ITCS 2014, ACM Press, pp 359-368
Learning Polynomials, Graphs, and Densities
This project will explore the use of these ideas in machine learning. The goal is to develop algorithms for estimation of probability densities, regression functions, and graphical models in high dimensions, using semi-definite programming techniques for convex polynomials. The work will also involve studying the statistical properties of the algorithms, and experimenting with them on real data.
- Jean Bernard Lasserre,"Moments, Positive Polynomials and Their Applications," Imperial College Press, 2010.
- Amir Ali Ahmadi, "Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis," MIT EECS Ph.D. Thesis, 2011.
- H. Liu, J. Lafferty, and L. Wasserman, "The nonparanormal: Semiparametric estimation of high dimensional undirected graphs," Journal of Machine Learning Research (JMLR), 2009.
- M. Cule, R. Samworth, and M. Stewart, "Maximum likelihood estimation of a multi-dimensional log-concave density," J. Roy. Statist. Soc., Ser. B., 2010.
Approximation algorithms and hardness results for Max k-CSP with very large domain size
The Boolean and non-Boolean variants of this problem have been extensively studied in the literature, and the approximability of the problem is well understood when $k > \Omega(d)$. On one hand, the problem admits an $\Omega(kd/d^k)$ approximation if $d > \Omega(\log k)$ [MM]. On the other hand, it is NP-hard to get a better than $\Omega(kd/d^k)$ approximation when $d > k$ [Chan]. However, known upper and lower bounds for the case when $d >> k$ are much weaker. This project will study upper and lower bounds for the problem in the case when $d >> k$.
- [Chan] S. O. Chan. Approximation resistance from pairwise independent subgroups. In Proc. of Symposium on Theory of Computing, 2013, pp. 447–456.
- [CMM] M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms 5, 3, Article 32, July 2009.
- [MM] K. Makarychev and Y. Makarychev. Approximation Algorithm for Non-boolean MAX k-CSP. In Proc. of APPROX, 2012, pp. 254–265.
Applications of deep convolutional neural networks
- OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks
- Visualizing and Understanding Convolutional Networks
Probability, linear algebra, basic programming skills (Python, Matlab, C++)
Generic framework for parameter optimization in machine learning
Basic machine learning/statistics, programming skills.
Finding New Classes of Approximation Resistant Predicates
$P$ is said to be approximation resistant if it is NP-hard to approximate CSP($P$) significantly better than just using a random assignment to the variables. Recently, Khot et al. gave a complete characterization of approximation resistant predicates in terms of their Fourier structure. The goal of this project is to find explicit examples of predicates which satisfy this characterization.It would also be interesting to study if one can obtain a simpler characterization for a special class of predicates.
- On the efficient approximability of constraint satisfaction problems
- A talk by Khot describing their characterization
Proving New Hardness Results for Semidefinite Hierarchies
For constraint satisfaction problems, Benabbas et al. proved that for a very general class of predicates, CSP($P$) is hard to approximate using LP hierarchies (even after adding some basic semidefinite constraints). This result also gives a candidate approach for proving these reults in the Lasserre SDP hierarchies, the technical part of which reduces to proving that a certain family of matrices is positive semidefinite. The project could start by computationally verifying this for small matrices and then trying to develop general techniques for proving this.