Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Daniel Minahan

dblp:189/7470 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
0since 2021 · last 2017
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 5 heaviest of 5, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity
algebraic complexity
0.312017
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017
Computational complexity › algebraic complexity › arithmetic circuit complexity
arithmetic circuit reconstruction
0.312017
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017
Computational complexity › boolean function complexity
read-once formulas
0.312017
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017
Computational complexity › algebraic complexity › polynomial identity testing
black-box identity testing
0.112017
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017
Computational complexity
derandomization
0.112017
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017

Methods — techniques the papers use, named apart from their topics

reconstruction · 0.3read-once formulas · 0.3polynomial identity testing · 0.3
YearPublicationVenuePosition
2017 Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas
abstract
In this paper we study the identity testing problem of arithmetic read-once formulas (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the operations are {+,x} and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for read-once formulas, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of [Shpilka-Volkovich, 2015]
Daniel Minahan, Ilya Volkovich
CCC1