Ilya Volkovich

Electron. Colloquium Comput. Complex., 2024

Launching Identity Testing into (Bounded) Space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies.

[BibT_eX]

[DOI]

Karthik Gajulapalli

Zeyong Li

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

The Power of Natural Properties as Oracles.

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

Comput. Complex., December, 2023

The final nail in the coffin of statistically-secure obfuscator.

[BibT_eX]

[DOI]

Inf. Process. Lett., August, 2023

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

Electron. Colloquium Comput. Complex., 2023

Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae.

[BibT_eX]

[DOI]

Pranav Bisht

Nikhil Gupta

Electron. Colloquium Comput. Complex., 2023

Linear Independence, Alternants and Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

New Characterization of the Factor Refinement Algorithm with Applications.

[BibT_eX]

[DOI]

Aditya Ravi

Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

Synergy Between Circuit Obfuscation and Circuit Minimization.

[BibT_eX]

[DOI]

Russell Impagliazzo

Valentine Kabanets

Proceedings of the Approximation, 2023

2022

On Solving Sparse Polynomial Factorization Related Problems.

[BibT_eX]

[DOI]

Pranav Bisht

Electron. Colloquium Comput. Complex., 2022

2021

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

One-way Functions and Partial MCSP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Approximating the Number of Prime Factors Given an Oracle to Euler's Totient Function.

[BibT_eX]

[DOI]

Yang Du

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

One-Way Functions and a Conditional Variant of MKTP.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

2020

One (more) line on the most Ancient Algorithm in History.

[BibT_eX]

[DOI]

Bruno Grenet

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

The Untold Story of SBP.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2020

The Power of Leibniz-Like Functions as Oracles.

[BibT_eX]

[DOI]

Jaeyoon Kim

Nelson Xuzhi Zhang

Proceedings of the Computer Science - Theory and Applications, 2020

2019

The Complexity of Finding <i>S</i>-factors in Regular Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Reconstruction of Depth-$4$ Multilinear Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

The Complexity of Finding S-Factors in Regular Graphs.

[BibT_eX]

[DOI]

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

A story of AM and Unique-SAT.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

One (more) line on the most Ancient Algorithm in History.

[BibT_eX]

[DOI]

CoRR, 2018

2017

On Some Computations on Sparse Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Characterizing Arithmetic Read-Once Formulae.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2016

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas.

[BibT_eX]

[DOI]

Daniel Minahan

Electron. Colloquium Comput. Complex., 2016

2015

A Guide to Learning Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Computations beyond Exponentiation Gates and Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Read-once polynomial identity testing.

[BibT_eX]

[DOI]

Comput. Complex., 2015

Deterministic polynomial identity tests for multilinear bounded-read formulae.

[BibT_eX]

[DOI]

Matthew Anderson

Dieter van Melkebeek

Comput. Complex., 2015

Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

On Reconstruction and Testing of Read-Once Formulas.

[BibT_eX]

[DOI]

Theory Comput., 2014

Deterministically Factoring Sparse Polynomials into Multilinear Factors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

On Learning, Lower Bounds and (un)Keeping Promises.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

2011

Polynomial identity testing and its relation to some algebraic problems.

[BibT_eX]

[DOI]

PhD thesis, 2011

Black-Box Identity Testing of Depth-4 Multilinear Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

2010

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.

[BibT_eX]

[DOI]

Matthew Anderson

Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2010

2009

Improved Polynomial Identity Testing for Read-Once Formulas.

[BibT_eX]

[DOI]