Demo Data from EDBT 2026 / reviewers in the wild / expert
Steven James Perron
dblp:85/1683
· DBLP profile ↗
1ranked-venue papers
1as first author
0since 2021 · last 2007
—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 · 83% Logic in computer science · 17% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › proof complexity
bounded arithmetic |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Computational complexity › proof complexity › frege systems
extended frege |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Computational complexity › proof complexity
frege systems |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Computational complexity
proof complexity |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Computational complexity › proof complexity
quantified boolean formula proof systems |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Logic in computer science › proof theory
witnessing theorem |
0.1 | 1 | 2007 | Examining The Fragments of G · LICS 2007 |
Methods — techniques the papers use, named apart from their topics
witnessing · 0.1p-simulation · 0.1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2007 | Examining The Fragments of GabstractWhen restricted to proving \Sigma _i^q i formulas, the quantified propositional proof system G_i^* is closely related to the \Sigma_i^b theorems of Buss's theory S_2^i . Namely, G_i^* has polynomialsize proofs of the translations of theorems of S_2^i , and S_2^i proves that G_i^* is sound. However, little is known about G_i^* when proving more complex formulas. In this paper, we prove a witnessing theorem for G_1^* similar in style to the KPT witnessing theorem for T_2^i. This witnessing theorem is then used to show that S_2^i proves G_1^* is sound with respect to prenex \Sigma_i+1^q formulas. Note that unless the polynomial hierarchy collapses S_2^i is the weakest theory in the S_2 hierarchy for which this is true. The witnessing theorem is also used to show that G_1^* is p-equivalent to a quantified version of extended-Frege. This is followed by a proof that G_i p-simulates G_i+1^*. We finish by proving that S_2 can be axiomatized by S_2^1 plus axioms stating that the cut-free version of G* is sound. All together this shows that the connection between G_i^* and S_2^i does not extend to more complex formulas. Steven James Perron |
LICS | 1 |