%% Theory of Computing
%% File: v010a012.bib
%% Publication date: October 8, 2014
%% Authors: Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
%
@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc. Press"}
@string{ams      = "Amer. Math. Soc."}
@string{cup      = "Cambridge Univ. Press"}
@string{doklady  = "Doklady Akademii Nauk SSSR, N.S."}
@string{oup      = "Oxford Univ. Press"}
@string{springer = "Springer"}

@string{soda=" Ann. ACM-SIAM Symp. on Discrete Algorithms"}
@string{soda10= "Proc. 21st" # soda  # " (SODA'10)"}
@string{soda11= "Proc. 22nd" # soda  # " (SODA'11)"}

@string{focs81="Proc. 22nd FOCS"}
@string{focs02="Proc. 43rd FOCS"}
@string{focs98="Proc. 39th FOCS"}
@string{stoc12="Proc. 44th STOC"}
@string{focs99="Proc. 40th FOCS"}

@string{stoc11="Proc. 43rd STOC"}

@string{latin=" Latin Amer. Symp. on Theoretical Informatics"}
@string{latin10=" Proc. 9th" # latin # " (LATIN'10)"}

@string{focs03="Proc. 44th FOCS"}
@string{focs07="Proc. 48th FOCS"}

@string{Algorithmica="Algorithmica"}
%
@string{jacm="J. ACM"}
%
@string{InformandComput="Inform. and Comput."}
%
@string{discamath="Discr. Appl. Math."}
%
@string{eccc="Electron. Colloq. on Comput. Complexity (ECCC)"}
%
@string{ipl      = "Inform. Process. Lett."}
%
@string{infcont="Inf. Control"}

@string{JComputSystemSci="J. Comput. System Sci."}
@string{jcss="J. Comput. System Sci."}
%
@string{tcs      = "Theoret. Comput. Sci."}
%
@article{flgs10,
title = {Sharp Separation and Applications to Exact and Parameterized Algorithms},
author = {Fedor V. Fomin and Fabrizio Grandoni and Daniel Lokshtanov and Saket Saurabh},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/978-3-642-12200-2_8}{LATIN'10}},
journal = {Algorithmica},
number = {3},
volume = {63},
year = {2012},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {692-706},
doi = {10.1007/s00453-011-9555-9},
}

@inproceedings{flgs10-original,
title = {Sharp Separation and Applications to Exact and Parameterized Algorithms},
author = {Fedor V. Fomin and Daniel Lokshtanov and Fabrizio Grandoni and Saket Saurabh},
booktitle = latin10,
year = {2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {72-83},
doi = {10.1007/978-3-642-12200-2\_8},
}


@book{kloks1994treewidth,
title = {Treewidth, Computations and Approximations},
author = {Ton Kloks},
publisher = springer,
isbn = {3-540-58356-4},
series = {Lecture Notes in Computer Science},
volume = {842},
note = {},
year = {1994},
bibsource = {DBLP, http://dblp.uni-trier.de},
doi = {10.1007/BFb0045375},
}


@article{marx2010can,
title = {Can You Beat Treewidth?},
author = {D\'{a}niel Marx},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/FOCS.2007.27}{FOCS'07}},
date-modified = {2011-08-08 21:27:34 +0800},
journal = {Theory of Computing},
volume = {6},
number = {5},
year = {2010},
pages = {85-112},
date-added = {2011-06-20 23:02:38 +0800},
doi = {10.4086/toc.2010.v006a005},
}

@inproceedings{marx2010can-conference,
title = {Can You Beat Treewidth?},
author = {D\'{a}niel Marx},
crossref = {pfocs07},
year = {2007},
publisher = ieee,
doi = {10.1109/FOCS.2007.27},
}
%
@inproceedings{gp08,
title = {Complexity and Algorithms for Well-Structured {\it k}-{SAT} Instances},
author = {Konstantinos Georgiou and Periklis A. Papakonstantinou},
booktitle = {Theory and Applications of Satisfiability Testing - SAT 2008},
publisher = springer,
series = {LNCS},
volume = {4996},
year = {2008},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {105-118},
doi = {10.1007/978-3-540-79719-7\_10},
}


@book{arora2009computational,
title = {Computational complexity: a modern approach},
author = {Sanjeev Arora and Boaz Barak},
publisher = cup,
volume = {1},
year = {2009},
doi = {10.1017/CBO9780511804090},
}

@article{ipz01,
title = {Which Problems Have Strongly Exponential Complexity?},
author = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1998.743516}{FOCS'98}},
journal = {J. Comput. Syst. Sci.},
number = {4},
volume = {63},
year = {2001},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {512-530},
doi = {10.1006/jcss.2001.1774},
}
%
@inproceedings{ipz01-conference,
title = {Which Problems Have Strongly Exponential Complexity?},
author = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
crossref = {pfocs98},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {653-663},
doi = {10.1109/SFCS.1998.743516},
}
%
@inproceedings{szeider03,
title = {On Fixed-Parameter Tractable Parameterizations of {SAT}},
author = {Stefan Szeider},
booktitle = {Theory and Applications of Satisfiability Testing - SAT 2003},
year = {2003},
series = {LNCS},
volume = {2919},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {188-202},
doi = {10.1007/978-3-540-24605-3\_15},
}
%
@article{venkateswaran1987properties,
title = {Properties that Characterize {LOGCFL}},
author = {H. Venkateswaran},
note = {Conference version in \href{http://dx.doi.org/10.1145/28395.28411}{STOC'87}},
journal = {J. Comput. Syst. Sci.},
number = {2},
volume = {43},
year = {1991},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {380-404},
doi = {10.1016/0022-0000(91)90020-6},
}

@inproceedings{venkateswaran1987properties-original,
title = {Properties that Characterize LOGCFL},
author = {H. Venkateswaran},
crossref = {pstoc87},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {141-150},
doi = {10.1145/28395.28411},
}

@inproceedings{venkateswaran1987properties-original,
title = {Properties that Characterize LOGCFL},
author = {H. Venkateswaran},
booktitle = {Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA.},
year = {1987},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {141-150},
doi = {10.1145/28395.28411},
}


@article{fischer08,
title = {Counting truth assignments of formulas of bounded tree-width or clique-width},
author = {Eldar Fischer and Johann A. Makowsky and Elena V. Ravve},
bdsk-url-1 = {http://dx.doi.org/10.1016/j.dam.2006.06.020},
date-modified = {2012-01-20 17:50:16 +0800},
url = {http://dx.doi.org/10.1016/j.dam.2006.06.020},
journal = discamath,
number = {4},
volume = {156},
year = {2008},
pages = {511--529},
date-added = {2012-01-20 17:49:49 +0800},
doi = {10.1016/j.dam.2006.06.020},
}

@article{gottlob2001complexity,
title = {The complexity of acyclic conjunctive queries},
author = {Georg Gottlob and Nicola Leone and Francesco Scarcello},
publisher = acm,
date-modified = {2011-08-08 21:22:13 +0800},
journal = jacm,
number = {3},
volume = {48},
year = {2001},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1998.743521}{FOCS'98}},
pages = {431-498},
date-added = {2011-06-22 23:54:35 +0800},
doi = {10.1145/382780.382783},
}
%
@article{alekhnovich2002satisfiability-journal,
title = {Satisfiability, Branch-Width and {T}seitin tautologies},
author = {Michael Alekhnovich and Alexander A. Razborov},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.2002.1181983}{FOCS'02}},
journal = {Comput. Complexity},
number = {4},
volume = {20},
year = {2011},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {649-678},
doi = {10.1007/s00037-011-0033-1},
}

@inproceedings{alekhnovich2002satisfiability,
title = {Satisfiability, Branch-Width and {T}seitin Tautologies},
author = {Michael Alekhnovich and Alexander A. Razborov},
crossref = {pfocs02},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {593-603},
doi = {10.1109/SFCS.2002.1181983},
note = {See also journal version in
 \href{http://dx.doi.org/10.1007/s00037-011-0033-1}{Comput. Complexity 20(4), 2011, 649-678}},
}


@article{cr,
title = {The Relative Efficiency of Propositional Proof Systems},
author = {Stephen A. Cook and Robert A. Reckhow},
date-modified = {2012-01-27 21:41:28 +0800},
journal = {J. Symbolic Logic},
number = {1},
volume = {44},
year = {1979},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/800119.803893}{STOC'74}},
pages = {36-50},
date-added = {2012-01-27 21:41:11 +0800},
doi = {10.2307/2273702},
}


@article{paturi1998improved,
title = {An Improved Exponential-Time Algorithm for {\it k}-{SAT}},
author = {Ramamohan Paturi and Pavel Pudl{\'a}k and Michael E. Saks and Francis Zane},
journal = jacm,
volume = {52},
number = {3},
pages = {337-364},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1998.743513}{FOCS'98}},
doi = {10.1145/1066100.1066101},
year = {1998},
}

@inproceedings{paturi1998improved-conference,
title = {An Improved Exponential-Time Algorithm for {\it k}-{SAT}},
author = {Ramamohan Paturi and Pavel Pudl{\'a}k and Michael E. Saks and Francis Zane},
crossref = {pfocs98},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {628-637},
doi = {10.1109/SFCS.1998.743513},
}


@article{bodlaender-formin-etal,
title = {A Note on Exact Algorithms for Vertex Ordering Problems on Graphs},
author = {Hans L. Bodlaender and Fedor V. Fomin and Arie M. C. A. Koster and Dieter Kratsch and Dimitrios M. Thilikos},
date-modified = {2011-08-08 20:58:09 +0800},
journal = {Theory of {C}omputing {S}ystems},
number = {3},
volume = {50},
year = {2012},
pages = {420-432},
bdate-added = {2011-07-07 09:11:14 +0800},
doi = {10.1007/s00224-011-9312-0},
}

@article{wilson,
title = {Relativizing Time, Space, and Time-Space},
author = {Ronald V. Book and Christopher B. Wilson and {Xu Mei-Rui}},
date-modified = {2012-03-29 21:48:47 +0800},
journal = {SIAM J. Comput.},
number = {3},
volume = {11},
year = {1982},
pages = {571-581},
date-added = {2012-03-29 21:48:29 +0800},
doi = {10.1137/0211048},
}

@inproceedings{wilson-conference,
title = {Relativizing time and space},
author = {Ronald V. Book and Christopher B. Wilson and {Xu Mei-Rui}},
crossref = pfocs81,
doi = {10.1109/SFCS.1981.39},
}
%
@inproceedings{bbi-eccc,
title = {Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space},
author = {Paul Beame and Chris Beck and Russell Impagliazzo},
note = {Later version in \href{http://dx.doi.org/10.1145/2213977.2213999}{STOC'12}},
booktitle = eccc,
volume = {18},
year = {2011},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {149},
}

@inproceedings{bbi,
title = {Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space},
note = {See also at \href{http://eccc.hpi-web.de/report/2011/149/}{ECCC}},
author = {Paul Beame and Christopher Beck and Russell Impagliazzo},
crossref = {pstoc12},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {213-232},
doi = {10.1145/2213977.2213999},
}

@inproceedings{ms11,
title = {A full derandomization of {Sch{\"o}ning's} {\it k}-{SAT} algorithm},
author = {Robin A. Moser and Dominik Scheder},
date-modified = {2011-08-08 21:10:09 +0800},
crossref = {pstoc11},
pages = {245-252},
date-added = {2011-08-08 21:08:56 +0800},
doi = {10.1145/1993636.1993670},
eprint = {arXiv: 1008.4067},
}

@article{grohe,
title = {The complexity of homomorphism and constraint satisfaction problems seen from the other side},
author = {Martin Grohe},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.2003.1238228}{FOCS'03}},
journal = {J. ACM},
number = {1},
volume = {54},
year = {2007},
pages = {1-24},
doi = {10.1145/1206035.1206036},
}
%
@inproceedings{grohe-conference,
title = {The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side},
author = {Martin Grohe},
crossref = {pfocs03},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {552-561},
doi = {10.1109/SFCS.2003.1238228},
}


@article{bdp,
title = {Solving {\#}{SAT} and {Bayesian} Inference with Backtracking Search},
author = {Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.2003.1238208}{FOCS'03}},
date-modified = {2012-02-21 15:10:34 +0800},
journal = {J. Artif. Intell. Res. (JAIR)},
volume = {34},
year = {2009},
pages = {391-442},
date-added = {2012-02-21 15:10:08 +0800},
doi = {10.1613/jair.2648},
}

@inproceedings{bdp-conference,
title = {Algorithms and complexity results for #SAT and Bayesian inference},
author = {Fahiem Bacchus and S. Dalmao and Toniann Pitassi},
crossref = {pfocs03},
doi = {10.1109/SFCS.2003.1238208},
}
@article{papakonstantinou2009note,
title = {A note on width-parameterized {SAT}: An exact machine-model characterization},
author = {Periklis A. Papakonstantinou},
publisher = {Elsevier},
date-modified = {2011-08-08 21:27:50 +0800},
journal = ipl,
number = {1},
volume = {110},
year = {2009},
pages = {8-12},
date-added = {2011-06-19 20:46:39 +0800},
doi = {10.1016/j.ipl.2009.09.012},
}

@article{cook85,
title = {A Taxonomy of Problems with Fast Parallel Algorithms},
author = {Stephen A. Cook},
journal = infcont,
number = {1-3},
volume = {64},
year = {1985},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/3-540-12689-9\_95}{FCT'83}},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {2-22},
doi = {10.1016/S0019-9958(85)80041-3},
}


@article{cook1971characterizations,
title = {Characterizations of pushdown machines in terms of time-bounded computers},
author = {Stephen A. Cook},
publisher = acm,
date-modified = {2011-08-08 21:20:54 +0800},
journal = {J. ACM},
number = {1},
volume = {18},
note = {Preliminary version in \href{http://dx.doi/org/10.1145/800169.805437}{STOC'69}},
year = {1971},
pages = {4-18},
date-added = {2011-06-19 17:21:06 +0800},
doi = {10.1145/321623.321625},
}

@inproceedings{lms11b,
title = {Planar {\it k}-Path in Subexponential Time and Polynomial Space},
author = {Daniel Lokshtanov and Matthias Mnich and Saket Saurabh},
bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-25870-1},
isbn = {978-3-642-25869-5},
date-modified = {2012-06-21 15:59:24 +0000},
url = {http://dx.doi.org/10.1007/978-3-642-25870-1},
booktitle = {Graph-Theoretic Concepts in Computer Science - 37th International Workshop, {WG} 2011},
bibdate = {2011-11-30},
year = {2011},
bibsource = {DBLP, http://dblp.uni-trier.de/db/conf/wg/wg2011.html#LokshtanovMS11},
pages = {262--270},
date-added = {2012-06-21 15:32:02 +0000},
doi = {10.1007/978-3-642-25870-1\_24},
}

@article{robertson1986graph,
title = {Graph Minors. {II}. Algorithmic Aspects of Tree-Width},
author = {Neil Robertson and Paul D. Seymour},
note = {},
journal = {J. Algorithms},
number = {3},
volume = {7},
year = {1986},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {309-322},
doi = {10.1016/0196-6774(86)90023-4},
}


@book{vollmer,
title = {Introduction to Circuit Complexity},
author = {Heribert Vollmer},
publisher = springer,
year = {1999},
doi = {10.1007/978-3-662-03927-4},
}

@article{bodlaender1993tourist,
title = {A Tourist Guide through Treewidth},
author = {Hans L. Bodlaender},
date-modified = {2011-08-08 21:13:34 +0800},
journal = {Acta Cybern.},
number = {1-2},
volume = {11},
note = {See at \href{http://www.inf.u-szeged.hu/actacybernetica/edb/vol11n1_2/Bodlaender_1993_ActaCybernetica.xml}{Act Cybernetica}},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.8755},
year = {1993},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1-22},
date-added = {2011-08-08 21:12:14 +0800},
eprint = {citeseerx:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.8755},
}

@article{robertson1983graph,
title = {Graph minors. {I}. Excluding a forest},
author = {Neil Robertson and Paul D. Seymour},
note = {},
journal = {J. Comb. Theory, Ser. B},
number = {1},
volume = {35},
year = {1983},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {39-61},
doi = {10.1016/0095-8956(83)90079-5},
}


@inproceedings{lms11,
title = {Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal},
author = {Daniel Lokshtanov and D{\'a}niel Marx and Saket Saurabh},
booktitle = soda11,
year = {2011},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {777-789},
doi = {10.1137/1.9781611973082.61},
eprint = {arXiv: 1007.5450},
}


@inproceedings{kp10,
title = {A Space-Time Tradeoff for Permutation Problems},
author = {Mikko Koivisto and Pekka Parviainen},
booktitle = soda10,
publisher = acm,
year = {2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {484-492},
doi = {10.1137/1.9781611973075.41},
}


@book{fomin.kratsch,
title = {Exact Exponential Algorithms},
author = {Fedor V. Fomin and Dieter Kratsch},
publisher = springer,
year = {2010},
doi = {10.1007/978-3-642-16533-7},
} 
%
@article{fomin.kratsch-journal,
title = {Exact exponential algorithms},
author = {Fedor V. Fomin and Petteri Kaski},
note = {},
journal = {Commun. ACM},
number = {3},
volume = {56},
year = {2013},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {80-88},
doi = {10.1145/2428556.2428575},
}


@article{aadvw00,
title = {Characterizing Small Depth and Small Space Classes by Operators of Higher Type},
author = {Manindra Agrawal and Eric Allender and Samir Datta and Heribert Vollmer and Klaus W. Wagner},
bdsk-url-1 = {http://cjtcs.cs.uchicago.edu/articles/2000/2/contents.html},
date-modified = {2012-01-20 23:14:48 +0800},
note = {\href{http://cjtcs.cs.uchicago.edu/articles/2000/2/contents.html}{CJTCS}},
journal = {Chicago J. Theor. Comput. Sci},
number = {2},
volume = {2000},
year = {2000},
date-added = {2012-01-20 23:14:12 +0800},
}

@article{ss10,
title = {Algorithms for propositional model counting},
author = {Marko Samer and Stefan Szeider},
journal = {J. Discrete Algorithms},
number = {1},
volume = {8},
year = {2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/978-3-540-75560-9\_35}{LPAR'07}},
pages = {50-64},
doi = {10.1016/j.jda.2009.06.002},
}


@article{bis,
title = {On Uniformity within {$\mathsf{NC}^1$}},
author = {David A. Mix Barrington and Neil Immerman and Howard Straubing},
journal = jcss,
number = {3},
volume = {41},
year = {1990},
pages = {274-306},
doi = {10.1016/0022-0000(90)90022-D},
}

@inproceedings{bis-conference,
title = {On Uniformity within {$\mathsf{NC}^1$}},
author = {David A. Mix Barrington and Neil Immerman and Howard Straubing},
booktitle = {Structure in Complexity Theory conference, 1988},
year = {1988},
publisher = ieee,
doi = {10.1109/SCT.1988.5262},
}

@article{bodlaender1998partial,
title = {A partial {\it k}-arboretum of graphs with bounded treewidth},
author = {Hans L. Bodlaender},
publisher = {Elsevier},
date-modified = {2011-06-19 15:04:42 +0800},
journal = tcs,
number = {1-2},
volume = {209},
year = {1998},
pages = {1-45},
date-added = {2011-06-19 15:04:42 +0800},
doi = {10.1016/S0304-3975(97)00228-4},
}

@article{bghk95,
title = {Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree},
author = {Hans L. Bodlaender and John R. Gilbert and Hj{\'a}lmt{\'y}r Hafsteinsson and Ton Kloks},
bdsk-url-1 = {http://dx.doi.org/10.1006/jagm.1995.1009},
date-modified = {2012-08-01 01:38:51 +0000},
url = {http://dx.doi.org/10.1006/jagm.1995.1009},
journal = {J. Algorithms},
bibdate = {2011-07-01},
number = {2},
volume = {18},
year = {1995},
bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/jal/jal18.html#BodlaenderGHK95},
pages = {238--255},
date-added = {2012-08-01 01:38:29 +0000},
doi = {10.1006/jagm.1995.1009},
}

@book{bghk95-ln,
title = {Approximating treewidth, pathwidth, and minimum elimination tree height},
author = {Hans L. Bodlaender and John R. Gilbert and Hj{\'a}lmt{\'y}r Hafsteinsson and Ton Kloks},
booktitle = {Graph-{T}heoretic concepts in Computer Science},
volume = {570},
pages = {1-12},
doi = {10.1007/3-540-55121-2\_1},
}
%
@article{bcdrt,
title = {Two Applications of Inductive Counting for Complementation Problems},
author = {Allan Borodin and Stephen A. Cook and Patrick W. Dymond and Walter L. Ruzzo and Martin Tompa},
journal = {SIAM J. Comput.},
number = {3},
volume = {18},
year = {1989},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SCT.1988.5271}{SCTC'88} Erratum in \href{http://dx.doi.org/10.1137/0218084}{SICOMP}},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {559-578},
doi = {10.1137/0218038},
}



@article{woeginger2003exact,
title = {Exact algorithms for {NP}-hard problems: A survey},
author = {Gerhard J. Woeginger},
publisher = springer,
date-modified = {2011-08-08 21:31:07 +0800},
journal = {Combinatorial Optimization---Eureka, You Shrink!},
volume = {2570},
number = {},
year = {2003},
pages = {185-207},
date-added = {2011-06-27 15:13:58 +0800},
doi = {10.1007/3-540-36478-1\_17},
}

@article{nie.ros,
title = {Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits},
author = {Rolf Niedermeier and Peter Rossmanith},
journal = InformandComput,
number = {2},
volume = {118},
year = {1995},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/BFb0023843}{LATIN'92}},
pages = {227--245},
doi = {10.1006/inco.1995.1064},
}

%
%
%
%
@article{schoning1999probabilistic,
title = {A Probabilistic Algorithm for {\it k}-{SAT} Based on Limited Local Search and Restart},
author = {Uwe Sch\"oning},
journal = Algorithmica,
volume = {32},
number = {4},
year = {2002},
pages = {615-623},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFFCS.1999.814612}{FOCS'99}},
doi = {10.1007/s00453-001-0094-7},
}
 
@inproceedings{schoning1999probabilistic-conference,
title = {A probabilistic algorithm for {\it k}-{SAT} and constraint satisfaction problems},
author = {Uwe Sch\"oning},
date-modified = {2011-08-08 21:30:13 +0800},
crossref = {pfocs99},
pages = {410-414},
date-added = {2011-06-27 02:20:57 +0800},
doi = {10.1109/SFFCS.1999.814612},
}

@article{ruzzo1980tree,
title = {Tree-size bounded alternation},
author = {Walter L. Ruzzo},
publisher = {Elsevier},
date-modified = {2012-01-23 17:43:49 +0800},
journal = jcss,
number = {2},
volume = {21},
year = {1980},
pages = {218-235},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/800135.804428}{STOC'79}},
date-added = {2011-06-19 23:49:13 +0800},
doi = {10.1016/0022-0000(80)90036-7},
}

proceedings{pstoc87,
booktitle = stoc87,
publisher = acm,
year = {1987}
}
@proceedings{pstoc12,
booktitle = stoc12,
publisher = acm,
year = {2012}
}

@proceedings{pfocs02,
booktitle = focs02,
publisher = ieee,
year = {2002}
}
@proceedings{pfocs98,
booktitle = focs98,
publisher = ieee,
year = {1998}
}
@proceedings{pfocs99,
booktitle = focs99,
publisher = ieee,
year = {1998}
}
@proceedings{pfocs03,
booktitle = focs03,
publisher = ieee,
year = {2003}
}
@proceedings{pfocs07,
booktitle = focs07,
publisher = ieee,
year = {2007}
}
@proceedings{pstoc11,
booktitle = stoc11,
publisher = acm,
year = {2011}
}
@proceedings{pfocs81,
booktitle = focs81,
publisher = ieee,
year = {1981}
}


