Shay Moran

I’m a Ph.D Student at Computer Science Department at the Technion – Israel Institute of Technology. I’m co-advised by Amir Shpilka and Amir Yehudayoff.
I’m also affiliated with the Algorithms and Complexity department of the Max Planck Institute. I wrote my Masters’ thesis at Kurt Mehlhorn’s group and received my Masters’ degree from the University of Saarland. My Masters’ thesis advisor was Ami Litman.

My email is: shaymoran1@gmail.com
My office is located at: Taub 509

Current research interests

Complexity theory: communication complexity.
Learning theory: statistical sample complexity, computational complexity.

Journal publications

• Sample compression schemes for VC classes
  accepted to the Journal of the ACM, 2016
• Direct sum fails for zero error average communication
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  Accepted to Algorithmica, 2016
• A note on average-case sorting
  Shay Moran and Amir Yehudayoff
  Order, Springer, 2015
• Simple and Optimal Fault-Tolerant Rumor Spreading
  Benjamin Doerr, Carola Doerr, Shay Moran, and Shlomo Moran
  Distributed Computing, Springer, 2014
• Shattering, Graph Orientations, and Connectivity
  László Kozma and Shay Moran
  The Electronic Journal of Combinatorics, 2013

Conference publications

• Node-balancing by edge-increments
  Friedrich Eisenbrand, Shay Moran, Rom Pinchasi, and Martin Skutella
  ESA 2015
• Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  FOCS 2015
  invited to FOCS special issue of SICOMP
  The conference version combines two separates papers:
  Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  Sample compression schemes for VC classes
  Shay Moran and Amir Yehudayoff
• Internal compression of protocols to entropy
  Balthazar Bauer, Shay Moran, and Amir Yehudayoff
  RANDOM 2015
• Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ICALP 2014
• Direct sum fails for zero error average communication
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ITCS 2014
  Invited to a special issue of Algorithmica
  

Manuscripts

• Hitting set for hypergraphs of low VC-dimension
  Karl Bringmann, László Kozma, Shay Moran, and N.S. Narayanaswami
• Shattered Sets and the Hilbert Function
  Shay Moran and Cyrus Rashtchian
• Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces
  Shay Moran and Rom Pinchasi
• Labeled compression schemes for extremal classes
  Shay Moran and Manfred K. Warmuth
• Sign rank, VC dimension and spectral gaps
  Noga Alon, Shay Moran, and Amir Yehudayoff
• Fooling Pairs in Randomized Communication Complexity
  Shay Moran, Makrand Sinha, and Amir Yehudayoff

Theses

• Shattering-Extremal Systems
  Shay Moran
  Masters’ thesis

Teaching

• Communication Complexity (236518):
  Computer Science faculty, TechnionTeaching Assistant: Spring 2015
• Probability Theory (104222):
  Mathematics faculty, TechnionTeaching Assistant: Winter 2014-2015
• Analytical Methods in Combinatorics (106376):
  Mathematics faculty, TechnionTeaching Assistant: Spring 2014
• Logic and Set Theory (234293),
  Computer Science Faculty, TechnionTeaching Assistant: Summer 2010, Winter 2013-2014
• Data Structures I (234218),
  Computer Science Faculty, TechnionTeaching Assistant: Winter 2012-2013
• Algorithms and Data Structures (advanced course):
  Computer Science Faculty, Saarland UniversityTeaching Assistant: WS 2011-2012
• Programming Languages (234319), Computer Science Faculty, TechnionTeaching Assistant: Winter 2010-2011
• Introduction to Computer Science
  (234293), Computer Science Faculty, TechnionTeaching Assistant: Spring 2010