Skip to Main Content

AMS Sectional Meeting Program by Special Session

Current as of Tuesday, April 12, 2005 15:09:23


Program  |  Deadlines  |  Inquiries:  meet@ams.org

1995 Fall Southern Sectional Meeting
Greensboro, NC, November 17-18, 1995
Meeting #906

Associate secretaries:
Robert J Daverman, AMS daverman@math.utk.edu

Special Session on Complexity Theory

  • Friday November 17, 1995, 8:00 a.m.-10:50 a.m.
    Special Session on Complexity Theory, I

    Triad Ballroom West, Greensboro Hilton Hotel
    Organizers:
    Jie Wang, University of North Carolina, Greensboro

    • 8:00 a.m.
      The complexity of matrix rank and feasible systems of linear equations.
      Eric W. Allender*, Rutgers University, Piscataway
      Robert Beals, Institute for Advanced Study
      Mitsunori Ogihara, University of Rochester
      (906-68-26)
    • 8:30 a.m.
      Comparing complexity classes.
      Ronald V. Book*, University of California, Santa Barbara
      (906-68-28)
    • 9:00 a.m.
      The resolution of a Hartmanis conjecture: $P$-sparse hard sets.
      Jin-Yi Cai*, State University of New York, Buffalo
      D. Sivakumar, State University of New York, Buffalo
      (906-68-29)
    • 9:30 a.m.
      The bounded query complexity of $NP$-approximation problems.
      Richard Chang*, University of Maryland, Baltimore County
      (906-68-30)
    • 10:00 a.m.
      Inverting Onto functions.
      Stephen A. Fenner*, University of Southern Maine
      Lance J. Fortnow, University of Chicago
      Ashish Naik, University of Chicago
      John Rogers, University of Chicago
      (906-68-31)
    • 10:30 a.m.
      Sharply bounded alternation within $P$.
      Stephen A. Bloch, Adelphi University
      Jonathan F. Buss, University of Waterloo
      Judy Goldsmith*, University of Kentucky
      (906-68-32)
  • Friday November 17, 1995, 2:15 p.m.-6:05 p.m.
    Special Session on Complexity Theory, II

    Blue Ridge, Greensboro Hilton Hotel
    Organizers:
    Jie Wang, University of North Carolina, Greensboro

    • 2:15 p.m.
      Tree canonization and transitive closure.
      Kousha Etessami, University of Massachusetts, Amherst
      Neil Immerman*, University of Massachusetts, Amherst
      (906-68-37)
    • 2:45 p.m.
      The study on the computation theory over ordered rings and fields.
      Li Xiang*, Guizhou University, People's Republic of China
      Li Guangyuan, Guizhou University, People's Republic of China
      Song Ronggong, Guizhou University, People's Republic of China
      (906-68-39)
    • 3:15 p.m.
      Resource bounded measure, then and now.
      Luc Longpre*, University of Texas, El Paso
      (906-68-40)
    • 3:45 p.m.
      Observations on measure and lowness for $\Delta_2^P$.
      Jack H. Lutz*, Iowa State University
      (906-68-25)
    • 4:15 p.m.
      Independence properties of algorithmically random sequences.
      Steven M. Kautz*, Randolph-Macon Woman's College
      (906-68-38)
    • 4:45 p.m.
      The $PL$ hierarchy collapses.
      Mitsunori Ogihara*, University of Rochester
      (906-68-41)
    • 5:15 p.m.
      Applications of error-correcting codes in complexity theory.
      Kenneth W. Regan*, State University of New York, Buffalo
      (906-68-42)
    • 5:45 p.m.
      Non-immunity of $NEXP$-complete sets.
      Nicholas Tran*, University of Pennsylvania
      (906-68-45)
  • Saturday November 18, 1995, 2:15 p.m.-5:35 p.m.
    Special Session on Complexity Theory, III

    Blue Ridge, Greensboro Hilton Hotel
    Organizers:
    Jie Wang, University of North Carolina, Greensboro

    • 2:15 p.m.
      Lower bounds for circuits with mod gates and one exact threshold gate.
      Frederic Green*, Clark University
      (906-68-33)
    • 2:45 p.m.
      Linearly restrictable sets and applications in complexity theory.
      Sanjay Gupta*, Virginia Polytechnic Institute and State University
      (906-68-34)
    • 3:15 p.m.
      On average-case computational complexity.
      Osamu Watanabe*, Tokyo Institute of Technology, Japan
      (906-68-44)
    • 3:45 p.m.
      Average time complexity classes.
      Alan L. Selman*, State University of New York, Buffalo
      Jin-yi Cai, State University of New York, Buffalo
      (906-68-43)
    • 4:15 p.m.
      Average-case hierarchies.
      Jay Belanger*, Northeast Missouri State University and University of North Carolina, Greensboro
      (906-68-27)
    • 4:45 p.m.
      Semi-feasible computation.
      Lane A. Hemaspaandra*, University of Rochester
      (906-68-35)
    • 5:15 p.m.
      Finding large cliques in very large graphs.
      Steven Homer*, Boston University
      Marcus Peinado, Boston University
      (906-68-36)
Inquiries:  meet@ams.org