Speaker: Sunaina Pati BSc 2
Title: On Cyclotomic polynomials, Zsigmondy Theorem
Abstract: Zsigmondy theorem states that If a,b in N and (a,b)=1, then there exists prime p such that p|a^n-b^n and p does not divide a^k-b^k for all k<n except: when n=2 and a+b is power of 2 or (a,b,n)=(2,1,6)
In the talk, we will discuss many properties and applications of cyclotomic polynomials and then try to prove the above two theorems.
Pre-requisites: Algebra-3, although knowing basic definitions of fields and rings should be enough for most parts.
Date, time, venue : 17th Jan, 6:30 PM, NKN hall
Speaker: Ananya Ranade BSc 3
Title : Interactive proofs with zero knowledge
Abstract : In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. We will explore the power of interaction and randomness, by constructing interactive protocols for a lot of problems. Later, we will see zero knowledge proofs, a protocol in which one party can convince another party that some given statement is true, without conveying to the verifier any information beyond the mere fact of that statement's truth.
Date, time, venue: 19th February, 6:30 PM, NKN hall
Speaker: Harsh Sharma BSc 2
Title: Information Theory in Computer Science
Abstract: In this seminar we will try to go over information theoretic tools used in Theoretical Computer Science and theoretical machine learning. It has both importance in combinatorics and complexity. Plan is to start from basic definition and gradually start attacking some classical problems using those techniques.I will also discuss some of the most important machine learning problems, which computer scientists are trying to attack using Information theory.Some problems which I want to discuss are bound on number of perfect matchings in a bipartite graph using entropy-based techniques. Another interesting problem we will discuss is the following geometric puzzle: Suppose n distinct points in R^3 have n1 distinct projections on XY-plane, n2 distinct projections on YZ plane and n3 distinct projections on XZ plane. is there a better bound here on n that is better than n<=n1*n2*n3? We will explore how information-theoretic tools can help tackle such problems. The seminar will also introduce communication complexity, focusing on how information theory can simplify seemingly difficult proofs. A classic example is the set intersection problem: Given that Alice has a set A and Bob has a set B, what is the minimum number of bits they must exchange to determine whether they share a common element? Originally studied with complex techniques, we will attempt to derive a clean and intuitive proof using information-theoretic arguments.
Date, time, venue: 21st February, 6:30 PM, NKN hall
Speaker: Pranath BSc 1
Title: The Baire Space, Continuum Hypothesis and the Perfect Set Theorem.
Abstract: The Baire Space is defined as $\mathcal{N} = \mathbb{N^N}$ with its (product) topology. Descriptive set theorists often call this space as the 'reals'. We will explore its topological properties (characterize closed, open and perfect sets) and why it is interesting to study them. Additionally, we will investigate a special collection, analytic subsets, of the space and see its link with Borel sets. These ideas intuitively produce a result called the Perfect Set Theorem which classifies the cardinalities of most sets of interest. If time permits, we'll see why the methods in this talk are insufficient in attacking the continuum hypothesis.
Prerequisites: None, however, understanding of Analysis-1 would be helpful.
Date, time, venue: 14th March, 6:30 pm, NKN hall
Speaker: Srijan MSc CS 1
Title: Paths, Permanents and Polynomials
Abstract: We look at two very classical graph theoretic problems of finding the shortest disjoint paths, and long paths:
1. k-Shortest Disjoint Paths(k-SDPP): Given an undirected graph and k pairs of terminals (s_i,t_i) for i\in [k], find a set of disjoint paths p_1,\ldots,p_k where p_i is a s_i-t_i path and the total length of the paths is minimized.
2. Long Path(k-Path): Find a path of length at least k in a graph of n vertices.
Both problems are NP-hard for non-constant k. We will look at a randomized polynomial time algorithm for 2-SDPP [Bjorklund, Husfeldt] and a randomized O*(2^k) algorithm for finding a k-path [Koutis, Williams]. Both approaches rely on algebraic techniques: for 2-SDPP, we leverage the computation of the permanent of a specially structured matrix (modulo a power of 2), along with the Isolation Lemma. For k-Path, we 'efficiently' detect a multilinear monomial in a nicely chosen polynomial. These approaches highlight the power of algebraic techniques in designing efficient algorithms for hard combinatorial problems.
Pre-req: Familiarity with the definition of the Permanent/Determinant and Cycle Covers
Date, time, Venue: 11th April, 6:30 PM, NKN hall
Speaker; Gautham V Bsc 4
Abstract: Suppose that we pick the coefficients of a power series, uniformly at random, independently of each other, from the set $[0, 1]$. Let this series be $P$. Then there is a constant $c$, which doesn't depend on $P$, such that with probability 1, the radius of convergence of $P$ is $c$. This is one of the coolest results I have ever seen, and we will try to sketch a proof of this in this talk. To understand probability over infinite domains, we would like a general notion of size, and a general notion of integration and expectation. One formalism for these ideas is measure theory. The plan for the talk is to explore what it could mean to define the notion of size for arbitrary subsets of the reals (not just intervals!) this allows us to define a less topological notion of the integral, and do probability over infinite domains. We'll prove that we cannot actually define a reasonable notion of size over arbitrary subsets of the reals, but we'll see that we don't quite need to do this in order to get a functioning and elegant theory. We'll then look at some applications of this to probability theory, in particular, Kolmogorov's zero-one law. As a corollary, we'll obtain the amazing result stated above.
Prerequisites: Just ANA 1 (so this will be accessible to everyone, including first years! Please come!)
Date, time, venue: 31st Jan, 6:30 pm, NKN hall
Speaker: Sunaina Pati BSc 2
Title: Cyclic codes for Error detection
Abstract: This talk is based on Peterson and Brown's famous paper "Cyclic Codes for Error Detection". I will be going over Cyclic codes which is a type of linear code with the property that any cyclic shift of a codeword is also a codeword, talk about their properties, BCH codes, error correction of BCH codes and how we can detect errors for various other kinds of cyclic codes.
Venue, time: NKN hall, 6:30 pm
Pre-requisites: Linear Algebra and Algebra-3. Familiarity with Coding theory is not required.