Institute for Mathematical Sciences                                        Programs & Activities

 

   
 

Online registration form
   

 

Enquiries

      General

      Scientific aspects


   

Workshop 1 on Log Rank Conjecture

(18 - 22 Jan 2016)

Venue: IMS Auditorium


Organizing Committee · Visitors and Participants · Overview · Activities · Venue

 

Monday, 18 Jan 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

The log-rank conjecture: recent progress and future directions I
Shachar Lovett, University of California, San Diego, USA

11:00am - 11:30am

--- Group Photo & Coffee Break ---

11:30am - 12:30pm

Sign-rank, machine learning, and communication complexity (PDF)
Shay Moran, Technion - Israel Institute of Technology, Israel

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Log-rank conjecture for some special classes of functions (PDF)
Shengyu Zhang, Chinese University of Hong Kong, Hong Kong

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Free Discussion

Tuesday, 19 Jan 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

The log-rank conjecture: recent progress and future directions II
Shachar Lovett, University of California, San Diego, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Extended formulations and circuit complexity
Mika Goos, University of Toronto, Canada

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Parity decision tree complexity and 4-party communication complexity of XOR- functions are polynomially equivalent (PDF)
Penghui Yao, University of Waterloo, Canada

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Separations in query complexity using cheat sheets (PDF)
Shalev Ben-David, Massachusetts Institute of Technology, USA

Wednesday, 20 Jan 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

The log-rank conjecture: recent progress and future directions III
Shachar Lovett, University of California, San Diego, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Separations in query complexity using pointer functions (PDF)
Alexander Belovs, University of Latvia, Latvia

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Free Discussion

Thursday, 21 Jan 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

The log-rank conjecture: recent progress and future directions IV
Shachar Lovett, University of California, San Diego, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Dependent random graphs and multiparty pointer jumping (PDF)
Joshua Brody, Swarthmore College, USA

12.30pm - 02:30pm

--- Lunch Reception at IMS ---

02:30pm - 03:30pm

A composition theorem for conical juntas with applications to query and communication complexity
T.S. Jayram, IBM Almaden Research Center, USA

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

On quantum vs. classical communication complexity (PDF)
Dmitry Gavinsky, The Czech Academy of Sciences, Prague, Czech Republic

Friday, 22 Jan 2016

09:45am - 10:00am

Registration

10:00am - 11:00am

Quantum information and the the round complexity of disjointness
Ankit Garg, Princeton University, USA

11:00am - 11:30am

--- Coffee Break ---

11:30am - 12:30pm

Nearly optimal separations between communication (or query) complexity and partitions

(PDF)

Robin Kothari, Massachusetts Institute of Technology, USA

12.30pm - 02:30pm

--- Lunch Break ---

02:30pm - 03:30pm

Relative discrepancy does not separate information and communication complexity
(PDF)
Iordanis Kerenidis, Université Paris Diderot, France

03:30pm - 04:00pm

--- Coffee Break ---

04:00pm - 05:00pm

Free Discussion


Organizing Committee · Visitors and Participants · Overview · Activities · Venue

top
Best viewed with IE 7 and above