Joshua Brody

According to our database, Joshua Brody authored at least 30 papers between 2008 and 2020.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2020

A Strong XOR Lemma for Randomized Query Complexity.

Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

Electron. Colloquium Comput. Complex., 2020

2019

Optimal Separation and Strong Direct Sum for Randomized Query Complexity.

Eric Blais, Joshua Brody

Proceedings of the 34th Computational Complexity Conference, 2019

2017

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search.

Joe Boninger, Joshua Brody, Owen Kephart

Electron. Colloquium Comput. Complex., 2017

Non-Adaptive Data Structure Bounds for Dynamic Predecessor.

Joseph Boninger, Joshua Brody, Owen Kephart

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Position-Based Cryptography and Multiparty Communication Complexity.

Joshua Brody, Stefan Dziembowski, Sebastian Faust, Krzysztof Pietrzak

IACR Cryptol. ePrint Arch., 2016

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Algorithmica, 2016

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, Nikolai K. Vereshchagin

Algorithmica, 2016

2015

Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures.

Joshua Brody, Kasper Green Larsen

Theory Comput., 2015

Dependent Random Graphs and Multiparty Pointer Jumping.

Joshua Brody, Mario Sánchez

Electron. Colloquium Comput. Complex., 2015

Dependent Random Graphs and Multi-Party Pointer Jumping.

Joshua Brody, Mario Sánchez

Proceedings of the Approximation, 2015

2014

Beyond set disjointness: the communication complexity of finding the intersection.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Cryptogenography.

Joshua Brody, Sune K. Jakobsen, Dominik Scheder, Peter Winkler

Proceedings of the Innovations in Theoretical Computer Science, 2014

The Information Complexity of Hamming Distance.

Eric Blais, Joshua Brody, Badih Ghazi

Proceedings of the Approximation, 2014

2013

A Tight Lower Bound for Monotonicity Testing over Large Ranges

Joshua Brody

CoRR, 2013

Space-bounded communication complexity.

Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Certifying Equality With Limited Interaction.

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Electron. Colloquium Comput. Complex., 2012

Towards a Reverse Newman's Theorem in Interactive Information Complexity.

Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman

Electron. Colloquium Comput. Complex., 2012

Property Testing Lower Bounds via Communication Complexity.

Eric Blais, Joshua Brody, Kevin Matulef

Comput. Complex., 2012

Space-Efficient Approximation Scheme for Circular Earth Mover Distance.

Joshua Brody, Hongyu Liang, Xiaoming Sun

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011

Lower Bounds for Testing Computability by Small Width OBDDs.

Joshua Brody, Kevin Matulef, Chenggang Wu

Proceedings of the Theory and Applications of Models of Computation, 2011

Streaming Algorithms with One-Sided Estimation.

Joshua Brody, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Some Communication Complexity Results and their Applications.

Joshua Brody

PhD thesis, 2010

Distributed monitoring of conditional entropy for anomaly detection in streams.

Chrisil Arackaparambil, Sergey Bratus, Joshua Brody, Anna Shubina

Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing, 2010

The Coin Problem and Pseudorandomness for Branching Programs.

Joshua Brody, Elad Verbin

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf

Proceedings of the Approximation, 2010

2009

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences.

Joshua Brody, Amit Chakrabarti

Electron. Colloquium Comput. Complex., 2009

The Maximum Communication Complexity of Multi-party Pointer Jumping.

Joshua Brody

Electron. Colloquium Comput. Complex., 2009

Functional Monitoring without Monotonicity.

Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound.

Joshua Brody, Amit Chakrabarti

Proceedings of the STACS 2008, 2008

Streaming Estimation of Information-Theoretic Metrics for Anomaly Detection (Extended Abstract).

Sergey Bratus, Joshua Brody, David Kotz, Anna Shubina

Proceedings of the Recent Advances in Intrusion Detection, 11th International Symposium, 2008