A game on several graphs Consider the following game on a directed weighted graph $G$ with a chip at some node.

All nodes of $G$ are marked by A or B.

There are two players Alice and Bob. The goal of Alice (Bob) is to shift the chip to a node that marked by A (B).

Initially Alice and Bob have $m_A$ and $m_B$ dollars respectively.

If a player is in a losing position (i.e., current position of the chip is marked by opposite letter) he or she can move the chip to a neighboring node. Such move costs some dollars (the weight of the corresponding edge).

The player loses if he or she is in a losing position and has not money to fix it.

Now consider the language GAME that consists of all directed weighted graphs $G$ (all weights are positive integers), initial position of the chip, and capitals of Alice and Bob that are given in the unary representation

such that Alice has a wining strategy at this game.

The language GAME belongs to P. Indeed, the current position of the game is defined by the position of the chip and the current capitals of Alice and Bob, so dynamic programming works (here it is important that initial capitals are given in the unary representation).

Now consider the following generalization of this game. Consider several directed weighted graphs $G_1, \ldots G_n$ with a chip at each graph. All nodes of all graphs are marked by A and B. Now Bob wins if all chips are marked by B and Alice wins  if at least one chip marked by A.

Consider the language MULTI-GAME that consists of all graphs $G_1, \ldots, G_n$, initial positions and capitals $m_A$ and $m_B$ (in the unary representation) such that Alice wins at the corresponding game.  Here it is important that capitals are common for all graphs so, it is not just several independent GAMEs.

Question What is the complexity of the language MULTI-GAMES? (Is it also belongs to P or there are some reasons to thing that this problem is hard?)

UPD1 Neal Young suggested to use Conway's theory. However I do not know is it possible to use this theory for several games with common capital.

UPD2 I want to show an example that shows that MULTI-GAME is not very simple.  Let Alice split her capital $m_A$ to some $n$ terms $m_A = a_1 + a_2 + \ldots a_n$ (She is going to use $a_i$ dollars for $i$-th graph). Define $b_i$ as the minimal number such that in $i$-th game Bob wins if Alice and Bob have $a_i$ and $b_i$ dollars respectively. If $b_1 + \ldots b_n > m_B$ (for  some spliting $m_A = a_1 + a_2 + \ldots a_n$) then Alice wins. However, the opposite is not true. Consider two copies of the following graph (initially the chip is at the left up A):

For one graph Bob wins if $m_A=0$ and $m_B=2$ or if $m_A=1$ and $m_B=3$.
However for the game with two copies of this graph Bob loses if $m_A=1$ and $m_B=5$. Indeed, Bob have to spend $4$ or $5$ dollars to shift both chips to a node marked by $B$. Then Alice can shift at least one chip to a node marked by A. After that Bob have not money to save his position.

UPD3 Since the question for arbitrary graphs seems difficult consider specific graphs. Denote the nodes of some graph $G_i$ as $1, \ldots k$. My restriction is the following: for every pair $i<j$ there exists edge from $i$ to $j$ and there is no the reverse edge. Also there exists a restriction for the costs of edges: for $i<j<k$ the edge $j$ to $k$ is not greater than from $i$ to $k$.

Since Steven Stadnicki's answer doesn't appear to have been accepted by the asker, I figured it may still be helpful to provide an update: I have a reduction from 3SAT to MULTI-GAME. I haven't looked at Steven's answer carefully or followed through the link he provided, but based on the following reduction I won't be surprised if MULTI-GAME is indeed PSPACE-complete. I might not bother extending this result beyond NP-hardness, however.

A 3SAT instance consists of clauses $C_1, \dots, C_m$, each clause being of the form $C_i = L_{i1} \vee L_{i2} \vee L_{i3}$ where each $L_{ik}$ is either one of the variables $x_1, \dots, x_n$ or the negation of one of the variables.

Given such a 3SAT instance, the reduction creates a MULTI-GAME instance consisting of $n + 1$ games -- one for each variable and another game used as an excess capital sink. First we'll define the structure of the graphs for each game, then look at an example and discuss the core idea, and then we'll figure out what exact costs to assign to the edges to make the reduction hold firm.

First, the variable game graph $G_j$ for each variable $x_j$:

Create vertex labeled $x_j$ marked with an A (i.e. a winning vertex for Alice). The chip for $G_j$ starts on vertex $x_j$.
Create a vertex labeled $T$ and a vertex labeled $F$, each marked with a B (i.e. both are winning positions for Bob). Create directed edges from $x_j$ to both $T$ and $F$, both with costs of $1$.
For each literal $L_{ik}$ of clause $C_i$, if $L_{ik} = x_j$ or $L_{ik} = \neg x_j$, create vertices labeled $C_iTA$ and $C_iFA$ marked with A and vertices labeled $C_iTB$ and $C_iFB$ marked with B. Add edges $(T, C_iTA)$ and $(F, C_iFA)$ with costs both set to $l_{ik}$. (We'll define $l_{ik}$ later.)

Add edges $(C_iTA, C_iTB)$ and $(C_iTA, C_iTB)$. If $L_{ik} = x_j$, then set $(C_iTA, C_iTB)$'s cost to $l_{ik} - 1$ and $(C_iTA, C_iTB)$'s cost to $l_{ik}$. Otherwise set $(C_iTA, C_iTB)$'s cost to $l_{ik}$ and $(C_iTA, C_iTB)$'s cost to $l_{ik} - 1$.

The capital sink game:

Create a vertex labeled $C$, marked with B.
For each clause $C_i$, create a vertex labeled $C_iA$ marked with A, and a vertex labeled $C_iB$ marked with B. Create an edge $(C, C_iA)$ with edge cost $c_i$ (again to be determined below), and an edge $(C_iA, C_iB)$ also with edge cost $c_i$.

This is a lot to take in, so hopefully an example makes this a little more digestible. Our 3SAT instance is as follows:

$C_1 = x_1 \vee x_2 \vee \neg x_3$

$C_2 = x_2 \vee x_3 \vee \neg x_4$

$C_3 = \neg x_1 \vee \neg x_3 \vee x_4$

The reduction turns this instance into 4 variable game graphs and 1 capital sink graph. In the diagrams below, the red vertices are marked with A (i.e. are winning positions for Alice), and the cyan vertices are marked with B (are winning positions for Bob).

Graph for $x_1$:

Graph for $x_2$:

Graph for $x_3$:

Graph for $x_4$:

Graph for capital sink:

The idea is as follows:

Bob is forced to make the first $n$ moves in order to get out of losing positions in the $n$ variable games. Each such move encodes an assignment of true or false to the corresponding variable.

Alice will then have enough capital to make exactly 4 moves, each of which Bob will need to have enough capital to match in order for Bob to win. The $c_i$ values and the $l_{ik}$ values are to be chosen so that Alice's only possible winning strategy is as follows, for some clause $C_i$:

  Alice's clause $C_i$ strategy: let $C_i = L_{i1} \vee L_{i2} \vee L_{i3}$. For each $k \in \{1, 2, 3\}$, if $L_{ik} = x_j$ or $\neg x_j$, move to $C_i?A$ in the variable game for $x_j$. Also move to $C_iA$ in the capital sink game.

($C_i?A$ denotes either $C_iTA$ or $C_iFA$, only one of which is reachable in a given variable game after Bob's opening moves.)

If Bob's opening corresponds to a truth assignment that leaves some clause $C_i$ unsatisfied, then Alice choosing $C_i$ and implementing the strategy above costs Alice $l_{i1} + l_{i2} + l_{i3} + c_i$ capital to implement, and Bob the same to beat; if on the other hand $C_i$ is satisfied, then Bob's counterplay gets a discount of at least $1$. Our goal in setting the $c_i$ and $l_{ik}$ values and Alice and Bob's starting capitals is to ensure that said discount is the deciding factor in whether Alice or Bob wins.

To that end, set $b = m + 1$, and set

$l_{ik} = 2b^{10} + ib^{2k}$ for each $k \in \{1, 2, 3\}$,

$c_i = 3b^{10} + b^8 - \sum_{k=1}^3 ib^{2k}$,

Alice's starting capital to $9b^{10} + b^8$,

and Bob's starting capital to $9b^{10} + b^8 + n - 1.$

Note that all of these values are polynomial in $m$, so the MULTI-GAME instance outputted by the reduction has size polynomial in the size of the 3SAT instance even if these costs are encoded in unary.

Note also that for each clause $C_i$, $l_{i1} + l_{i2} + l_{i3} + c_i = 9b^{10} + b^8$ is Alice's starting capital. (Which is also $1$ greater than Bob's capital after making the first $n$ moves.)

First of all, it is immediately clear that if Bob's opening defines a truth assignment that leaves a clause $C_i$ unsatisfied, then Alice wins using her clause $C_i$ strategy given above.

If Bob's opening satisies all clauses, we can argue constraints on Alice's options which rule out any other possibility of Alice winning. Note that the order in which Alice makes her moves is irrelevant, as Bob's responses are forced and the total capital Bob will require to respond to Alice's moves is unchanged by the order of Alice's moves.

Alice can't make more than 4 moves: if Alice makes 5 or more moves, then her moves have a total cost of $\ge 5b^{10}$, which exceeds her budget.
Alice must make 4 moves: if Alice selects 3 moves from the capital sink game then her total cost is $\ge 9b^{10} + 3b^8 - 3b^7 > 9b^{10} + 2b^8$ which is over budget. If she selects even one move of 3 from a variable game, then her total cost is $\le 8b^{10} + 2b^8 + b^7$ which is is substantially less than Bob's post-opening capital, so Bob can easily afford the counterplay.
Alice must select a move from the capital sink game: if she doesn't, then she selects 4 moves from variable games, with total cost $\le 8b^{10} + 4b^7$, and again Bob can easily afford the counterplay. (Note that if there were a separate capital sink game per clause, we could even show that Alice must play in exactly one such game.)

From this stage we can disregard the $b^{10}$ and $b^8$ terms in the move costs chosen, as they will always sum to $9b^{10} + b^8$.
Since Alice must choose exactly one move in the capital sink game, assume that move is to $C_iA$. Then Alice has (ignoring $b^{10}$ and $b^8$ terms) $\sum_{k=1}^3 ib^{2k}$ capital remaining, and Bob has $1$ less than this amount remaining.

Alice must select at least one move costing $l_{j3}$ for some clause $C_j$: if she doesn't, then her moves cost (again lower-order terms) $\le 3b^5$, and Bob has more than enough capital for counterplay.
Said move costing $l_{j3}$ must be the move costing $l_{i3}$: it can't be a move costing $l_{j3}$ for $j > i$, otherwise this move alone costs $\ge (i+1)b^6$ which is greater than Alice's remaining budget. If it's $l_{j3}$ for $j < i$, then the $l_{(i - j)3}$ cost move must also be chosen by Alice to exhaust the $b^6$-order term in Bob's remaining budget. But then Either the $b^2$-order term in Bob's remaining budget or the $b^2$-order term doesn't get exhausted, so Bob wins handily.

Similar arguments should establish that Alice must select the moves costing $l_{i2}$ and $l_{i1}$. If Bob's truth assignment satisfies $C_i$, then even this strategy doesn't work, as the discount Bob gets on one of the $l_{ik}$-based costs makes up for the $1$ less capital he has after his opening.

A remark on my previous answer: it's obvious in hindsight that, for the TABLE-GAME variant of MULTI-GAME I defined in the comments of that answer, a knapsack-style DP suffices to determine which player has a winning strategy. You can argue that Bob's best strategy is to always respond to a losing state in a given game table with the minimal investment possible (this can't cut off a subsequent move for Bob that he would have otherwise), and from there that the order of Alice's moves doesn't matter. It then becomes a matter of choosing a split of Alice's capital among the games such that the sum of Bob's minimal winning responses over those games exceeds his budget, which can be reframed as a knapsack-style problem, which has a polynomial-time DP due to the unary representation of costs. (My recurrence actually would've worked for TABLE-GAME if I framed it in terms of Alice.)

It turns out that even a simple tree structure for each game, with constant depth and really only one meaningful fork per game (namely those at the start which force Bob to choose a truth assignment) is sufficient to get NP-hardness. I had some ideas for getting rid of that initial fork, which stalled out at somehow forcing Bob to invest a relatively large fixed amount of capital in $n$ games without Alice having to precommit to those games in advance, but obviously since TABLE-GAME is in P this is not possible without the fork.

I haven't thought much about your special case from UPD3. I suspect it's also NP-hard, for the reason that my variable gadgets seem at a glance like they may be adaptable to those constraints, but I probably won't look into it further.


BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP I read the paper

Ahmed Younes, "A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems", 2015. doi:10.1007/s11128-015-1069-y

which is published in Springer's journal Quantum Information Processing.
The paper seems to claim that it provides
a BQP algorithm for the NP-hard problems of min-bisection and max-bisection.

If true, this should imply that $NP\subseteq BQP$,
which would be very surprising because it is common conjecture that
$NP\not\subseteq BQP$.
There is even a result that relative to an random oracle,
$NP\nsubseteq BQP$ with probability 1.

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani,
"Strengths and Weaknesses of Quantum Computing", 1997. doi: 10.1137/S0097539796300933

I'm puzzled because it seems to me that
the complexity analysis of the paper
concerns query complexity not time complexity.
In other words,
it is not clear the algorithm is in BQP.
On the other, the implications of the paper
should have been clear to any reviewer
in quantum computing so
I expect that the reviewers really checked
all the details of the paper to confirm the result
otherwise it wouldn't be published.

Is the algorithm in the paper really in BQP?
Does the paper really imply that NP $\subseteq$ BQP?

Ahmed Younes, Jonathan E. Rowe, "A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability", 2015

Another paper with the same idea by Ahmed Younes and Jonathan E. Rowe, A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability. The algorithm is not polynomial time.


Alternatives to Diffie Hellman Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem that will facilitate computationally secure key exchange?

The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few nonabelian and infinite abelian ones), so they get very close to the spirit of the question you are asking. The learning with errors problem mentioned by one of the commenters is on that list.

