User miforbes - MathOverflow

What is the easiest randomized algorithm to motivate to the layperson?

2010-09-09T23:27:17Z

When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but the standard randomized algorithms don't admit a simple description (or proof of correctness) in a lay-atmosphere. I often resort to the saying that randomized algorithms allow "finding hay in a haystack", but that has little mathematical substance.

The question: Is there a good example of a problem that:

is easily explained (and sufficiently interesting)
has a simple randomized algorithm
appears non-trivial to get an efficient deterministic algorithm

and ideally also satisfies:

the randomized algorithm has a somewhat understandable proof of correctness - so no Markov/Chernoff/random-walk-mixing-times

Answer by miforbes for What is the complexity of this problem?

2011-07-12T00:21:34Z

If one relaxes the question to asking the row-reduction distance of arbitrary matrices over $\mathbb{F}_2$ then it can be shown that the problem is $NP$-Complete. That is, consider

RRD (Row Reduction Distance):

Input: $m\times n$ matrices $M$, $N$ over $\mathbb{F}_2$, and an integer $k$

Output: Whether $M$ can be row-reduces to $N$ in $\le k$ steps

The claim is that this problem RRD is $NP$-complete. It is within $NP$, so the hardness is all that remains. To do this, consider the following related problem.

MHW (Min Hamming Weight):

Input: $P\in\mathbb{F}_2^{m\times n}$, $b\in\mathbb{F}_2^n$, integer $k$

Output: Is $b$ expressible as a linear combination of $\le k$ rows of $P$.

I'll first show that MHW reduces to RRD, then show that RRD is $NP$-hard. This together will show RRD is NP-hard.

Let $(P,b,k)$ be an instance of MHW. Create $M$ and $N$ as $(m+1)\times n$ matrices, where $M$ is just $P$ with the zero row appended on, and $N$ is just $P$ with the row $b$ appended on. I'll now show that $b$ is expressible as a linear combination of at most $k$ rows of $P$ iff $M$ is row-reducible to $N$ it at most $k$ steps.

The forward direction of this claim is straightforward. Now for the backward direction. Row-reduction operations over $\mathbb{F}_2$ are just "add this row to that row", or "swap this and that row". It follows that in $\le k$ row-reductions have at most $k$ "source" rows of where the additions come from. Thus, the last row of $N$ is equal to the last row of of $M$ (which is zero) plus at most $k$ other rows of $M$. This is exactly what was wanted, as the last row of $M$ is just $b$.

This completes the proof that MHW reduces to RRD.

Now let's show that MHW is NP-hard. We'll do so with:

SET-COVER

Input: Sets $S_1,\ldots,S_m\subseteq[n]$, integer $k$,

Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets $S_i$

It is know that Set-Cover is NP-complete. Here we need a slightly stronger version of this fact, where all of the sets are of constant size, and this is still NP-complete. (To see this, one first shows that 3SAT is still NP-complete when each variable appears in at most 3 clauses. Then one runs through the "standard" reduction from 3SAT to Set-Cover, and notices that all of the sets are of constant size).

Now consider a set-cover instance. Note that if we through in all subsets of each $S_i$, the answer to the cover question doesn't change. Note that we can do this as each subset is of constant size, so there aren't too many subsets to add. Thus we get

Hered-Set-Cover

Input: Let $\mathcal{S}\subseteq 2^{[n]}$ be a family of sets, each of size $O(1)$, that is subset closed. Let $k$ be an integer.

Ouptut: Decide if $[n]$ is the union of $\le k$ of the sets from $\mathcal{S}$.

and Hered-Set-Cover is NP-complete, as argued above. We'll now reduce Hered-Set-Cover to MHW. Take a Hered-Set-Cover instance, with the family of sets $\mathcal{S}$ and integer $k$. Suppose there are $m$ sets. Then write out $P$ to be the $m\times n$ matrx where the rows are the indicator vectors for the sets in $\mathcal{S}$. The target vector $b$ is the all ones vector, and $k$ is as in the original problem. So if $b$ is a $\le k$ linear combination of the rows, then this immediately gives the set-cover of $\le k$ sets. If there is a set-cover of $\le k$ sets, then we can always pass to subsets so that each element in the ground set is covered exactly once, and thus when we sum up the relevant vectors in $\mathcal{F}_2$ we never run into the issue that 2=0.

