%% ToC v002/a004.bib

@string{pofthe=	"Proceedings of the "}
@string{stoc ="ACM Symposium on Theory of Computing"}
@string{asttoc=" Annual " # stoc}
@string{stoc05=pofthe # "Thirty-Seventh"  # asttoc}
@string{stoc04=pofthe # "Thirty-Sixth"  # asttoc}
@string{stoc99=pofthe # "Thirty-First"  # asttoc}
@string{stoc96=pofthe # "Twenty-Eighth" # asttoc}
@string{focs=" Annual Symposium on Foundations of Computer Science"}
@string{focs99=pofthe # "Fortieth" # focs}
@string{focs02=pofthe # "Forty-Third" # focs}
@string{focs03=pofthe # "Forty-Fourth " # focs}
@string{discamath="Discrete Applied Mathematics"}
@string{doklady="Doklady Akademii Nauk SSSR, n.s."}
@string{jsl="Journal of Symbolic Logic"}
@string{dcs="Department of Computer Science"}
@string{ipco99=pofthe # "Seventh Annual Conference on Integer Programming and Combinatorial Optimization"}
@string{stacs=" Annual Symposium on Theoretical Aspects of Computer Science"}
@string{stacs02=pofthe # "Eighteenth" # stacs}
@string{icalp=" International Colloquium on Automata, Languages and Programming"}
@string{icalp02=pofthe # "Twenty-Ninth" # icalp}

@inproceedings{bw:reswidth,
  author={Ben-Sasson, E. and Wigderson, A.},
  title={Short proofs are narrow -- {R}esolution made simple},
  booktitle=stoc99,month=may,year=1999,address={Atlanta, GA},
  pages={517--526},
  eprint="stoc:301250.301392"}

@inproceedings{cei:grobner,
  author={Clegg, M. and  Edmonds, J. and Impagliazzo, R.},
  title={Using the {G}r\"obner basis algorithm to find proofs of
     unsatisfiability},
  booktitle=stoc96,month=may,year=1996,address={Philadelphia, PA},
  pages={174--183},
  eprint="stoc:237814.237860"}

@article{chvatal:cut,
  author={Chv{\'a}tal, V.},
  title={Edmonds polytopes and a hierarchy of combinatorial problems},
  journal={Discrete Mathematics},
  volume=4,
  number=4,
  pages={305--337},
  year=1973,
  eprint={DiscMath:10.1016/0012-365X(73)90167-2}}

@article{cs:resolution,
  author={Chv{\'a}tal, V. and Szemer{\'e}di, E.},
  title={Many Hard Examples for Resolution},
  journal=jacm,
  volume=35,
  number=4,
  year=1988,
  pages={759-768},
  eprint="jacm:48014.48016"}

@article{cct:cut,
  author={Cook, W. and Coullard, {C.\,R.} and Tur{\'a}n, G.},
  title={On the complexity of cutting plane proofs},
  journal=discamath,
  volume=18,
  year=1987,
  pages={25--38},
  eprint={damath:10.1016/0166-218X(87)90039-4}}

@article{haken:pigeon,
  author={Haken, A.},
  title={The intractability of resolution},
  journal=tcs,
  volume=39,
  year=1985,
  pages={297-305},
  eprint="tcs:10.1016/0304-3975(85)90144-6"}

@article{khachian:lp,
  author={Khachian, {L.\,G.}},
  title={A Polynomial Time Algorithm for Linear Programming},
  journal=doklady,
  volume=244,
  number=5,
  pages={1093-1096},
  note={English translation in {\em Soviet Math. Dokl. 20}, 191--194.},
  year=1979}

@article{ls:cones,
  author={Lov{\'a}sz, L. and Schrijver, A.},
  title={Cones of matrices and set-functions and 0-1 optimization},
  journal={SIAM J. Optimization},
  volume=1,
  number=2,
  pages={166--190},
  year=1991,
  eprint="siopt:01/0801013"
}

@article{pudlak:real,
  author={Pudl{\'a}k, Pavel},
  title={Lower bounds for resolution and cutting plane proofs and
	    monotone computations},
  journal=jsl,
  volume=62,
  number=3,
  pages={981--998},
  month=sep,
  year=1997}

@incollection{tseitin68,
  author={Tseitin, {G.\,S.}},
  title={On the complexity of derivation in the propositional calculus},
  booktitle={Studies in Constructive Mathematics and Mathematical Logic, Part II},
  year=1968,
  editor={Slisenko, {A.\,O.}}}

@inproceedings{ipu:cp,
  author={Impagliazzo, R. and Pitassi, T. and Urquhart, A.},
  title={Upper and lower bounds on tree-like Cutting Planes proofs},
  booktitle={Proceedings from Logic in Computer Science},
  year=1994,
  eprint={lics:10.1109/LICS.1994.316069},
  }

@inproceedings{bg:reswidth,
  author={Bonet, {M.\,L.} and Galesi, N.},
  title={A study of proof search algorithms for {R}esolution and 
{P}olynomial {C}alculus},
  booktitle=focs99,
  pages={422-431},
  year=1999,
  eprint="focs:10.1109/SFFCS.1999.814614"}

@article{dp:prover,
  author={Davis, M. and Putnam, H.},
  title={A computing procedure for quantification theory},
  journal=jacm,
  volume=7,
  number=3,
  year=1960,
  pages={201--215},
  eprint="jacm:321033.321034"}

@Article{krish:GTn,
  title =        "Short Proofs for Tricky Formulas",
  author =       "B.~Krishnamurthy",
  pages =        "253--275",
  journal =      "Acta Informatica",
  year =         "1985",
  volume =       "22",
  eprint="actainf:mp65776636126242"
}	

@InProceedings{Gom:60,
  author =       "{R.\,E.} Gomory",
  title =        "Solving linear programming problems in integers",
  booktitle =    "Combinatorial Analysis",
  year =         "1960",
  editor =       "R. Bellman and M. {Hall, Jr.}",
  organization = "Symposia in Applied Mathematics X, American
                 Mathematical Society",
  address =      "Providence, RI",
  pages =        "211--215",
}

@inproceedings{Eisenbrand:99,
  author =       "Friedrich Eisenbrand and Andreas S. Schulz",
  title =        "Bounds on the {C}hv{\'a}tal Rank of Polytopes in the
                 $0/1$-Cube",
  booktitle=ipco99,
  series =      "Lecture Notes in Computer Science",
  number =       "1610",
  pages =        "137--150",
  year =         "1999",
  coden =        "LNCSD9",
  ISSN =         "0302-9743",
  bibdate =      "Tue Feb 5 11:54:07 MST 2002",
  url =          "http://link.springer-ny.com/link/service/series/0558/bibs/1610/16100137.htm;
                 http://link.springer-ny.com/link/service/series/0558/papers/1610/16100137.pdf",
  acknowledgement = ack-nhfb,
  eprint="ipco:y0ruretrf6paebe1"
}

@Article{CCH:89,
  author =       "V. Chv{\'a}tal and W. Cook and M. Hartmann",
  title =        "On cutting-plane proofs in combinatorial
                 optimization",
  journal =      "Linear Algebra and its Applications",
  volume =       "114/115",
  pages =        "455--499",
  year =         "1989",
  coden =        "LAAPAW",
  ISSN =         "0024-3795",
  mrclass =      "90C27 (68R10 90C10)",
  mrnumber =     "90d:90067",
  mrreviewer =   "Endre Boros",
  bibdate =      "Thu Jan 23 11:18:08 MST 1997",
  acknowledgement = ack-nhfb,
  eprint = {laappl:10.1016/0024-3795(89)90476-X},
}

@article{BEHS:99,
  author =       "A. Bockmayr and F. Eisenbrand and {M.\,E.} Hartmann and
		  {A.\,S.} Schulz",
  title =        "On the {C}hv{\'a}tal Rank of Polytopes in the 0/1 Cube",
  journal =      "Discrete Applied Mathematics",
  month =        oct,
  number =       "1-2",
  volume =       "98",
  year =         "1999",
  pages =        "21--27",
  eprint =       {damath:10.1016/S0166-218X(99)00156-0}
}

@inproceedings{GHP02,
    author = "D. Grigoriev and {E.\,A.} Hirsch and {D.\,V.} Pasechnik",
    title = "Complexity of Semi-algebraic Proofs",
    booktitle =stacs02,
    series    = {Lecture Notes in Computer Science},
    number    = {2285},
    pages = "419--430",
    year = "2002",
    url = "citeseer.nj.nec.com/505088.html",
    eprint="stacs:t7lpe5yvaphpp0j6"
 }

@inproceedings{GHP02a,
    author = "D. Grigoriev and {E.\,A.} Hirsch and {D.\,V.} Pasechnik",
    title = "Exponential lower bound for static semi-algebraic proofs",
    booktitle=icalp02,
    series= "Lecture notes in computer science",
    number = "2380",
    pages = "257--268",
    year = "2002",
    eprint="icalp:j2k07b37hmw2pfgw"}

@techreport{HK:03,
   author={{E.\,A.} Hirsch and A. Kojevnikov},
   title={Several notes on the power of {G}omory-{C}hv{\'a}tal cuts},
   institution={ECCC},
   number={TR03-012},
   year=2003,
   eprint="eccc:TR03-012"
}

@article{stalmark:GTn,
    author = "G. Stalmark",
    title = "Short Resolution proofs for a sequence of tricky formulas",
    journal = "Acta Informatica",
    volume = "33",
    number=3,
    pages = "277-280",
    year = "1996",
    eprint="actainf:lhrhe2glkmgflbu1"}

@InProceedings{ABL:02,
  author =       "S. Arora and B. Bollob{\'a}s and L. Lov{\'a}sz",
  title =        "Proving Integrality Gaps without Knowing the Linear
                 Program",
  booktitle =    focs02,
  pages="313--322",
  year =         "2002",
  eprint="focs:10.1109/SFCS.2002.1181954"
}

@ARTICLE{ABLT:06,
  author={S. Arora and B. Bollob{\'a}s and L. Lov{\'a}sz and I. Tourlakis},
  title ={Proving Integrality Gaps without Knowing the Linear
                 Program},
  year = 2006,
  journal = {Theory of Computing},
  volume = 2,
  number = 2,
  pages = {19--51},
  eprint = {toc:v002/a002}
}
  

@unpublished{TourlakisVC:05,
  author={I. Tourlakis},
  title ={New lower bounds for vertex cover in the {L}ov{\'a}sz-{S}chrijver
                 hierarchy},
  year = 2005,
  note="Manuscript"}

@InProceedings{aat:04,
  author={M. Alekhnovich and S. Arora and I. Tourlakis},
  title={Towards strong approximability results in the {L}ov{\'a}sz-{S}chrijver
hierarchy},
  booktitle=stoc05,
  pages="294--303",
  year = 2005,
  eprint="stoc:1060590.1060634"}

@inproceedings{ARV:04,
  author = "S. Arora and S. Rao and U. Vazirani",
  title = "Expander flows, geometric embeddings and graph partitioning",
  booktitle=stoc04,month=jun,year=2004,address={Chicago, IL},
  pages="222--231",
  eprint="stoc:1007352.1007355"
}

@article{Hastad:01,
  author = "J. H{\aa}stad",
  title = "Some optimal inapproximability results",
  journal = "Journal of the ACM",
  volume = "48",
  number=4,
  year = "2001",
  pages = "798--859",
  eprint="jacm:502090.502098"
}

@phdthesis{dash:01,
  author={S. Dash},
  title={On the matrix cuts of {L}ov{\'a}sz and {S}chrijver and their
		  use in Integer Programming},
  month=mar,
  year=2001,
  school=dcs # ", Rice University"}

@article{dash:05,
  author =       "S. Dash",
  title =        "An exponential lower bound on the length of some
		  classes of branch-and-cut proofs",
  journal =    "Mathematics of Operations Research",
  year =         "2005",
  volume =     "30",
  number =     "3",
  pages =      "678--700"
}

@article{GT:00,
    author = "M. Goemans and L. Tun\c{c}el",
    title = "When does the postive semidefiniteness constraint help
		  in lifting procedures",
    journal = "Mathematics of Operations Research",
    volume = "26",
    pages = "796--815",
    year = "2001"}

@Article{ST:99,
  author =	"T. Stephen and L. Tun\c{c}el",
  title =	"On a representation of the matching polytope via
		 semidefinite liftings",
  year = 	"1999",
  journal =	"Mathematics of Operations Research",
  volume =	"24(1)",
  pages =	"1--7",
  URL =  	"http://www.math.uwaterloo.ca/~ltuncel",
}

@book{GLS:93,
    AUTHOR = {Gr{\"o}tschel, Martin and Lov{\'a}sz, L{\'a}szl{\'o} and
              Schrijver, Alexander},
     TITLE = {Geometric algorithms and combinatorial optimization},
    SERIES = {Algorithms and Combinatorics},
    VOLUME = {2},
   EDITION = {Second},
 PUBLISHER = {Springer-Verlag},
   ADDRESS = {Berlin},
      YEAR = {1993},
     PAGES = {xii+362},
      ISBN = {3-540-56740-2},
   MRCLASS = {90-02 (52C07 90C27)},
  MRNUMBER = {95e:90001},
MRREVIEWER = {Ulrich Faigle},
}

@article{FK:03,
    author = "U. Feige and R. Krauthgamer",
    title = "The probable value of {L}ov{\'a}sz-{S}chrijver relaxations for
		maximum independent set",
    journal = "SIAM Journal on Computing",
    volume = "32",
    number = "2",
    pages = "345--370",
    year = "2003",
    eprint="sicomp:10.1137/S009753970240118X"}		

@techreport{abl-cp:03,
  author={A. Atserias and {M.\,L.} Bonet and J. Levy},
  title={On {C}hv{\'a}tal Rank and Cutting Planes Proofs},
  institution={ECCC},
  number={TR03-041},
  year = 2003,
  eprint={eccc:TR03-041}}

@inproceedings{bghmp:03,
  author={J. Buresh-Oppenheim and N. Galesi and S. Hoory and A. Magen
		  and T. Pitassi },
  title={Rank Bounds and Integrality Gaps for Cutting Planes Procedures},
  booktitle=focs03,
  year=2003,
  pages="318--327",
  eprint="focs:10.1109/SFCS.2003.1238206"}	

@Article{GW:95,
  author = "M. Goemans and D. Williamson",
  title = "Improved Approximation algorithms for maximum cut and
          satisfiability problems using semidefinite programming",
  journal =jacm,
  volume = "42",
  number = "6",
  year = "1995",
  pages = "1115--1145",
  eprint="jacm:227683.227684"
}

@InProceedings{TourlakisHVC:05,
  author =       "I. Tourlakis",
  title =        "Towards Optimal Integrality Gaps for hypergraph 
              vertex cover in the {L}ov{\'a}sz-{S}chrijver hierarchy",
  pages =        "233--244",
  booktitle =    "Proceedings of Eighth International Workshop on Approximation Algorithms
                for Combinatorial Optimization Problems and Ninth
                International Workshop on Randomization and
Computation",
  year =         "2005",
  ps="http://www.cs.princeton.edu/~itourlak/publications/approx05.ps"
}

@phdthesis{hartmann,
  author={Hartmann, Mark},
  title={Cutting Planes and the Complexity of the Integer Hull},
  year=1988,
  school={Cornell University},
  note={Department of Operations Research and Industrial Engineering}
}