Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Sign rank, VC dimension and spectral gaps
Speaker:Shay Moran
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Advanced Mini-Course
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 12 December 2014
Time:13:00
Duration:45 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
The sign-rank of an N by N matrix A of signs is the minimum possible rank of a real matrix B in which every entry has the same sign as the corresponding entry of A. The VC-dimension of A is the maximum cardinality of a set of columns I of A so that for every subset J of I there is a row i of A so that A_{ij}=+1 for all j in J and A_{ij}=-1 for all j in I-J.

I will describe explicit examples of N by N matrices with VC-dimension 2 and sign-rank Omega(N^{1/4}). I will also discuss the maximum possible sign-rank of an N by N matrix with VC-dimension d. Finally, I will mention the applications of these results to communication complexity and learning theory.

Joint work with Noga Alon and Amir Yehudayoff

Contact
Name(s):Shay Moran
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Shay Moran, 11/27/2014 11:19 PM
  • Shay Moran, 11/27/2014 11:18 PM -- Created document.