So really we are doing a "set-cover with odd covering at each vertex" in the MHW instance. The point is that allowing the subsets in the family makes the exact number of coverings irrelevant, and so we can assume things are covered exactly once.

It seems like there might be a more direct reduction from the problem Exact-Cover (where in set-cover we require that each element be covered exactly once). Indeed, I sort of just untangled the reductions needed to use Exact-Cover. But Exact-Cover doesn't seem exactly right, because if $b$ is a $\le k$ linear combination this doesn't immediately translate to an exact cover.

This approach doesn't seem to address the issue when $M$ and $N$ are full-rank in the RRD problem, as the reduction of MHW to RRD needs non-full-rank, and the MHW problem is solvable in polynomial time when $P$ is full rank.

Answer by miforbes for What is the complexity of this problem?

2011-07-11T03:26:12Z

This is not a full answer, but perhaps too long for a comment.

Your question is about the distance problem in a fixed Cayley graph. If one also considers the Cayley graph as part of the input then some things are known. This makes sense in the context of permutation groups, where we can explicitly give the generators in a succinct way.

Even and Goldreich in the paper "Minimum-Length Generator Sequence Problem is NP-Hard" (J. ALGORITHMS. Vol. 2, no. 3, pp. 311-313. 1981) showed:

We examine the following questions: (1) Given a set of generators of a permutation group G and a target permutation P, find (the length of) a shortest generator sequence realizing P. (2) Given a set of generators of a permutation group G, find the minimum upper bound on the length of generator sequences needed to realize any permutation in G. We show that both problems are NP-Hard by reducing the 3XC problem to each of them. The reductions we use show that these results hold even if the given set of generators is restricted to contain for each generator its inverse, too.

This actually makes the problem NP-Complete (when the length is written in unary).

In other work, Mark Jerrum in "The complexity of finding minimum-length generator sequences" (Theoretical Computer Science Volume 36, 1985, Pages 265-289) showed:

The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to be Image -complete and, indeed,is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set contains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known Image -complete problems. Some restricted versions of the problem, in which the generator set is fixed rather than being part of the problem instance, are also investigated and shown to be computationally tractable. One result of this kind is that determining the most compact expression of a permutation in terms of ‘cyclicly adjacent transpositions’ can be achieved in polynomial time. Thus, from an initial arrangement of distinct objects on a circle, one can quickly compute the smallest number of interchanges of adjacent objects required to realise any other arrangement. Surprisingly, this problem appears substantially more difficult to solve than the related one (for which a solution has been known for some time) in which the objects are arranged on a line segment.

Note that Jerrum considers the length of the path in binary, which changes things.

Examples of Super-polynomial time algorithmic/induction proofs?

2010-07-30T16:19:18Z

In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:

-The proof moves through stages

-An invariant is shown to hold by induction from previous stages

-The algorithm is shown to terminate

-The invariant holding at termination implies the desired claim.

Perhaps the best example I know of is an algorithmic proof of Konig's theorem, which in a sense is just a max-flow/min-cut algorithm. In some sense, most induction proofs fit this mold.

The above example runs in polynomial time. Are there good examples of algorithmic/induction proofs that take super-polynomial time to prove things that don't obviously need such induction?

That is, I don't want Ackermann-like recurrences, or anything that is "brute-force". Further, I'm not looking for super-polynomial time algorithms that solve instances of problems, but rather am looking for super-polynomial time algorithms that prove a theorem of some sort (eg. like a combinatorial max-min theorem in the above example).

Answer by miforbes for how to determine whether an ideal is prime or not by an algorithm

2011-04-07T16:27:15Z

