Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Dominik Scheder, Shuyang Tang, and Jiaheng Zhang. Searching for Cryptogenography Upper Bounds via Sum of Square Programming. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{scheder_et_al:LIPIcs.ISAAC.2019.31, author = {Scheder, Dominik and Tang, Shuyang and Zhang, Jiaheng}, title = {{Searching for Cryptogenography Upper Bounds via Sum of Square Programming}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {31:1--31:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.31}, URN = {urn:nbn:de:0030-drops-115276}, doi = {10.4230/LIPIcs.ISAAC.2019.31}, annote = {Keywords: Communication Complexity, Secret Leaking, Sum of Squares Programming} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eric Blais and Joshua Brody. Optimal Separation and Strong Direct Sum for Randomized Query Complexity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blais_et_al:LIPIcs.CCC.2019.29, author = {Blais, Eric and Brody, Joshua}, title = {{Optimal Separation and Strong Direct Sum for Randomized Query Complexity}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.29}, URN = {urn:nbn:de:0030-drops-108511}, doi = {10.4230/LIPIcs.CCC.2019.29}, annote = {Keywords: Decision trees, query complexity, communication complexity} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Joseph Boninger, Joshua Brody, and Owen Kephart. Non-Adaptive Data Structure Bounds for Dynamic Predecessor. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{boninger_et_al:LIPIcs.FSTTCS.2017.20, author = {Boninger, Joseph and Brody, Joshua and Kephart, Owen}, title = {{Non-Adaptive Data Structure Bounds for Dynamic Predecessor}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {20:1--20:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.20}, URN = {urn:nbn:de:0030-drops-83892}, doi = {10.4230/LIPIcs.FSTTCS.2017.20}, annote = {Keywords: dynamic data structures, lower bounds, predecessor search, non-adaptivity} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Joshua Brody and Mario Sanchez. Dependent Random Graphs and Multi-Party Pointer Jumping. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 606-624, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2015.606, author = {Brody, Joshua and Sanchez, Mario}, title = {{Dependent Random Graphs and Multi-Party Pointer Jumping}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {606--624}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.606}, URN = {urn:nbn:de:0030-drops-53266}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.606}, annote = {Keywords: random graphs, communication complexity, number-on-the-forehead model, pointer jumping} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Eric Blais, Joshua Brody, and Badih Ghazi. The Information Complexity of Hamming Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 465-489, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{blais_et_al:LIPIcs.APPROX-RANDOM.2014.465, author = {Blais, Eric and Brody, Joshua and Ghazi, Badih}, title = {{The Information Complexity of Hamming Distance}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {465--489}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.465}, URN = {urn:nbn:de:0030-drops-47174}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.465}, annote = {Keywords: Hamming distance, communication complexity, information complexity} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 545-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{brody_et_al:LIPIcs.APPROX-RANDOM.2014.545, author = {Brody, Joshua and Chakrabarti, Amit and Kondapally, Ranganath and Woodruff, David P. and Yaroslavtsev, Grigory}, title = {{Certifying Equality With Limited Interaction}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {545--581}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.545}, URN = {urn:nbn:de:0030-drops-47229}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.545}, annote = {Keywords: equality, communication complexity, information complexity} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Joshua Brody and Amit Chakrabarti. Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{brody_et_al:LIPIcs.STACS.2008.1341, author = {Brody, Joshua and Chakrabarti, Amit}, title = {{Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {145--156}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1341}, URN = {urn:nbn:de:0030-drops-13415}, doi = {10.4230/LIPIcs.STACS.2008.1341}, annote = {Keywords: Communication complexity, pointer jumping, number on the forehead} }
Feedback for Dagstuhl Publishing