Past Events

Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

Speaker: 

Nutan Limaye

Organisers: 

Piyush Srivastava

Time: 

Tuesday, 28 November 2017, 16:00 to 17:00

Venue: 

Webpage: 

https://www.cse.iitb.ac.in/~nutan/

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $P$.

Finding Euler Tours in One Pass in the W-Streaming Model with $\mathcal{O}(n\log n)$ Memory

Speaker: 

Anand Srivastav

Organisers: 

Jaikumar Radhakrishnan

Time: 

Monday, 27 November 2017, 10:15 to 11:15

Venue: 

We study the problem of finding an Euler tour in an undirected graph $G$ in the W-Streaming model with $\mathcal{O}(n\,\textrm{polylog}(n))$ RAM, where $n$ resp.\ $m$ is the number of nodes resp.\ edges of $G$.  Our main result is the first one pa

Entanglement Distillation in Quantum Information Theory

Speaker: 
Sayantan Chakraborty, TIFR

Organisers: 

Varun Narayanan

Time: 

Friday, 24 November 2017, 17:15 to 18:15

Venue: 

Entanglement is an important resource in quantum communication protocols and as such the problem of turning a preshared entangled state between two parties Alice and Bob into a Bell state has been studied extensively.

New Constructions for Reusable Garbled Circuits

Speaker: 

Shweta Agrawal

Organisers: 

Piyush Srivastava

Time: 

Monday, 23 October 2017, 14:30 to 15:30

Venue: 

Webpage: 

http://www.cse.iitm.ac.in/~shwetaag/

Garbled circuits are a central primitive in cryptography. Intuitively, a garbled circuit enables its holder to evaluate a circuit on an input, so that the evaluator learns the output but learns nothing about the circuit or the input.

Pages