@BOOK{AS,
AUTHOR="N. Alon and J. Spencer and P. Erd{\"o}s",
YEAR="1992",
TITLE="The 
	Probabilistic Method",
PUBLISHER="Wiley",
address={New York}
}

@Book{B,
Author="B. Bollob{\'a}s",
Title="Random 
	Graphs",
Publisher="Academic Press",
address={London},
Year=1985
}

@article{BoppanaR,
author={Boppana, R.},
title={The average sensitivity of bounded-depth circuits},
journal={Information Processing Letters},
volume=63,
pages={257--261},
year=1997
}
 
@inproceedings{PPSZ,
author="R. Paturi and P. Pudl{\'a}k and M. E. Saks and F. Zane",
title="An 
	Improved Exponential-time Algorithm for $k$-SAT",
booktitle={1998 Annual IEEE Symposium on Foundations of Computer Science},
year = 1998,
publisher={IEEE Computer Society},
pages = {628--637}
}

@inproceedings{Sch,
author="U. Sch{\"o}ning",
title="A 
	Probabilistic Algorithm for $k$-SAT and Constraint 
Satisfaction Problems",
booktitle="1999 Annual IEEE Symposium on Foundations of Computer Science",
publisher={IEEE Computer Society},
year=1999,
page={410--414}
}

@InCollection{BoppanaS,
title={The Complexity of Finite Functions},
author={Boppana, R. B. and Sipser, M.},
booktitle={Handbook of Theoretical Computer Science, Vol. A},
pages={759--804},
publisher={MIT Press},
address={Cambridge},
year=1990
}

@InProceedings{Cook71,
title={The 
		Complexity of Theorem-Proving Procedures},
author={Cook, S. A.},
pages={151--158},
booktitle={Conference Record of Third Annual ACM Symposium on Theory of
Computing},
month={3--5 May},
year=1971,
address={Shaker Heights, Ohio},
publisher={ACM},
}

@InProceedings{Hastad86,
title={Almost Optimal Lower Bounds for Small Depth Circuits},
author={H{\aa}stad, J.},
pages={6--20},
booktitle={Proceedings of the Eighteenth Annual ACM Symposium on
Theory of Computing},
month={28--30 May},
year=1986,
address={Berkeley, Calif.},
publisher={ACM},
}

@InProceedings{HastadJP93,
title={Top-Down Lower Bounds for Depth 3 Circuits},
author={H{\aa}stad, J. and Jukna, S. and Pudl{\'a}k, P.},
pages={124--129},
booktitle={Thirty-Fourth Annual Symposium on Foundations of Computer
Science},
month={3--5 November},
year=1993,
address={Palo Alto, Calif.},
publisher={IEEE Computer Society},
}

@Article{Levin,
title={Universal Sorting Problems},
author={Levin, L. A.},
year=1973,
journal={Problemy Peredaci Informacii},
volume=9,
pages={115-116}
}

@Article{MonienS,
title={Solving Satisfiability In Less Than $2^n$ Steps},
author={Monien, B. and Speckenmeyer, E},
year=1985,
volume=10,
journal={Discrete Applied Mathematics},
pages={287--295}
}

@InProceedings{PaturiSZ1997,
title={Exponential Lower Bounds for Depth~3 {Boolean} Circuits},
author={Paturi, R. and Saks, M. E. and Zane, F.},
pages={86--91},
booktitle={Proceedings of the Twenty-Ninth Annual ACM Symposium on
Theory of Computing},
month={4--6 May},
year=1997,
address={El Paso, Tex.},
publisher={ACM},
}

@Article{Raz1,
title={Lower Bounds on the Size
of Bounded Depth Networks over a Complete Basis with Logical
Addition},
author={Razborov, A. A.},
year=1986,
volume=41,
pages={598--607},
journal={Mathematische Zametki},
note={English Translation in
{\em Mathematical Notes of the Academy of Sciences of the USSR}}
}

@InCollection{Raz2,
title={Bounded 
	Arithmetic and Lower Bounds in Boolean Complexity},
author={Razborov, A. A},
year=1995,
booktitle={Feasible Mathematics II},
publisher={Birkh\"{a}user},
address={Boston},
pages={344-386}
}



@inproceedings{Schiermeyer1,
title={Solving 
	3-Satisfiability in less than $1.579^n$ Steps},
author={Schiermeyer, I.},
year=1993,
booktitle={Selected Papers from CSL 1992},
Series={Lecture Notes in Computer Science},
Volume= {702},
publisher={Springer-Verlag},
pages={379--394},
}

@Unpublished{Schiermeyer2,
author={Schiermeyer, I.},
title={Pure Literal Look Ahead: {A}n \mbox{$O(1.497^n)$} 
3-Satis\-fi\-a\-bil\-i\-ty Algorithm},
year=1996,
note={Preprint}
}

@InProceedings{Smolensky87,
title={Algebraic Methods in the Theory of Lower Bounds for {Boolean}
Circuit Complexity},
author={Smolensky, R.},
pages={77--82},
crossref={STOC19},
}

@Proceedings{STOC19,
title={Proceedings of the Nineteenth Annual ACM Symposium on Theory of
Computing},
booktitle={Proceedings of the Nineteenth Annual ACM Symposium on
Theory of Computing},
month={25--27 May},
year=1987,
address={New York},
publisher={ACM},
}

@InProceedings{Valiant,
title={Graph-theoretic 
	arguments in low-level complexity},
author={Valiant, L. G.},
year=1977,
booktitle={Proceedings of the 6th Symposium on Mathematical
Foundations of Computer Science},
series={Lecture Notes in Computer Science},
volume={53},
publisher={Springer-Verlag},
pages={162-176},
}

@Article{Zhang1996:277,
title={Number of models and satisfiability of sets of clauses},
author={Zhang, W.},
pages={277--288},
journal={Theoretical Computer Science},
month={26 February},
year=1996,
volume=155,
number=1,
}