EDBT 2026 Demo / reviewers in the wild / expert
Daniel Minahan
dblp:189/7470
· DBLP profile ↗
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
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
algebraic complexity |
0.3 | 1 | 2017 | Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017 |
Computational complexity › algebraic complexity › arithmetic circuit complexity
arithmetic circuit reconstruction |
0.3 | 1 | 2017 | Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017 |
Computational complexity › boolean function complexity
read-once formulas |
0.3 | 1 | 2017 | 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.1 | 1 | 2017 | Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas · CCC 2017 |
Computational complexity
derandomization |
0.1 | 1 | 2017 | 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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2017 | Complete Derandomization of Identity Testing and Reconstruction of Read-Once FormulasabstractIn 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 |
CCC | 1 |