% The Chicago Journal of Theoretical Computer Science, Volume 1995, Abstracts
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1995 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,contents]{cjstruct}
\else
\documentclass[v1.1,contents]{cjstruct}
\fi
%
\ifltwoe\else\newcommand{\textmd}[1]{{\rm #1\/}}\fi
\ifltwoe\else\newcommand{\textit}[1]{{\it #1\/}}\fi
%
\newcommand{\cjabsheadind}{\hspace*{1em}}
%
\newlength{\cjabsparwidth}
\newlength{\cjabspardec}
\settowidth{\cjabspardec}{\cjabsheadind}
\newlength{\cjabslabdec}
\setlength{\cjabslabdec}{1.4em}
%
\newcommand{\cjabshead}[4]{\par\addvspace{\bigskipamount}{%
  \setlength{\cjabsparwidth}{\textwidth}
  \subsection*{{%
    #1.
    \addtolength{\cjabsparwidth}{-\cjabslabdec}
    \parbox[t]{\cjabsparwidth}{{\raggedright #2\\
      \addtolength{\cjabsparwidth}{-\cjabspardec}
      \cjabsheadind\parbox[t]{\cjabsparwidth}{{\raggedright\textmd{#3}\\
        \cjabsheadind\parbox[t]{\cjabsparwidth}{\raggedright\textmd{\textit{#4}}}
      }}%
    }}%
  }}%
}}%
%
\ifltwoe\else\newcommand{\textsl}[1]{{\sl #1\/}}\fi
%
\ifltwoe\else\newcommand{\emph}[1]{{\em #1\/}}\fi
\ifltwoe\else\newcommand{\textup}[1]{{\rm #1\/}}\fi
%
\newcommand{\textuprm}[1]{\textup{\textrm{#1}}}
%
\mathstyleclass{\complexityclass}{\mathord}{\textsl}
\newcommand{\complement}[1]{\mathord{\mbox{\sl co\begin{math}#1\end{math}}}}
\mathstyleclass{\systemmodel}{\mathord}{\textuprm}
%
\mathstyleclass{\function}{\mathord}{\textup}
\newcommand{\umod}{\mathop{\bmod}}
\newcommand{\polynomial}[1]{#1}
\newcommand{\orderge}[1]{\Omega(#1)}
\newcommand{\orderle}[1]{O(#1)}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\oftype}{\colon}
\newcommand{\funccomp}{\circ}
%
\newcommand{\deceased}[1]{\dag#1}
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1995, Abstracts\\
      {\it 31 December 1995}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142; (617)253-2889; {\em journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item {\em http://www-mitpress.mit.edu/jrnls-catalog/chicago.html/}
    \item {\em http://www.cs.uchicago.edu/publications/cjtcs/}
    \item {\em gopher.mit.edu}
    \item {\em gopher.cs.uchicago.edu}
    \item anonymous {\em ftp\/} at {\em mitpress.mit.edu}
    \item anonymous {\em ftp} at {\em cs.uchicago.edu}
  \end{itemize}
\sentence
}
%
\copyrightstmt{%
  \copyright 1995 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  {\em journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The {\em Chicago Journal of Theoretical Computer Science\/}
  is a peer-reviewed scholarly
  journal in theoretical computer science\@. The journal is committed
  to providing a forum for significant results on theoretical
  aspects of all topics in Computer Science\@.
  \par
  \begin{trivlist}
    \item[{\em Editor in chief:}] Janos Simon
    \item[{\em Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[{\em Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Stephen Homer & Alan Selman \\
        Jin-Yi Cai & Neil Immerman & Nir Shavit \\
        Anne Condon & \deceased{Paris Kanellakis} & Eva Tardos \\
        Cynthia Dwork & Howard Karloff & Sam Toueg \\ 
        David Eppstein & Philip Klein & Moshe Vardi \\
        Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
        Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
        Steven Fortune & Michael Merritt
      \end{tabular}
    \vspace{1ex}
    \item[{\em Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[{\em Electronic mail:}] {\em chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1995}
%
\articleid{Abstracts}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Abstracts from Volume 1995}
\shorttitle{Abstracts 1995}
\collectiontitle{}
%
\shortauthors{Editorial}
%
\begin{editinfo}
  \published{31}{12}{1995}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}
%
\cjabshead{1}{%
  Symmetric \(\complexityclass{Logspace}\) is Closed Under
  Complement%
}%
  {Noam~Nisan, \mbox{Amnon~Ta-Shma}}%
  {30 June 1995}
%
\apar{1. Abstract-1}
We present a \(\complexityclass{Logspace}\), many-one reduction from
the undirected \mbox{\(s\)--\(t\)} connectivity problem to its
complement\@. This shows that
\(\complexityclass{SL}=\complement{\complexityclass{SL}}\)\@.
%
\cjabshead{2}{%
  On the Weak \(\umod m\) Representation of Boolean Functions%
}%
  {Vince~Grolmusz}%
  {21 July 1995}
%
\begin{sloppypar}
\apar{2. Abstract-1}
Let \(\polynomial{P}\) be a polynomial over the ring of \(\umod m\) integers\@.
\(\polynomial{P}\) \emph{weakly represents} Boolean function
\(f\oftype\funcspace{\{0,1\}^n}{\{0,1\}}\) if there is a subset
\(S\subseteq{\{0,1,\ldots,m-1\}}\) such that \(f(x)=0\) if and only if
\(\polynomial{P}(x)\in S\)\@. The smallest degree of polynomials
\(\polynomial{P}\) weakly representing \(f\) is called the \emph{weak
\(\umod m\) degree of \(f\)}\@. We give here an \(\orderge{\log n}\)
lower bound  for the weak degree of the generalized inner product
function (\(\function{GIP}\)) of Babai, Nisan, and Szegedy\@. This is
the first lower-bound result for the weak degree
of a Boolean function that does not deteriorate if the number of prime
divisors of \(m\) increases\@.
%
\apar{2. Abstract-2}
In the second part of the paper, we give superpolynomial lower bounds
for the number of monomials with nonzero coefficients in polynomials
weakly representing the \(\function{OR}\) and the
\(\function{GIP}\funccomp\function{PARITY}\) functions\@.
\end{sloppypar}
%
\cjabshead{3}{%
  Rabin Measures%
}%
  {Nils~Klarlund, Dexter~Kozen}%
  {20 September 1995}
%
\apar{3. Abstract-1}
\emph{Rabin conditions} are a general class of properties of infinite
sequences that encompass most known automata-theoretic acceptance
conditions and notions of fairness\@. In this paper, we introduce a
concept, called a \emph{Rabin measure}, which in a precise sense
expresses progress for each transition toward satisfaction of the
Rabin condition\@.
%
\apar{3. Abstract-2}
We show that these measures of progress are linked to the
Kleene-Brouwer ordering of recursion theory\@. This property is used
in [Kla94a(JPL)] to establish an exponential upper bound
for the complementation of automata on infinite trees\@.
%
\apar{3. Abstract-3}
When applied to termination problems under fairness constraints, Rabin
measures eliminate the need for syntax-dependent, recursive
applications of proof rules\@.
%
\cjabshead{4}{%
  Probabilistically Checkable Debate Systems and Nonapproximability
  of \(\complexityclass{PSPACE}\)-Hard Functions
}
  {Anne~Condon, Joan~Feigenbaum, Carsten~Lund, Peter~W.~Shor}%
  {19 October 1995}
%
\apar{4. Abstract-1}
We initiate an investigation of \emph{probabilistically checkable
debate systems} (\(\systemmodel{PCDS}\)), a natural generalization of
probabilistically checkable proof systems (\(\systemmodel{PCPS}\))\@. A
\(\systemmodel{PCDS}\) for a language \(L\) consists of a
probabilistic polynomial-time verifier \(V\) and a debate between
player \(1\), who claims that the input \(x\) is in \(L\), and player \(0\),
who claims that the input \(x\) is not in \(L\)\@. We show that there is
a \(\systemmodel{PCDS}\) for \(L\) in which \(V\) flips
\(\orderle{\log n}\) random coins and reads \(\orderle{1}\) bits of
the debate if and only if \(L\) is in
\(\complexityclass{PSPACE}\)\@. This characterization of
\(\complexityclass{PSPACE}\) is used to show that certain
\(\complexityclass{PSPACE}\)-hard functions are as hard to approximate
closely as they are to compute exactly\@.
%
\end{articletext}
%
\end{document}