SIGTACS

Lectures

Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four

Coordinates: 4PM IST, 08th Sept 2021

Abstract

One of the major motivations to study Arithmetic/Algebraic Circuit Complexity was due to the “slow” progress in proving lower bounds in Boolean Circuit Complexity. Based on some empirical evidence, researchers believed that the power of underlying algebra and the possibility of cancellations could help understand computations on the algebraic setting.

In this talk we shall outline some of the connections between Boolean Circuit Complexity and Algebraic Circuit Complexity. In particular (by building upon some previous work [due to Yao, Beigel & Tarui, Forbes, Kumar & Saptharishi], we shall present a path towards proving stronger (nonuniform) ACC0 lower bounds via proving “functional” lower bounds in the algebraic setting.

Joining Link: Google Meet


VNP (probably) does not have natural proofs.

Coordinates: - Watch It Here

Slides

Abstract

In view of the lack of strong lower bounds in most branches of complexity theory, some of the research has focused on whether the known approaches can ever lead to strong enough results. In the case of Boolean circuits, Razborov and Rudich (1995) observed that most of the then known lower bounds could be proven using a certain template, which they called the ‘natural proofs’ framework. They further showed that if strong enough One-Way-Functions exist, then no natural proof can lead to a super-polynomial lower bound against Boolean circuits!

Recently, Forbes, Shpilka and Volk (2018) and Grochow, Kumar, Saks and Saraf (2017) independently came up with an algebraic analogue of the natural proofs framework: algebraic or (algebraically) natural proofs. A bit like the Boolean case, both these works show that the existence of algebraic natural proofs for poly-sized algebraic circuits (called VP) directly contradicts a derandomisation assumption about algebraic circuits. However, this assumption is quite non-standard and it is therefore difficult to form any strong opinion about it.

In a recent joint work with Mrinal Kumar (IITB), C. Ramya (TIFR) and Ramprasad Satharishi (TIFR), we show that if there is an exponential separation between the classes VNP (algebraic NP) and VP (algebraic P), then there are no algebraic natural proofs for the class VNP. This is perhaps the only known result about the existence of algebraic natural proofs that follows from standard hardness assumptions. Moreover, this statement also has some interesting consequences for the efficacy of ‘natural lower bound techniques’ in the algebraic world.

In this talk, we will first get to know the framework of algebraic natural proofs, and then discuss our result and its consequences. After that, if the time permits, we will briefly go over the main ideas behind our proof.

Joining Link: Google Meet


Dimension preserving reductions between lattice problems.

Coordinates: - Watch It Here

Slides

Abstract

The recent advances in the design and construction of quantum computers require us to design the cryptosystem secure even after quantum computers. Most of the current day cryptosystem’s security is dependent on the hardness of integer factoring or discrete log problem. Both these are polynomial-time solvable by a quantum computer [Shor, FOCS, 1994]. The quantum resistance and many other lattices’ unique properties make lattice-based cryptosystem the most popular candidate for post-quantum cryptography.

In this talk, we will present a number of exponential time reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓp norms (SVPp and CVPp respectively). We will also discuss how theses reductions are useful for the fine grained hardness of the lattice problems.

This is a joint work with Divesh Aggarwal, Yanlin Chen, Zeyong Li and Noah Stephens-Davidowitz.


Computing Igusa's local zeta function of univariates in deterministic polynomial-time

Coordinates: - Watch It Here

Slides

Abstract

The famous millennium prize problem “The Riemann Hypothesis” is about the zeros of a zeta function known as “Riemann Zeta Function”. In this talk we will talk about another interesting zeta function which counts the number of roots of a polynomial, $f(x_1,\dots,x_n)$ with integer coefficients, reduced mod a prime-power $p^k$, for all k; known as— Igusa’s Local Zeta Function $Z_{f,p}(s)$.

It is a famous result, in analytic number theory, that $Z_{f,p}(s)$ converges to a rational function. We give an elementary proof of this fact for a 1-variable polynomial $f(x)$. Our proof is constructive as it gives an explicit formula for the number of roots of $f(x) \mod{p^k}$. Our proof, when combined with the recent root-counting algorithm of (Dwivedi, Mittal, Saxena, CCC, 2019), yields the first deterministic poly-time algorithm to compute the rational form of $Z_{f,p}(s)$.

This is based on joint work ANTS 2020 with Professor Nitin Saxena.


Optimal Streaming Approximations for all Boolean Max-2CSPs

Coordinates: - Watch It Here

Slides

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+\varepsilon)$-approximation for Max-CUT requires $\Omega(n)$ space while there is a trivial $1/2$-approximation using $O(\log n)$ space. However, the knowledge of the right approximation ratio for other boolean 2CSP in the streaming model remains 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 boolean hidden matching problem (DBHP).

