Algebra and Algorithms

Abstract

The main goal of the course is to demonstrate the mutual influence between algebra and computer science, while reviewing/introducing important concepts of computational complexity theory. On one hand, algebraic approaches help create fast algorithms for solving problems not originally formulated in algebraic terms. On the other hand, there are important algebraic operations that we want to perform quickly by themselves. In the course, we will encounter various computational models: the popular RAM model, known functional element circuits, as well as binary decision diagrams, parallel processor circuits, and others.

Topics Covered in Lectures During Fall Semester 2019-2020

• Review of some complexity theory concepts. Problems with binary answers (“yes-no problems”). Classes \(\mathrm{P}\) and \(\mathrm{NP}\). Definition of \(\mathrm{NP}\) class as problems solvable in polynomial time on a computer with unlimited parallel processors. Classes \(\mathrm{NC}^{k}\) and \(\mathrm{NC}\). Parallel computation of prefixes of “products” of \(n\) elements for associative operations. [Kozen, §28.3] Binary number addition in class \(\mathrm{NC}^1\). Binary number multiplication in class \(\mathrm{NC}^1\). [Kozen, §30]
• Division with remainder (Newton’s method-based algorithm). [Kozen, §30]
• Discussion of circuit size for arithmetic operations. Sub-quadratic size circuit for number multiplication: Karatsuba-Ofman algorithm [Vereshchagin-Shen, §1.3, Theorem 13]. Complexity estimates for “most complex function”. Asymptotically optimal circuit for decoder (induction → meet-in-the-middle trick). Optimal circuit for universal multiplexer (arbitrary circuit → topological sorting → duplicate elimination). Boolean function decomposition formula by several variables. Upper bound on complexity of most complex function \(10\cdot\frac{2^n}{n}\). [Wegener, §4.1, §4.2] [Vereshchagin-Shen, §1.3, Problem 13]
• Note on explicit construction of optimal universal multiplexer: first build all elementary conjunctions, then use only disjunction elements to build functions in order of increasing number of ones in value column. [??] Lower asymptotic bound for Shannon function \(\mathrm{const}\cdot\frac{2^n}{n}\) (counting method - if complexity is small, there aren’t enough circuits): transition from circuits to labeled trees; estimating number of unlabeled root trees using depth-first search, multiply by number of labelings. Shannon effect: almost all functions are complex. Note on huge difference between known estimates for almost all functions and lower bounds for specific functions. [Wegener, §4.1, §4.2]
• Csanky’s algorithm for computing matrix determinant in class \(\mathrm{NC}\) (reducing determinant problem to computing traces of matrix powers and subsequent solving of “lower triangular” system of linear equations). Note on solvability of general linear systems in \(\mathrm{NC}\). [Kozen, §31]
• Lipton-DeMillo-Schwartz-Zippel theorem (Schwartz-Zippel lemma). [Wikipedia] Application of Schwartz-Zippel lemma to perfect matching existence problem (computing determinant of bipartite graph adjacency matrix) and rooted tree isomorphism problem. [Kozen, §40]
• DLS problem (optimization of additive function on family of subsets of finite set). Isolation lemma (Mulmuley-Vazirani-Vazirani theorem). [Ta-Shma] Probabilistic parallel algorithm for finding perfect matching in bipartite graph [Motwani-Raghavan, §12.4.2]
• Application of “divide and conquer” approach in matrix multiplication: Strassen’s algorithm. [Aho-Hopcroft-Ullman, §6.2]
• Transitive closure of graph (relation) problem and connection to matrix multiplication. Arlazarov-Dinitz-Kronrod-Farajev method for speeding up Boolean matrix multiplication (“Four Russians’ Algorithm”). [Aho-Hopcroft-Ullman, §6.6]
• Connection between matrix multiplication complexity and rank of trilinear forms. Computational equivalence of matrix multiplication tasks of different sizes. [Alekseev (Survey), §4-5]
• Toom’s algorithm for number multiplication with complexity \( O(n^{1+\epsilon}) \) for arbitrarily small \( \epsilon \). [Alekseev, §2.4] Matrix multiplication constant. NVP-decomposition of matrix. Computational equivalence of matrix inversion and multiplication tasks. Fast determinant computation given fast matrix multiplication algorithm. [Aho-Hopcroft-Ullman, §§6.3-6.5]
• Freivalds’ probabilistic algorithm for matrix multiplication verification with quadratic complexity. [Wikipedia] Tutte’s theorem: “physical” algorithm for embedding 3-connected planar graphs - without proof of correctness. [Lovász], [slides]
• PageRank algorithm: main idea (interpretations with “reputation weight redistribution” and “random walk on internet graph”), problems (with sink vertices). Introduction of “teleportation” as solution to the problem. [Büttcher-Clarke-Cormack, §15.3]
• Discrete Fourier Transform. Connection with polynomial multiplication and signal transformation in time-invariant linear systems. Fast Fourier Transform algorithm. [Dasgupta-Papadimitriou-Vazirani, §2.6]
• Linear Programming. Duality in linear programming as existence of optimality certificates. [Dasgupta-Papadimitriou-Vazirani, §7.4] Application of linear programming to vertex cover problem in graphs. Simple rounding in weighted vertex cover problem. 2-approximation algorithm for vertex cover not using linear programming solution. [Trevisan, §7]
• Sparsest cut problem in graphs. Approximation algorithm based on graph Laplacian eigenvalues. [Matoušek, §31]
• Hadamard theorem, Hadamard matrices, Hadamard conjecture. Error-correcting codes. Block coding. Bose-Shrikhande codes based on Hadamard matrices (two types). Plotkin bound, its achievability on Bose-Shrikhande codes. Field of residues modulo prime, primitive element, quadratic residues, Legendre symbol and its multiplicativity. Construction of Hadamard matrix of order \( p+1 \) when \( 4\mid(p+1) \) using Paley construction. [lecture notes on coding theory], [Romashchenko-Rumyantsev-Shen]
• Barrington’s theorem on constructing constant-width and polynomial-size BDD from \(\mathrm{NC}^1\) circuit. [Wikipedia], [Lecture notes]

