Search results
- 1.0374819 - MÚ 2012 RIV US eng J - Journal Article
Tzameret, Iddo
Algebraic proofs over noncommutative formulas.
Information and Computation. Roč. 209, č. 10 (2011), s. 1269-1292. ISSN 0890-5401. E-ISSN 1090-2651
R&D Projects: GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : proof complexity * algebraic proof systems * frege proofs
Subject RIV: BA - General Mathematics
Impact factor: 0.560, year: 2011
http://www.sciencedirect.com/science/article/pii/S089054011100109X
Permanent Link: http://hdl.handle.net/11104/0207646File Download Size Commentary Version Access Tzameret.pdf 1 355.8 KB Publisher’s postprint require - 2.0369682 - MÚ 2012 RIV DE eng J - Journal Article
Thapen, Neil
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.
Archive for Mathematical Logic. Roč. 50, 7-8 (2011), s. 665-680. ISSN 0933-5846. E-ISSN 1432-0665
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded arithmetic * proof complexity * search problems
Subject RIV: BA - General Mathematics
Impact factor: 0.341, year: 2011
http://www.springerlink.com/content/l19kr20362065t86/
Permanent Link: http://hdl.handle.net/11104/0203691File Download Size Commentary Version Access Thapen1.pdf 1 239.5 KB Publisher’s postprint require - 3.0369680 - MÚ 2012 RIV GB eng J - Journal Article
Skelley, A. - Thapen, Neil
The provably total search problems of bounded arithmetic.
Proceedings of the London Mathematical Society. Roč. 103, č. 1 (2011), s. 106-138. ISSN 0024-6115. E-ISSN 1460-244X
R&D Projects: GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : Pigeonhole principle * polynomial hierarchy * local search
Subject RIV: BA - General Mathematics
Impact factor: 1.324, year: 2011
http://plms.oxfordjournals.org/content/103/1/106
Permanent Link: http://hdl.handle.net/11104/0203689File Download Size Commentary Version Access Thapen2.pdf 6 329.4 KB Publisher’s postprint require - 4.0369662 - MÚ 2012 RIV SG eng J - Journal Article
Krajíček, Jan
On the proof complexity of the Nisan-Wigderson generator based on a hard NP boolean AND coNP function.
Journal of Mathematical Logic. Roč. 11, č. 1 (2011), s. 11-27. ISSN 0219-0613. E-ISSN 1793-6691
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : proof complexity * Nisan-Wigderson generator
Subject RIV: BA - General Mathematics
Impact factor: 0.500, year: 2011
http://www.worldscinet.com/jml/11/1101/S0219061311000979.html
Permanent Link: http://hdl.handle.net/11104/0203675File Download Size Commentary Version Access Krajicek1.pdf 3 436.2 KB Publisher’s postprint require - 5.0369652 - MÚ 2012 RIV DE eng J - Journal Article
Krajíček, Jan
A note on propositional proof complexity of some Ramsey-type statements.
Archive for Mathematical Logic. Roč. 50, 1-2 (2011), s. 245-255. ISSN 0933-5846. E-ISSN 1432-0665
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : proof complexity * Ramsey theorem * resolution
Subject RIV: BA - General Mathematics
Impact factor: 0.341, year: 2011
http://www.springerlink.com/content/q27255801x225772/
Permanent Link: http://hdl.handle.net/11104/0203666File Download Size Commentary Version Access Krajicek.pdf 2 188.1 KB Publisher’s postprint require - 6.0359552 - MÚ 2012 RIV NL eng J - Journal Article
Kolodziejczyk, L. A. - Thapen, Neil - Nguyen, Phuong
The provably total NP search problems of weak second order bounded arithmetic.
Annals of Pure and Applied Logic. Roč. 162, č. 6 (2011), s. 419-446. ISSN 0168-0072. E-ISSN 1873-2461
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : complexity * fragments
Subject RIV: BA - General Mathematics
Impact factor: 0.450, year: 2011
http://www.sciencedirect.com/science/article/pii/S0168007210001491
Permanent Link: http://hdl.handle.net/11104/0197323File Download Size Commentary Version Access Thapen.pdf 1 500.9 KB Publisher’s postprint require - 7.0353751 - MÚ 2011 RIV US eng J - Journal Article
Krajíček, Jan
A form of feasible interpolation for constant depth Frege systems.
Journal of Symbolic Logic. Roč. 75, č. 2 (2010), s. 774-784. ISSN 0022-4812. E-ISSN 1943-5886
R&D Projects: GA AV ČR IAA100190902; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : feasible interpolation * Frege proof systems * lower bounds
Subject RIV: BA - General Mathematics
Impact factor: 0.584, year: 2010
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9061183&fileId=S0022481200002772
Permanent Link: http://hdl.handle.net/11104/0192907File Download Size Commentary Version Access Krajicek2.pdf 1 134.5 KB Publisher’s postprint require - 8.0337059 - MÚ 2010 RIV DE eng J - Journal Article
Kolodziejczyk, L. A. - Thapen, Neil
The polynomial and linear time hierarchies in V-0.
[Polynomiální a lineární hierarchie ve V-0.]
Mathematical Logic Quarterly. Roč. 55, č. 5 (2009), s. 509-514. ISSN 0942-5616. E-ISSN 1521-3870
R&D Projects: GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : Prefix parity * linear hierarchy * bounded arithmetic * bounded depth circuits
Subject RIV: BA - General Mathematics
Impact factor: 0.523, year: 2009
Permanent Link: http://hdl.handle.net/11104/0181147File Download Size Commentary Version Access Thapen.pdf 1 208.2 KB Publisher’s postprint require - 9.0319585 - MÚ 2009 RIV US eng J - Journal Article
Kolodziejczyk, L. A. - Thapen, Neil
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails.
[Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP.]
Journal of Symbolic Logic. Roč. 73, č. 2 (2008), s. 578-592. ISSN 0022-4812. E-ISSN 1943-5886
R&D Projects: GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : polynomial and linear hierarchies in models
Subject RIV: BA - General Mathematics
Impact factor: 0.439, year: 2008
Permanent Link: http://hdl.handle.net/11104/0168692File Download Size Commentary Version Access Thapen.pdf 1 5.7 MB Publisher’s postprint require - 10.0088021 - MÚ 2008 RIV US eng J - Journal Article
Cook, S. - Krajíček, Jan
Consequences of the Provability of $NP /subseteq P/poly$.
[Důsledky dokazatelnosti $NP /subseteq P /poly $.]
Journal of Symbolic Logic. Roč. 72, č. 4 (2007), s. 1353-1371. ISSN 0022-4812. E-ISSN 1943-5886
R&D Projects: GA AV ČR IAA1019401; GA ČR GA201/05/0124; GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : computational complexity * proof complexity * bounded arithmetic
Subject RIV: BA - General Mathematics
Impact factor: 0.609, year: 2007
Permanent Link: http://hdl.handle.net/11104/0149701File Download Size Commentary Version Access Krajicek1.pdf 1 1.5 MB Publisher’s postprint require