Coordinates: - Watch It Here
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.
Coordinates: - Watch It Here
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.
Coordinates: - Watch It Here
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
Coordinates: - Watch It Here
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
Coordinates: KD101, 11AM 14th Feb 2020
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.
Coordinates: KD103, 4 PM 8th Feb 2020
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).
Coordinates: KD103, 4:30 PM 25th Jan 2020
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.
Coordinates: KD103, 4 PM 18th Jan 2020
The tensor product GxH of two graphs G and H has the vertex set $V(G)\times V(H)$, and the pairs $(g,h)$ and $(g’,h’)$ are adjacent if and only if $g$ is adjacent to $g`$ in G and $h$ is adjacent to $h$ in H. A proper colouring $g \to C(g)$ for graph $G$ can be ‘lifted’ to give a proper colouring $(g,h) \to C(g)$ for $G \times H$, and similarly a lifting can be done for a proper colouring of H as well. This implies that the minimum between the chromatic numbers of $G$ and $H$ forms an upper bound on the chromatic number of $G \times H$ (i.e, $X(G \times H) \leq \min(X(G), X(H)$). In 1966, S. Hedetniemi conjectured that equality holds for all finite simple graphs. In 2019, Yaroslav Shitov refuted the conjecture by constructing a counterexample using the concept of exponential graphs, which have vertices corresponding to every possible c-colouring of an n-vertex graph, with two vertices being adjacent only if the corresponding colourings paint every adjacent vertex with different colours.
In this talk, we will discuss exponential graphs in detail, and then look at the construction of the counterexample.
Coordinates: KD103, 4 PM 11th Jan 2020
Cryptographic hash functions are widely used in modern cryptography such as in digital signatures, message integrity and authentication. The U.S. National Institute of Standards and Technology (NIST) announced the “NIST hash function competition” for the Secure Hash Algorithm-3 (SHA-3) in 2006. They received 64 proposals from around the world. Among these, KECCAK designed by Bertoni, Daemen, Peeters, and Van Assche became one of the candidates for SHA-3. It won the competition in October 2012 and was standardized as a “Secure Hash Algorithm 3” .
In this talk, we will look at new preimage attacks on KECCAK-384 and KECCAK-512 for 2, 3 and 4 rounds. The attacks are based on non-linear structures (structures that contain quadratic terms). These structures were studied by Guo et al. and Li et al. to give preimage attacks on round reduced KECCAK. We carefully construct non-linear structures such that the quadratic terms are not spread across the whole state. This allows us to create more linear equations between the variables and hash values, leading to better preimage attacks. As a result, we get the best theoretical preimage attack on KECCAK-384 and KECCAK-512 for 2 and 3-rounds and also KECCAK-384 for 4-rounds.
Coordinates: KD103, 12 PM 20th Nov 2019
Hilbert’s Nullstellensatz is an important theorem in Commutative Algebra and Algebraic Geometry. It connects the notion of ideals (in Commutative Algebra) to that of varieties (in Algebraic Geometry). In this project, we investigate the computational version of this problem (HN) which basically translates to finding how hard is it to decide whether or not 1 lies in the ideal generated by a set of polynomials, say {f1, f2, …, fm} in k[x1, x2, …, xn]. In particular, we look at the two most important results pertaining to the complexity of the above problem (for field k of zero-characteristic): HN is in PSPACE, and under Generalized Riemann Hypothesis, HN is in AM.