1. Symmetric Logspace is Closed Under Complement by Noam Nisan and Amnon Ta-Shma, 30 June 1995

   We present a Logspace, many-one reduction from the undirected s-t connectivity problem to its complement. This shows that SL=coSL.

2. On the Weak mod m Representation of Boolean Functions by Vince Grolmusz, 21 July 1995

   Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f:{0,1}^n -> {0,1} if there is a subset S of {0,1, ... ,m-1} such that f(x)=0 if and only if P(x)is a member of S. The smallest degree of polynomials P weakly representing f is called the weak mod m degree of f. We give here an O(log n) lower bound for the weak degree of the generalized inner product 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.

   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 OR and the GIP composed with PARITY function.

3. Rabin Measures by Nils Klarlund and Dexter Kozen, 20 September 1995

   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 Rabin measure, which in a precise sense expresses progress for each transition toward satisfaction of the Rabin condition.

   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.

   When applied to termination problems under fairness constraints, Rabin measures eliminate the need for syntax-dependent, recursive applications of proof rules.

4. Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions by Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor, 19 October 1995.

   We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A 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 PCDS for L in which V flips O(log n) random coins and reads O(1) bits of the debate if and only if L is in PSPACE. This characterization of PSPACE is used to show that certain PSPACE-hard functions are as hard to approximate closely as they are to compute exactly.

Volume 1996 Abstracts

Volume 1995

Published articles

Last modified: Fri Jan 26 13:33:58 1996