Past Events

Short Proofs of the Quantum Substate Theorem

Speaker: 

<p>Ashwin Nayak<br /> Dept. of Combinatorics and Optimization<br /> Faculty of Mathematics<br /> University of Waterloo<br /> 200 University Avenue West<br /> Waterloo, Ontario N2L 3G1<br /> Canada</p>

Organisers: 

John Barretto

Time: 

Monday, 9 January 2012, 11:30 to 12:30

Venue: 

Webpage: 

http://www.math.uwaterloo.ca/~anayak/

The Quantum Substate Theorem due to Jain, Radhakrishnan, and (2002) gives us a powerful operational interpretation of relative entropy, in fact, of the observational divergence of two quantum states, a quantity that is related to their relative en

Fighting Boolean Circuits: New Correlation Bounds and Pseudorandom Generators

Speaker: 

<p>Srikanth Srinivasan<br /> Rutgers University<br /> DIMACS<br /> New Brunswick<br /> New Jersey<br /> United States of America</p>

Organisers: 

John Barretto

Time: 

Wednesday, 4 January 2012, 11:30 to 12:30

Venue: 

Webpage: 

http://dimacs.rutgers.edu/~srikanth/

The general problem of proving limitations on what efficient algorithms can accomplish has been the subject of much research over the past four decades. In this talk, we consider the specific question of bounding the power of Boolean circuits.

Welfare and Profit Maximization with Procurement Costs

Speaker: 

<p>Ankit Sharma<br /> <span class="subtitle">Carnegie Mellon University</span><br /> School of Computer Science<br /> 5000 Forbes Avenue<br /> Pittsburgh PA 15213-3891<br /> United States of America</p>

Organisers: 

Kavitha Telikepalli

Time: 

Tuesday, 3 January 2012, 14:30 to 15:30

Venue: 

What is the problem?
A limited resource needs to be allocated amongst a set of self-interested
agents. For instance, a company manager wants to allocate resources such as

Refined Approaches to Randomized Rounding

Speaker: 

<p>Nikhil Bansal<br /> Eindhoven University of Technology<br /> Department of Maths. &amp; Computing Science<br /> HG 9.01<br /> P.O. Box 513<br /> 5600 MB Eindhoven<br /> The Netherlands</p>

Organisers: 

John Barretto

Time: 

Tuesday, 3 January 2012, 11:30 to 12:30

Venue: 

Webpage: 

http://www.win.tue.nl/~nikhil/

Randomized rounding is a classic method to produce an integral 0/1 solution from a fractional one by interpreting the fractions as probabilities.

A Logic of Interactive Proofs

Speaker: 

<p><a href="http://www.simon-kramer.ch/">Simon Kramer</a><br /> University of Luxembourg<br /> Interdisciplinary Centre for<br /> Security and Trust Campus<br /> Kirchberg, F103 6, rue<br /> Richard Coudenhove-<br /> Kalergi 1359&nbsp;<br /> Luxembourg</p>

Time: 

Monday, 19 December 2011, 11:30 to 12:30

Venue: 

We propose a logic of interactive proofs as the first and main step towards an intuitionistic foundation for interactive computation to be obtained via an interactive analog of the Godel Kolmogorov-Artemov definition of intuitionistic logic as emb

Observing Markov Chains by Timed Automata

Speaker: 

<p>Joost-Pieter Katoen<br /> RWTH Aachen University<br /> LS2: Software Modeling and Verification<br /> D-52056 Aachen<br /> Germany</p>

Time: 

Friday, 16 December 2011, 11:30 to 12:30

Venue: 

Webpage: 

http://www-i2.informatik.rwth-aachen.de/~katoen/

Markov chains are omnipresent. They are used as semantical backbone of Markovian queueing networks, stochastic Petri nets, stochastic process algebras, and calculi for systems biology.

Generalized Network Sharing bound and Two-Unicast Networks

Speaker: 

<p>Sudeep Kamath<br /> University of California at Berkeley<br /> Department of Electrical Engineering and<br /> Computer Science<br /> California 94720<br /> United States of America</p>

Organisers: 

Vinod M. Prabhakaran

Time: 

Wednesday, 14 December 2011, 14:00 to 15:00

Venue: 

Webpage: 

http://www.eecs.berkeley.edu/~sudeep/

The talk will be in two parts.

Pages