Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
William M. Hoza. A Technique for Hardness Amplification Against AC⁰. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hoza:LIPIcs.CCC.2024.1, author = {Hoza, William M.}, title = {{A Technique for Hardness Amplification Against AC⁰}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {1:1--1:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.1}, URN = {urn:nbn:de:0030-drops-203977}, doi = {10.4230/LIPIcs.CCC.2024.1}, annote = {Keywords: Bounded-depth circuits, average-case lower bounds, hardness amplification, XOR lemmas} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. A Strong Direct Sum Theorem for Distributional Query Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 16:1-16:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blanc_et_al:LIPIcs.CCC.2024.16, author = {Blanc, Guy and Koch, Caleb and Strassle, Carmen and Tan, Li-Yang}, title = {{A Strong Direct Sum Theorem for Distributional Query Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {16:1--16:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.16}, URN = {urn:nbn:de:0030-drops-204123}, doi = {10.4230/LIPIcs.CCC.2024.16}, annote = {Keywords: Query complexity, direct product theorem, hardcore theorem} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 104:1-104:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{larsen_et_al:LIPIcs.ICALP.2024.104, author = {Larsen, Kasper Green and Pagh, Rasmus and Persiano, Giuseppe and Pitassi, Toniann and Yeo, Kevin and Zamir, Or}, title = {{Optimal Non-Adaptive Cell Probe Dictionaries and Hashing}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {104:1--104:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.104}, URN = {urn:nbn:de:0030-drops-202471}, doi = {10.4230/LIPIcs.ICALP.2024.104}, annote = {Keywords: non-adaptive, cell probe, dictionary, hashing} }
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} }