There is such a test. Some explanation can be found in: "An introduction to Gröbner bases, By William Wells Adams, Philippe Loustaunau", or the original article (http://portal.acm.org/citation.cfm?id=65034) the above text is based on. See also the singular manual.

Answer by miforbes for Language in Space(n) but not in NP

2011-03-29T04:31:33Z

Neither part of your question is known. To see this, note that $PSPACE$ contains $SPACE(n)$ (and $NP$), so exhibiting a language in $SPACE(n)$ not in $NP$ would separate $PSPACE$ and $NP$ - this is not known.

$SPACE(n)$ contains $L$ (logspace), and it is open whether $NP=L$ (note that $NP$ contains $L$). Thus, giving a language which is in $NP$ but not in $SPACE(n)$ would separate $NP$ and $L$ - also not known.

Answer by miforbes for Lower bound for sum of binomial coefficients?

2011-02-16T08:09:21Z

Summing binomial coefficients $\sum_{i=0}^k\binom{n}{i}$ can be seen as asking "how many binary strings are close to the length-$n$ all-zero string, differing in at most $k$ places?". One can generalize this to larger alphabets, and this almost captures your question on $\sum_{i=0}^k\binom{n}{i} (1-a)^{n-k}a^k$. So perhaps the coding theory community has more to say on this issue?

One place to start is this set of lecture notes by Venkat Guruswami:

http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes2.pdf

(see page 3).

Answer by miforbes for A generalization of Boolean matrix multiplication for order-3 tensors

2010-08-03T04:44:03Z

I've been studying tensors (but mostly concerning lower bounds for their rank) for some months now, and can't say I've come across this and wouldn't be surprised if its new. Loosely, there are two groups of people I've seen studying tensors: mathematicians/theory-comp-sci-people interested in matrix multiplication algorithms, and numerical analysts interested in approximating 3D data with low-rank tensors (that is, a way of compressing 3D data by taking the "most important" aspects).

For the first group, a good reference is "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi. I wouldn't expect your operation to be known in this community as it is a triary-operation, as opposed to binary. Mathematics of triary-operations doesn't seem common.

The other community does seem to be exploring operations on tensors, in particular interest with generalizing things such as SVD to tensors. Their literature is harder to navigate for me, but a good start is this page, and to know that tensor decomposition is sometimes called "PARAFAC" analysis (parallel factorization).

Answer by miforbes for Reconstructing a polynomial from resultants

2010-07-31T17:54:46Z

I really like this question, but unfortunately I think that it doesn't have any algorithm in the general case, as I'll explain below. Thus, to reconstruct your desired $f$, either you need to use $g_m$'s that are special, or assume that $f$ has some special structure (or both).

My claim goes against your stated algorithm (which is a shame, as it is a nice idea), so I'll first describe why I don't think that the algorithm works. I thought I had a formal proof that the algorithm was faulty (aside from the below counter-example), but it didn't go through. The problems I see are two fold:

Even if one solves the system, I feel like it may not always be possible to get back to the actual coefficients of $f$ (I wouldn't be surprised if it was possible, though).
You claim that once we have enough equations then we should be able to solve the system of equations, but I don't currently see a proof that these equations are linearly independent (I feel like this is really where the algorithm breaks down).

So now I'll give my counter-example: in a nutshell I'll construct an infinity family of monic, integer, coprime polynomials $g_m$ such that there are (at least) two monic integer polynomials $f_{-1}$ and $f_1$ such that $Res_x(f_1(x),g_m(x))=Res_x(f_{-1}(x),g_m(x))$ for all $m$. Thus, the resultants do not contain enough information to reconstruct $f$, no matter how long the algorithm takes.

Now for the details. First I'll assume that both $d$ and $e$ are even (I don't feel like this is a big restriction, but who knows?) [but I don't actually need $d>e$]. Define $g_m(x):=x^e-m^e$, for $m\in{2,3,\ldots}$. Clearly they are monic, integer, and coprime. Define $f_1=(x-1)^d$ and $f_{-1}=(x+1)^d$. Recall the formula for the resultant of monic polynomials (over the closure of whatever field we are working over):

$Res_x(P,Q)=\Pi_{(a,b):P(a)=Q(b)=0}(a-b)$

where the product is over roots, taken with multiplicity. So then

$Res_x(f_1,g_m)=\Pi_{j=1}^e (1-m\omega^j)^d$

where $\omega$ is a primitive $e$-root of unity (again, over the closure of the field). But as $d$ is even, this means that $-1$ is a $d$-root of unity so,

$=\Pi_{j=1}^e (1-m\omega^j)^d=\Pi_{j=1}^e (-(1-m\omega^j))^d=\Pi_{j=1}^e (-1+m\omega^j)^d$

and using $e$ is even, and thus that $-\omega$ is an $e$-th root iff $\omega$ is, we see that via reindexing

$=\Pi_{j=1}^e (-1-m\omega^j)^d=Res_x(f_{-1},g_m)$

so I've established the equality of the resultants, for any $m$. So clearly any algorithm that attempts reconstruction will fail, as it cannot distinguish between $f_{-1}$ and $f_{1}$.

Clearly, this result relies crucially on the fact that both $e$ and $d$ are even, but otherwise has no restriction. I feel like something could be done for cases when a small prime divides both $d$ and $e$, but at the moment this result seems sufficient for your purposes.

I suppose in a sense this counter-example "shows" that the "linearized" system you proposed cannot be invertible in general. It could be an interesting to ask for conditions for when the $g_m$ do form such an invertible system. However, as you say above, your $g_m$ are given you, so I'm not sure of a quick way to avoid this counter-example.

I hope that something is still recoverable for your application.

Answer by miforbes for Lower bounds for chromatic number of a graph

2010-07-30T08:51:16Z

Determining the chromatic number of an $n$-vertex graph is NP-Complete, and even approximating the chromatic number within an $NP^{1-\epsilon}$ ratio is $NP$-hard for every fixed $\epsilon>0$ (see http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity ). This means that assuming $ P\ne NP$ (which is consider a very reasonable conjecture by many in complexity theory) that no lower bound algorithm exists that is - general, as it works on all graphs - efficient, as it gives a lower bound in runtime polynomial in the size of the graph - good, as in it comes close to the true lower bound

So in a way, the best algorithm that computes a lower-bound efficiently is the trivial algorithm that always outputs 1 or 2 (as we can decide 2-colorability).

In of itself, that above isn't terrible for your purposes because in a sense all one needs for a lower-bound proof is a certificate that the given family of graphs has high chromatic number. However, assuming $NP\ne coNP$ (another plausible conjecture), there cannot be a proof system such that: - general, as it works for all graphs - small, in the sense that it is of size polynomial in the size of the graph - good, as for all graphs with chromatic number >=4 the proof system lower bounds the chromatic number likewise

(This last point follows from the fact that even determining if a graph is 3-colorable is $NP$-Complete.)

So in a sense, there can't be "general lower-bound technique" but rather only a collection of ad-hoc methods.

Answer by miforbes for Structure theorems for Turing-decidable languages?

2010-07-22T16:58:09Z

It should be noted that the idea of finding a "property" that can be used to show non-membership in a certain class of languages was a driving force in computability theory in the 1950's or so. Specifically, Emil Post posed the question: are there computably enumerable (aka "c.e.", also known as Turing-recognizable (but not necessarily decidable)) sets that are undecidable and strictly Turing-below the Halting problem (note that any c.e. set is Turing-below the halting problem). That is, we want a c.e. set A such that $\emptyset <_T A <_T H$, where $H$ is the halting problem. This became known as Post's Problem. Further, he proposed Post's Program, which was to find a property of c.e. sets that implied the required conditions, and then to find an A with this property. Examples of such candidate properties are being "simple" (its a technical term).

Post's problem was solved in the positive by Friedberg and Muchnik, but by using a clever sort of delayed diagonalization, a sort of "injury argument". However, this did not show that Post's program could be solved in the positive, but indeed Harrington and Soare showed in 1991 that there is such a property satisfying Post's conditions (and a corresponding set A satisfying this property).

See the wikipedia article: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem as well as the Harrington-Soare article explaining some of the background (its open-access): http://www.ncbi.nlm.nih.gov/pmc/articles/PMC52904/

Counting colored rook configurations in the cube - when is it even?

2010-03-06T01:57:47Z

Informal Statement

In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,k)$ if and only if $i+j+k=0\mod n$. In general, there are "many" ways to do this.

Each such "attack-free" rook position can be colored with $c$ colors. When we fix an $i$, we can then count the colors in the matrix $(i,.,.)$, and can do similarly for each $j$ and $k$. Call this set of tuples of colors-counts the "color profile". For each color profile, there is either an even or odd number of colored rook positions that achieve it. I want to know the largest $c$ such that all color profiles have an even number of colored rook positions achieving it. In particular, I want to say that $c=\omega(n)$. This question came up in some complexity theory research, but the question seems interesting in its own right.

Formal Statement

Define $[n]$ to be the set ${1,\ldots, n}$, and define $[n]^3=[n]\times[n]\times[n]$. Define a $c$-coloring of a set $S\subseteq[n]^3$ to be a function $C:S\to[c]$. We can say that this is a $c$-coloring of $[n]^3$ with the convention that $C(i,j,k)=0$ for $(i,j,k)\notin S$. A $c$-coloring $C$ induces a color profile $P$, which is a function from $P:[n]\times[3]\times[c]\to[n]$, via the rules

$P(i,1,c)$ is the number of $(j,k)\in[n]^2$ such that $C(i,j,k)=c$.
$P(j,2,c)$ is the number of $(i,k)\in[n]^2$ such that $C(i,j,k)=c$.
$P(k,3,c)$ is the number of $(i,j)\in[n]^2$ such that $C(i,j,k)=c$.

where we keep in mind the convention above on $(i,j,k)\notin S$.

Call a set $S\subseteq [n]^3$ to be a rook set, if

for all $i,j\in[n]$, there is exactly one $k\in[n]$ such that $(i,j,k)\in S$
for all $j,k\in[n]$, there is exactly one $i\in[n]$ such that $(i,j,k)\in S$
for all $i,k\in[n]$, there is exactly one $j\in[n]$ such that $(i,j,k)\in S$

Let a colored rook set $C_S$ correspond the coloring $C$ of a rook set $S$.

Define $N(P)$ to be the number of colored rook sets $C_S$ that induce the color profile $P$.

The question is:

For each fixed $n$, what is the largest $c$ such that for all color profiles $P$, $N(P)\equiv 0\mod 2$? In particular, is the largest $c$ asymptotically $\omega(n)$?

What I know

It should be clear that this problem can be defined analogously in any dimension, and I'm interested in this more general question. I state it with $d\ge3$ because I can solve the $d=2$ case exactly. In particular

For each $n$, for any $c\le n-1$, and any color profile $P$ on grid $[n]^2$, $N(P)\equiv 0 \mod 2$. For $c\ge n$, there are profiles $P$ where $N(P)\equiv 1\mod 2$.

This can be proven by exhibiting a bijection between colored rook sets (which in d=2 are just permutation matrices). Specifically, using the pigeonhole principle $c\le n-1$ implies that there are two rooks with the same color. If they were at positions $(i,j)$ and $(i',j')$, then we replace them with the rooks of the same color at positions $(i,j')$ and $(i',j)$. (Of course, one needs to make this well-defined to ensure a bijection.)

Possible Methods

I see two possible methods of proof

generalize the above bijection proof to the 3-dimensional case
- I don't know how to use the pigeonhole principle to get such an extension, but it seems possible that there is a method to show that some motif exists in any colored rook set, and then argue that we can alter this motif to get the bijection
define a system of polynomials (over $\mathbb{F}_2$) such that the solution set corresponds to exactly the colored rook sets inducing a color profile $P$. Then try to apply the Chevalley-Warning theorem.
- I've tried this, but can't seem to get systems of polynomials where the sum of the total degrees is strictly less than the number of variables, so the C-W theorem does not apply.
- One can observe the the C-W theorem is an "iff" here: if $N(P)$ is even then there is a multilinear polynomial with degree strictly less than the number of variables, such that the solution set encodes those $C_S$'s that induce $P$.
Instead of using "rook sets", one can ask the question for other classes of subsets of $[n]^3$. I'd be happy with establishing $c=\omega(n)$ for any class of subsets (although I'd like to be able to compute at least one example of such a subset efficiently).

