Joshua Brody Tsinghua University cell: 13126790077 joshua.e.brody at gmail resume CV

I am a postdoctoral researcher at the Institute for Theoretical Computer Science, part of the newly formed IIIS at Tsinghua University.

From September 2011-August 2013 I will be a postdoc at the University of Aarhus.

In September 2010 I completed my Ph.D. in computer science at Dartmouth College, working under Amit Chakrabarti.
My thesis focuses on communication complexity. I am also interested in upper and lower bounds and other aspects of theory of computation and algorithms.

I organize the lunch meeting at IIIS. Each Thursday we (graduate students, postdocs, faculty) meet over lunch, and two graduate students give 35 minute presentations on their research.
See also the website from Fall 2010.

Publications

• Streaming Algorithms with One-Sided Estimation
  (with David Woodruff)
  pdf
  RANDOM 2011 (to appear)
  
  
• Lower Bounds for Testing Computability by Small Width OBDDs
  (with Kevin Matulef and Chenggang Wu)
  pdf
  TAMC 2011
  
  
• Property Testing Lower Bounds via Communication Complexity
  (with Eric Blais and Kevin Matulef)
  pdf
  CCC 2011
  
  
• The Coin Problem, and Pseudorandomness for Branching Programs
  (with Elad Verbin)
  pdf
  FOCS 2010
  
  
• Better Gap-Hamming Lower Bounds via Better Round Elimination
  (with Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf)
  pdf
  RANDOM 2010
  
  
• Distributed Monitoring of Conditional Entropy for Anomaly Detection in Streams
  (with Chrisil Arackaparambil, Sergey Bratus, and Anna Shubina)
  pdf
  SSPS 2010
  
  
• A Multi-Round Communication Lower bound for Gap Hamming and Some Consequences
  (with Amit Chakrabarti)
  pdf slides
  CCC 2009
  
  
• The Maximum Communication Complexity of Multiparty Pointer Jumping
  pdf slides
  CCC 2009
  
  
• Functional Monitoring Without Monotonicity
  (with Chrisil Arackaparambil and Amit Chakrabarti)
  pdf
  Preliminary version available as Dartmouth College Technical Report TR2008-639
  ICALP 2009
  
  
• Information-Theoretic Metrics for Anomaly Detection (Extended Abstract)
  (with Sergey Bratus, David Kotz, and Anna Shubina)
  extended abstract poster
  RAID 2008
  
  
• Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound
  (with Amit Chakrabarti)
  pdf slides
  STACS 2008

Last updated 6/22/11