Talk abstracts for Midwest Theory Day, December 5th, 1998.


Cynthia Dwork, IBM Almaden
"Concurrent Zero-Knowledge"

When zero-knowledge proofs are executed concurrently both parties can be at risk.  The 
verifier faces malleability issues: the prover with which it is interacting may in fact be 
using some concurrently running second interaction as an "oracle" to help answer the 
verifier's queries, yielding an invalid "proof" (for example, in the case of a proof of 
knowledge).  The prover faces the risk that concurrent executions of the protocol, with one
or more verifiers, may leak information and may not be zero-knowledge in toto. 
Malleability of interactive proofs was first addressed in 1991.  In contrast, concurrency 
remained essentially unaddressed in the literature until this year, when it experienced an 
explosion of activity resulting in four papers. This talk explains the difficulties in 
achieving concurrent zero-knowledge, and describes the state of the art. 
              

Satya Lokam, Loyola University
"Remarks on Graph Complexity"

We revisit the notion of graph complexity introduced by Pudlak, Rodl, and Savicky [PRS]. Using their 
framework, we observe that sufficiently strong superlinear monotone lower bounds for the very special 
class of 2-slice functions would imply superpolynomial lower bounds for some other functions. Given an 
n-vertex graph G, the corresponding 2-slice function f_G on n variables evaluates to zero on inputs with 
less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's, 
f_G evaluates to 1 exactly when the pair of variables set to 1 correspond to an edge in G. Combining our 
observations with those from [PRS], we can show, for instance, that a lower bound of n^{1+Omega(1)} on 
the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2^{Omega(l)} 
lower bound on the formula size of another explicit function g on l variables, where l =Theta(log n). 

We consider lower bound questions for depth-3 bipartite graphcomplexity. We prove some weak lower 
bounds on this measure using algebraic methods. For instance, our results give a lower bound of 
Omega((log n / log \og n)^2) for bipartite graphs arising from Hadamard matrices, such as the Paley-type 
bipartite graphs. Lower bounds on  graph complexity are motivated by their applications to boolean circuit 
and communication complexity lower bounds. 

(This talk is based on a paper that will appear in the Proceedings of FSTTCS '98 (Foundations of 
Software Tech and Theoretical Computer Science).  


Ken Takata, University of Illinois at Chicago
"On Frequent Sets of Boolean Matrices"

Given a Boolean matrix and a threshold t, a subset of the columns is frequent if there are at least t rows 
having a 1 entry ineach corresponding position.  This concept is used in the algorithmic, combinatorial 
approach to knowledge discovery and data mining.  We consider the complexity aspects of frequent sets. 
An explicit family of subsets is given that requires exponentially many rows to be represented as the 
family of frequent sets of a matrix, with any threshold.  Examples are given of families that can be 
represented by a small matrix with threshold t, but that require a significantly larger matrix if the threshold 
is less than t.  We also discuss the connections of these problems to circuit complexity and the existence 
of efficient listing algorithms.


Karen Bernstein, DePaul University
"Structured Operational Semantics of Higher-Order Languages"

For a programming language definition that uses bisimulation as the  notion of equivalence, it is desirable 
for the bisimulation relation  to be compatible with the language constructs; i.e. be a congruence.  Several 
syntactic rule formats have been defined, so that as long as a  definition satisfies certain syntactic 
constraints, then the defined  bisimulation relation is guaranteed to be a congruence.  Unfortunately these 
rule formats have not proven very useful for defining languages with higher-order features such as first-
class functions.  This talk will present  a new rule format that is suitable for defining higher-order 
languages  and describe a definition in the new format for the lazy lambda-calculus.



Ian Sutherland, Bell Labs
"Provably Correct Algorithms for Real Number Computation"

This talk will present a model of inexact real arithmetic called asymptotic computation that can be used to 
develop provably correct algorithms that compute with real numbers. This model is based on a form of 
real analysis called nonstandard Analysis.  Specifically, I will:

Describe the asymptotic computation model (including a brief description of nonstandard analysis), and 
contrast it with other models of computer real arithmetic.

Give an example of how the model can be used to develop an algorithm.

Describe techniques for asymptotically computing certain kinds of transcendental function and numerical 
integrals.

State the classification, in terms of classical recursion theory, of what functions can be asymptotically 
computed.

List future research directions.


Inna Pivkina, University of Kentucky
"Revision programming = Logic programming + constraints"

We study revision programming, a logic-based mechanism for enforcing constraints on databases. The 
central concept of this approach is that of a justified revision based on a revision program. We show that 
for any program P and for any pair of initial databases I and I' we can transform (shift) the program P to a 
program P' so that the size of the resulting program does not increase and so that P-justified revisions of I 
are shifted to P'-justified revisions of I'. Using this result we show that revision programming is closely 
related to a subsystem of general logic programming. This, in turn, allows us to reduce revision 
programming to logic programming with stable model semantics extended by the concept of a constraint. 
Finally, we use the connection between revision programming and general logic programming to 
introduce a disjunctive version of our formalism.


Pradyut Shah, University of Chicago
"Induced Graph Ramsey Theory"

Ramsey Theory is the study of finding large regular substructures within other larger structures.

Given a graph G, Induced Graph Ramsey Theory asks how large a graph F has to be to contain G as an 
induced subgraph under any two-coloring.  For a large variety of graphs G, good upper bounds are 
known on the size of F. However, most of these constructions are non-explicit, relying on the probabilistic
method as a key step in the construction. In this talk, we give several explicit constructions of induced 
ramsey graphs for several interesting classes of graphs G -- trees, bipartite graphs, paths and cycles.

(This is joint work with Marcus Schaefer.)