Are there other methods for counting modulo two that I missed?

Comment by miforbes

2011-07-13T18:20:17Z

@mhum: Thanks, I had an inkling that MHW might be related to some coding theory problems, but was only aware of the NP-hardness of computing minimum distance. To summarize the proof by Berlekamp et al, they basically do a reduction from 3-Dimensional-Matching, which is essentially a restricted version of exact-cover. They avoid the need to make the family of sets subset closed because any matching must have a certain size, so even if a bunch of sets cover the entire ground set, it can only be a matching if it has the required number of elements.

Comment by miforbes

2011-07-12T00:22:00Z

Perhaps a title such as "The complexity of minimum distance in cayley graphs" would be more informative.

Comment by miforbes

2011-07-11T03:33:26Z

It's worth mentioning that determining permutation group membership is doable in polynomial time, as shown by Sims/Furst-Hopcroft-Luks (eg, see "Polynomial-time algorithms for permutation groups" by FHL).

Comment by miforbes

2011-07-11T03:31:52Z

An idea: Instead of considering full rank matrices, consider arbitrary matrices. In such a case, one can consider the following. Given a matrix M (in F_2) and a vector b, what is the minimum hamming weight of a vector x such that x^tM=b. I've convinced myself that a progress argument shows that this is equivalent to asking for the number of row operations needed to transform M with a zero row at the bottom into M with a row b at the bottom. This hamming-weight problem seems related to known problems such as set-cover (but one needs to be careful over F_2 (or even Z)).

Comment by miforbes

2010-09-10T05:28:04Z

Deutsch-Jozsa is very much a query problem, and as such always feels too unnatural to try to motivate over a dinner with friends (which is approximately my target audience).

Comment by miforbes

2010-09-10T05:25:58Z

As I commented below, I don't like the max-cut/vertex-cover results because they aren't too much harder than the derandomized versions. But I do really like Anup's directed connectivity story, and it plays nicely with the SL=L result of Reingold. Of course, it doesn't have an easily-explained correctness proof, but it is a nice story at least (about steady-state distributions, etc). Still hoping for a better answer though ...

Comment by miforbes

2010-09-10T05:23:08Z

I know I'm being picky here, but I suppose I'm looking for an algorithm to solve a problem exactly. But further, I don't consider the "derandomized" 2-approximation algorithm for max-cut to be non-trivial - it is just a greedy/conditional-expectation result. (also, the randomized algorithm shows existence apriori, and to get efficiency we need a Markov-type result; not hard but not easily to explain to a layperson)

Comment by miforbes

2010-09-10T05:20:01Z

@Steve,Ricky,David: I don't consider polynomial identity testing to be a natural problem for the layperson. While I don't dispute its theoretical interest (and indeed, am interested in it myself), it is harder to digest for people not too familiar with polynomials. I think PIT really becomes interesting on a practical level when it is used to solve another problem (such as matchings) but at that point the explanation of encodings is too hard.