This is joint work with Santhoshini Velusamy and Sasha Golonev.


Poly-time blackbox identity testing for sum of log-variate, constant-width ROABPs

Coordinates: - Watch It Here

Slides

Abstract

The talk is based on joint work with Prof. Nitin Saxena. We explore blackbox PIT (Polynomial Identity Testing) problem for the model of “Sum of ROABPs (Read-once oblivious Algebraic Branching Programs)”. Recent bootstrapping results motivate us to study log-variate ROABPs. We also restrict the width of ROABP to a constant but study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox PIT for sum of constant-many, size-$s$, $O(\log s)$-variate constant-width ROABPs. The previous best for this model was a quasi-polynomial time which is comparable to brute-force in the log-variate setting. Also, we handle unbounded-many such ROABPs if each ROABP computes a homogeneous polynomial.

Our new techniques comprise– (1) a ROABP computing a homogeneous polynomial can be made syntactically homogeneous in the same width; and (2) overcome the hurdle of unknown variable order in sum-of-ROABPs in the log-variate setting (over any field).

In the talk, we will begin from scratch with definitions of PIT and various models including ROABPs. Then, we shall discuss the motivations behind this model and its non-triviality. Finally, we will give a brief overview of the PIT algorithms and why they work.

See the paper for more detials: TR20-042


Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

Coordinates: - Watch It Here

Slides

Abstract

We consider the univariate polynomial $f_d := (x + 1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$ .

We show a stunning connection of the conjecture to the two main problems in algebraic complexity: Polynomial Identity Testing (PIT) and VP vs. VNP. Our conjecture on f_d implies blackbox-PIT in P. Assuming the Generalized Riemann Hypothesis (GRH), it also implies VP $\neq$ VNP. No such connection to PIT, from lower bounds on constant-powers representation of polynomials was known before. We establish that studying the expression of $(x + 1)^d$ , as the sum of 25th-powers of univariates, suffices to solve the two major open questions.

This is based on joint work (submitted) with Prof. Nitin Saxena (IIT Kanpur) and Prof. Thomas Thierauf (Aalen University); see the paper for details: TR20-039


Characterising Hardness for QBF Resolution via Circuit Complexity.

Coordinates: KD101, 11AM 14th Feb 2020

Abstract

This talk will start with an overview of the relatively young field of QBF proof complexity, explaining QBF proof systems (including QBF resolution) and an assessment of which lower bound techniques are available for QBF proof systems. In the main part of the talk, I will explain hardness characterisations for QBF proof systems in terms of circuit complexity, yielding very direct connections between circuit lower bounds and QBF proof system lower bounds.

Joint work with Olaf Beyersdorff and Joshua Blinkhorn. ECCC Technical Report TR20-005.

About the Speaker: Meena Mahajan is a professor at Institute of Mathematical Sciences, Chennai. She completed her B.Tech and M.Tech from IIT Bombay and her Ph.D. at IIT Madras under Prof. Kamala Kritivasan. She has been a faculty at IMSc since 1994. She has extensively contributed in the area of Computational Complexity Theory especially Algebraic Complexity, Circuit Complexity, Proof Complexity and its connections to Automata.


Matroid intersection

Coordinates: KD103, 4 PM 8th Feb 2020

Abstract

Matroids are abstract structures which generalize the notion of linear independence in vector spaces. This lead to surprising connections to graph theory, combinatorial optimization, and topology. In this talk, we would introduce the idea of matroids in simple words, look at the idea of matroid intersection, and a greedy algorithm for finding it. Outline/reference: https://codeforces.com/blog/entry/69287 The talk will be accessible to someone with knowledge of linear algebra, matrices, and basic graph algorithms (e.g., DFS, BFS, Kruskal’s/Prim’s minimum spanning tree algorithms).


Barrington's Theorem

Coordinates: KD103, 4:30 PM 25th Jan 2020

Abstract

Barrington’s theorem is a result in classical complexity which states that any boolean function in NC^1 can be computed by a branching program of bounded width. We will discuss the proof of this surprising theorem.