I do not know of a general answer to the question of "What is the power of DL in arbitrary (that is, nonabelian) groups?".


Counting sum of parities of cycle covers in cubic, planar, bipartite graphs Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and let $c_0,c_1,c_2$ be respectively the number of cycles in $M_1\cup M_2, M_2\cup M_0, M_0\cup M_1$ respectively.

Is $c_0 + c_1 + c_2 \equiv 0 \bmod{2}$? If yes, what is the proof? If not, a counterexample?

Small examples such as a cube or two concentric hexagons with $6$ cross edges etc. seem to point towards the first possibility but I am not sure either way.

Any references will be greatly appreciated!

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$

Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$

To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$

Define $f: S_n \to \{0, 1\}$ such that $f(\sigma) = 0$ iff $\sigma$ is an even permutation, and define $c: S_n \to \mathbb{N}$ so that $c(\sigma)$ is the number of cycles in $\sigma.$ We know that $c(\sigma) \equiv n-f(\sigma) \pmod{2}.$

Now, it is direct to see that the number of cycles in $M_i \cup M_j$ is simply $c(\sigma_j^{-1}\sigma_i) \equiv n-f(\sigma_j^{-1})-f(\sigma_i) \equiv n-f(\sigma_j)-f(\sigma_i) \pmod{2}.$ Summing gives us that $$c_1+c_2+c_3 \equiv 3n-2f(\sigma_1)-2f(\sigma_2)-2f(\sigma_3) \equiv n \pmod{2}$$ as claimed.

So you question really is: are there planar cubic graphs with an odd number of vertices on each side of the bipartition? At this point it's not hard to draw out an explicit counterexample; I'll give a sketch of how to find one.

Make 3 hexagons, so that $G$ would have $9$ vertices on both sides of its bipartition. Now, we have to add 9 more edges, 3 between each pair of hexagons that preserves the graph being bipartite and is planar. It isn't hard to just draw 9 such edges by hand. Ask if you are still having trouble, I can explicitly describe the graph then.


PTAS for a variant of multiple knapsack? I am interested in the following variant of multiple knapsack. There are $n$ items with values $v_1,\ldots,v_n$. We want to partition the items into $m$ subsets $S_1,\ldots,S_m$ to maximize $\min_{j\in\{1,\ldots,m\}}\sum_{i\in S_j} v_i$. In words, we want to assign the items to $m$ bins to maximize the minimum total value in any bin.

