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. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Steven James Perron

dblp:85/1683 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Computational complexity › proof complexity
bounded arithmetic
0.112007
Examining The Fragments of G · LICS 2007
Computational complexity › proof complexity › frege systems
extended frege
0.112007
Examining The Fragments of G · LICS 2007
Computational complexity › proof complexity
frege systems
0.112007
Examining The Fragments of G · LICS 2007
Computational complexity
proof complexity
0.112007
Examining The Fragments of G · LICS 2007
Computational complexity › proof complexity
quantified boolean formula proof systems
0.112007
Examining The Fragments of G · LICS 2007
Logic in computer science › proof theory
witnessing theorem
0.112007
Examining The Fragments of G · LICS 2007

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

witnessing · 0.1p-simulation · 0.1
YearPublicationVenuePosition
2007 Examining The Fragments of G
abstract
When 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
LICS1