Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
Karthik Gajulapalli, Zeyong Li, and Ilya Volkovich. Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gajulapalli_et_al:LIPIcs.FSTTCS.2024.23, author = {Gajulapalli, Karthik and Li, Zeyong and Volkovich, Ilya}, title = {{Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies}}, booktitle = {44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-355-3}, ISSN = {1868-8969}, year = {2024}, volume = {323}, editor = {Barman, Siddharth and Lasota, S{\l}awomir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.23}, URN = {urn:nbn:de:0030-drops-222122}, doi = {10.4230/LIPIcs.FSTTCS.2024.23}, annote = {Keywords: fixed circuit lower bounds, semantic time hierarchy, oblivious complexity, range avoidance} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Pranav Bisht, Nikhil Gupta, and Ilya Volkovich. Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2023.9, author = {Bisht, Pranav and Gupta, Nikhil and Volkovich, Ilya}, title = {{Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {9:1--9:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.9}, URN = {urn:nbn:de:0030-drops-193829}, doi = {10.4230/LIPIcs.FSTTCS.2023.9}, annote = {Keywords: Identity Testing, Derandomization, Bounded-Read Formulae, Arithmetic Formulas} }
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 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 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 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