The problem is clearly NP-hard even for the case of two bins; it is essentially the PARTITION problem. However, SUBSET-SUM has an FPTAS and many generalizations of SUBSET-SUM and KNAPSACK have a PTAS; there are so many of them, though... Is there a generalization of these problems that is known to have a PTAS and captures my problem? (On the other hand, the problem is a special case of the Santa Claus problem [Bansal and Sviridenko, STOC'06], which seems to be quite hard to approximate.)

If I'm not mistaken, in the introduction of Bansal and Sviridenko, they mention that your special case - where children value items equally aka jobs take the same time on all machines - was the topic of Woeginger (1994) and shown to have a PTAS. Woeginger also points out that the problem is strongly NP-hard and hence does not permit an FPTAS unless P=NP.

Note however that if the number of bins $m$ is fixed rather than being part of the input, then the usual discretization method used for Knapsack and others, where items are rounded to powers of $(1+\epsilon/n)$, seems to yield an FPTAS.


Different definitions of grammar complexity It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L_0 \supseteq L$), production complexity (minimal possible $|P|$ for grammar $(N, \Sigma, P, S)$ generating $L$)... What are other kinds of grammar complexity studied in literature? How these complexities depend on each other?

I think that among the most obvious measures are variable and production complexity. These are structural measures, in the sense there is for each k an infinitude of languages having measure k. And they are independent from each other, unless you consider the numbers for grammars in Chomsky normal form.
Another obvious measure is the total size of the grammar. Here you can compare required size in various normal forms, for example. It's also the thing to look at for grammar  based compression. This measure is less a structural measure, but more a descriptional complexity measure. The textbook by M. Harrison on formal language theory (1978) has some coverage in chapter 4 of the early works on this by J. Gruska and others.
Here are a few pointers to the recent literature. I'm not aware of recent surveys, but maybe look at the cited references.
Jürgen Dassow, Ronny Harbich:
Production Complexity of Some Operations on Context-Free Languages. DCFS 2012: 141-154
Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid: On the Complexity of Grammar-Based Compression over Fixed Alphabets. ICALP 2016: 122:1-122:14
Stefan Hetzl, Simon Wolfsteiner:
On the cover complexity of finite languages. Theor. Comput. Sci. 798: 109-125 (2019)
EDIT (05/04/2021): An observation regarding the relation between number of variables and productions in context-free grammars: the left-hand side of every production from $P$ is a variable from $V$, so $|P|\ge |V|$, provided we assume (w.l.o.g.) that every variable is used in at least one production. Every finite language can be generated by a context-free grammar with just one variable (the start symbol), and with one production for each word – of which there are finitely many. On the other hand, there are finite languages for which the minimum number of productions required by any context-free grammar equals the number of words in the language (by work of Bucher, Maurer, Culik, Wotschke). This shows that the "production hierarchy" is more fine-grained than the "variable hierarchy".


What is the difference between unification and anti-unification? I understand that in Unification we try to find a general solution to an equation between two terms, but what is anti-unification, and how is it different?

The following category theory inspired analysis (adapted from Plotkin's A Note on Inductive Generalization) explains a sense in which unification and anti-unification are dual concepts. As notation, let's write
$$t \underset{\sigma}{\Longrightarrow} u$$
for two terms $t$ and $u$ and a substitution $\sigma$ whenever $t\sigma = u$.  The existence of such a subsitution $\sigma$ implies that $t$ is a generalization of $u$, and that $u$ is a specialization of $t$.

Suppose given two terms $t_1,t_2$.  A unifier of $t_1$ and $t_2$ is a term $u$ together with a pair of substitutions $\sigma_1$ and $\sigma_2$ such that
$$
t_1 \underset{\sigma_1}{\Longrightarrow} u \underset{\sigma_2}{\Longleftarrow} t_2
$$
It is a most general unifier if it is a generalization of any other unifier, that is, if for any other unifier
$$
t_1 \underset{\sigma_1'}{\Longrightarrow} u' \underset{\sigma_2'}{\Longleftarrow} t_2
$$
there is some $\sigma'$ such that
$$
u \underset{\sigma'}{\Longrightarrow} u'
$$
In other words, a most general unifier is precisely a coproduct in the category $\mathcal{C}$ whose objects are terms and where there is a morphism $t \to u$ just in case $t \underset{\sigma}{\Longrightarrow} u$ for some $\sigma$.

To define anti-unification we just reverse all the arrows!  Which is to say that...

An anti-unifier of $t_1$ and $t_2$ is a term $u$ together with a pair of substitutions $\sigma_1$ and $\sigma_2$ such that
$$
t_1 \underset{\sigma_1}{\Longleftarrow} u \underset{\sigma_2}{\Longrightarrow} t_2
$$
It is a least general anti-unifier if it is a specialization of any other anti-unifier, that is, if for any other anti-unifier
$$
t_1 \underset{\sigma_1'}{\Longleftarrow} u' \underset{\sigma_2'}{\Longrightarrow} t_2
$$
there is some $\sigma'$ such that
$$
u' \underset{\sigma'}{\Longrightarrow} u
$$
This means that a least general anti-unifier is precisely a product in the category $\mathcal{C}$ defined above.

Update: fixed the accidentally dualized terminology in the original description (thanks Yann Hamdaoui!).


High probability events without low probability coordinates Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small constant $\delta$. Let $E \subseteq \rm{Supp}(X)$ be an event in the support of $X$ such that $\Pr[X \in E] \ge 1 - \varepsilon$, where $\varepsilon$ is an arbitrarily small constant.

We say that a pair $(i,\sigma)$ is a low probability coordinate of $E$ if $\Pr[X \in E | X_i = \sigma] \le \varepsilon$. We say that a string $x \in \Sigma^n$ contains a low probability coordinate of $E$ if $(i, x_i)$ is a low probability coordinate of $E$ for some $i$.

In general, some strings in $E$ may contain low probability coordinates of $E$. The question is can we always find a high probability event $E' \subseteq E$ such that no string in $E'$ contains a low probability coordinate of $E'$ (and not of $E$).

Thanks!

How does $\epsilon$ compare to $n$? If $\epsilon$ can be $O(1/\sqrt{n})$, then I think we can accomplish what you want. Let $B = \mbox{Supp}(X) - E$. Note that $B$ is given $\epsilon$ probability mass under $X$. Let $\lambda(i,\sigma)\epsilon$ denote the probability mass assigned to strings in $B$ such that the $i$th coordinate has symbol $\sigma$.

Suppose $(i,\sigma)$ were a low probability coordinate for some strings in $E$. Let $\delta(i,\sigma)$ denote the probability mass assigned to those strings. Then, by definition, $\frac{\delta(i,\sigma)}{\delta(i,\sigma) + \lambda(i,\sigma)\epsilon} \leq \epsilon$, implying that $\delta(i,\sigma) \leq 2\lambda(i,\sigma)\epsilon^2$. We can discard these low probability strings while only suffering a $\delta(i,\sigma)$ loss in prob. mass to $E$.

Continue doing this for all possible bad $(i,\sigma)$, and in the end we only discard at most $\sum_{i,\sigma} \delta(i,\sigma) \leq \sum_{i} \sum_{\sigma} 2\lambda(i,\sigma)\epsilon^2 \leq 2\sum_{i} \epsilon^2 = 2n\epsilon^2$. This uses the fact that for all $i$, $\sum_{\sigma} \lambda(i,\sigma) = 1$.

If you wanted $E'$ to have probability mass $1 -\gamma$, then $\epsilon$ needs to be such that $\epsilon + 2n\epsilon^2 \leq \gamma$, or that $\epsilon = O(\gamma/\sqrt{2n})$ suffices.

It's not clear to me at the moment whether this dependence on $n$ can be gotten rid of; I'll continue thinking about it.


Can typed lambda calculi express *all* algorithms below a given complexity? I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming larger as the expressiveness of the type system grows. I recall that, e.g., the Calculus of Constructions can express at most doubly exponential complexity.

My question concerns whether the typed lambda calculi can express all algorithms below a certain complexity bound, or only some? E.g. are there any exponential-time algorithms not expressible by any formalism in the Lambda Cube? What is the "shape" of the complexity space which is completely covered by different vertices of the Cube?

I will give a partial answer, I hope others will fill in the blanks.

In typed $\lambda$-calculi, one may give a type to usual representations of data ($\mathsf{Nat}$ for Church (unary) integers, $\mathsf{Str}$ for binary strings, $\mathsf{Bool}$ for Booleans) and wonder what is the complexity of the functions/problems representable/decidable by typed terms.  I know a precise asnwer only in some cases, and in the simply typed case it depends on the convention used when defining "representable/decidable".  Anyhow, I don't know of any case in which there is a doubly exponential upper bound.

First, a brief recap on the Lambda Cube.  Its 8 calculi are obtained by enabling or disabling the following 3 kinds of dependencies on top of the simply typed $\lambda$-calculus (STLC):

polymorphism: terms may depend on types;
dependent types: types may depend on terms;
higher order: types may depend on types.

(The dependency of terms on terms is always there).

Adding polymorphism yields System F.  Here, you can type the Church integers with $\mathsf{Nat}:=\forall X.(X\rightarrow X)\rightarrow X\rightarrow X$, and similarly for binary strings and Booleans. Girard proved that System F terms of type $\mathsf{Nat}\rightarrow\mathsf{Nat}$ represent exactly the numerical functions whose totality is provable in second order Peano arithmetic. That's pretty much everyday mathematics (albeit without any form of choice), so the class is huge, the Ackermann function is a sort of tiny microbe in it, let alone the function $2^{2^n}$. I don't know of any "natural" numerical function which cannot be represented in System F. Examples usually are built by diagonalization, or encoding the consistency of second order PA, or other self-referential tricks (like deciding $\beta$-equality within System F itself).  Of course in System F you can convert between unary integers $\mathsf{Nat}$ and their binary representation $\mathsf{Str}$, and then test for instance whether the first bit is 1, so the class of decidable problems (by terms of type $\mathsf{Str}\rightarrow\mathsf{Bool}$) is equally huge.

The other 3 calculi of the Lambda Cube which include polymorphism are therefore at least as expressive as System F.  These include System F$_\omega$ (polymorphism + higher order), which can express exactly the provably total functions in higher order PA, and the Calculus of Constructions (CoC), which is the most expressive calculus of the Cube (all dependencies are enabled).  I don't know a characterization of the expressiveness of the CoC in terms of arithmetical theories or set theories, but it must be pretty frightening :-)

I am much more ignorant regarding the calculi obtained by just enabling dependent types (essentially Martin-Löf type theory without equality and natural numbers), higher order types or both. In these calculi, types are powerful but terms can't access this power, so I don't know what you get.  Computationally, I don't think you get much more expressiveness than with simple types, but I may be mistaken.

So we are left with the STLC. As far as I know, this is the only calculus of the Cube with interesting (i.e., not monstrously big) complexity upper bounds. There is an unanswered question about this on TCS.SE, and in fact the situation is a bit subtle.

First, if you fix an atom $X$ and define $\mathsf{Nat}:=(X\rightarrow X)\rightarrow X\rightarrow X$, there is Schwichtenberg's result (I know there's an english translation of that paper somewhere on the web but I can't find it now) which tells you that the functions of type $\mathsf{Nat}\rightarrow\mathsf{Nat}$ are exactly the extended polynomials (with if-then-else). If you allow some "slack", i.e. you allow the parameter $X$ to be instantiated at will and consider terms of type $\mathsf{Nat}[A]\rightarrow\mathsf{Nat}$ with $A$ arbitrary, much more can be represented. For example, any tower of exponentials (so you may go well beyond doubly exponential) as well as the predecessor function, but still no subtraction (if you consider binary functions and try to type them with $\mathsf{Nat}[A]\rightarrow\mathsf{Nat}[A']\rightarrow\mathsf{Nat}$). So the class of numerical functions representable in the STLC is a bit weird, it is a strict subset of the elementary functions but does not correspond to anything well known.

In apparent contradiction with the above, there's this paper by Mairson which shows how to encode the transition function of an arbitrary Turing machine $M$, from which you obtain a term of type $\mathsf{Nat}[A]\rightarrow\mathsf{Bool}$ (for some type $A$ depending on $M$) which, given a Church integer $n$ as input, simulates the execution of $M$ starting from a fixed initial configuration for a number of steps of the form
$$2^{2^{\vdots^{2^n}}},$$
with the height of the tower fixed. This does not show that every elementary problem is decidable by the STLC, because in the STLC there is no way of converting a binary string (of type $\mathsf{Str}$) representing the input of $M$ to the type used for representing the configurations of $M$ in Mairson's encoding. So the encoding is somehow "non-uniform": you can simulate elementarily-long executions from a fixed input, using a distinct term for each input, but there is no term that handles arbitrary inputs.

In fact, the STLC is extremely weak in what it can decide "uniformly".  Let us call $\mathcal C_{ST}$ the class of languages decidable by simply typed terms of type $\mathsf{Str}[A]\rightarrow\mathsf{Bool}$ for some $A$ (like above, you allow arbitrary "slack" in the typing). As far as I know, a precise characterization of $\mathcal C_{ST}$ is missing. However, we do know that $\mathcal C_{ST}\subsetneq\mathrm{LINTIME}$ (deterministic linear time). Both the containment and the fact that it is strict may be shown by very neat semantic arguments (using the standard denotational semantics of the STLC in the category of finite sets). The former was shown recently by Terui. The latter is essentially a reformulation of old results of Statman. An example of problem in $\mathrm{LINTIME}\setminus\mathcal C_{ST}$ is MAJORITY (given a binary string, tell whether it contains strictly more 1s than 0s).

(Much) Later add-on: I just found out that the class I call $\mathcal C_{ST}$ above actually does have a precise characterization, which is moreover extremely simple.  In this beautiful 1996 paper, Hillebrand and Kanellakis prove, among other things, that

  Theorem. $\mathcal C_{ST}=\mathsf{REG}$ (the regular languages on $\{0,1\}$).

(This is Theorem 3.4 in their paper).

I find this doubly surprising: I am surprised by the result itself (it never occurred to me that $\mathcal C_{ST}$ could correspond to something so "neat") and by how little known it is. It is also amusing that Terui's proof of the $\mathrm{LINTIME}$ upper bound uses the same methods employed by Hillebrand and Kanellakis (interpreting the simply-typed $\lambda$-calculus in the category of finite sets). In other words, Terui (and myself) could have easily re-discovered this result were it not for the fact that we were somehow happy with $\mathcal C_{ST}$ being a "weird" class :-)

(Incidentally, I shared my surprise in this answer to a MO question about "unknown theorems").


Implications of Riemann Hypothesis variants in TCS The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,

  what are the major implications of the Riemann hypothesis in TCS?

As a start here is an example from a recent paper, Homomorphism Polynomials complete for VP by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction:

  One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH.

Second, a terminological note: contrary to popular belief, there is no such thing as “the generalized Riemann hypothesis” or “the extended Riemann hypothesis”. Both of these terms are used more-or-less interchangeably in the literature as a loose denotation of any kind of generalizations of the RH to some class of $L$-functions. They have no fixed specific meaning, or at least none consistent across papers of different authors (or even different papers of the same author).

The result mentioned in the OP is based on a result of Koiran that the existential theory of $\mathbb C$ (which commonly goes under the confusing name “Hilbert’s Nullstellensatz”) is in AM, and therefore in the polynomial hierarchy. It assumes the RH for Dedekind $\zeta$-functions; specifically, it relies on an effective version of the Chebotarev density theorem.

Another class of CS applications exploit the fact that every nontrivial quadratic Dirichlet character modulo $m$ assumes $\chi(x)=-1$ for some $x=O((\log m)^2)$, originally due to Ankeny, often stated with a reference to Bach who improved the constant in the $O$-notation. It relies on the RH for $L$-functions of quadratic Dirichlet characters, which is weaker than the one for Dedekind $\zeta$-functions. (The result actually holds more generally for finite-order Hecke characters, and in full generality it needs the RH for $L$-functions of said Hecke characters, which is in fact equivalent to the RH for Dedekind $\zeta$-functions. However, the CS applications I’m aware of do not need this.) The consequences are that one can derandomize several algorithms, such as the Miller–Rabin primality testing algorithm, or the Shanks–Tonelli algorithm for computing square roots modulo primes.

As far as I know, RH is not useful to deterministically find primes in a given interval, as alluded to in a comment above. This would follow from Cramér’s conjecture or a similar bound on prime gaps, but the RH is too weak to prove such bounds (the error term in the prime number theorem is at least of order roughly $\sqrt x$ no matter what).


Problems with complexity between P and NP that have  NP-complete generalizations Can anyone list some well-known problems that satisfies the following conditions:

1. has a generalization problem that is known to be NP-complete
2. has not been proved to be NP-complete nor has a known polynomial time solution.

Most famously: Graph Isomorphism, and Dominating Set on Tournaments.

Generalizations are natural.


Are there non-constructive algorithm existence proofs? I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity.

I struggle wrapping my mind around how this can be the case; how a non-constructive proof for the existence of an algorithm would look like.

Do there actually exist such problems? Do they have a lot of practical value?

Consider the function (taken from here)

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Despite the looks, $f$ is computable by the following argument. Either

$0^n$ occurs for every $n$ or
there is a $k$ so that $0^k$ occurs but $0^{k+1}$ does not.

We do not know which it is (yet), but we know that $f \in F = \{f_\infty, f_0, f_1, \dots \}$ with

$f_\infty(n) = 1$ and
$f_k(n) = [n \leq k]$.

Since $F \subset \mathsf{RE}$, $f$ is computable -- but we can not say what  $f$ is.


Determining Graph Hulls Consider the following undirected unweighted graph:

The green nodes separate the graph from the "external environment". Let's call them the graph hull. Now, a graph may have several hulls. Consider the following graph, where the green nodes constitute the hull:

If we rearrange the drawing in the following way (stretching the blue nodes to the outside) then the blue nodes become the hull:

Questions

Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, one of its hulls?
Is it possible that the number of hulls of a graph is superpolynomial in $|V|$?
Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, its minimum hull (i.e. the hull having the minimum number of vertices)?
Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, its maximum hull (i.e. the hull having the maximum number of vertices)?

This question turned out to be trivial. As Lev Reyzin said in his comment, the answer was already encoded in the figures. I should have watched them more carefully...Of course, looking at the figures, it was already evident that those hulls are cycles. What was not immediately evident to me is the obvious fact that given whatever drawing like those, you could pick whatever cycle in it (even a 3-cycle), "enlarge" it, and "throw" all the remaining nodes inside it, thus obtaining a hull. So:

As Tsuyoshi Ito pointed out, if the drawing is not requested to be planar, then every cycle is a hull, and this observation simultaneously answers all the four questions I've posted.
As Hsien-Chih Chang and Peter Shor indicated, if the drawing is requested to be planar, then the questions can be answered by using planar graph embedding algorithms.

Finally, to make things worse, it seems that the choice of the term "hull" was unfortunate: the correct term to indicate what I had in mind is "outer face" (although such term is probably meaningless for non-planar graphs).


Nontrivial membership in NP Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language?

Instead, the fact that the language is in $NP$ would be proven by reducing it to another language in $NP$, where the link between the two is not trivial and needs careful analysis.

More generally, are there some interesting examples of problems in $NP$ so that it is hard to see that they are in $NP$?

A semi-answer would be the problem of deciding the winner in parity games: to show that it is in $NP$ (even $NP\cap coNP$), we need the positional determinacy theorem which is deep and non-trivial. However this answer is not ideal, because it still boils down to the existence of a polynomial witness for this exact problem (the positional strategy), and does not reduce to another different $NP$-problem.

Another one would be the AKS primality algorithm: deciding whether a number is prime is polynomial, while there is a priori no small witness for this fact. Let's say we rule out the "surprising polynomial algorithms", since many of them would fit the description above. I'm more interested in surprising $NP$ algorithms which are not deterministic.

Integer Programming.

Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See

Christos Papadimitriou, "On the Complexity of Integer Programming", JACM, 1981.


reduction of maximum independet set to minimum distance of code Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity check matrix?

For the benefit of the others, the minimum code distance problem for codes over $\mathbb{F}_2$ is: given a matrix $H$ ($m$ by $n$, with elements from $\mathbb{F}_2$) and a positive integer $w$, does there exist a vector $x$ such that $Hx = 0$ and the hamming weight (number of 1's) of $x$ is at most $w$.

Since both max ind set and the minimum distance of a linear code are NP complete, there are many-one reductions in either direction. However, it doesn't seem that any of the reductions in the literature that I have seen are directly from max independent set. Actually it seems that the known reductions are from other problems related to coding. Alexander Vardy proved the NP-hardness of computing the min distance by reducing from the max-likelihood decoding problem: given a matrix $H$ over $\mathbb{F}_2$, a vector $s$ and a positive integer $w$, does there exist a vector $x$ such that $Hx = s$ and the weight of $x$ is at most $w$. This problem was shown to be NP-hard by Berlekamp and others by reduction from 3-dimensional matching (which is one of the Karp problems and can be reduced to from 3SAT). If you want to reduce max independent set to 3SAT and piece together all these reductions, I guess you can get what you want...

There is a line of work that looks at hardness of approximating the min distance problem. However, reductions there are also from other coding problems. For example, Dumer and others show a hardness of approximation result for the min distance problem by reducing from the nearest codeword problem (given a message find the nearest codeword in hamming distance). A hardness of approximation result for the latter problem was proved by Arora and others, as far as I can tell using two methods: reducing from set cover, or reducing from label cover.


Drunken birds vs drunken ants: random walks between two and three dimensions It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly less than 1 of returning to the origin.

My question is:

  Is there something in between ? For example, suppose my space was
  actually a bounded region of the plane extruded out to infinity in the
  z-direction. (what's often called 2.5 dimensional). Do the
  two-dimensional results apply, or the three dimensional ?

This came up in discussions, and one heuristic argument saying that it behaves two dimensionally is that since the finite region of the plane will be covered eventually, the only nontrivial part of the walk is the 1 dimensional ray along the z direction, and so return to the origin will happen.

Are there other shapes that interpolate between the two-D and the three-D case ?

Update (pulled in from comments): a related question was asked on MO - a short summary is that if the walk is even (2+ϵ) dimensional, then uncertain return follows loosely from a diverging series. However, the above question is slightly different IMO since I'm asking about other kinds of shapes that might admit certain return.

Probability on Trees and Networks by Peres and Lyons mentions this in Chapter 2 (page 50):

  One way to make sense of this is to ask about the type of spaces intermediate between $\mathbb{Z}^2$ and $\mathbb{Z}^3$. For example, consider the wedge

  $$ W_f := \{ (x, y, z) : |z| \leq f(|x|) \} $$

  where $f : \mathbb{N} \rightarrow \mathbb{N}$ is an increasing function. The number of edges that leave $W_f \cap \{(x, y, z) : |x| \text{ or } |y| \leq n\}$ is of the order $n(f(n)+1)$, so that according to the Nash-Williams Criterion,

  $$\sum_{n \geq 1}\frac{1}{n(f(n)+1)} = \infty$$

  is sufficient for recurrence.


Analysis of Comb Sort? EDIT: The Wikipedia article mentioned here was incorrect and has since been updated.  Comb sort's worst-case behavior is $\Omega(n^2)$, not $O(n \log n)$ as was claimed.

Yesterday I stumbled on the comb sort algorithm, a modification of bubble sort similar in spirit to Shell sort.  The idea is to maintain a gap of some size, then use a bubble-sort pass over the array using that gap size to roughly position the elements into their proper positions.  Each iteration decreases the gap size, until eventually the algorithm degrades into bubble sort.

The Wikipedia article claims that the algorithm runs in O(n log n) time worst-case, but the citation for this claim is a paper on GPU processing that mentions this result offhand without providing any analysis or citation.  One of the original papers on comb sort doesn't even attempt to prove a worst-case bound, and in fact not a single source I've found has attempted to analyze the worst-case or even average-case complexity of comb sort.  This concerns me, since I've found a lot of sites that are clearly getting their information from the Wikipedia article, and I would hate for a single bad source to propagate the O(n log n) claim if it is incorrect.

My question is this: is there a reliable source that proves the O(n log n) worst-case behavior of comb sort?

Thanks!

The $\Omega(n^2)$ worst-case lower bound of Comb sort (or Dobosiewicz sort) has also been proved using the incompressibility method based on Kolmogorov complexity. See for example the survey by Vitanyi, page 16. If you are also interested in the average-case lower bound on the running time, the paper gives that as well. Moreover the proofs obtained with the method are natural, easy-to-follow and usually quite short.


nested pseudorandom generator Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer between 1 and K.

Question A: Is it possible to adapt PRNG to yield pseudorandom integer numbers uniformly distributed between 1 and K?

Assuming that the answer to this question is yes, let's denote by PRNG(k; 1, K) the number between 1 and K yielded by the adapted PRNG when the seed state is k.

We can then build a new pseudorandom number generator by nesting PRNG, i.e.

newPRNG(k) = PRNG(PRNG(k; 1, K))

Question B: From a theoretical point of view, can we say something about the properties of the new PRNG? In particular, does this nesting trick increase or decrease the randomness of the generator, in some sense?
I think this question is a natural one but I didn't find any answer on the web.

Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using this. However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator.

To get some intuition on why this is so, try to view the problem from an adversarial point of view where the goal is to guess the outcome of the PRNG. If $P_{guess}>1/K$ is the probability of the most probable outcome of the PRNG, then there is no deterministic way to lower the adversary's guessing probability without adding randomness. Therefore if you are to transform the outcome to a uniform distribution then all the equaly likely outcomes must happen with probability at least $P_{guess}$, so there can be at most $1/P_{guess}$ outcomes. Of couse, I'm assuming that the adversary knows the deterministic procedure that is applied, as is usually the case in cryptography.

So the answer to question B is that this nesting trick does not increase randomness, it can only decrease it. There is no deterministic procedure that can increase randomness.

Hope this helps


Communication complexity with a referee Assume a framework in communication complexity where we have two players A(lice) and B(ob) and a R(eferee). A and B don't communicate directly with each other. In each round of communication, each of them sends a message ($m_A$, $m_B$) to the R. R computes two functions $f_A(m_A,m_B)$ and $f_B(m_A,m_B)$ and sends the results to them. The functions are fixed. The idea is that the communication between the players is restricted. Moreover the referee might do some processing on the messages.

Example:

A and B send two (arbitrary large) numbers to R, R checks which of them is greater and informs the players.

In this framework, we can design a simple protocol that easily computes the following function using a single round. A and B send $x$ and $y$ to R, R returns the answer to them, and they output the answer.

$$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$$

Obviously this is not an interesting case, since the function we are computing is the same as the referee functions. A more interesting case is when we have a fixed linear inequality $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ and the values for the variables are partitioned between players (A has $\vec{x}$ and B has $\vec{y}$). The task is to decide if the inequality is correct. The protocol in this case is that players compute their part and then send them to the referee.

Question:

Has this kind of communication complexity been studied? If yes where can I find more about this?

note 1: on page 49 Kushilevitz and Nisan mention a framework which involves a referee but seems very different from what I am asking.

note 2: I am not sure if calling R a referee is the right thing, please comment if you have a better suggestion.

I'm sure you know the following paper, but I put a link to it because other readers may be interested: Interpolation by Games

This paper is an attempt to use the communication complexity framework to show lower bounds for cutting planes.  The protocol is used to produce an interpolant circuit for unsatisfiable CNF:
$$
A(x,y)\lor B(x,z).
$$

Player $A$ gets input $a$ and $y^a$, player $B$ gets $b$ and $z^b$.  If there is a shallow tree-like proof in cutting planes then the two players have a communication protocol such that

any communication is mediated by the referee, which helps in evaluating the inequalities in the proof;
the amount of communication is small (the tree is shallow);
the two players either decide which of $A$ or $B$ is falsified;
they find a position $i$ in which $a_i \not= b_i$.

The referee is turned into a probabilistic protocol for inequalities.  In this way it is possible to turn lower bound for tree-like probabilistic protocols in the communication complexity framework into lower bound for tree-like cutting planes proofs.

If we had lower bound for communication protocol of the form of a PLS, then we would get lower bound for dag-like cutting planes proofs.

Notice that this technique does not depend on the actual inference rules of cutting planes. If we assume the inference rules to be (1) positive combination (2) integer division with floor we can build the monotone interpolant circuit using Pavel Pudlák argument.


On integer programming Integer programming is NP-hard.

What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ category)?

Integer programming in fixed parameters is P.

What is the status of integer programming problem in fixed parameters that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ category)?

(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer program by a parsimonious reduction, finding a second integer point in an integer program is also $\mathsf{NP}$-hard.

(2) Barvinok [2] showed that in fixed dimension, you can actually count the number of integer points in polynomial time, so the answer to your second question is $\mathsf{P}$.

[1] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003. (freely available author's copy)

[2] FOCS 1993


NP-hardness of a planar SAT variant Background:
An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals.
Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $G_\phi$ that contains a vertex per each variable and per each clause, and has an edge between a variable-vertex
and a clause-vertex if and only if the variable appears in the clause. When $G_\phi$ is planar then $\phi$ is also said to be planar.
Planar Monotone 3-SAT (de Berg and Khosravi [1]) is an NP-hard SAT variant where instances are both monotone and planar.
Furthermore, it remains hard when the graph $G_\phi$ has the following rectilinear representation:
All variable-vertices lie on a horizontal line and all positive clause vertices are above it and all the negative clause vertices are below it. For example:
 (Figure adapted from [1])
In this representation, each clause has at most 3 vertical lines, called legs, that go up/down to each of the variables it contains. We say that two legs enclose a clause $C$ if $C$ is horizontally between the two legs (and is on the same side as the legs with respect to the variables).
A new definition: A clause (of size 3) is bi-enclosing if both its leftmost and rightmost pair of legs enclose some other clauses. For example, in the figure above $C_i$ is the only bi-enclosing clause (as all others clauses have a pair of legs with no clauses between them).
The SAT variant I'm asking about: All Planar Monotone 3-SAT instances in rectilinear representation where there are no bi-enclosing clauses. Is deciding satisfiability in this case NP-hard?
I haven't seen this version addressed explicitly before. Interestingly, the first example of the rectilinear representation for (the more general) planar 3-SAT problem, given in Knuth and Raghunatan [3], has no bi-enclosing clauses:

Edit following domotorp's answer: Here is an instance where we cannot change the order of the variables in order to prevent $(x_1 ∨ x_3 ∨ x_5)$ from being bi-enclosing:

(Note that in the variant in question we cannot move clauses to the other side of the variables. In Planar 3-SAT, however, we could easily do that to fix the bad clause above and so a more complex example would be required for a "non-fixable" instance in that case).

The following paper answers the question in the affirmative – the variant remains NP-hard using a reduction from Monotone Planar 3-SAT:
http://epubs.siam.org/doi/abs/10.1137/1.9781611976465.105
(arXiv: http://arxiv.org/abs/2009.12369)
The paper presents a slightly more restricted variant, Monotone Planar 3-SAT with Neighboring Variable Pairs, which requires each clause with three variables to contain two variables that are adjacent on the line on which all variables are embedded.
If there is a bi-enclosing clause in this variant, it must enclose a redundant clause due to monotonicity, so we can assume no bi-enclosing clauses.


Holographic Algorithms - Equivalence of Bases I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper.

I cannot see why is it the case that if there is a generator with certain values for $valG$ with a basis $\{(a_1,b_1) \ldots (a_r,b_r)\}$, then there exists some generator with same $valG$ values for any basis $\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$ ($1^{st} kind$) or $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$ ($2^{nd} kind$) for any $x,y \in F$.

Valiant points out the reason in preceding paragraph  - namely the $1^{st}$ kind of transformation can be achieved by appending to every input or output node an edge of weight $1$. The $2^{nd}$ kind of transformation, Valiant says, can be achieved by appending to input or output nodes chains of length $2$ weighted by $x$ and $y$ respectively.

I have not been really able to understand these statements. Maybe they are already clear, but still I cannot really see why the above construct helps achieve any realizable $valG$ values with one basis with the new basis which is one of the above types.

Please help illuminate them to me. On a different note, are there some tensor free surveys for hologaphic algorithms available online. Most of them use tensors which, sadly, scare me :-(

Best
-Akash

Tensors (in this sense) are just arrays of numbers, so I don't think you'll find tensor free surveys unless they're completely free of calculations.

The "$T^{\otimes k}$" operation formalizes both the operations of changing basis and attaching gadgets to each output node (in fact I like to think of a change of basis as a sort of gadget operation). Let $\Gamma$ be a generator matchgate with standard signature $M_{i_1i_2\cdots i_k}=u(\Gamma)$. This an array of $2^k$ numbers. The signature in a new basis is given by

$(T^{\otimes k}M)_{i_1i_2\cdots i_k}:=\sum_{i_1',\cdots,i_k'} T_{i_1i_1'} \cdots T_{i_ki_k'} M_{i_1'i_2'\cdots i_k'}$

where $T$ is some two-by-two matrix descring the new basis.

Let $\Gamma'$ be the matchgate formed by adding $k$ new vertices to $\Gamma$, taking these to be the new outputs, and connecting them to the old outputs by an edge of weight $x$. Then the new signature is $C^{\otimes k}M$ where $C_{ij}$ is the matrix $\begin{pmatrix}0&x\\1&0\end{pmatrix}$. If you then perform the change of basis $TC^{-1}$ you get the signature $T^{\otimes k}M$.


Numerical precision in sum-of-squares method? I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the rug.

From my (admittedly limited) understanding of the method, the following should be true:

  Given any system of polynomial equalities $E$ over real-valued variables $x \in \mathbb{R}^n$, where all parameters are $O(1)$ ($n$, $|E|$, and degree of each constraint), the degree-"$2n$" ($=O(1)$) SOS method finds a satisfying assignment of the variables or proves none exists in $O(1)$ time.

My first question is whether the above claim is true (is there a naive argument that doesn't use SOS to solve this?). The second question is where numerical accuracy fits in. If I want to get an assignment that satisfies all constraints to within additive $\varepsilon$ accuracy, how does the runtime depend on $1/\varepsilon$? In particular, is it polynomial?

The motivation for this is to, say, apply a divide-and-conquer approach on a large system until the base case is an $O(1)$-size system.

EDIT: From Barak-Steurer, it appears that the "degree $l$ sum-of-squares algorithm" on p.9 (and the paragraphs leading up to it) all define problems for solutions over $\mathbb{R}$, and in fact the definition of a pseudo-distribution in section 2.2 is over $\mathbb{R}$. Now I am seeing from Lemma 2.2, however, that one is not guaranteed a solution/refutation at degree $2n$ without binary variables.

So I can refine my question a little bit. If your variables are not binary, the worry is that the sequence of outputs $\varphi^{(l)}$ is not finite (maybe not even monotonic increasing?). So the question is: is $\varphi^{(l)}$ still increasing? And if so, how far you have to go to get additive accuracy $\varepsilon$?

Though this likely does not change anything, I happen to know my system is satisfiable (there is no refutation of any degree), so I am really just concerned about how large $l$ needs to be. Finally, I am interested in a theoretical solution, not a numerical solver.

I think my answer is probably insufficient, but it remains for completeness' sake (although see Boaz's comments below for probably a better answer)

When we limit ourselves to boolean variables, the claim can be seen when $(x_i^2-1) \in E$ for all $i \in[n]$ with the observation that degree $2n$ pseudo-distributions are actual distributions, that is, suppose you have a pseudo-distribution $\mu(x)$ over solutions $x$ of your polynomial equalities $E$ satisfying:

$\sum_{ x \in \{-1,1\}^n} \mu(x)$ and $\sum_{x\in\{-1,1\}^n} \mu(x) p^2(x)\ge0$ for all polynomials $p$ with degree at most $n$

But degree $n$ polynomials include the indicator polynomial (for example, $x_1 = 1, x_2=-1, x_3=1$ has $2^{-3}(1+x_1)(1-x_2)(1+x_3)$ which is all-zero elsewhere and 1 on that assignment). So $\mu(x) \ge 0$ for all $x\in\{-1,1\}^n$, so we conclude $\mu$ is an actual distribution over the solutions of $E$. Degree $\ell$ pseudo-distributions can be found by using semidefinite programming to find an associated degree $\ell$ pseudo-expectation operator in $n^{O(\ell)}$ time, so we can find the actual distribution $\mu$ in time $n^{O(n)}$ by using that pseudo-expectation (now an actual expectation) to find all the moments of $\mu$.

So, if $|E| = O(1)$, then you can find a distribution of solutions to $E$ in $O(1)$ time. Of course, brute force search guarantees the same.

However, if the solutions are not necessarily boolean, then degree-$2n$ pseudo-expectations are not sufficient to find a distribution over solutions. As can be seen above, the proof that degree $2n$ pseudo-distributions are actual distributions depends on the fact that degree $n$ polynomials are sufficient to 'pick out' individual assignments, which is not true more generally. Another way of viewing it is that boolean-variable polynomials are considered $\mod(x_i^2)$, so the degree of every monomial is at most $n$.

For example, one could consider replacing every binary variable with a 4-ary variable, say by including $(x_i^2-1)(x_i^2-4) \in E$. Then you would have to have a degree $4n$ pseudo-expectation in order to guarantee recovery of a distribution over solutions.

Now, for theoretical guarantees, it seems like approximating a root of a system of polynomals is also known as Smale's 17th problem, and apparently there is a randomized (Las Vegas) polynomial time algorithm that solves this - see http://arxiv.org/pdf/1211.1528v1.pdf. Note that this seems to be in the Blum-Shub-Smale model, so real operations are the primitive. I am not sure if this gives the guarantee that you need.


Validity of a modal argument about "vagueness" (2nd version to make explicit my implicit assumptions about A, B and C, and the definitions of the non-logical constants "⊂" and "≡".)
Intuitively, the following modal argument seems valid to me and to other people. However, can it be formally proved valid? Or proved not valid?
Definition: "◇p" means "We don't know that not p".
Definition: "◻p" means "We know that p".

∃A
∃B
∃C
∀x, ∀y, ∀z, ((x ⊂ y) ∧ (y ⊂ z) → (x ⊂ z))
∀x, ∀y, ((x ⊂ y) ∧ (y ⊂ x) → (x ≡ y))
◇(A ⊂ C)
◻(B ⊂ C)
∴ ◇(A ≡ B)

Or, in ordinary language, where "⊂" means set inclusion and "≡" means identity:

A, B and C exist
A may be some part of C
B is some part of C
Therefore, A and B may be the same part of C

I'm researching expressiveness of modal logic, i.e. to what extent modal logic can express the kind of assertions people make using some ordinary, informal language.
The particular relation identified in the argument here, which I think we can best describe as one of vagueness, seems to polarise the population surveyed into (mainly) two groups, and broadly equal in size: those who accept the argument as valid, and those who do not. However, those who do not accept validity appear for the moment, as I see it, unable to articulate a conclusive rationale in favour of invalidity.
The only substantial rationale for invalidity offered so far is to exhibit an interpretation of A, B and C which keeps both premises true but makes the assertoric version of the conclusion, i.e. "Therefore, A is the same as B", false. This is sometimes loosely qualified as a form of "undistributed term".
However, I take this to be inconclusive as it doesn't preclude other interpretations of A, B and C that make true the same assertoric conclusion "Therefore, A is the same as B". So, A and B may be the same. QED.
As I see it, there is nothing in the premises that implies that A and B are necessarily different. This in turn implies that they are possibly the same, which is the conclusion of the argument. QED.
Isn't that good enough?

How about just a blanket statement with no assumptions:

  A and B may be the same part of C

This would seem to be valid by the same reasoning! However it is only so if "may" ranges over all models of the language. If, as is usual, "may" only ranges over the possible worlds in a single model, it is not valid.


Recovering the slope of a digitized line Has there been any work on recovering the slope of a line segment from its digitization?
One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized line an interval of possible slopes.

(The notion of a digitized line that I am using is Rosenfeld's: the set of pairs $(i,nint(ai+b))$ where $i$ ranges over the integers (or a block of consecutive integers) and $nint(x)$ denotes the integer nearest to $x$ (if $x=k+1/2$, we take $nint(x)=k$).)

I've done some work on this on my own (see http://jamespropp.org/SeeSlope.nb) but I have
no formal background in computational geometry so I suspect I may be reinventing the wheel, since the question seems like such a basic one.

In fact, I know that the linear regression method of estimating the slope is in the
literature, but I haven't been able to find my $O(1/n^{1.5})$ result anywhere.  (This
result says that if one chooses $a$ and $b$ uniformly at random in $[0,1]$, then the
difference between the slope $a$ of the line $y=ax+b$ and the slope $\overline{a}$ of
the regression line approximating the $n$ points $(i,nint(ai+b))$ ($1 \leq i \leq n$)
has standard deviation $O(1/n^{1.5})$.)

Any leads or pointers to relevant literature will be greatly appreciated.

Jim Propp (JamesPropp@ignorethis.gmail.com)

The computational geometry approach would replace each pixel (i,j) with vertical segment (i, j+[-1/2,1/2]), take the convex hulls of the upper and lower sets of endpoints, and compute the inner common tangents -- these delimit the range of slopes that produce this digital line. This is just the geometric interpretation of the linear program that you mention in your slides.  O(n) time suffices for the LP by Meggiddo, or for the hulls and tangents by Graham-Yao.


Evidence that UniqueSat is dense UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete.

  What is the density of UniqueSAT?

I know only weak evidence to support that it can not be sparse: All known CoNP-complete sets are dense and UniqueSAT is CoNP-hard.

Here, density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.

Motivation: I would like to link the existence of Karp reduction from SAT to UniqueSAT to the existence of "large gap" between the density of the two problems. Mahaney's Theorem gives evidence that Karp reduction can not exist between two $NP$ sets with densities separated by "large gap".

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely many $n$.)
The following argument works even for the revised definition of "dense" introduced in version 5 of the question, where all instances of size up to $n$ are taken into account.  Note that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$.

Consider formulas in CNF with $v$ clauses, each clause containing exactly one literal, such that each variable occurs precisely once in the formula.
An example of such a "complete 1-SAT" formula for $v=3$ is $x_1\land x_2 \land \lnot x_3$, completely specifying the solution $x_1 = 1, x_2 = 1, x_3 = 0$.

We establish an exponential lower bound for the number of complete 1-SAT formulas of size $n$.
Logarithms are base 2.

Complete 1-SAT formulas each have precisely one solution, and with $v$ variables such a formula has size $v(1+\log v)$.
There are also $2^v.v!$ distinct complete 1-SAT formulas over $v$ variables.

We then just need to ensure that $v$ is as large as possible in terms of the instance size $n$.

Let $v = n/(\log n)^\delta$ for some $\delta = \delta(n)$.
For the size of complete 1-SAT formulas with $v$ variables to be precisely $n$ bits, we require that
$n = v(1+\log v)
= (n/(\log n)^\delta)(1+\log n - \delta\log\log n)$
so $1+\log n - \delta\log\log n = (\log n)^\delta$.
We can always choose $\delta$ appropriately to satisfy this expression; note that $1/2 < \delta < 1$ for large enough $n$, with $\delta \to 1$ as $n \to \infty$.

This already shows that there are at least $2^{n/\log n}$ such instances, so UniqueSAT is not sparse.

Moreover, the high order term of the exponent of $2^v.v!$ is then $n[(u/(1+u))-(\log e - 1)]$, where $u = \log n - \delta \log\log n$ and $\log e - 1 \approx 0.4427$.
(For instance, this follows from Robbins' bounds for the factorial function, $\log n! = n\log n - n\log e + 0.5\log n +r_n\log e + 0.5(1+\log \pi)$, where $1/(12n+1) < r_n < 1/(12n)$ for $n \ge 1$.)
Now $u/(1+u) > 1/2$ for large enough $n$, so there are $2^{\Omega(n)}$ complete 1-SAT instances, and hence $2^{\Omega(n)}$ UniqueSAT instances.


Finding the largest set of points of limited diameter Given points $p_1,\ldots,p_n$ in $\mathbb{R}^{d}$ and a distance $l$ find the
largest subset of these points such that the Euclidian distance of no
two of them exceeds $l$.

What is the complexity of this problem?

In the graph over the points which has an edge whenever the distance
of two points is at most $l$, the problem is equivalent to finding a
maximum clique. The converse may not hold, because not every graph can
be obtained this way (an example is the star $K_{1,7}$ for $d=2$). Therefore a related question is: what is known about this class
of graphs?

There's an $O(n^3\log n)$ time algorithm for the two-dimensional version of this problem in my paper with Jeff Erickson, "Iterated nearest neighbors and finding minimal polytopes", Disc. Comp. Geom. 11:321-350, 1994. Actually the paper primarily looks at the dual problem: given the number of points in the subset, find the smallest possible diameter; but it uses the problem you describe as a subroutine. At least at the time we wrote it, we didn't know anything subexponential for higher dimensions (although if the subset has only $k$ points in it the exponential part can be made dependent on $k$ rather than $n$ using techniques in the same paper).


Re-packing of integers into fixed-size bins We are given a constant $B \geq 3$, a set of positive integers $I$  s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$,
and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.

An adversary replaces two numbers with their addition so that a packing exists. I.e.,
for some $i,j \in I, i+j \leq B$, the set
$I' = (I \setminus \{i,j\}) \cup \{i+j\}$ admits a packing into $N/B$ bins.

An optimal update minimizes the number of touched bins during the re-packing for $I'$.
We are interested in the maximum number of bins  an optimal update would touch.

Questions:
How many bins (at most) an optimal update has to touch in a worst case?

Does it depend on the number of bins or it is some function of only $B$?

We can show there's an upper bound based only on B.

Fix B, then i and j. Let the tuple $(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k}$ denote the packing where we have $x_{t}$ bins of type $t$, where the type of a bin is just the numbers that are packed in it. We have the trivial upper bound $k \leq 2^{B-1}$.

Let $f(x_{1}, \dots, x_{k}) : \mathbb{N}_{\geq 0}^{k} \mapsto \mathbb{N}_{\geq 0} \cup \infty$ be a function mapping any packing into the minimum number of bins we have to touch, with $f = \infty$ if there exists no repacking. Clearly $f(y_{1}, \dots, y_{k}) \geq f(x_{1}, \dots, x_{k})$ when $y_{t} \leq x_{t}$ for all $t$, since any repacking we can do with $Y$ we can also do with $X$.

Now define $S = \{(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k} \mid f(x_{1}, \dots, x_{k}) < \infty\}$. This is a set of $k$-tuples of nonnegative integers, therefore by Dickson's lemma it has only finitely many minimal elements, where an element $X = (x_{1}, \dots, x_{k}) \in S$ is minimal if there exists no other element $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$. Let $H_{i, j}$ be the maximum value of $f$ over the minimal elements. As the maximum of a finite number of finite elements, it is finite.

Now for any $X = (x_{1}, \dots, x_{k}) \in S$ there exists minimal $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$, but then $f(x_{1}, \dots, x_{k}) \leq f(y_{1}, \dots, y_{k}) \leq H_{i, j}$. Therefore if $f$ is finite it is at most $H_{i, j}$.

Therefore $\max_{i, j} H_{i, j}$ is an upper bound on the number of bins we need to touch, and it depends only on $B$. As the maximum of a finite number of finite elements, it is finite.


Learning from derivative data In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there exist some algorithms which can estimate unknown function using derivative data of unknown function and their corresponding inputs. For example,

$$
\mbox{Given }D = {(x_1, y_1),\ldots,(x_n, y_n)}$$
$$\mbox{ where }y_{1} = \frac{d{f(x)}}{dx}\Bigg|_{x=x_1},\ldots,y_n=\frac{d{f(x)}}{dx}\Bigg|_{x=x_n}$$
$$\mbox{ Find  } f(x).$$

I found one curve fitting method which is called Hermite interpolation in wiki and some papers about Hermite learning. However, in these methods, outputs of unknown function and derivative outputs of it and corresponding inputs are given. Especailly, I want to know there exist some methods that utilize only derivative data. Also is it possible to find unknown function from derivative data, in particular, the error bound between unknown function and our estimator can decrease as the number of training data increases. How can we prove it?

If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. Obviously, you will only able to recover $f$ up to an additive constant from the derivative.

Update: As for error estimates, here's a simple one. Suppose you've managed to recover $f'$ up to $\epsilon$-accuracy in $L_\infty$. Suppose further that you know that $f(0)=0$ and you only care about $f$ on $[0,T]$. Then your estimate of $f$ (obtained by integrating $f'$) is accurate up to $T\epsilon$ in $L_\infty$.


Intermediate Problems between FP and #P Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.

Use Schöning's theorem:

  Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:

  $A_1 \notin C_1$, $A_2 \notin C_2$
  $C_1$ and $C_2$ are recursively presentable,
  $C_1$ and $C_2$ are closed under finite variations.

  Then there exists a recursive set $A$ such that:

  $A \notin C_1$, $A \notin C_2$,
  if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$.

For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.


Bipartite scale-free networks The Barabasi-Albert model describes a mechanism of generating random scale-free networks:

Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with $m$ ($<m0$) edges that link the new node to $m$ different nodes already present in the network.
Preferential attachment: When choosing the nodes to which the new node connects, we assume that the probability $P$ that a new node will be connected to node $i$ depends on the degree $k_i$ of node $i$, such that

$$P\propto \frac{k_i}{\sum_i k_i}$$

Is there a similar model for scale-free bipartite networks? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of scale-free networks?

You could apply the principle of the Configuration Model (Molloy & Reed'95) to bipartite graphs. It allows generating a network possessing any predefined degree distribution. In the original version, you first generate a set of "stubs", where each node is repeated as many times as its targeted degree (i.e. a node whose degree should be 5 will appear as 5 distinct stubs). Then, you randomly draw pairs of stubs, and connect the corresponding nodes in your graph. See this page for additional details.

In the case of a bipartite network, you could do the same thing, but using two distinct sets of stubs (corresponding to both types of nodes). The pairs you draw should be constituted of one stub from each set.

If you want to keep the growth property of the model, you could also directly modify the Barabasi-Albert model you mention, by adding two extra constraints. First, alternate the type of the inserted nodes (I mean: once a node of the first type, then a node of the second type, then another node of the first type, and so on). Second, connect it only to nodes of the other type, using the preferential attachment principle.

Edit: you might be interested by the Networkx library, cf. the Bipartite section in this page.


Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi? I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.

The implementation of the algorithm in computers usually calls for the use of $\pi$, or a trigonometric function, which, even if they are implemented as truncated series, sort of defeats the purpose.

To circumvent this issue, there is the well-known rejection-method algorithm: draw coordinates in the unit square, and see whether they belong to the unit quarter circle. This consists in drawing two uniform reals $x$ and $y$ in (0,1), and counting them only if $x^2+y^2 < 1$. In the end, the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$.

This second algorithm is usually passed off as Buffon's needle, thought it is considerably different. Unfortunately, I have not been able to track down who originated it. Does anybody have any information (documented, or at worst undocumented) as to who/when this idea originated?

The Monte-Carlo method is usually attributed to Metropolis and Ulam, the latter was a mathematician on the Manhattan project.

If my memory is good, Ulam published a paper where he computes pi using the algorithm.


System of "stochastic equations" Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x_u - x_v$. More precisely, $z$ is a truly random quantity in $(x_u - x_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).

I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x_i$'s. Is there some body of work on problems of this type?

Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x_s - x_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?

The problem of computing $x_s - x_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)

The area you want to look at for answers to is machine learning. You have desribed a graphical model. I think in this case methods as easy as Belief Propagation should suffice.


NP-completeness: sum of "some" paths in a spanning tree I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful:

Instance: undirected, unweighted, connected graph $G=(V,E)$, positive integer $K \in \mathbb{Z}^+$

Question: Is there a spanning tree $T$ of $G$ such that
$$\sum_{e=(u,v) \in E-T}d_T(u,v) \leq K$$

where $d_T(u,v)$ is the length (ie: number of edges) of the path from $u$ to $v$ in $T$. Note that the sum ranges over the complementary edges of $T$.

There is a similiar problem in the book by Garey and Johnson, namely "Shortest Total Path Length Spanning Tree" which was proved to be NP-complete in the paper "The complexity of the network design problem" (by Johnson, Lenstra and Rinnooy Kan). The difference is that the sum ranges over all pair of vertices.

The only technique I know so far is to find a reduction, is there a more suitable technique in this case? Any comment, suggestion or bibliographic reference will be of invaluable help.

You are asking for the minimum weight fundamental cycle basis (in an unweighted graph). I think the standard reference for its NP-hardness is:

Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software, 8 (1): 26–42, doi:10.1145/355984.355988.


Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams? Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how efficient they are.

For instance, for data compression, we know that data with low entropy (some symbols appearing more often than other, many repetitions) can be compressed very well while completely random data cannot be compressed.

  Is there an analogous intuition for estimating how efficiently ROBDDs can represent a given boolean formula?

For example, I have heard that multiplication of $n$-bit numbers cannot be represented efficiently, the minimum ROBDD size is exponential in $n$. Do you know of an intuitive argument that explains why this is the case?

Related question: intuition about efficiency of BDDs that calculate numbers (multiple terminal BDDs, etc.)

There is a relation between the width of an OBDD for a function $f$ and the communication complexity of a one-way communication protocol for the best-case partition of variables for $f$ (see E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997).

This is a powerful tool for proving exponential size OBDDs for various functions (together with coauthors, we used this method for proving that $\epsilon$-bipartiteness is hard for OBDDs, see here).
Basically, if there exists an OBDD of width at most $w$ that solves $f$, then $\kappa_{best}(f) \leq \log w$.
I think this is more intuitive to think in terms of communication complexity rather than OBDD.


Minimizing entropy plus a modular function I have a question about whether there are faster algorithms for specific submodular minimization problems.

In particular, I am trying to find a fast algorithm for minimizing the following set function

$$f(S) = - [\sum_{i \in S} \alpha_i \log(\alpha_i) + (1-\sum_{i \in S} \alpha_i) \log(1-\sum_{i \in S} \alpha_i)] + \sum_{i \in S} w_i$$

where $S \subset \{1,...,n\}$, $\{\alpha_i\}_{i=1}^N$ is a vector of positive numbers that add up to 1, and $w_i$ is a set of (possibly negative) weights.

The first term in the function is a submodular function of $S$. The second term is a modular function of $S$. I know there exist algorithms (Fujishige-Wolfe) to minimize a general submodular function. Are there known algorithms to quickly minimize the sum of the entropy of a set and a modular function?

Unless I'm mistaken, you can solve your problem in $O(n\log n)$ time using a greedy algorithm.

Minimizing $f(S)$ is equivalent to maximizing
$$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in S'} \alpha_i\big) \log \sum_{j \in S'} \alpha_j$$
for $b_i=w_i + \alpha_i\log(\alpha_i)$.  Here $S'$ is the complement of your $S$.

Assume WLOG that $\alpha_i>0$ (otherwise $i\in S'$ iff $b_i>0$).

Introduce indicator variable $x_i$ for the event that $i\in S'$,
then relax the problem by allowing $x_i\in[0,1]$.  The relaxed problem is to choose $x\in[0,1]^n$ maximizing
$$\textstyle G(x) = \sum_{i} x_i b_i + \big(\sum_i x_i \alpha_i\big) \log \sum_{j} x_j \alpha_j.$$
The partial derivative of $G(x)$ with respect to $x_i$ is
$$\textstyle b_i + \alpha_i\, \lambda(x),$$
where $\lambda(x) = 1 + \log\sum_j x_j \alpha_j$.
So at any optimal $x$, you have
$$x_i = \begin{cases}
0 & \text{if}~ b_i/\alpha_i < -\lambda(x) \\
1 & \text{if}~ b_i/\alpha_i > -\lambda(x) \\
? & \text{if}~ b_i/\alpha_i = -\lambda(x).
\end{cases}
$$

WLOG, the ratios $b_i/\alpha_i$ are distinct for each $i$ (otherwise an insignificant perturbation of the $b_i$'s makes them so).  So only a single $x_i$ is undetermined by the above condition.  Since $G(x)$ is convex, one of the two neighboring solutions $x'$ (obtained by changing that $x_i$ to zero or one) has $G(x') \ge G(x)$.
Hence, defining $S_j = \{i : b_i/\alpha_i \le b_j/\alpha_j\}$ and $S_0=\emptyset$, the optimal set is $S_j$ for some $j\in\{0,\ldots,n\}$.

So, here is the algorithm.  Assume that $\alpha_i > 0$ for each $i$, and (by sorting first in $O(n\log n)$ time), that
$b_1/\alpha_1 > b_2/\alpha_2 > \cdots > b_n/\alpha_n$.
Enumerate all sets $S_j$ (and compute $G(S_j)$ for each) in $O(n)$ time, then take the best.


Generating a language from a given grammar So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there any software out there that does this? Or a library?

Many thanks in advance

Since you want to generate -all- words of a given length, it really doesn't matter if it's stochastic/probabilistic or deterministic, you just want to see if a word is possible (the following method should be modifiable to also compute the probability of any given word.

Two methods, one theoretical and cool and programmable in a couple lines of inscrutable Mathematica, or a practical efficient algorithm which I'd rather not both to code in ML/Haskell.

you can interpret a (context free) grammar as defining a set of polynomials equations (the way the theory works, you just can't do this for context-sensitve or worse grammars). Use Groebner bases to simplify the system, and solve for the generating function, from which you can then extract the number of -derivations- (we don't now if it's unambiguous) of words of a given size. Yes, that is a short sentence to describe the work you'd have to do, and that's not even from scratch. (For a regular grammar, Groebner bases is kind of a jack hammer when all you need is the small jeweler's hammer of the Kleene algorithm to generate the regular expression for the language from the right linear grammar converted to NFA. And then the generating function can (almost!) be read straight off from the regexp.
a way to implement the above, bypassing all the intensive algebraic manipulation, don't bother with all that fix-point computation (that's really what the algebraic manipulation is doing for you). Instead, create a vector of length $n$ for each variable, set them all to 0's. Then operate on each rule thinking of union as vector addition and concatenation as vector convolution (if A <- B C, then $a_k = \sum a_j b_{k-j}$, and the base case is a terminal which is $\langle 0,1,0,0,0,0... \rangle$. (this method might work for CSGs but I think it takes longer to converge).

I'm sure there's an easier way to do it in a straightforward manner, but you know how it is, sometimes the complicated big guns that take a steep learning curve to manage are some how more familiar and easier to think about than an obvious simple solution.


How can I formalize key value stores with set theory? I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category theory? I want to use some more simple and lightweight mathematics for the mathematical description of key-value stores. Set theory looks like it might offer some possibilities.

You did not say why you want a formalization, but presumably you want to do things with it, for instance prove properties of dictionaries and operations on them. In fact, your question can be understood in two ways: you want a mathematical description of dictionaries, or you want a computer formalization of dictionaries.

For a computer formalization have a look at the Coq standard library module FMaps, and if someone can find something better, please post it in the comments or just edit this question.

For a mathematical description all you have to note is that a dictionary is the same thing as a mapping with a finite domain. That is, if we have a dictionary (using Python style syntax):

d = { 'a' : 1, 'b' : 3, 'c' : 2 }

that is the same thing as a map $d$ whose domain of definition is the set $\{a, b, c\}$ and is defined as:
$$ d(a) = 1, \quad d(b) = 3, \quad d(c) = 2.$$
So now you can take any mathematical description of a map and use that. In set theory we would say that $d$ is the set of ordered pairs
$$\{(a,1), (b,3), (c,2)\}.$$


Example of #P-intermediate problem The previous question

Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn't find a reference.

An Answer to the previous question

Use Schöning's theorem:

  Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:

  $A_1 \notin C_1$, $A_2 \notin C_2$
  $C_1$ and $C_2$ are recursively presentable,
  $C_1$ and $C_2$ are closed under finite variations.

  Then there exists a recursive set $A$ such that:

  $A \notin C_1$, $A \notin C_2$,
  if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$.

For the purposes of counting dichotomy theorems, the two relevant classes of decision problems are $\text{P}$ and $\text{P}^{\#\text{P}}$.

My question

  Is there a concrete example of #P intermediate problem under some plausible assumption?
  More specifically, is there an explicit function $F$ satisfying the following conditions?
  $F\notin \mathsf{FP}$ and $F$ is not  $\# \mathsf{P}$-complete.

Assuming $\mathsf{PH}$ does not collapse and that Graph Isomorphism is not in $\mathsf{P}$, then $\# GI$ (the counting version of graph isomorphism) satisfies your conditions. This is because $\# GI \equiv_m^p GI$.


Context-sensitive grammar for SAT? By a classic result of Kuroda, the complexity class NSPACE[$n$] (also known as NLIN-SPACE) is precisely the class CSL of context-sensitive languages.  The satisfiability problem SAT is in NSPACE[$n$], since a linear-sized guess for a solution can be checked with at most a linear amount of overhead for book-keeping.  This means that SAT must have a context-sensitive grammar (CSG).

  Has anyone attempted to provide a CSG for SAT?

I realise many questions related to CSLs are undecidable (for instance deciding if a given CSG generates the empty language).  Even given a CSG for SAT one would still have to overcome the obstacle that deciding membership in the language given by a CSG is PSPACE-complete in general.  But it might be the case that the membership problem for the CSG that defines SAT is in NP, due to some special structure of the language.  Rephrasing, to address comment by MCH: But it might be the case that the membership problem for the CSG that defines SAT could be shown to be in NP due to some special structure of the grammar, and not because we already know it must be in NP.

S.-Y. Kuroda, Classes of languages and linear-bounded automata, Information and Control 7(2) 207–223, 1964.  doi:10.1016/S0019-9958(64)90120-2

Clarification:

The intended focus here is the special feature of the grammar for SAT which allows it to be recognized by an NTIME[poly($n$)] machine, rather than the NSPACE[$n$] $\subseteq$ DTIME[$2^{O(n)}$] bound.

The proof of Theorem 3 in Landweber's 1963 paper constructs a CSG from a linear-bounded automaton.  (Kuroda provided the converse, constructing a linear-bounded automaton for any CSG.)  However, Landweber's procedure does not seem to yield a grammar for SAT that is of special form: all NSPACE[$n$] recognizers are treated in the same generic way.  In other words, it is not clear why the SAT CSG should have an NP membership problem, rather than being PSPACE-complete.  I was hoping for a more explicit construction that uses the NP-ness of SAT in some essential way.

Perhaps a better, more precise, question is whether:

there exists a linear-bounded automaton that recognizes SAT,
from which one can extract a CSG,
so that the language defined by the CSG is in NP due to some feature of the grammar (and not because we already know it is in NP)?

In the intervening five decades, surely someone has tried to do this!  Since I can't find anything published along these lines, I would be interested in understanding why this approach did not work, or a pointer to work I have missed.

Peter S. Landweber, Three theorems on phrase structure grammars of type 1, Information and Control 6(2) 131–136, 1963.  doi:10.1016/S0019-9958(63)90169-4

Though not directly constructing a context sensitive grammar for SAT, the following paper might shed some light.

W. C. Rounds, Complexity of recognition in intermediate Level languages, Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

The paper by Rounds gives a one-way nondeterministic stack automaton (1-NSA) recognizing SAT, and then shows the membership problem of 1-NSA (and its proper superset, Aho's Indexed Grammar) is in general in NP. In other words, SAT as a CSL/linear-bounded-automata is special in the sense that it uses its memory only as a stack.


Chernoff-type Inequality for pair-wise independent random variables Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value and the deviation. Is there a Chernoff-type inequality for any sum of pairwise independent random variables? In other words, is there a result that shows the following: the probability that a sum of pairwise independent random variables deviates from its expected value is exponentially small in the expected value and the deviation?

Pairwise independence is not enough for a Chernoff-type bound on the expectation.

This follows from the fact that there are $poly(n)$-size sample spaces on $n$ 0-1 random variables, where all the variables are pairwise independent, and each is variable is uniform (it is $1$ with probability $1/2$). So the expected value of their sum is $n/2$. But because there are only $poly(n)$ possible events in the sample space, even the probability that a sum is exactly a particular value $v$ is at least $1/poly(n)$ (hence, it can't be at most $1/exp(n)$).

For a reference to this sample space construction, see pages 11-12 in this survey.


NP-hardness of a bilinear program? Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

subject to

$b_i\leq x_i\leq c_i$   for each $i\in [n]$;
$0\leq y_i\leq 1$   for each $i\in [n]$;
$y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$;
$\sum_{i\in [n]} x_i=1$

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?

Your objective is to minimize the convex function $-\sum_{i=1}^n(x_i−a_i)y_i$ subject to a system of linear constraints on the continuous variables $x_i$ and $y_i$.

Such convex minimization problems are polynomially solvable by so-called interior point methods; see for instance the book by Stephen Boyd and Lieven Vandenberghe: "Convex Optimization"; free pdf copy at: http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf