Re: How to compute "A1 x. .. x An subset B" fast if B is fixed?

sasha mal wrote:
Let B be any fixed subset of {1,...,d}^n.
On a RAM, is there a representation of B of size polynomial in d and at
most exponential in n so that the following query can be answered in
time polynomial in d and n:
Let A1, ..., An be any subsets of {1,...,d}. Is A1 x ... x An subset B?

I don't know, but here's a way to think about it in terms of lattices.

Let L denote the lattice of subsets of {1,..,d}, with meet and join given
by set intersection and union. Let L^n = Lx...xL denote the n-fold
Cartesian product of L with itself, so that meet and join in L^n are given
by pointwise set intersection and pointwise set union, respectively.

Given B, define a function f : L^n -> {0,1} by
f(A1,..,An) = 1 if A1 x ... x An is a subset B
= 0 otherwise
Note that f is continuous. In other words, it satisfies
f(x join y) = f(x) and f(y)
f(x meet y) = f(x) or f(y)
for all x,y in L^n.

I claim that this puts the possible values of B into bijective
correspondence with the set of continuous functions L^n -> {0,1}.
Given B,B' with B!=B' and their corresponding functions f,f', we can
show that f!=f' by picking any point (a1,..,an) that is in B but not B'
(or vice versa) and noticing that f({a1},..,{an}) != f'({a1},..,{an}).
Also, given any continuous function f, we can derive its corresponding B
as follows. First, note that f is determined by its values on the set of
all inputs of the form ({a1},..,{an}), with each ai in L. (This follows
by repeated application of the identity f(x join y) = f(x) and f(y).)
Now the set B can be constructed as B = {(a1,..,an) : f({a1},..,{an})
= 1}. This shows that each B corresponds to a unique function f, and
each continuous function f corresponds to a unique B.

With this background, we can reduce your problem to the following:

Problem 2. Given a continuous function f : L^n -> {0,1}, find a way
to compress f down to a data structure of size polynomial in d and at
most exponential in n, such that there is a way (if you have access to
this data structure) to evaluate f on arbitrary inputs in time polynomial
in d and n.

I don't know whether Problem 2 has a solution, but maybe this is a helpful
alternative way to think about things.

I hope I didn't make any mistakes above. I didn't check any of these
assertions, so I encourage you to do so yourself -- I could easily have
made some mistake in my reasoning somewhere.
.