Ilya Volkovich

79 papers A* 8A 5B 1Misc 2Journal 48Unranked 14

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Linear Independence, Alternants and Applications. SIAM J. Comput. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2026	A	`conf`	Upper and Lower Bounds for the Linear Ordering Principle. STACS Edward A. Hirsch, Ilya Volkovich
2026	J	`jnl`	Yet Another Proof that $BPP \subseteq PH$. Electron. Colloquium Comput. Complex. Ilya Volkovich
2026	—	`conf`	Yet Another Proof that BPP ⊆ PH. SOSA Ilya Volkovich
2025	J	`jnl`	A Note on Avoid vs MCSP. CoRR Edward A. Hirsch, Ilya Volkovich
2025	J	`jnl`	A Note on Avoid vs MCSP. Electron. Colloquium Comput. Complex. Edward A. Hirsch, Ilya Volkovich
2025	J	`jnl`	Communication Complexity of Equality and Error Correcting Codes. Electron. Colloquium Comput. Complex. Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich
2025	—	`conf`	Communication Complexity of Equality and Error-Correcting Codes. FSTTCS Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan E. Prior, Ilya Volkovich
2025	J	`jnl`	Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies. CoRR Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2025	J	`jnl`	On Solving Sparse Polynomial Factorization Related Problems. Comput. Complex. Pranav Bisht, Ilya Volkovich
2025	J	`jnl`	Reconstruction of Depth-4 Multilinear Circuits. ACM Trans. Comput. Theory Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2025	J	`jnl`	Upper and Lower Bounds for the Linear Ordering Principle. CoRR Edward A. Hirsch, Ilya Volkovich
2025	J	`jnl`	Upper and Lower Bounds for the Linear Ordering Principle. Electron. Colloquium Comput. Complex. Edward A. Hirsch, Ilya Volkovich
2024	J	`jnl`	Launching Identity Testing into (Bounded) Space. Electron. Colloquium Comput. Complex. Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich
2024	J	`jnl`	Oblivious Classes Revisited: Lower Bounds and Hierarchies. Electron. Colloquium Comput. Complex. Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2024	—	`conf`	Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies. FSTTCS Karthik Gajulapalli, Zeyong Li, Ilya Volkovich
2023	J	`jnl`	Linear Independence, Alternants and Applications. Electron. Colloquium Comput. Complex. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023	A*	`conf`	Linear Independence, Alternants, and Applications. STOC Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2023	J	`jnl`	Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	B	`conf`	New Characterization of the Factor Refinement Algorithm with Applications. ISSAC Aditya Ravi, Ilya Volkovich
2023	A	`conf`	Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	J	`jnl`	The Power of Natural Properties as Oracles. Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2023	J	`jnl`	The final nail in the coffin of statistically-secure obfuscator. Inf. Process. Lett. Ilya Volkovich
2023	—	`conf`	Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. FSTTCS Pranav Bisht, Nikhil Gupta, Ilya Volkovich
2023	J	`jnl`	Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. Electron. Colloquium Comput. Complex. Pranav Bisht, Nikhil Gupta, Ilya Volkovich
2022	—	`conf`	On Solving Sparse Polynomial Factorization Related Problems. FSTTCS Pranav Bisht, Ilya Volkovich
2022	J	`jnl`	On Solving Sparse Polynomial Factorization Related Problems. Electron. Colloquium Comput. Complex. Pranav Bisht, Ilya Volkovich
2021	—	`conf`	Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function. FSTTCS Yang Du, Ilya Volkovich
2021	—	`conf`	One-Way Functions and a Conditional Variant of MKTP. FSTTCS Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021	J	`jnl`	One-way Functions and Partial MCSP. Electron. Colloquium Comput. Complex. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
2021	J	`jnl`	Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. CoRR Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021	J	`jnl`	Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits. Electron. Colloquium Comput. Complex. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021	A*	`conf`	Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. STOC Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2021	J	`jnl`	The Final Nail in the Coffin of Statistically-Secure Obfuscator. Electron. Colloquium Comput. Complex. Ilya Volkovich
2020	J	`jnl`	Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. J. ACM Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020	—	`conf`	One (more) line on the most Ancient Algorithm in History. SOSA Bruno Grenet, Ilya Volkovich
2020	A*	`conf`	Reconstruction of Depth-4 Multilinear Circuits. SODA Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2020	Misc	`conf`	The Power of Leibniz-Like Functions as Oracles. CSR Jaeyoon Kim, Ilya Volkovich, Nelson Xuzhi Zhang
2020	Misc	`conf`	The Untold Story of SBP. CSR Ilya Volkovich
2019	J	`jnl`	Reconstruction of Depth-$4$ Multilinear Circuits. Electron. Colloquium Comput. Complex. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2019	J	`jnl`	The Complexity of Finding Electron. Colloquium Comput. Complex. Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
2019	—	`conf`	The Complexity of Finding S-Factors in Regular Graphs. FSTTCS Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis
2018	J	`jnl`	A story of AM and Unique-SAT. Electron. Colloquium Comput. Complex. Ilya Volkovich
2018	J	`jnl`	Black-Box Identity Testing of Depth-4 Multilinear Circuits. Comb. Shubhangi Saraf, Ilya Volkovich
2018	J	`jnl`	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. ACM Trans. Comput. Theory Daniel Minahan, Ilya Volkovich
2018	A*	`conf`	Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. FOCS Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018	J	`jnl`	Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. CoRR Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018	J	`jnl`	Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree. Electron. Colloquium Comput. Complex. Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich
2018	J	`jnl`	One (more) line on the most Ancient Algorithm in History. CoRR Ilya Volkovich
2018	A	`conf`	The Power of Natural Properties as Oracles. CCC Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2017	A	`conf`	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. CCC Daniel Minahan, Ilya Volkovich
2017	—	`conf`	On Some Computations on Sparse Polynomials. APPROX-RANDOM Ilya Volkovich
2017	J	`jnl`	The Power of Natural Properties as Oracles. Electron. Colloquium Comput. Complex. Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
2016	A*	`conf`	A Guide to Learning Arithmetic Circuits. COLT Ilya Volkovich
2016	J	`jnl`	Characterizing Arithmetic Read-Once Formulae. ACM Trans. Comput. Theory Ilya Volkovich
2016	J	`jnl`	Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. Electron. Colloquium Comput. Complex. Daniel Minahan, Ilya Volkovich
2015	J	`jnl`	A Guide to Learning Arithmetic Circuits. Electron. Colloquium Comput. Complex. Ilya Volkovich
2015	J	`jnl`	Computations beyond Exponentiation Gates and Applications. Electron. Colloquium Comput. Complex. Ilya Volkovich
2015	J	`jnl`	Deterministic polynomial identity tests for multilinear bounded-read formulae. Comput. Complex. Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2015	—	`conf`	Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. APPROX-RANDOM Ilya Volkovich
2015	J	`jnl`	Read-once polynomial identity testing. Comput. Complex. Amir Shpilka, Ilya Volkovich
2014	J	`jnl`	Characterizing Arithmetic Read-Once Formulae. CoRR Ilya Volkovich
2014	J	`jnl`	Deterministically Factoring Sparse Polynomials into Multilinear Factors. Electron. Colloquium Comput. Complex. Ilya Volkovich
2014	—	`conf`	On Learning, Lower Bounds and (un)Keeping Promises. ICALP (1) Ilya Volkovich
2014	J	`jnl`	On Learning, Lower Bounds and (un)Keeping Promises. Electron. Colloquium Comput. Complex. Ilya Volkovich
2014	J	`jnl`	On Reconstruction and Testing of Read-Once Formulas. Theory Comput. Amir Shpilka, Ilya Volkovich
2013	J	`jnl`	Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in. SIAM J. Comput. Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2011	J	`jnl`	Black-Box Identity Testing of Depth-4 Multilinear Circuits. Electron. Colloquium Comput. Complex. Shubhangi Saraf, Ilya Volkovich
2011	A*	`conf`	Black-box identity testing of depth-4 multilinear circuits. STOC Shubhangi Saraf, Ilya Volkovich
2011	A	`conf`	Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. CCC Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2011	—	`—`	Polynomial identity testing and its relation to some algebraic problems. Ilya Volkovich
2010	J	`jnl`	Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Electron. Colloquium Comput. Complex. Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich
2010	A*	`conf`	Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. STOC Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2010	—	`conf`	On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. ICALP (1) Amir Shpilka, Ilya Volkovich
2010	J	`jnl`	On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. Electron. Colloquium Comput. Complex. Amir Shpilka, Ilya Volkovich
2010	J	`jnl`	Read-Once Polynomial Identity Testing. Electron. Colloquium Comput. Complex. Amir Shpilka, Ilya Volkovich
2009	J	`jnl`	Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. Electron. Colloquium Comput. Complex. Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich
2009	—	`conf`	Improved Polynomial Identity Testing for Read-Once Formulas. APPROX-RANDOM Amir Shpilka, Ilya Volkovich
2008	A*	`conf`	Read-once polynomial identity testing. STOC Amir Shpilka, Ilya Volkovich