Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. Synergy Between Circuit Obfuscation and Circuit Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 31:1-31:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{impagliazzo_et_al:LIPIcs.APPROX/RANDOM.2023.31, author = {Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya}, title = {{Synergy Between Circuit Obfuscation and Circuit Minimization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {31:1--31:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.31}, URN = {urn:nbn:de:0030-drops-188569}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.31}, annote = {Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Pranav Bisht and Nitin Saxena. Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 9:1-9:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.9, author = {Bisht, Pranav and Saxena, Nitin}, title = {{Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.9}, URN = {urn:nbn:de:0030-drops-174012}, doi = {10.4230/LIPIcs.FSTTCS.2022.9}, annote = {Keywords: Multivariate polynomial factorization, derandomization, sparse polynomials, symmetric polynomials, factor-sparsity, convex polytopes} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Pranav Bisht and Ilya Volkovich. On Solving Sparse Polynomial Factorization Related Problems. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.10, author = {Bisht, Pranav and Volkovich, Ilya}, title = {{On Solving Sparse Polynomial Factorization Related Problems}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {10:1--10:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.10}, URN = {urn:nbn:de:0030-drops-174023}, doi = {10.4230/LIPIcs.FSTTCS.2022.10}, annote = {Keywords: Sparse Polynomials, Identity Testing, Derandomization, Factor-Sparsity, Multivariate Polynomial Factorization} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119, author = {van Melkebeek, Dieter and Morgan, Andrew}, title = {{Polynomial Identity Testing via Evaluation of Rational Functions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {119:1--119:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119}, URN = {urn:nbn:de:0030-drops-157158}, doi = {10.4230/LIPIcs.ITCS.2022.119}, annote = {Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-Way Functions and a Conditional Variant of MKTP. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 7:1-7:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{allender_et_al:LIPIcs.FSTTCS.2021.7, author = {Allender, Eric and Cheraghchi, Mahdi and Myrisiotis, Dimitrios and Tirumala, Harsha and Volkovich, Ilya}, title = {{One-Way Functions and a Conditional Variant of MKTP}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {7:1--7:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.7}, URN = {urn:nbn:de:0030-drops-155181}, doi = {10.4230/LIPIcs.FSTTCS.2021.7}, annote = {Keywords: Kolmogorov complexity, KT Complexity, Minimum KT-complexity Problem, MKTP, Conditional KT Complexity, Minimum Conditional KT-complexity Problem, McKTP, one-way functions, OWFs, average-case hardness, pseudorandom generators, PRGs, pseudorandom functions, PRFs, distinguishers, learning algorithms, NP-completeness, reductions} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Yang Du and Ilya Volkovich. Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 17:1-17:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{du_et_al:LIPIcs.FSTTCS.2021.17, author = {Du, Yang and Volkovich, Ilya}, title = {{Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {17:1--17:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.17}, URN = {urn:nbn:de:0030-drops-155286}, doi = {10.4230/LIPIcs.FSTTCS.2021.17}, annote = {Keywords: Euler’s Totient Function, Integer Factorization, Number of Prime Factors, Derandomization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Mrinal Kumar and Ben Lee Volk. A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 9:1-9:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kumar_et_al:LIPIcs.ITCS.2021.9, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {9:1--9:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.9}, URN = {urn:nbn:de:0030-drops-135486}, doi = {10.4230/LIPIcs.ITCS.2021.9}, annote = {Keywords: Rigid Matrices, Linear Circuits, Degree Bounds, Circuit Lower Bounds} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The Complexity of Finding S-Factors in Regular Graphs. 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. 21:1-21:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kolisetty_et_al:LIPIcs.FSTTCS.2019.21, author = {Kolisetty, Sanjana and Le, Linh and Volkovich, Ilya and Yannakakis, Mihalis}, title = {{The Complexity of Finding S-Factors in Regular Graphs}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {21:1--21:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.21}, URN = {urn:nbn:de:0030-drops-115834}, doi = {10.4230/LIPIcs.FSTTCS.2019.21}, annote = {Keywords: constraint satisfaction problem, Dichotomy theorem, Graph Factors, Regular Graphs} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties as Oracles. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 7:1-7:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{impagliazzo_et_al:LIPIcs.CCC.2018.7, author = {Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya}, title = {{The Power of Natural Properties as Oracles}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {7:1--7:20}, 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.7}, URN = {urn:nbn:de:0030-drops-88824}, doi = {10.4230/LIPIcs.CCC.2018.7}, annote = {Keywords: natural properties, Minimal Circuit Size Problem (MCSP), circuit lower bounds, hardness of MCSP, learning algorithms, obfuscation, Indistinguishability Obfuscators (IO)} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Ilya Volkovich. On Some Computations on Sparse Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 48:1-48:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{volkovich:LIPIcs.APPROX-RANDOM.2017.48, author = {Volkovich, Ilya}, title = {{On Some Computations on Sparse Polynomials}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {48:1--48:21}, 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.48}, URN = {urn:nbn:de:0030-drops-75976}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.48}, annote = {Keywords: Derandomization, Arithmetic Circuits, Reconstruction} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Daniel Minahan and Ilya Volkovich. Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 32:1-32:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{minahan_et_al:LIPIcs.CCC.2017.32, author = {Minahan, Daniel and Volkovich, Ilya}, title = {{Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {32:1--32:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.32}, URN = {urn:nbn:de:0030-drops-75128}, doi = {10.4230/LIPIcs.CCC.2017.32}, annote = {Keywords: Derandomization, Read-Once Formulas, Identity Testing, Arithmetic Circuits, Reconstruction} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Ilya Volkovich. Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 943-958, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{volkovich:LIPIcs.APPROX-RANDOM.2015.943, author = {Volkovich, Ilya}, title = {{Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {943--958}, 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.943}, URN = {urn:nbn:de:0030-drops-53469}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.943}, annote = {Keywords: Derandomization, Multivariate Polynomial Factorization, Sparse polynomials} }
Feedback for Dagstuhl Publishing