I will outline some aspects of the program (as it is presently understood) of proving circuit complexity lower bounds from the design of particular algorithms for analyzing circuits.
NOTE: Due to a technical error, the first 10 minutes of the presentation have been cut. We apologize for any inconvenience.
I will outline some aspects of the program (as it is presently understood) of proving circuit complexity lower bounds from the design of particular algorithms for analyzing circuits.
Restrictions are a means of simplifying circuits by assigning values to a subset of input variables. This talk will present an overview of lower bounds based on restrictions, especially random restrictions. This includes a review Hastad’s classic switching lemma for p-random restrictions and a discussion of recent extensions which have led to #SAT algorithms and bounds on the Fourier spectrum of AC^0 functions. We will also discuss other types of random restrictions (projections and affine restrictions) which have been instrumental in recent breakthroughs in circuit complexity and proof complexity.
Restrictions are a means of simplifying circuits by assigning values to a subset of input variables. This talk will present an overview of lower bounds based on restrictions, especially random restrictions. This includes a review Hastad’s classic switching lemma for p-random restrictions and a discussion of recent extensions which have led to #SAT algorithms and bounds on the Fourier spectrum of AC^0 functions. We will also discuss other types of random restrictions (projections and affine restrictions) which have been instrumental in recent breakthroughs in circuit complexity and proof complexity.
I will talk about the broad field of proof complexity. Its central question is whether there exists an NP algorithm certifying that a Boolean formula is unsatisfiable. Or, put differently, whether there exists a propositional
proof system P in which every unsatisfiable formula has a short refutation. The expected answer is ”no”, but this can be unconditionally proved only for relatively weak systems P, such as Resolution, Cutting Planes, or bounded-depth Frege. I will overview techniques used in the area, as well as focus on open problems.
I will talk about the broad field of proof complexity. Its central question is whether there exists an NP algorithm certifying that a Boolean formula is unsatisfiable. Or, put differently, whether there exists a propositional
proof system P in which every unsatisfiable formula has a short refutation. The expected answer is ”no”, but this can be unconditionally proved only for relatively weak systems P, such as Resolution, Cutting Planes, or bounded-depth Frege. I will overview techniques used in the area, as well as focus on open problems.
We will review how circuit lower bounds have been used to design algorithms, and in particular, to give deterministic analogs of randomized algorithms. In the first hour, we will discuss the generic “hardness as randomness” paradigm, following Nisan and Wigderson. We will also discuss using this paradigm in the algebraic circuit setting. In the second hour, we will show how specific lower bound techniques (algebraic approximation and random restrictions) have been used to construct efficient pseudo-random generators.
We will review how circuit lower bounds have been used to design algorithms, and in particular, to give deterministic analogs of randomized algorithms. In the first hour, we will discuss the generic “hardness as randomness” paradigm, following Nisan and Wigderson. We will also discuss using this paradigm in the algebraic circuit setting. In the second hour, we will show how specific lower bound techniques (algebraic approximation and random restrictions) have been used to construct efficient pseudo-random generators.
Algebraic complexity theory studies the complexity of multivariate polynomials over a fixed field. The classical models of computation are algebraic circuits, algebraic formulas, algebraic branching programs, and determinants of affine linear forms. If the ground field is the real or complex numbers, then the set of polynomials of complexity at most n lies dense in an algebraic variety. Studying its geometric structure dates back to early work by Mulmuley and Sohoni (2001), and also Bürgisser (2001). Analogous studies have been conducted much earlier by Bini et al. (1979, 1980) in the setting of tensors when studying matrix multiplication. Following Mulmuley and Sohoni, we carefully adjust the algebraic complexity measures so that set of polynomials of complexity at most n becomes an algebraic variety that is endowed with a group action of the general linear group. This enables us to study complexity lower bounds using representation theory. No prior knowledge about algebraic complexity theory, algebraic geometry, or representation theory is needed for this talk.
Algebraic complexity theory studies the complexity of multivariate polynomials over a fixed field. The classical models of computation are algebraic circuits, algebraic formulas, algebraic branching programs, and determinants of affine linear forms. If the ground field is the real or complex numbers, then the set of polynomials of complexity at most n lies dense in an algebraic variety. Studying its geometric structure dates back to early work by Mulmuley and Sohoni (2001), and also Bürgisser (2001). Analogous studies have been conducted much earlier by Bini et al. (1979, 1980) in the setting of tensors when studying matrix multiplication. Following Mulmuley and Sohoni, we carefully adjust the algebraic complexity measures so that set of polynomials of complexity at most n becomes an algebraic variety that is endowed with a group action of the general linear group. This enables us to study complexity lower bounds using representation theory. No prior knowledge about algebraic complexity theory, algebraic geometry, or representation theory is needed for this talk.
Arithmetic circuits are the natural computational model for problems that can be cast in the language of computing one or more multivariate polynomials. The Determinant, Permanent, and Matrix Multiplication are some well-known examples of problems of this kind. In this tutorial, we will start with basic definitions related to the arithmetic circuit model (and variants), introduce some basic questions regarding this model, and see the ideas behind some well-known lower bound results in the area.
Arithmetic circuits are the natural computational model for problems that can be cast in the language of computing one or more multivariate polynomials. The Determinant, Permanent, and Matrix Multiplication are some well-known examples of problems of this kind. In this tutorial, we will start with basic definitions related to the arithmetic circuit model (and variants), introduce some basic questions regarding this model, and see the ideas behind some well-known lower bound results in the area.
Communication complexity can be viewed as the “master model” for proving lower bounds on discrete models. Reductions show that lower bounds on communication complexity give lower bounds on boolean circuits, data structures, algorithms in distributed computing, proof complexity, branching programs, Ramsey theory...after more than 3 decades of work, this list is still growing every year. We will give a quick introduction to the basic model of communication, see some examples of how it is connected to other models of computation, and discuss some of the major open questions in communication complexity.
Communication complexity can be viewed as the “master model” for proving lower bounds on discrete models. Reductions show that lower bounds on communication complexity give lower bounds on boolean circuits, data structures, algorithms in distributed computing, proof complexity, branching programs, Ramsey theory...after more than 3 decades of work, this list is still growing every year. We will give a quick introduction to the basic model of communication, see some examples of how it is connected to other models of computation, and discuss some of the major open questions in communication complexity.
In this talk, we survey the techniques that have been proposed for proving unconditional lower bounds for dynamic data structures. We start by introducing the chronogram method of Fredman and Saks 1989, for proving logn/loglogn lower bounds. We then proceed to present the information transfer method of Patrascu and Demaine 2004, which allow us to prove logn lower bounds. After that, we present the current strongest technique, due to Larsen 2012, which allow us to prove (logn/loglogn)^2 lower bounds. We finally conclude by introducing recent work by Larsen, Weinstein and Yu 2018, which proves the first lower bounds of (logn/loglon)^(3/2) for decision problems. This improves over the best previous logn lower bounds for decision problem, due to Patrascu and Demaine 2004.
In this talk, we survey the techniques that have been proposed for proving unconditional lower bounds for dynamic data structures. We start by introducing the chronogram method of Fredman and Saks 1989, for proving logn/loglogn lower bounds. We then proceed to present the information transfer method of Patrascu and Demaine 2004, which allow us to prove logn lower bounds. After that, we present the current strongest technique, due to Larsen 2012, which allow us to prove (logn/loglogn)^2 lower bounds. We finally conclude by introducing recent work by Larsen, Weinstein and Yu 2018, which proves the first lower bounds of (logn/loglon)^(3/2) for decision problems. This improves over the best previous logn lower bounds for decision problem, due to Patrascu and Demaine 2004.
A recent line of work studied the efficiency of learning under memory constraints. This was highlighted in the celebrated result of Raz [FOCS, 2016] who showed that efficient parity learning requires a quadratic memory. The model of computation in these works is the streaming model: a bounded memory learner tries to learn a concept from a stream of random labeled examples. We would survey lower bounds for learning parities, sparse parities, low-degree polynomials, as well as more general results based on properties of the matrix associated with the learning problem.
A recent line of work studied the efficiency of learning under memory constraints. This was highlighted in the celebrated result of Raz [FOCS, 2016] who showed that efficient parity learning requires a quadratic memory. The model of computation in these works is the streaming model: a bounded memory learner tries to learn a concept from a stream of random labeled examples. We would survey lower bounds for learning parities, sparse parities, low-degree polynomials, as well as more general results based on properties of the matrix associated with the learning problem.
These two talks will introduce the main techniques used to prove lower bounds and unsolvability results for distributed computing, including indistinguishability, covering arguments, and valency arguments. No previous knowledge of distributed computing will be assumed.
These two talks will introduce the main techniques used to prove lower bounds and unsolvability results for distributed computing, including indistinguishability, covering arguments, and valency arguments. No previous knowledge of distributed computing will be assumed.