Comment by miforbes

2010-09-10T05:15:17Z

@Thierry-Zell: I like to tell lots of different people about theoretical-computer-science (it being my field). I don't expect a full proof to be convincing in conversation, but it should at least be intuitive enough to be graspable. For example, the P vs NP question can be phrased as asking whether finding a needle in a haystack requires searching the entire haystack, while the P vs RP question can be phrased similarly: we have a haystack with some needles, but now we need to find the hay. I like this motivation and am hoping for a correctness proof in this vein for a natural algo.

Comment by miforbes

2010-09-10T05:10:36Z

@steve-huntsman: That primality-testing is now known to reside in polynomial time is not a concern for me with respect to this question: this result was open for a while and so in some respects is still "open" for a layperson.

Comment by miforbes

2010-08-05T04:55:06Z

@Gerry: I agree. Perhaps something is recoverable if we require the $g_i$ to have roots of a "sufficiently different" character? I can't formalize this at the moment, but the counter-example relies on all of the $g_i$ to be essentially similar. Suppose, for concreteness we think of the roots as lying in the complex plane. One can consider the "patterns" formed by the convex hulls of the roots of the $g_i$. Somehow I imagine that if the convex hulls were pairwise disjoint then recovery should be possible - perhaps even efficient. In some sense I'm thinking of "triangulating" the polynomial.

Comment by miforbes

2010-08-05T04:47:29Z

I'm sorry for such discouraging news; again I hope that is something is still recoverable ...

Comment by miforbes

2010-08-01T17:59:38Z

@Gerry: Indeed; I'll have to admit I was somewhat surprised by the result. That is, I was expecting successful recovery (albeit with a strong lower bound on the number of resultants needed) upon first reading the question.

Comment by miforbes

2010-08-01T10:38:50Z

That it is an interesting possibility, but I feel like the above counter-example should be generalizable to a situation where the number of finite possibilities is rather large. But even in this case, I'm not sure how one would find the finite number of possibilities, as clearly any linear system as either a unique solution or an infinite number (over an infinite field). Also, I'm not sure if this would be sufficient for the application at hand.

Comment by miforbes

2010-07-31T14:31:38Z

Thanks, I am aware of Papadimitriou's various inefficient proofs of existence, but I consider these more of a brute-force type of proof in the sense that the algorithms themselves don't really establish the existence of the desired object - it is the various lemmas (parity, etc) that he uses to establish the existence. The algorithms sort of fall out in a trivial way. Though, perhaps it isn't a meaningful distinction.