Du Yang; Volkovich, Ilya Approximating the number of prime factors given an oracle to Euler’s totient function. (English) Zbl 07799595 Bojańczyk, Mikołaj (ed.) et al., 41st IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2021, virtual conference, December 15–17, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 213, Article 17, 10 p. (2021). MSC: 68N30 68Qxx PDFBibTeX XMLCite \textit{Du Yang} and \textit{I. Volkovich}, LIPIcs -- Leibniz Int. Proc. Inform. 213, Article 17, 10 p. (2021; Zbl 07799595) Full Text: DOI
Bhargava, Vishwas; Saraf, Shubhangi; Volkovich, Ilya Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. (English) Zbl 07765212 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 809-822 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{V. Bhargava} et al., in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 809--822 (2021; Zbl 07765212) Full Text: DOI arXiv
Minahan, Daniel; Volkovich, Ilya Complete derandomization of identity testing and reconstruction of read-once formulas. (English) Zbl 1427.68363 ACM Trans. Comput. Theory 10, No. 3, Article No. 10, 11 p. (2018). MSC: 68W20 68W40 PDFBibTeX XMLCite \textit{D. Minahan} and \textit{I. Volkovich}, ACM Trans. Comput. Theory 10, No. 3, Article No. 10, 11 p. (2018; Zbl 1427.68363) Full Text: DOI
Volkovich, Ilya On some computations on sparse polynomials. (English) Zbl 1470.68043 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 48, 21 p. (2017). MSC: 68Q06 68W20 PDFBibTeX XMLCite \textit{I. Volkovich}, LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 48, 21 p. (2017; Zbl 1470.68043) Full Text: DOI
Minahan, Daniel; Volkovich, Ilya Complete derandomization of identity testing and reconstruction of read-once formulas. (English) Zbl 1440.68329 O’Donnell, Ryan (ed.), 32nd computational complexity conference, CCC 2017, July 6–9, 2017, Riga, Latvia. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 79, Article 32, 13 p. (2017). MSC: 68W20 68Q06 68W40 PDFBibTeX XMLCite \textit{D. Minahan} and \textit{I. Volkovich}, LIPIcs -- Leibniz Int. Proc. Inform. 79, Article 32, 13 p. (2017; Zbl 1440.68329) Full Text: DOI
Volkovich, Ilya Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials. (English) Zbl 1375.68228 Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 943-958 (2015). MSC: 68W30 12E05 12Y05 68Q25 PDFBibTeX XMLCite \textit{I. Volkovich}, LIPIcs -- Leibniz Int. Proc. Inform. 40, 943--958 (2015; Zbl 1375.68228) Full Text: DOI
Anderson, Matthew; van Melkebeek, Dieter; Volkovich, Ilya Deterministic polynomial identity tests for multilinear bounded-read formulae. (English) Zbl 1346.68105 Comput. Complexity 24, No. 4, 695-776 (2015). MSC: 68Q25 12Y05 68W30 PDFBibTeX XMLCite \textit{M. Anderson} et al., Comput. Complexity 24, No. 4, 695--776 (2015; Zbl 1346.68105) Full Text: DOI
Shpilka, Amir; Volkovich, Ilya Read-once polynomial identity testing. (English) Zbl 1329.68147 Comput. Complexity 24, No. 3, 477-532 (2015). MSC: 68Q25 12Y05 68W30 PDFBibTeX XMLCite \textit{A. Shpilka} and \textit{I. Volkovich}, Comput. Complexity 24, No. 3, 477--532 (2015; Zbl 1329.68147) Full Text: DOI
Karnin, Zohar S.; Mukhopadhyay, Partha; Shpilka, Amir; Volkovich, Ilya Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. (English) Zbl 1285.68067 SIAM J. Comput. 42, No. 6, 2114-2131 (2013). MSC: 68Q25 12Y05 PDFBibTeX XMLCite \textit{Z. S. Karnin} et al., SIAM J. Comput. 42, No. 6, 2114--2131 (2013; Zbl 1285.68067) Full Text: DOI
Saraf, Shubhangi; Volkovich, Ilya Black-box identity testing of depth-4 multilinear circuits. (English) Zbl 1288.68137 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 421-430 (2011). MSC: 68Q25 12Y05 94C10 PDFBibTeX XMLCite \textit{S. Saraf} and \textit{I. Volkovich}, in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 421--430 (2011; Zbl 1288.68137) Full Text: DOI
Karnin, Zohar S.; Mukhopadhyay, Partha; Shpilka, Amir; Volkovich, Ilya Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in. (English) Zbl 1293.90040 Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 649-658 (2010). MSC: 90C05 PDFBibTeX XMLCite \textit{Z. S. Karnin} et al., in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC '10. Cambridge, MA, USA, June 5--8, 2010. New York, NY: Association for Computing Machinery (ACM). 649--658 (2010; Zbl 1293.90040) Full Text: DOI