Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Louis Golowich and Tali Kaufman. NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 54:1-54:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{golowich_et_al:LIPIcs.ITCS.2024.54, author = {Golowich, Louis and Kaufman, Tali}, title = {{NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {54:1--54:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.54}, URN = {urn:nbn:de:0030-drops-195829}, doi = {10.4230/LIPIcs.ITCS.2024.54}, annote = {Keywords: NLTS Hamiltonian, Quantum PCP, Sum-of-squares lower bound, Quantum LDPC code} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Roy Gotlib and Tali Kaufman. Fine Grained Analysis of High Dimensional Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gotlib_et_al:LIPIcs.APPROX/RANDOM.2023.49, author = {Gotlib, Roy and Kaufman, Tali}, title = {{Fine Grained Analysis of High Dimensional Random Walks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {49:1--49:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.49}, URN = {urn:nbn:de:0030-drops-188740}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.49}, annote = {Keywords: High Dimensional Expanders, High Dimensional Random Walks, Local Spectral Expansion, Local to Global, Trickling Down} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10, author = {Abdolazimi, Dorna and Oveis Gharan, Shayan}, title = {{An Improved Trickle down Theorem for Partite Complexes}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.10}, URN = {urn:nbn:de:0030-drops-182807}, doi = {10.4230/LIPIcs.CCC.2023.10}, annote = {Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Roy Gotlib and Tali Kaufman. List Agreement Expansion from Coboundary Expansion. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gotlib_et_al:LIPIcs.ITCS.2023.61, author = {Gotlib, Roy and Kaufman, Tali}, title = {{List Agreement Expansion from Coboundary Expansion}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {61:1--61:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.61}, URN = {urn:nbn:de:0030-drops-175647}, doi = {10.4230/LIPIcs.ITCS.2023.61}, annote = {Keywords: High dimensional Expanders, Property Testing, Agreement Testing} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Tali Kaufman and Ran J. Tessler. Garland’s Technique for Posets and High Dimensional Grassmannian Expanders. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 78:1-78:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kaufman_et_al:LIPIcs.ITCS.2023.78, author = {Kaufman, Tali and Tessler, Ran J.}, title = {{Garland’s Technique for Posets and High Dimensional Grassmannian Expanders}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {78:1--78:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.78}, URN = {urn:nbn:de:0030-drops-175819}, doi = {10.4230/LIPIcs.ITCS.2023.78}, annote = {Keywords: High dimensional Expanders, Posets, Grassmannian, Garland Method} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Tali Kaufman and David Mass. Double Balanced Sets in High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.3, author = {Kaufman, Tali and Mass, David}, title = {{Double Balanced Sets in High Dimensional Expanders}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {3:1--3:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.3}, URN = {urn:nbn:de:0030-drops-171257}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.3}, annote = {Keywords: High dimensional expanders, Double balanced sets, Pseudorandom functions} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Tali Kaufman and Izhar Oppenheim. High Dimensional Expansion Implies Amplified Local Testability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.5, author = {Kaufman, Tali and Oppenheim, Izhar}, title = {{High Dimensional Expansion Implies Amplified Local Testability}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {5:1--5:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.5}, URN = {urn:nbn:de:0030-drops-171276}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.5}, annote = {Keywords: Locally testable codes, High dimensional expanders, Amplified testing} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gaitonde_et_al:LIPIcs.APPROX/RANDOM.2022.16, author = {Gaitonde, Jason and Hopkins, Max and Kaufman, Tali and Lovett, Shachar and Zhang, Ruizhe}, title = {{Eigenstripping, Spectral Decay, and Edge-Expansion on Posets}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {16:1--16:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.16}, URN = {urn:nbn:de:0030-drops-171381}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.16}, annote = {Keywords: High-dimensional expanders, posets, eposets} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Dan Karliner, Roie Salama, and Amnon Ta-Shma. The Plane Test Is a Local Tester for Multiplicity Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 14:1-14:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14, author = {Karliner, Dan and Salama, Roie and Ta-Shma, Amnon}, title = {{The Plane Test Is a Local Tester for Multiplicity Codes}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {14:1--14:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.14}, URN = {urn:nbn:de:0030-drops-165761}, doi = {10.4230/LIPIcs.CCC.2022.14}, annote = {Keywords: local testing, multiplicity codes, Reed Muller codes} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Tali Kaufman and David Mass. Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kaufman_et_al:LIPIcs.ISAAC.2021.56, author = {Kaufman, Tali and Mass, David}, title = {{Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.56}, URN = {urn:nbn:de:0030-drops-154898}, doi = {10.4230/LIPIcs.ISAAC.2021.56}, annote = {Keywords: High dimensional expanders, Unique-neighbor-like expansion, Cosystolic expansion} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Tali Kaufman and Izhar Oppenheim. Coboundary and Cosystolic Expansion from Strong Symmetry. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kaufman_et_al:LIPIcs.ICALP.2021.84, author = {Kaufman, Tali and Oppenheim, Izhar}, title = {{Coboundary and Cosystolic Expansion from Strong Symmetry}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {84:1--84:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.84}, URN = {urn:nbn:de:0030-drops-141539}, doi = {10.4230/LIPIcs.ICALP.2021.84}, annote = {Keywords: High dimensional expanders, Cosystolic expansion, Coboundary expansion} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7, author = {Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi}, title = {{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7}, URN = {urn:nbn:de:0030-drops-127681}, doi = {10.4230/LIPIcs.FUN.2021.7}, annote = {Keywords: puzzles, sliding blocks, PSPACE-hardness} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Tali Kaufman and Ella Sharakanski. Chernoff Bound for High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2020.25, author = {Kaufman, Tali and Sharakanski, Ella}, title = {{Chernoff Bound for High-Dimensional Expanders}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {25:1--25:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.25}, URN = {urn:nbn:de:0030-drops-126287}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.25}, annote = {Keywords: High Dimensional Expanders, Random Walks, Tail Bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Tali Kaufman and David Mass. Local-To-Global Agreement Expansion via the Variance Method. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaufman_et_al:LIPIcs.ITCS.2020.74, author = {Kaufman, Tali and Mass, David}, title = {{Local-To-Global Agreement Expansion via the Variance Method}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {74:1--74:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.74}, URN = {urn:nbn:de:0030-drops-117597}, doi = {10.4230/LIPIcs.ITCS.2020.74}, annote = {Keywords: Agreement testing, High dimensional expanders, Local-to-global, Variance method} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Roy Gotlib and Tali Kaufman. Testing Odd Direct Sums Using High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gotlib_et_al:LIPIcs.APPROX-RANDOM.2019.50, author = {Gotlib, Roy and Kaufman, Tali}, title = {{Testing Odd Direct Sums Using High Dimensional Expanders}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.50}, URN = {urn:nbn:de:0030-drops-112651}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.50}, annote = {Keywords: High Dimensional Expanders, Property Testing, Direct Sum} }
Feedback for Dagstuhl Publishing