Joshua Brody Aarhus University phone: +45-8715-6225 email: joshua.e.brody at gmail Here is my CV. Copies of my research and teaching statements are available on request.

Starting September 2013, I will be a visiting Assistant Professor at Swarthmore College.

Since October 2011, I have been a postdoctoral researcher at Aarhus University, under the supervision of Peter Bro Miltersen.
From September 2010-July 2011, I was a postdoc at Tsinghua University Institute for Interdisciplinary Information Sciences, where my supervisor was Andy Yao.

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.

Teaching

• Sublinear Time Algorithms: Property Testing. Aarhus University. Third Quarter Winter 2013.
• Communication Complexity. Aarhus University. Second Quarter Fall 2011.
• Research Immersion in Theoretical Computer Science. Tsinghua University. Summer 2011.
• Computer Architecture (CS37). Dartmouth College. Summer 2010.

Manuscripts

• Certifying Equality with Limited Interaction
  (with Amit Chakrabarti and Ranganath Kondapally)
  pdf
  
  
• Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
  (with Kasper Green Larsen)
  pdf

Journal Publications

• Property Testing Lower Bounds via Communication Complexity
  (with Eric Blais and Kevin Matulef)
  pdf
  Computational Complexity volume 21, number 2. Special Issue devoted to select papers from CCC 2011 (see below)
  Some slides from a survey talk I've given a couple of times on this technique.
  
  Note: Oded Goldreich recently reformulated our technique. His notation is general and hopefully easier to use than our notation.
  

Conference Publications

• Towards a Reverse Newman's Theorem in Interactive Information Complexity
  (with Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, and Nikolay Vereshchagin)
  pdf
  CCC 2013 (to appear)
  
  
• Space-Bounded Communication Complexity
  (with Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, and Xiaoming Sun)
  pdf
  ITCS 2013
  
  
• Space Efficient Approximation Scheme for Circular Earth Mover Distance
  (with Hongyu Liang and Xiaoming Sun)
  pdf
  LATIN 2012
  
  
• Streaming Algorithms with One-Sided Estimation
  (with David Woodruff)
  pdf
  RANDOM 2011
  
  
• 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 17 May, 2013