Past Events

Identifying Low-dimensional Data in High-dimensional Spaces

Speaker: 

Anindya De

Organisers: 

Piyush Srivastava

Time: 

Tuesday, 11 December 2018, 14:00 to 15:00

Venue: 

Abstract: Motivated by the problem of feature selection in machine learning, the problem of testing juntas, i.e., checking if a Boolean function on the n-dimensional hypercube only depends on k<<n coordinates, has attracted

Complexity of Constant Player Potential Game

Speaker: 
Vidya Sagar Sharma, TIFR

Organisers: 

Prerona Chatterjee

Time: 

Friday, 30 November 2018, 17:15 to 18:15

Venue: 

Abstract: It is well known that multi-player potential game is PLS-complete.We show that constant player potential game is also PLS-complete.We also show that,there exist a constant-player potential game with some initial strategy such that it can

The Log-Approximate-Rank Conjecture is False

Speaker: 
Suhail Sherif, TIFR

Organisers: 

Ramprasad Saptharishi

Time: 

Tuesday, 27 November 2018, 14:00 to 15:00

Venue: 

Abstract: The Log-Approximate-Rank Conjecture was a long-standing conjecture which posited that the randomised communication complexity of a function and log of the approximate rank of its communication matrix are polynomially related.

Uniform Geometric and Subgeometric Ergodicity for Multiclass Many Server Queues in Heavy Traffic

Speaker: 

Aristotle Arapostathis

Organisers: 

Sandeep K Juneja

Time: 

Thursday, 22 November 2018, 16:00 to 17:00

Venue: 

Abstract: We study ergodic properties of multiclass multi-server queues, which are uniform over scheduling policies, as well as the size n of the system.  The system is heavily loaded in the Halfin-Whitt regime, and the scheduling

On the Structure and Lower Bounds for Multilinear Branching Programs

Speaker: 

Ramya C.

Organisers: 

Ramprasad Saptharishi

Time: 

Wednesday, 21 November 2018, 16:00 to 17:00

Venue: 

Abstract: Polynomials are the most fundamental mathematical objects in algebra and it is compelling to understand the complexity of computing polynomials. That is, given a polynomial we want to understand the number of arithmetic

Pages