[FOM] Reply to Chow's message

[Sam Buss]

  Tim Chow asked about Brower's fixedpoint theorem and resolution proof
lower bounds.  
  For some related work, that has appeared since Papadimitriou's papers,
you might check the following references:

Beame, Cook, Edmonds, Impagliazzo, Pitassi,
"The relative complexity of NP search problems"
J. Computer and System Sciences 57 (1998) 3-19.

Joshua Buresh-Oppenheim, Tsuyoshi Morioka
"Relativized NP Search Problems and Propositional Proof Systems"
ECCC Report TR03-084, Dec. 2003.

And, a preprint of mine:
"Polynomial-Size Frege and Resolution Proofs of 
st-Connectivity and Hex Tautologies", available at
http://www.math.ucsd.edu/~sbuss/ResearchWeb/stFrege/index.html

The last paper has upper and lower bounds on proofs of some tautologies
related to the Papadimitriou PPAD classes.

 -- Sam Buss