User mhum - MathOverflow

Answer by mhum for P vs NP and OWFS

2011-10-20T04:22:51Z

P != NP does not imply anything about the existence of one-way functions. From Goldwasser and Bellare's "Lecture Notes on Cryptography":

However, the above mentioned necessary condition (e.g.: P != NP) is not a sufficient one. P != NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct "encryption schemes" for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worse-case hardness is a poor measure of security.

Also, two of Impagliazzo's worlds where P != NP, Heuristica and Pessiland, have no one-way functions while two others, Minicrypt and Cryptomania, do.

Answer by mhum for What is so "plactic" about the plactic monoid?

2011-09-26T07:50:41Z

You can find the original Lascoux & Schützenberger paper here. My French (especially mathematical French) is not great, so I haven't been able to determine how the term "plaxique" comes in. However, I can observe that L&S first introduce la congruence plaxique and define le monoïde plaxique as the quotient of the free monoid over the congruence. So, it seems to me that they were really thinking of the congruence as plactic/plaxic more than the monoid itself (perhaps a fine distinction?). They highlight the relevant properties of the congruence in Proposition 2.5, so maybe that provides a clue?

EDITED TO ADD: A quick scan of the OED yields no results for either "plactic" or "plaxic", but there is one result for the Latin "plaxus" under the etymology for the obsolete word "plash" (To bend down and interweave (stems partly cut through, branches, and twigs) so as to form a hedge or fence.):

an unattested post-classical Latin form *plaxus , alteration of classical Latin plexus , past participle of plectere to plait, interweave, twine (see plexus n.)

So, perhaps "plaxique" is meant to invoke a sense of intertwining or weaving? I could see how that could apply to the congruence relation.

Bonus fun fact: Plaxico Burress makes an appearance in the OED in a citation for the entry "return date":

New York Giants star receiver and gun nut Plaxico Burress breezed in and out of Manhattan Criminal Court in 15 minutes yesterday, with little happening besides the setting of a June 15 return date.

Answer by mhum for Titles composed entirely of math symbols

2011-07-11T07:23:39Z

Would IP=PSPACE count?

Answer by mhum for Why semigroups could be important?

2011-02-18T18:49:13Z

Semigroups provide a fundamental, algebraic tool in the analysis of regular languages and finite automata. This book chapter (pdf) by J-E Pin gives a brief overview of this area.

Answer by mhum for Hubbiness of a graph

2010-10-21T20:54:35Z

Here are some concepts that might be helpful to you:

A vertex $v$ of a connected graph $G$ is an articulation point if the removal of $v$ from $G$ causes $G$ to be disconnected. My interpretation is that an articulation point corresponds to a "hub". This may or may not match your intuition. On the one hand, the center vertex in a star is an articulation point, but then so is any interior point in a path.
A connected graph $G$ is biconnected if it does not contain any articulation points (i.e.: the removal of any single vertex from $G$ does not disconnect $G$). By convention, the graph consisting of just two vertices and one edge is considered biconnected.
A biconnected component of a graph $G$ is a maximal, biconnected subgraph.
Finally, we can define the block tree $BT(G)$ of a connected graph $G$ as follows: The vertices of $BT(G)$ are the biconnected components of $G$ and an edge $(u,v)$ exists in $BT(G)$ iff the biconnected components corresponding to $u$ and $v$ share a vertex (in $G$). This Wikipedia article has a nice illustration of this concept and a description of an algorithm for constructing the block tree.

I would suggest that the degree of "hubbiness" of a graph $G$ is related to the size of $BT(G)$. Let $G$ be a graph with $n$ vertices. Then:

If $G$ is biconnected, then $|BT(G)| = 1$
If $G$ is a star, then $|BT(G)| = n$
If $G$ is a path, then $|BT(G)| = n-2$
In general, if $G$ is a tree, then$|BT(G)|$ equals the number of interior vertices

Answer by mhum for number of muti-indices of a fixed order which are less than a given multi-index

2011-01-21T19:54:51Z

Expanding my comment into a full answer:

By inspection, we can see that $C(n,s,p)$ is the coefficient of $x^s$ in:

$(1 + x + x^2 + \cdots + x^{p_1}) (1 + x + x^2 + \cdots + x^{p_2}) \cdots (1 + x + x^2 + \cdots + x^{p_n})$

$= \Pi_{j=1}^n \Sigma_{i=0}^{p_j} x^i $

$= \Pi_{j=1}^n {{(x^{p_j+1}-1)}\over{(x-1)}}$

I'm not particularly expert at generating functions, so I haven't been able to reduce this to a more pleasing (closed-form) expression. Perhaps more time studying Wilf's generatingfunctionology will yield better results.

The asker also mentions the special case where the $k \leq p$ constraint is ignored (which is equivalent to the situation when $p_i \geq s$ for all $i$). In this case, we can get a better formula. Let $C(n,s)$ denote the desired quantity.

First, we recall the definition of the composition of an integer. Next, we observe that there are ${s-1}\choose{i-1}$ compositions of $s$ into $i$ (non-zero) parts and that there are ${n}\choose{i}$ ways to distribute these $i$ parts into the $n$ indices (we let the other $n-i$ indices be zero). Thus, we have $$C(n,s) = \Sigma_{i=1}^{min(n,s)} {{s-1}\choose{i-1}} {{n}\choose{i}}$$

Answer by mhum for Is pattern recognition NP-complete?

2010-12-14T03:05:12Z