Some Topics from Previous Years’ Lectures

• Solving discrete problems as computing Boolean functions. Functional element circuits (algorithm → sequence of circuits). Bases \(B_0\) and \(B_2\). Circuit complexity measures: size and depth. [Vereshchagin-Shen, §1.3, Theorems 7 and 16] Complexity of “most complex functions” of \(n\) arguments. Upper bound on number of circuits with given number of inputs and complexity. Lower asymptotic bound \(\frac{2^n}{n}\) (counting method - if complexity is small, there aren’t enough circuits). Shannon effect: almost all functions are complex. Note on huge difference between known estimates for almost all functions and lower bounds for specific functions. Lower bound of \(2n-3\) for \(\bmod 3\) counter functions. [Wegener, §5.2] Asymptotically optimal circuit for decoder (induction → meet-in-the-middle trick). Optimal circuit for universal multiplexer (arbitrary circuit → topological sorting → duplicate elimination). Boolean function decomposition formula by several variables. Upper bound on complexity of most complex function \(10\cdot\frac{2^n}{n}\). [Wegener, §4.1, §4.2] Classes \(\mathrm{NC}\) and \(\mathrm{AC}\).
• Connection between depth and computation time by circuit. Equivalence of bases in terms of growth order of size and depth of circuits. Estimates of circuit depth built from formulas through their size. [Vereshchagin-Shen, §1.3, Theorems 7 and 16]
• Recurrence inequality theorem. [Cormen, §4.5]
• Wigderson’s theorem on simulating contact schemes with parity circuits. [Jukna 1st edition, Theorem 12.6]
• Classes \(\mathrm{RP}\), \(\mathrm{co‑RP}\) and \(\mathrm{ZPP}\). Equality \(\mathrm{RP} \cap \mathrm{co‑RP} = \mathrm{ZPP}\). [Cai, §5.4] Lipton-DeMillo-Schwartz-Zippel theorem (Schwartz-Zippel lemma). Application of Schwartz-Zippel lemma to perfect matching existence problem (computing determinant of bipartite graph adjacency matrix). [Kozen, §40]
• Probabilistic parallel algorithm for finding perfect matching in bipartite graph [Motwani-Raghavan, §12.4.2]
• Transitive closure problem and connection to matrix multiplication. Arlazarov-Dinitz-Kronrod-Faradev method for speeding up Boolean matrix multiplication (“Four Russians’ Algorithm”). [Aho-Hopcroft-Ullman, §6.6]
• Discrete Fourier Transform. Connection with polynomial multiplication. Note on signal processing applications. Fast Fourier Transform algorithm. [Dasgupta, §2.6] [Optional: Schönhage-Strassen algorithm. [Aho-Hopcroft-Ullman, ch. 7]
• Introduction to search engine ranking problem. Random walk on web graph: PageRank. System of linear equations for its computation.
• Linear Programming. Duality in linear programming as existence of optimality certificates. Example: shortest path problem as problem of “stretching graph made of threads” and its dual problem - minimum cost flow problem. [Dasgupta-Papadimitriou-Vazirani, §7.4]
• Application of linear programming to covering problem. Simple rounding in weighted vertex cover problem. Probabilistic rounding in set cover problem. Combinatorial algorithm based on duality for weighted vertex cover problem. [Trevisan, §7]
• Error-correcting codes. Hamming and Plotkin bounds. Hadamard matrices. Sketch of Hadamard theorem proof. Using Hadamard matrices to construct codes achieving Plotkin bound. [Romashchenko-Rumyantsev-Shen]
• Homogeneous sets of binary strings. Construction of homogeneous sets based on Reed-Muller codes. Application of 3-homogeneous sets for solving weakened 3-SAT problem. [Dainyak, §9.3]
• Application of group theory in computer science. Barrington’s theorem on constructing constant-width BDD from Boolean formula with polynomial complexity growth. [Wikipedia]

Literature

• V. B. Alekseev. Introduction to Algorithm Complexity Theory. Moscow: MSU CMC Faculty Publishing Department, 2002, 82 p.
• V. B. Alekseev. Matrix Multiplication Complexity. Survey. // Cybernetics Collection, issue 25. 1988.
• A. Aho, J. Ullman, J. Hopcroft. The Design and Analysis of Computer Algorithms. Moscow: Mir, 1979. [Ch. 6,7]
• N. K. Vereshchagin, A. Shen. Languages and Computation. 4th ed., revised, Moscow: MCCME, 2012, 240 p.
• A. B. Dainiak. Lecture Notes on Coding Theory
• S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. Moscow: MCCME, 2014.
• P. Naudin, C. Quitté. Algebraic Algorithmics. Moscow: Mir, 1999.
• A. Romashchenko, A. Rumyantsev, A. Shen. Notes on Coding Theory. Moscow: MCCME, 2011.
• A. Shen. Introduction to Theoretical Computer Science, course on Stepik platform.
• S. Büttcher, C. L. A. Clarke, G. V. Cormack. Information Retrieval. Implementing and Evaluating Search Engines. MIT Press, 2010.
• J.-Y. Cai. Lectures in Computational Complexity. (Lecture notes).
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.
• S. Jukna. Extremal Combinatorics with Applications to Computer Science (1st edition). Springer, 2001.
• S. Jukna. Extremal Combinatorics with Applications to Computer Science (2nd edition). Springer, 2011.
• D. Kozen. Design and Analysis of Algorithms. Springer, 1991.
• L. Lovász. Geometric Representations of Graphs. Institute of Mathematics Eötvös Loránd University, Budapest. 2009.
• J. Matoušek. Thirty-three miniatures: mathematical and algorithmic applications of linear algebra. Springer, 2010.
• R. Motwani, P. Raghavan. Randomized algorithms. Cambridge University Press, 1995.
• M. Sudan. Algorithmic Introduction to Coding Theory. Lecture notes. MIT, 2001.
• N. Ta-Shma. A simple proof of the Isolation Lemma // ECCC Report TR15-080.
• L. Trevisan. Combinatorial Optimization: Exact and Approximate Algorithms. 2011.
• I. Wegener. The Complexity of Boolean Functions. Wiley, 1987.