Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Huck Bennett and Chris Peikert. Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bennett_et_al:LIPIcs.APPROX/RANDOM.2023.37, author = {Bennett, Huck and Peikert, Chris}, title = {{Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {37:1--37:20}, 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.37}, URN = {urn:nbn:de:0030-drops-188622}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.37}, annote = {Keywords: Lattices, Shortest Vector Problem, Reed-Solomon codes, NP-hardness, derandomization} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Swastik Kopparty and Vishvajeet N. Extracting Mergers and Projections of Partitions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kopparty_et_al:LIPIcs.APPROX/RANDOM.2023.52, author = {Kopparty, Swastik and N, Vishvajeet}, title = {{Extracting Mergers and Projections of Partitions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {52:1--52: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.52}, URN = {urn:nbn:de:0030-drops-188777}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.52}, annote = {Keywords: randomness extractors, randomness mergers, extracting mergers, partitions, projections of partitions, covers, projections of covers} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Itay Kalev and Amnon Ta-Shma. Unbalanced Expanders from Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kalev_et_al:LIPIcs.APPROX/RANDOM.2022.12, author = {Kalev, Itay and Ta-Shma, Amnon}, title = {{Unbalanced Expanders from Multiplicity Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {12:1--12:14}, 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.12}, URN = {urn:nbn:de:0030-drops-171346}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.12}, annote = {Keywords: Condensers, Multiplicity codes, Differential equations} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Svyatoslav Gryaznov, Pavel Pudlák, and Navid Talebanfard. Linear Branching Programs and Directional Affine Extractors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gryaznov_et_al:LIPIcs.CCC.2022.4, author = {Gryaznov, Svyatoslav and Pudl\'{a}k, Pavel and Talebanfard, Navid}, title = {{Linear Branching Programs and Directional Affine Extractors}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {4:1--4:16}, 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.4}, URN = {urn:nbn:de:0030-drops-165664}, doi = {10.4230/LIPIcs.CCC.2022.4}, annote = {Keywords: Boolean Functions, Average-Case Lower Bounds, AC0\lbrack2\rbrack, Affine Dispersers, Affine Extractors} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Harm Derksen, Visu Makam, and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{derksen_et_al:LIPIcs.CCC.2022.9, author = {Derksen, Harm and Makam, Visu and Zuiddam, Jeroen}, title = {{Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {9:1--9:23}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.9}, URN = {urn:nbn:de:0030-drops-165716}, doi = {10.4230/LIPIcs.CCC.2022.9}, annote = {Keywords: tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 32:1-32:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32, author = {Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien}, title = {{On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {32:1--32:23}, 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.32}, URN = {urn:nbn:de:0030-drops-165942}, doi = {10.4230/LIPIcs.CCC.2022.32}, annote = {Keywords: Partial Derivative Method, Barriers to Lower Bounds} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Deepanshu Kush and Shubhangi Saraf. Improved Low-Depth Set-Multilinear Circuit Lower Bounds. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kush_et_al:LIPIcs.CCC.2022.38, author = {Kush, Deepanshu and Saraf, Shubhangi}, title = {{Improved Low-Depth Set-Multilinear Circuit Lower Bounds}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {38:1--38:16}, 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.38}, URN = {urn:nbn:de:0030-drops-166003}, doi = {10.4230/LIPIcs.CCC.2022.38}, annote = {Keywords: algebraic circuit complexity, complexity measure, set-multilinear formulas} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 29:1-29:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhrushundi_et_al:LIPIcs.APPROX/RANDOM.2020.29, author = {Bhrushundi, Abhishek and Harsha, Prahladh and Hatami, Pooya and Kopparty, Swastik and Kumar, Mrinal}, title = {{On Multilinear Forms: Bias, Correlation, and Tensor Rank}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {29:1--29:23}, 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.29}, URN = {urn:nbn:de:0030-drops-126325}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.29}, annote = {Keywords: polynomials, Boolean functions, tensor rank, bias, correlation} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lund_et_al:LIPIcs.APPROX/RANDOM.2020.30, author = {Lund, Ben and Potukuchi, Aditya}, title = {{On the List Recoverability of Randomly Punctured Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {30:1--30:11}, 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.30}, URN = {urn:nbn:de:0030-drops-126330}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.30}, annote = {Keywords: List recovery, randomly punctured codes, Reed-Solomon codes} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kumar_et_al:LIPIcs.CCC.2020.5, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{Lower Bounds for Matrix Factorization}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.5}, URN = {urn:nbn:de:0030-drops-125578}, doi = {10.4230/LIPIcs.CCC.2020.5}, annote = {Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 35:1-35:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kopparty_et_al:LIPIcs.CCC.2020.35, author = {Kopparty, Swastik and Moshkovitz, Guy and Zuiddam, Jeroen}, title = {{Geometric Rank of Tensors and Subrank of Matrix Multiplication}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {35:1--35:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.35}, URN = {urn:nbn:de:0030-drops-125874}, doi = {10.4230/LIPIcs.CCC.2020.35}, annote = {Keywords: Algebraic complexity theory, Extremal combinatorics, Tensors, Bias, Analytic rank, Algebraic geometry, Matrix multiplication} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bensasson_et_al:LIPIcs.ITCS.2020.5, author = {Ben-Sasson, Eli and Goldberg, Lior and Kopparty, Swastik and Saraf, Shubhangi}, title = {{DEEP-FRI: Sampling Outside the Box Improves Soundness}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {5:1--5:32}, 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.5}, URN = {urn:nbn:de:0030-drops-116901}, doi = {10.4230/LIPIcs.ITCS.2020.5}, annote = {Keywords: Interactive Oracle Proofs of Proximity, STARK, Low Degree Testing} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Aditya Potukuchi. On the AC^0[oplus] Complexity of Andreev’s Problem. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{potukuchi:LIPIcs.FSTTCS.2019.25, author = {Potukuchi, Aditya}, title = {{On the AC^0\lbrackoplus\rbrack Complexity of Andreev’s Problem}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.25}, URN = {urn:nbn:de:0030-drops-115879}, doi = {10.4230/LIPIcs.FSTTCS.2019.25}, annote = {Keywords: List Recovery, Sharp Threshold, Fourier Analysis} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On List Recovery of High-Rate Tensor Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 68:1-68:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kopparty_et_al:LIPIcs.APPROX-RANDOM.2019.68, author = {Kopparty, Swastik and Resch, Nicolas and Ron-Zewi, Noga and Saraf, Shubhangi and Silas, Shashwat}, title = {{On List Recovery of High-Rate Tensor Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {68:1--68:22}, 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.68}, URN = {urn:nbn:de:0030-drops-112832}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.68}, annote = {Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-Case to Average Case Reductions for the Distance to a Code. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bensasson_et_al:LIPIcs.CCC.2018.24, author = {Ben-Sasson, Eli and Kopparty, Swastik and Saraf, Shubhangi}, title = {{Worst-Case to Average Case Reductions for the Distance to a Code}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {24:1--24:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.24}, URN = {urn:nbn:de:0030-drops-88654}, doi = {10.4230/LIPIcs.CCC.2018.24}, annote = {Keywords: Proximity testing, Reed-Solomon codes, algebraic coding complexity} }
Feedback for Dagstuhl Publishing