The key phrase you are looking for is "resource-bounded Kolmogorov complexity". This paper by Allender, et. al. may be a good starting point. Also, this PhD thesis might provide some helpful background.

Edited to add:

According to the first article, Ko, K.-I. "On the complexity of learning minimum time-bounded Turing machines", SIAM Journal on Computing, 20 (1991) may be even more relevant. In that paper, Ko demonstrates that determining whether or not computing time-bounded Kolmogorov complexity is NP-hard requires non-relativizing techniques.

Answer by mhum for How can you compute the number of topological sorts in a DAG?

2010-11-12T23:36:48Z

This problem is #P-complete. See "Counting linear extensions is #P-complete", G. Brightwell and P. Winkler, Proc. 23rd ACM Symposium on the Theory of Computing, 1991

Answer by mhum for How do I approach Optimal Control?

2010-10-28T22:51:53Z

One potential tactic would be start with Estimation Theory rather than Control Theory. I've enjoyed the approach taken in H. Vincent Poor's An Introduction to Signal Detection and Estimation.

Answer by mhum for How to solve a generalization of the Coupon Collector's problem

2010-10-12T21:40:48Z

Perhaps this is naive, but shouldn't the expected number of trials be $M/m * T$ where $T$ is the expected number of trials when $M = m$ (i.e.: in the case worked out by Newmann & Shepp)? If half the coupons are useless to you, wouldn't it just take twice as long to collect the ones you wanted?

Answer by mhum for Generating Unique Combinations from a list of possible repeated characters

2010-10-06T17:35:48Z

Suppose that your list contains $k$ distinct characters and the $i^{th}$ character appears $n_i$ times, for $1 \leq i \leq k$. Then, each combination corresponds to a vector of integers $(x_1, x_2, \ldots, x_k)$ where $0 \leq x_i \leq n_i$.

Comment by mhum

2013-05-07T15:19:33Z

I stand corrected. The approximation ratios for Set Cover do appear to be independent of the number of sets. I'm not sure why I thought otherwise.

Comment by mhum

2013-05-06T23:11:18Z

If I understand your objection correctly, I think this issue may be resolved by observing that the problem size of Set Cover is related to the size of the universe set and all the subsets. The subsets constitute part of the input for Set Cover.

Comment by mhum

2012-01-31T21:14:32Z

@spanferkel: Ah. Understood. I misread.

Comment by mhum

2012-01-31T19:39:58Z

@spanferkel: is the complement of $2nK_3$ the same as the complete tri-partitite graph $K_{2n, 2n, 2n}$?

Comment by mhum

2011-11-01T23:03:20Z

@Valerio Caprano: In property one, do you require that $[x,y]$ is non-empty for all $x,y$? If not, you could take $\Gamma = E$ for any $X = (V,E)$ which will satisfy properties one through three. I don't have a sense of what contractibility might mean in the case of graphs.

Comment by mhum

2011-11-01T21:52:20Z

I am mistaken. It turns out not to be the case that $\Gamma$ forms a tree. Consider $X$ to be a triangle with $\Gamma$ equal to the three edges.

Comment by mhum

2011-11-01T18:40:52Z

Ah, okay. In that case, would that imply that the union of all paths in $\Gamma$ forms a tree inside of $X$? Maybe I am still confused?

Comment by mhum

2011-11-01T17:50:14Z

I may have misunderstood your definition, but it seems to me that the first property implies that there is a unique path between any two vertices. If that is the case, then X is a tree, extremal vertices appear to be leaves in the tree, and the second property seems to imply that the graph is just a path.

Comment by mhum

2011-10-21T01:28:16Z

Maybe the asker is thinking of the specific case where $r(f,2^n) = n^2$?

Comment by mhum

2011-10-20T20:54:48Z

I guess the unspoken assumption which should be spoken is "given our current knowledge". That is to say, as far as I know, we do not yet have any additional results that when combined with $P \neq NP$ implies either the existence or non-existence of one-way functions. Results in this line of investigation would likely be very interesting.

Comment by mhum

2011-10-20T20:05:22Z

Perhaps it is more accurate to say that $P\neq NP$ alone does not imply the existence of one-way functions? Or, that $P\neq NP$ is consistent with the existence of one-way functions and also consistent with the non-existence of one-way functions? My understanding is that the exact manner in which $P\neq NP$ determines the existence of one-way functions. Roughly, if NP problems are hard only in the worst-case but easy on average (for appropriate definitions of hard, easy, and average), OWF don't exist; if NP problems are hard on average, OWF may (but are not guaranteed to) exist.

Comment by mhum

2011-08-06T00:32:46Z

Counting antichains in a partial order is #P-complete according to the abstract for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected", SIAM J. Comput. 12 (1983), 777-788 (epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/…).

Comment by mhum

2011-07-26T06:49:38Z

Does anything nice happen to the horrible-looking formula if $a_1 = a_2 = \ldots = a_m$?

Comment by mhum

2011-07-13T08:11:26Z

You can also find a proof that MHW is NP-complete in "On the Inherent Intractability of Certain Coding Problems" (1978) by Berlekamp, et al. authors.library.caltech.edu/5607/1/…

Comment by mhum

2011-06-23T04:16:44Z

@sarannmr: If you do not accept the existence of the non-computable, then you must also reject the existence of uncountable things. Without the uncountable, you do not have the real numbers, only the rationals. This rejection is apparently also a feature of intuitionism (en.wikipedia.org/wiki/Intuitionism). Maybe worth a look?