Call for the

	       2001 COMPLEXITY CONFERENCE RESEARCH ABSTRACTS

			  William Gasarch, Editor

Each year the Complexity conference issues a booklet of research abstracts
which are available electronically a week before the conference. You are
encouraged to **bring** your copy to the Complexity conference.  Our goal
is to provide a means for researchers to publicize new results in
complexity theory.  Our goal is **not** to endorse, verify, or referee
these abstracts.  Note that abstracts do not ordinarily count as
publications.  Each abstract will be assigned a number and then
systematically referenced by that number.

DEADLINES. To be included in the issue, the abstract ***must*** be received
on or before June 13, 2001(5:00PM Washington DC time).  
To submit an abstract electronically email to

	submitabs@cs.umd.edu
	
Abstracts may be withdrawn before the deadline as well. To do this just
email to

	gasarch@cs.umd.edu 

and tell me what to delete.

DISTRIBUTION.  The booklet will be available June 14, 2000, 5:00

Email to abstract00@cs.umd.edu  for LaTeX

Email to abstract00ps@cs.umd.edu for postscript

If email before the deadline your request will NOT be queued. You may also 
email: abstract92@cs.umd.edu, abstract93@cs.umd.edu, abstract94@cs.umd.edu, 
abstract95@cs.umd.edu, abstract96@cs.umd.edu, abstract97@cs.umd.edu, etc.
for the 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999 editions
(and abstract92ps@cs.umd.edu ...)

All researchers are encouraged to submit abstracts for inclusion, with
the only restrictions being the following.
    (1) The subject matter of abstracts must be in keeping with the
	research themes of the Complexity conference.
    (2) Abstracts must be short in length. They *must* fit on one page.
    (3) Email and postal addresses must be included in abstract with
	the authors names.
    (4) Each abstract must indicate whether or not a complete version of
	the paper is available. 
    (5) Try to get the title onto one line. Try not to use \bf
        except in the title (this makes it easier for me to 
 	compile the whole thing in the end).
    (6) DO NOT include anything about page numbers,page format, or 
	margins.
    (7) Make SURE that your file is a stand-alone latex file that
        compiles and runs on your machine and does not have any \include
        or other things that would make it not run on someone elses machine.
        (Note- LaTeX, NOT LaTeX2e)
    (8) DO NOT have before your abstract a note like
	``Dr. Gasarch, here is an abstract for you''
		or anything else, since that will make the file
		not LaTeX
    (9) Try to get the FIRST AUTHOR to email it to me and also to email it in
        alphabetcial order (e.g. If Beigel and Gasarch have an abstract,   
        and also Beigel and Fortnow have an abstract, it would be good if 
        Beigel send me FIRST the beigel-Fortnow abstract, and then the 
        Beigel-Gasarch). THIS IS NOT ESSENTIAL but would make my life a 
        little easier.
    (10) A version of the paper should be available either when the
	submission is made or shortly thereafter. 
        (This last item is simply good scientific practice).

Researchers submitting abstracts must do the following:

   Use the easy-to-use format provided by the example below. (Note that
   you do not need to know LaTeX to use it.)  Also, please do not use any
   macros-they make it hard to assemble the final document. 
   If you email more than one send it ONE abstract PER email message.
   (The `Abstract Number 98-X' part of the sample should be there as written.
    I will fill in the numbers when I compile the whole thing)

% START OF THE EXAMPLE ABSTRACT.
%
% The following is LaTeX
%
\documentstyle[11pt]{article}

\begin{document}

\vskip .5in
\noindent\fbox{
\begin{minipage}{6.0in} 
  {\bf The Complexity of Song Writing}\hfil\smallskip\break
  {\it Todd N. Nukehal},
  Departanebt L.S.I., Universitat Polit\`{e}cnica de Catalunya, 
	Pau Gargallo 5, 08028 Barcelona, SPAIN,
	({\tt nukehal@cs.umx.edu})
		\hfil\break
  {\it Milli Vanilli},
  Fachbereich Informatik, Universit\"{a}t Hamburg,
	Rothenbaumchaussee 67/69, 2000 Hamburg 13, GERMANY.
	({\tt vanilli@cs.fake.edu})
		\hfil
\bigskip\break



\centerline{\bf Abstract Number 00-X}

  Traditionally Kolgomorov theory tells us that it takes $O(n)$ characters
  to store a song of length $n$.  Only recently has this been improved,
  first by ``Old McDonald had a Farm'' which manages $O(n \log n)$ and
  ``Hickory Dickory Dock'' which manages $O(n^{1/2})$ This last result was
  important as it showed that $O(n^{1-\epsilon})$ could be achieved,
  contrary to popular belief and pop songs of that time.  We have made
  great strides in this area by showing that ``$n$ bottles of beer on the
  wall'' can be stored in $O(\log n)$.  We have extended these results and
  have some (admittedly contrived) examples of songs that take only $O(1)$
  storage.  Disco may provide more natural, though less listenable,
  examples in the future. 

\bigskip\break 
  A full paper is available by email to nukehal@cs.umx.edu
\end{minipage}}
\end{document}