Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Vahid R. Asadi and Igor Shinkar. Relaxed Locally Correctable Codes with Improved Parameters. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 18:1-18:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{asadi_et_al:LIPIcs.ICALP.2021.18, author = {Asadi, Vahid R. and Shinkar, Igor}, title = {{Relaxed Locally Correctable Codes with Improved Parameters}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {18:1--18:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.18}, URN = {urn:nbn:de:0030-drops-140878}, doi = {10.4230/LIPIcs.ICALP.2021.18}, annote = {Keywords: Algorithmic coding theory, consistency test using random walk, Reed-Muller code, relaxed locally decodable codes, relaxed locally correctable codes} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Local Testability in the Non-Signaling Setting. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 26:1-26:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2020.26, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Local Testability in the Non-Signaling Setting}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {26:1--26:37}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.26}, URN = {urn:nbn:de:0030-drops-117112}, doi = {10.4230/LIPIcs.ITCS.2020.26}, annote = {Keywords: non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar. String Matching: Communication, Circuits, and Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 56:1-56:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.56, author = {Golovnev, Alexander and G\"{o}\"{o}s, Mika and Reichman, Daniel and Shinkar, Igor}, title = {{String Matching: Communication, Circuits, and Learning}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {56:1--56: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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.56}, URN = {urn:nbn:de:0030-drops-112717}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.56}, annote = {Keywords: string matching, communication complexity, circuit complexity, PAC learning} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Xin Li. Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 28:1-28:49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{li:LIPIcs.CCC.2019.28, author = {Li, Xin}, title = {{Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {28:1--28:49}, 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.28}, URN = {urn:nbn:de:0030-drops-108507}, doi = {10.4230/LIPIcs.CCC.2019.28}, annote = {Keywords: extractor, non-malleable, privacy, codes} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 25:1-25:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chiesa_et_al:LIPIcs.ITCS.2019.25, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.25}, URN = {urn:nbn:de:0030-drops-101188}, doi = {10.4230/LIPIcs.ITCS.2019.25}, annote = {Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Tony Johansson. The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 45:1-45:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{johansson:LIPIcs.APPROX-RANDOM.2018.45, author = {Johansson, Tony}, title = {{The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.45}, URN = {urn:nbn:de:0030-drops-94494}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.45}, annote = {Keywords: Random walk, random regular graph, cover time} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing Linearity against Non-Signaling Strategies. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 17:1-17:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chiesa_et_al:LIPIcs.CCC.2018.17, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{Testing Linearity against Non-Signaling Strategies}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {17:1--17:37}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.17}, URN = {urn:nbn:de:0030-drops-88731}, doi = {10.4230/LIPIcs.CCC.2018.17}, annote = {Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 39:1-39:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chiesa_et_al:LIPIcs.APPROX-RANDOM.2017.39, author = {Chiesa, Alessandro and Manohar, Peter and Shinkar, Igor}, title = {{On Axis-Parallel Tests for Tensor Product Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {39:1--39:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.39}, URN = {urn:nbn:de:0030-drops-75882}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.39}, annote = {Keywords: tensor product codes, locally testable codes, low-degree testing, extremal graph theory} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Subhash Khot and Igor Shinkar. An ~O(n) Queries Adaptive Tester for Unateness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 37:1-37:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{khot_et_al:LIPIcs.APPROX-RANDOM.2016.37, author = {Khot, Subhash and Shinkar, Igor}, title = {{An \textasciitildeO(n) Queries Adaptive Tester for Unateness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {37:1--37:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.37}, URN = {urn:nbn:de:0030-drops-66603}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.37}, annote = {Keywords: property testing, boolean functions, unateness} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Huck Bennett, Daniel Reichman, and Igor Shinkar. On Percolation and NP-Hardness. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 80:1-80:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{bennett_et_al:LIPIcs.ICALP.2016.80, author = {Bennett, Huck and Reichman, Daniel and Shinkar, Igor}, title = {{On Percolation and NP-Hardness}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {80:1--80:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.80}, URN = {urn:nbn:de:0030-drops-62056}, doi = {10.4230/LIPIcs.ICALP.2016.80}, annote = {Keywords: percolation, NP-hardness, random subgraphs, chromatic number} }
Feedback for Dagstuhl Publishing