Coordinates: KD103, 3 PM 16th Nov 2019
In this talk, we will explore the problem of Polynomial Identity Testing (PIT) which is of finding an algorithm that checks if a given polynomial is zero or not in polynomial time. The problem is central to the field of Algebraic complexity and has known connections to lower bounds, as well as other problems in complexity theory. It has a simple randomized black-box solution but a deterministic algorithm is not known.
We will take a look at the restricted class of circuits of depth-4 constant Top and Bottom Fan-in. Solving the problem for the depth-4 case will imply a solution for the general PIT using depth reduction in [AV08]. The case of constant top Fan in depth-3 has been solved for both white-box [KS07] and black-box [SS13] cases. Thus, this remains the next unsolved case in the field, for which even the white-box solution is not known. We will look at the conjectures in [Gup14] of Sylvester-Gallai type theorems for non-linear polynomials proposed to solve the case, and prove one of the easier conjectures for quadratic polynomials from [Shp18].
Coordinates: KD102, 3 PM 9th Nov 2019
This will be a series of 2 or 3 tutorial talks about factoring and root finding of a univariate polynomial f(x) mod a prime power p^k. The case of factoring f(x) mod p (special case k=1) is a very fundamental problem in computational number theory and theoretical computer science and finds applications in (but not limited to) cryptography, coding theory and other areas of mathematics. This problem has known efficient randomized algorithms but finding an efficient deterministic algorithm has been an enigma.
On the contrary, the general version of the problem, factoring f(x) mod p^k, has no known efficient randomized algorithm yet. The main objective of this talk series is to talk about the recent discoveries which takes us closer to this goal and also make aware the audience about the hurdles in the way. Mainly, an intuitive understanding of the problem will be given along with efficient randomized algorithm (Berthomieu, Lecerf and Quintin [BLQ13]) for finding roots, recent derandomization of [BLQ13] (D., Mittal and Saxena CCC’19) and factoring f(x) mod p^k for k<5 (D., Mittal and Saxena ISSAC’19).
Update 1 Talk was continued on 13th Nov 2019 at 3PM in KD102.
Update 2 Final part of the talk will be delivered by speaker on 15th Nov 2019 at 5PM in KD103
Coordinates: KD102, 4 PM 2nd Nov 2019 - Watch It Here
In this talk, we will define the ABP (Algebraic branching program) model of computation, followed by non-commutative and read once oblivious ABPs (ROABPs). Nisan [Nis91] gave an exact characterization to determine the size and width of non commutative ABPs which will be the highlight of this talk . We will also derive the same characterization in the language of ROABPs.
Coordinates: KD103, 11 AM 19th Oct 2019 - Watch It Here
Unambiguous computation is a restriction of nondeterministic computation where the nondeterministic machine has at most one accepting computation path on each input. In logspace computation these classes are know as NL and UL. An important question is whether these classes are equal or not. This question is equivalent to asking whether the reachability in directed graphs can be solved in UL or not. In this talk I will present a result which showed that reachability in O(log n) genus directed graphs can be solved in UL.
Coordinates: KD103, 4 PM 16th Oct 2019 - Watch It Here
A randomness extractor is a function that outputs almost uniform bits from a weakly random entropy source. The Leftover Hash Lemma (LHL) states that universal hash functions are good randomness extractors. LHL leads to simple and efficient extractors and hence has applications in many areas of cryptography and complexity theory.
In this talk, the speaker will give a short description of extractors, discuss the proof for LHL and give a simple application of LHL.
Coordinates: KD103, 4 PM 7th Oct 2019
Reachability and strong-connectivity are some of the fundamental graph problems. In the static setting, both problems can be solved in O(m+n) time for any directed graph G with n vertices and m edges. However, most real-world networks are prone to failures. The failures are transient and occur for a small duration of time. Under such a setting, we would like to preprocess the graph to compute data-structures that can achieve robustness by being functional even after the occurrence of failures. In recent years, researchers have studied various questions pertaining to connectivity, distances, routing, min-cuts, etc. in the domain of fault tolerance networks.
In this talk, the speaker will discuss the following questions:
The solutions to these problems employ extremely basic tools like max-flows, min-cuts, and heavy-path-decomposition.
Coordinates: KD102, 4 PM 28th Sept 2019
The approximation closure of a class of polynomials A is another class of polynomials which can approximate the polynomials of A in an appropriate sense. Motivated from the problem of checking separation of these classes, recently a class of small-width algebraic branching programs (ABP) and its approximation closure were studied. In this talk, we will discuss some of those central findings.
In the first half of the talk, we will set the prelude by discussing briefly on introduction to arithmetic circuits, algebraic branching program (ABP) and some popular algebraic complexity classes like VF, VBP and their approximation closures. In the latter half, we will discuss how the introduced classes are related to each other and with their approximation closure. And if time permits, we can also look into Fibonacci polynomials, Fibonacci complexity and Border Fibonacci complexity of polynomials.
Coordinates: KD102, 4 PM 22th Sept 2019
A sunflower is a collection of sets with constant pairwise intersection. In this talk we discuss a recent improvement in the upper bound for the number of sets required for a sunflower to always exist.
Coordinates: KD102, 4 PM 14th Sept 2019
Today, datasets (such as social-networks) have become prohibitively large to store on a single system. The streaming setting models this problem. Here, an algorithm works a small memory (typically, logarithmic in size of the input) and solves the problem by repeatedly traversing the input. In this talk, we introduce the communication problem, where two or more systems have to jointly perform a task that neither can finish individually. We look at several communication problems and surprisingly find that they can be used to study the “hardness” of problems in the streaming setting.
This talk would be interesting for students with interest in algorithms and probability. It would be helpful for those working in other areas, who would like to explore streaming and/or communication complexity. Finally, many references to the latest research would be useful for those working in these fields.
The talk will be accessible through high-school level math, and yet, will introduce interesting ideas from probability theory, information theory, and communication complexity. At the end of the talk, we will provide a comprehensive list of references for further reading.
Coordinates: KD102, 4 PM 24th Aug 2019
The proof of the Kneser conjecture by Lovasz in 1978 gave rise to the field of topological combinatorics: applying topological and algebraic topological methods to combinatorial problems. In this talk, I will present some simple applications of the Borsuk Ulam theorem to discrete problems.