texts: Bounding the rate of increase of the price of anarchy across equilibrium concepts

texts:
We know and love a bunch of nested classes of solution concepts:

PN: Pure Nash Equilibrium
MN: Mixed Nash Equilibrium
CE: Correlated equilibrium
CCE: Course correlated equilibrium.

The relationship between these sets is:
$$PN \subset MN \subset CE \subset CCE$$
We can consider the price of anarchy over any one of these solution concepts: the worst case social welfare for any profile in the set, divided by the optimal social welfare:
$$POA(S) = \max_{s \in S}\frac{COST(s)}{OPT}$$
So, by the above containments:
$$POA(PN) \leq POA(MN) \leq POA(CE) \leq POA(CCE)$$
My question: are their known bounds on how fast this quantity can grow? It is possible to have a game with $POA(PN)$ finite, but $POA(CCE)$ unboundedly large. But if I know $POA(PN)$ is finite, does $POA(MN)$ also have to be finite? $POA(CE)$? How much larger can they be?


texts: Maximum Positive Negative Set Cover Problem

texts:
I am considering the following problem.

Input: Given two disjoint subsets $A$ and $B$ and a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq A \cup B$ for all $i=1\ldots k$.

Solution form: A collection $C' \subseteq C$.

Objective: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| + \left|B \setminus\left(\bigcup\limits_{c \in C'} c\right)\right|$.

That is, maximize the nodes in A covered plus the nodes in B not covered.

I am wondering the hardness of approximation.

Related work:

If we consider minimizing the objective, it becomes the problem studied in the following paper.

Miettinen, Pauli. "On the positive–negative partial set cover problem." Information Processing Letters 108.4 (2008): 219-221


texts: Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

texts: I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen.  I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does anyone have suggestions?


texts: Why did Kolmogorov publish Karatsuba's algorithm?

texts:
Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy of Sciences 145: 293–294.

According to Karatsuba (1995, "The complexity of computations", Proc. Steklov Institute
of Mathematics 211: 169–183), this paper was actually written by Kolmogorov (and possibly Ofman) without Karatsuba's knowledge. By modern standards this seems a strange and grave breach of ethics.

Why would Kolmogorov have done this? What did he gain?


texts: Does fixed hyperparameters perform well regardless the number of training examples?

texts:
I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper.

I'm interested in deep learning network models and have a question about this.

Suppose we have a feedforward neural network models with different hyperparameters (for example, the number of layers, neurons and so on), say $H_1,..., H_n$. Also assume all the samples are selected from a particular distribution.

First we got $100$ samples. If we find that a typical hyperparameter set, $H_i$, performs best. Now I want to increase the number of samples to $1000, 10000,$ even millions. Is $H_i$ still the best hyperparameter set to perform among $H_i$'s? I want to know whether there are references about such topics. The best is a mathematical proof about this fact.

Again, please tell me if this question is not proper to the community. Thanks a lot!


texts: Application of methods from dynamical system to the study of k-SAT and similar problems

texts:
I am looking for literature (survey and non-survey papers) about
transforming the k-SAT problem (or similar problems) into
a system of Ordinary Differential Equations (ODEs) and
study the solution of the k-SAT using methods from dynamical systems theory,
such as computing stable/unstable manifolds,
dynamics on strange attractors,
fixed point theory and so on.

Motivation:
I am not a computer scientist. I am a researcher working in the areas of applied dynamical systems, with focus on applying geometrical and topological methods to study chaotic phenomena. I am always looking for application of the nonlinear dynamical systems theory and I happened to come across the following paper today:
Optimization hardness as transient chaos in an analog approach to constraint satisfaction by Ercesy-Ravasz and Toroczkai, Nature Physics 2011
This paper is very interesting to me, and most of the dynamical systems theory used in it is pretty standard fare these days in my community.
I am looking for CS references that will help me understand the CS-part of this, mainly about solving problems like k-SAT using dynamical systems.


texts:
What is the funniest TCS-related published work you know?

Please include only those that are intended to be funny.  Works which are explicitly crafted to be intelligently humorous (rather than, say, a published collection of short jokes regarding complexity theory) are preferred.  Works with humorous (actually humorous, not just cute) titles are also accepted.

Please only one work per answer so the "best" ones can bubble to the top.


texts: How to sample a lot of independent uniform spanning trees?

texts:
There are a bunch of good algorithms for sampling a uniform spanning tree from a graph $G$. For example, Aldous/Broder and Wilson's algorithm are pretty efficient. However, each of these graphs only samples one tree at a time.

I have a graph that I want to draw a lot of independent uniform spanning trees from, and I want to know if there is an useful preprocessing kind of step I can do that will make it easy to draw a large number of independent, uniform spanning trees.

Here is one approach: the spanning trees can be put into an efficient bijection with the sandpile group. This suggests that a fast way to generate a lot of random spanning trees by: 1) computing the decomposition of the sandpile group into a product of (hopefully small) Abelian groups 2) Fix a spanning tree T, and draw randomly from this product of abelian groups, and apply them to T. (This is discussed here: https://arxiv.org/pdf/1107.1313.pdf see 6.2)

Has anyone tried this? Are there other methods for drawing a lot of independent uniform spanning trees that are worth looking in to?

Edit: After we skimmed the paper I'm a little dismayed about some of the constants that appear in their bounds of efficiency. Our graph G is naturally a ribbon graph, so it's possible to use the rotor router action ( https://arxiv.org/abs/0801.3306 ) instead of the bijection described in the first link. It's not clear to me if this will run any faster... we'll experiment and see.


texts:
What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?

Update: I forgot to mention that I'm interested in languages not known to be in $coNP$.


texts: What is the state of the art research in analysing algorithms on GPU architectures?

texts:
I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved when using a specific GPU.

However I could not find a lot of papers on theoretically analysing algorithms, proving bounds etc when working in this new model.

Is it because that is too difficult to do or not very interesting?


texts: Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

texts:
I'd like to have proof that Chaitin's constant for lambda calculus and/or SKI combinatory logic is pretty small. I've found some approximations (accurate to about 63 binary digits) for truing machines and as expected they were low, below 1% in fact. I can't find any bounds for lambda calculus or combinatory logic. I'd really just like to show that it is less than 10% to 20%. Does anyone know of such a paper or how to get such an awnser?

I also found this but it doesn't have a reference for how it got that answer. If correct it would show that the probability is between 0.125 and 0.0625 which is great for me! Does anyone have a citation for this?


texts: Lower bound on number of oracle calls for solving $n$ instances of the halting problem

texts:
I encountered the following question, which is an easy exercise (spoiler below).

We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of them halt on $\epsilon$. That is, we need to output $\{i: M_i\text{ halts on }\epsilon\}$. We are given an oracle for the halting problem, but we have to use it a minimal number of times.

It is not hard to show that it can be done with $\log (n+1)$ calls.

  My question is: can we prove a lower bound? Is there reason to suspect that such a bound will be very hard to find?

The answer to the question itself (spoiler, hover mouse):

   Consider the case of $3$ TMs. We can construct a TM $H_2$ that runs $M_1,M_2,M_3$ in
 parallel, and halts if at least two of them halt (otherwise it gets stuck).
 Similarly, we can construct a TM $H_1$ that halts if at least one of them halts.
 We can then call the oracle on $H_2$. If it halts, then we can run the machines in
 parallel, and wait for one to halt. We can then call the oracle on the last one. If the
 oracle says "no", then we run the oracle on $H_1$. If it halts, then we run the machines
 until one halts, and it's the only one that halts. If $H_1$ does not halt, then none of
 them halt. Extending this to $n$ machines is easy.

The first observation about this question is that it seems impossible to solve using information-theoretic tools, since we crucially rely on our ability to obtain information by running the machines without the oracle.


texts:
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense : there is a function $\sigma:\Sigma^*\to Q$ which can be used to pilot runs of $A$. We formalize this by the following conditions :

$\sigma(\epsilon)=q_0$

for all $u\in\Sigma^*$ and $a\in\Sigma$, $(\sigma(u),a,\sigma(ua))\in\Delta$

for all $w=a_0a_1a_2\dots\in L$, the run piloted by $\sigma$ is accepting, i.e. the sequence $\sigma(\epsilon),\sigma(a_0),\sigma(a_0a_1),\sigma(a_0a_1a_2),\dots$ has infinitely many elements in $F$.

To subsume the conditions, $A$ can accept any word of its language without having to guess anything about the future.
Then, under these assumptions on $A$, is it true that $A$ can be determinized just by removing transitions ? In other words, can we always choose the next transition depending only on the current state and letter ? Is there any reference on the subject ? The same question can then be asked on co-Büchi automata, and more generally on parity automata.
What is known
Here are some partial results.
First, we can restrict $\sigma$ to nondeterminstic choices between states having the same residual. Indeed, if $L(q)$ is the language accepted from $q$, an accepting strategy cannot choose $q_1$ over $q_2$ at some point, if there is $w\in L(q_2)\setminus L(q_1)$.
Notice that the remaining choices do matter, so despite the intuition, this is not enough to get rid of the nondeterminism. This is because it is possible to stay ad infinitum in a good residual (i.e. the remaining of the word is in the residual), but reject the word because not infinitely many Büchi states are seen. This is the main difficulty of the problem : an infinite run can be wrong, without making any fatal mistake at some point.
Second, the problem is solved if $L=\Sigma^\omega$, i.e. all words are accepted by $A$. In this case, we can view $A$ as a Büchi game where Player I chooses input letters and Player II chooses transitions. Then we can use positional determinacy of Büchi games to extract a positional strategy for Player II. This arguments even works in the more general case of parity automata. The difficulty of this problem comes from the fact that some words are not in $L$, and in this case the strategy $\sigma$ can have any behaviour.
Third, here is a proof that under the assumptions, the language $L$ is in the class of deterministic Büchi languages, witnessed by an automaton with states $2^Q$.
Notice that this implies that $L$ cannot be any $\omega$-regular language, for instance  if $L=(a+b)^*a^\omega$, no strategy $\sigma$ matching the conditions can exist.
We start by restricting the transitions according to the first remark : the only choices we can make do not impact on the residual language. We only take successors with the maximum residual, they must exist because $\sigma$ exists.
Then, we build $A'=\langle \Sigma, 2^Q, \{ q_0\},F',\Delta'\rangle$ in the following way. $A'$ is the subset automaton of $A$, but every time a Büchi state $q$ appears in the component, all other states can be removed from the component, and we start again from the singleton $\{ q\}$. Then we can set $F'=\{\{ q\} : q\in F\}$. We can verify that $A'$ is a deterministic Büchi automaton for $L$.
Finally, by putting together the second and the third remarks, we can always obtain a finite memory-strategy $\sigma$, by using a positional strategy for Player II in the game $A\times A'$ where Player I chooses letters, Player II chooses transitions in $A$ and wins if $A$ accepts whenever $A'$ accepts.


texts: What is the difference between a second preimage attack and a collision attack?

texts:
Wikipedia defines a second preimage attack as:

  given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1).

Wikipedia defines a collision attack as:

  find two arbitrary different messages m1 and m2 such that hash(m1) = hash(m2).

The only difference that I can see is that in a second preimage attack, m1 already exists and is known to the attacker. However, that doesn't strike me as being significant - the end goal is still to find two messages that produce the same hash.

What are the essential differences in how a second preimage attack and collision attack are carried out? What are the differences in results?

(As an aside, I can't tag this question properly. I'm trying to apply the tags "cryptography security pre-image collision" but I don't have enough reputation. Can someone apply the appropriate tags?)


texts: Instance of FPT-reductions that is not a polynomial-time reduction

texts:
In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially in the parameter k. But in practice all the FPT-reductions I've seen are p-time reductions, which means W[t]-hardness proofs almost always imply NP-completeness proofs.

I wonder if someone can give me a FPT-reduction that indeed runs exponentially in the parameter $k$. Thanks.


texts: Optimization as LP on the convex hull of its solution space

texts:
I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem (even though enumerating the constraints that define the polytope could be computationally very expensive).

Is this correct? If so, what class of optimization problems can be re-written this way? and what references can I use to back up this claim?


texts: Generating Graphs with Trivial Automorphisms

texts:
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.

It is "commonplace" (yet controversial!) to assume the existence of BPP algorithms capable of generating "hard instances of the Graph Isomorphism problem." (Along with a witness of isomorphism.)

In my contrived protocol, I'm gonna assume the existence of such BPP algorithms, which satisfy one additional requirement:

Let the generated graphs be $G_1$ and $G_2$. There's just one witness (permutation) that maps $G_1$ to $G_2$.

This implies that $G_1$ has only trivial automorphisms. In other words, I'm assuming the existence of some BPP algorithm, which works as follows:

On input $1^n$, generate an $n$-vertex graph $G_1$, such that it has only trivial automorphisms.
Pick a random permutation $\pi$ over $[n]=\{1,2,\ldots,n\}$, and apply it on $G_1$ to get $G_2$.
Output $\langle G_1,G_2,\pi \rangle$.

I'm gonna assume that, in Step 1, $G_1$ can be generated as needed, and
$\langle G_1,G_2 \rangle$ is a hard instance of the Graph Isomorphism problem. (Please interpret the word "hard" naturally; a formal definition is given by Abadi et al. See also the paper by Impaliazzo & Levin.)

  Is my assumption reasonable? Could anyone please point me to some references?


texts:
What is the current state of the art for $L_0$ estimation when not in a stream?  I assume that the total number of (not necessarily distinct) objects is very large so you can only see a sample of them.

I found http://en.wikipedia.org/wiki/Good%E2%80%93Turing_frequency_estimation but that seems rather older than I was expecting.


texts: Ambiguity in regular and context-free languages

texts:
I understand the following claims to be true:

Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string.
When there are derivations of some string in a given CFG that attribute different parse trees, the CFG is ambiguous.
Some context-free languages generated by ambiguous CFGs are also generated by unambiguous CFGs.
Some languages are such that the only CFGs that can generate them (and there are some such) are ambiguous.

Q1. I understand it also to be undecidable whether an arbitrary CFG is ambiguous, in the sense of point 3 above. Or is it rather that it's undecidable whether a context-free language is ambiguous, in the sense of point 4? Or are both undecidable?

Q2. Which of points 1-4 become false when we replace "context-free" with "regular"? Are regular grammars and languages always unambiguous?


texts: Information channel with symmetric channel matrix

texts:
It took me a while to figure out that a "symmetric channel" does not mean a channel with a symmetric channel matrix. (Rather, "symmetric channel" means that the rows of the matrix are all permutations of each other, and so are the columns.) This is obvious in hindsight because an arbitrary channel can have a different number of input symbols and output symbols, in which case the matrix isn't square and so can't possibly be symmetric.

Is there a word for a channel with a symmetric channel matrix (implying it has the same number of input symbols and output symbols)?

Does this property simplify the computation of channel capacity at all?


texts: Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

texts:
The standard problem 1-in-3 SAT (or XSAT or X3SAT) is:
Instance: a CNF formula with every clause containing exactly 3 literals
Question: is there a satisfying assignment setting precisely 1 literal per clause true?

The problem is NP-complete and remains hard even if no variable occurs negated. I wonder whether this problem becomes easy or remains hard if each variable is required to occur at least once positively and at least once negatively.

The usual reduction from 3SAT showing that 1-in-3 SAT is hard replaces a clause $(x\lor y \lor z)$ by clauses $(\lnot x \lor a \lor b)$, $(y\lor b\lor c)$, $(\lnot z \lor c \lor d)$ where $a,b,c,d$ are fresh for each clause. Thus, this reduction doesn't help in answering my question. I've had trouble coming up with a gadget showing hardness of this variant, since if exactly 1 literal in a clause is true, then non-symmetrically 2 literals are false. If it turns out to be easy, thinking in terms of partitions of the clause set might do it, but I can't see how.


texts: I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?


texts: Reconstructing a tree from separator queries

texts:
Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in constant time by an oracle. We know the value of $n$, the number of nodes in the tree. The objective is to minimize the time taken to output the tree in terms of $n$.

Does there exist an $o(n^2)$ algorithm for the above problem?

Assume that the degree of any node in $T$ is at most 3.

What I know

Bounded diameter case is easy. If the diameter of the tree is $D$, then we can get a divide-and-conquer algorithm:

Any binary tree has a good separator that divides the tree into components of size no less than 1/3n.

Pick any vertex x. If it is a good separator label that and recurse.
Find all the 3 neighbors of x.
Move in the direction of the neighbor which has the largest number of nodes. Repeat Step 2 with the neighbor.

Since finding the separator takes at most $D$ steps, we get a $O(nD\log n)$ algorithm.

An $O(n\;\log^2 n)$ randomized algorithm. (moved from comments below)

Pick two vertices x and y randomly. With 1/9 probability they will lie on the opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a separator, if not do binary search.

It takes $O(n\;\log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm.

Background. I learnt about this problem from a friend who works in probabilistic graphical models. The above problem roughly corresponds to learning the structure of a junction tree using an oracle which, given three random variables X,Y and Z, can tell the value of mutual information between X and Y given the value of Z. If the value is close to zero, we may assume that Z lies on the path from X to Y.


texts: Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

texts:
I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in automated theorem proving and mainly the theory behind these areas (I don't like implementation that much). Which universities are specialized in these fields?
Thanks in advance!


texts: Why are so few natural candidates for NP-intermediate status?

texts:
It is well known by Ladner's Theorem that if ${\mathsf P}\neq \mathsf {NP}$, then there exist infinitely many $\mathsf {NP}$-intermediate ($\mathsf{NPI}$) problems. There are also natural candidates for this status, such as Graph Isomorphism, and a number of others, see
Problems Between P and NPC. Nevertheless, the vast majority in the crowd of known $natural$ $\mathsf {NP}$-problems are known to be either in $\mathsf {P}$ or $\mathsf {NPC}$. Only a small fraction of them remains a candidate for $\mathsf {NPI}$. In other words, if we randomly pick a natural $\mathsf {NP}$-problem among the known ones, we have very little chance to pick an $\mathsf {NPI}$ candidate. Is there any explanation for this phenomenon?

I could think up 3 possible explanations, more on the philosophical side:

The reason for having such a small fraction of natural $\mathsf {NPI}$ candidates is that     $\mathsf {NPI}$ will eventually turn out to be empty. I know, this implies ${\mathsf P} =\mathsf {NP}$, so it is very unlikely. Nevertheless, one could still argue (though I'm not one of them) that the rareness of natural $\mathsf {NPI}$ problems is  an empirical observation that appears to actually support ${\mathsf P} =\mathsf {NP}$, in contrast to most other observations.
The smallness of "natural-$\mathsf {NPI}$" represents a kind of sharp phase transition between easy and hard problems. Apparently,  the meaningful, natural algorithmic problems behave in a way that they tend to be either easy or hard, the transition is narrow (but still exists).
The argument in 2 can be taken to the extreme: eventually all problems in "natural-$\mathsf {NPI}$" will be put into $\mathsf {P} \cup \mathsf {NPC}$, yet ${\mathsf P}\neq \mathsf {NP}$, so $\mathsf {NPI}\neq \emptyset$. This would mean that all remaining problems in $\mathsf {NPI}$ are "unnatural" (contrived, without real-life meaning). An interpretation of this could be that natural problems are either easy or hard; the transition is only a logical construct, without "physical" meaning. This is somewhat reminiscent to the case of irrational numbers, which are perfectly logical, but do not arise as the measured value of any  physical quantity. As such, they do not come from physical reality, they are rather in the "logical closure" of that reality.

Which explanation do you like the best, or can you suggest another one?


texts: Is it worthwhile to try to prove a conjecture by mapping it to a Turing machine?

texts:
Lets assume the proof of a conjecture, for example, the famous Goldbach conjecture. Is it possible to try to prove or disprove such a conjecture by devising a Turing machine that accepts if the proof is possible.
So, for Turing machine M,

If, the conjecture is provable, accept, else reject.

So, in essence, we don't try to find a proof of the conjecture, but, try to find whether its provable, something like zero-knowledge proofs.

Additional Details:
I felt the way most of these conjectures go, is they say: For all n, C holds true.
So, in essence, even if it can be shown that C holds up to some n, but, it hasn't been able to be derived for all n. And, this seems to bear a striking similarity to the Halting problem. So, I felt a mapping must be worthwhile to study/research.


texts: Finding the largest set of points of limited diameter

texts:
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?


texts:
I already asked this question on stackoverflow, but maybe it is better suited for this site.

The problem is:

I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped at any point.  Sometimes there is no solution, so I need to throw an exception then.

Example:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5
6 5     <-- swapped
8 3     <-- swapped

^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result.
or

in pairs:
1 5
6 9

out:
not possible

Thanks

edit:

Tom Sirgedas on SO proposed the best solution. It is really easy to implement and works in O(log(n) * n). Thank you all for the answers and interest. I really enjoyed mjqxxxx analysis.


texts: Is there a method of solving the game of "war"

texts:
I was thinking of determining the game of war. I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal.

Because in war the order of the cards matter it is also not a question of simply summing up the "power" of the cards. If the decks were Q-Q-J-J and K-K-1-1 then the game would go as follows even though the first player has more power:

Q-K (QJJ, K11)

Q-K (JJ, 11QK)

J-1 (J, 1QKQK)

J-1 (1J, QKQK)

1-Q (J1J, KQK)

J-K (1J, QK1Q)

1-Q (J, QK1QJK)

J-K (∅, K1QJK1Q)

∅ (∅, 1QJK1QJK)

I've been trying to think of a method of determine the winner of the game without going through the entire deck each and every time (and thus possibly going for thousands of iterations.)

If you could provide me with some pointers to start thinking about this question - that would be great!

I wasn't exactly sure where to ask this question: so if this is off topic here please redirect me.


texts: Composition theorem for randomized communication complexity

texts:
I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find
$$ R_{1/4} (f \circ g^{n}) = \mathcal{O}(RT_{1/4}(f)R_{1/4}(g)\log RT_{1/4}(f)) $$ coming from Nisan's paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf, where $RT(f)$ is denoted as query complexity and $R(f)$ is the randomized communication complexity.
However, I am not sure I notice such a conclusion has ever been drawn in Nisan's paper. The closest claim I suppose is the lemma 3, where Nisan claims that

Let $G$ be a family of functions. If a function $f$ can be computed by a circuit consisting of $s$ gates from $G$ then, for all $k$, $R^{k}(f) \leq s \cdot R^{k}_{1/3s}(G)$.

My question is : is it the lemma leading to the theorem 5 of the first paper, and how? Or am I missing something here?


texts: Is there a name for trees were siblinghood cannot happen between a leaf and a non-leaf?

texts:
The title of this question pretty much says it all.
I would like to know if there is some standard name for trees in which, if any two nodes are siblings, then either they are both leaves, or they are both non-leaves.
One variation of the same situation occurs in trees with two types of nodes, such that one of these two types can have children, and the other one cannot.  (An everyday example of this is a simple file system consisting exclusively of "folders" and "files".)  In this case, the condition in the title could be modified to requiring that siblinghood can happen only between nodes of the same type.  (With this variation, the number of children a node happens to have plays no role in whether the tree containing tree satisfies the condition or not.)
Is there a standard name for either of the two variations described above?
(P.S. Should I post this in math.stackexchange.com instead.)


texts: How to compute powers of square matrices?

texts:
Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?

The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.

For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).

Can matrix exponentiation in the general case be sped up?

Fast exponentation suggest a variation of this question is useful, too:

Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?


texts:
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:

Input: integer n > 1.

Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b > 1$, output composite.
Find the smallest $r$ such that $ord_r(n) > (\log_2 n)^2$ (if $r$ and $n$ are not coprime, then skip this $r$).
For all $2 ≤ a ≤\min(r, n−1)$, check that $a$ does not divide $n$: If $a|n$ for some $2 ≤ a ≤ \min(r, n−1)$, output composite.
If $n ≤ r$, output prime.
For $a = 1$ to ${\displaystyle \left\lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log_{2}(n)}\right\rfloor}$ do

if $((X+a)^n - (X^n+a))≠0\bmod (X^r − 1,n)$, output composite;
Output prime.

After Emil's comment note 5. is not in $NC$ hierarchy. It seems step 2. is not in $NC$ since $GCD$ is not known to be in $NC$.

Since we have $r\leq polylog(n)$ unconditional bound we may even look for smallest $r$ parallely (by testing $r|(n^k-1)$ in $NC$ at each of the parallel processor testing a different $r$) if coprimality is in $NC$ and we can use a boolean logic to combine steps 2 and 5 so they run in parallel. All other steps seem parallelizable wholly with some boolean logic.

  So is it true that if coprimality testing (rather than $GCD$ finding) and polynomial identity testing for this particular polynomial in 5. proved in $NC$ then primality is in $NC$?

It seems it is possible coprimality is in $NC$. Note this is easier than $GCD$ finding.


texts: Graduate studies (PhD) in CS Theory vs. Applied Math

texts:
Given most American universities only accept applications in only one field, I'm trying to figure out what are the advantages/disadvantages of applying to a CS theory program vs an applied math program given one's interest lies somewhere in both departments.

To be more specific, my areas of interest in decreasing order are
1. Combinatorics (Both algebraic and extremal),
2. Optimization (Both convex and combinatorial),
3. Probability theory, randomized algorithm, and information theory.

I don't exactly know on what or with whom I want to work which makes applying to graduate programs a huge headache. So far my understanding is applied math programs are more flexible given CS theory groups are usually very small and focused. On the other hand, I feel a CS degree would fare better in industry if one happened to venture that path.

So to reiterate my question, for someone who doesn't exactly know what he wants to do but generally interested in aforesaid topics, which is better? CS Theory or Applied Math


texts:
I have a working genetic algorithm which uses a few genetic operators on pairs of individuals.

These two individuals are selected by fitness-proportional (roulette-wheel) selection, that is, an individual's likelihood of being selected is proportional to its fitness.

The way a pair is selected is simply by selecting a single individual from the population twice. Sometimes, the same chromosome can be selected twice, and then all genetic operators are simply operating on two copies of the same individual.

For example, crossover is meaningless in this case.

My question is, should I take measures to ensure the pair that are selected are not equal?

Or should I mitigate the problem by performing operators on single individuals first (such as mutation), so the pair are more likely to be different when it comes to things like crossover?

Or should I ignore the problem completely, "let nature take its course", and allow an individual to breed with itself?


texts: Complexity of finding a consistent hyperplane

texts:
Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample point $d$-tuples which span all candidate hyperplanes, and the dimension $d$ is the hardness parameter (see the paper by Höffgen et al.)
What about the realizable case? Here two natural algorithms come to mind: the Perceptron and Linear Programming. The Perceptron has runtime quadratic in inverse margin. Since we currently don't know of any strongly polynomial LP solvers, all current methods depend, in the worst case, on the configuration of the labeled points -- i.e., the runtime also depends on the margin.
Question: Is there a strongly polynomial algorithm for finding a consistent hyperplane?
Edit (04-Oct-2018). I had accepted an answer but there is a problem with it, so as of now the status of the question is unknown. Is consistent hyperplane as hard as general LP?
Edit 2 (06-Oct-2018). Status: solved!


texts: Congruency check for set of points in 3D using inertia tensor

texts:
You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and rotation which set one-to-one correspondence between points in $A$ and points in $B$.

One can come up with following $O(n^2)$ algorithm. First of all, make a transition in such a way that centers of mass are matched. After that calculate convex hull of both sets. It will have $O(n)$ nodes. One can fix some edge from convex hull of $A$, then try to match it with all possible edges from convex hull of $B$ in $O(n)$ and check if it produces correct matching in another $O(n)$.

I suggest the following improvement to $O(n)$ which should work unless sets of points have some special kinds of symmetry. Consider inertia tensors of this set of points

$$I=\sum\limits_{i=1}^n\begin{pmatrix}x_i^2 & -2x_iy_i & -2x_i z_i \\ -2x_i y_i & y_i^2 & -2y_iz_i \\ -2x_iz_i & -2y_iz_i & z_i^2\end{pmatrix}$$

Since this is symmetric matrix, there is basis of its eigenvectors. Thus we can try to only match the main axes of inertia. This works find but only if all three eigenvalues are distinct. I assume there is also a way to solve the problem in the case when two eigenvalues coincide by reducing in to $2D$ case along the left axis but if all eigenvalues match there's nothing we can get from inertia tensor.

So, is it possible to avoid this issue with inertia tensor having same central main moments of inertia? And in general, are there any known algorithms to solve the problem in $o(n^2)$? Also are there any research considering this approach to solve the problem?


texts: What is "Flynn's algorithm" relating to linked lists?

texts: The other day, I came across an offhand mention of something called "Flynn's algorithm," which, as I gathered, had something to do with a linked list.  But that's all I was really able to discern.  Can anyone point me to a paper, or at least a web page that might further enlighten me?


texts: Are there wholistic models of the universe in terms of Quantum Complexity?

texts:
Quantum Computers are an abstraction (a finite circuit of matrices + measurements) that captures the computability properties of local quantum devices.

But is there a notion, akin to "computability", that transfers a wholistic model of the universe (from Physics) into an abstract model into computer science.

For instance, it is natural to ask these two questions:
(a) Can the notion of a finite quantum circuit be generalized to a continuous one. The measurements are the quirky part, but the answer is generally yes, resulting in an object similar to a manifold over matrix transformations (but slightly more general).
(b) Given you believe in (a), does a "quantum manifold" (specifically its symmetries, i.e. cycles) capture important conservation laws in the computational properties of the universe itself.

Are there be papers going down this path in the literature already?


texts:
I came across the following definition in a paper:

We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: For every $n \geq 1$, call $f : N \rightarrow R$ n-approximable if there is a rational-valued computable approximation $\varphi$ such that $\lim_{k\rightarrow \infty} \varphi(x, k) = f(x)$ and such that for every $x$, the number of $k$’s such that $\varphi(x,k + 1) − \varphi(x,k) < 0$ is bounded by $n − 1$. That is, $n − 1$ is a bound on the number of fluctuations of the approximation.

Note that the $1$-approximable functions are precisely the lower semicomputable ($\Sigma_1^0$) ones (zero fluctuations). Also note that a set $A \subseteq \mathbb N$ is $n$-c.e. if and only if the characteristic function of A is n-approximable.

I have two questions.

Is this a commonly used principle? Google didn't give me any relevant results.
If I have an $n$-c.e. function $\varphi(x)$, with $\varphi(x,k)$ approximating it. Couldn't I just build a Turing machine $\varphi'(x, k')$ that dovetails the computation of $\varphi(x, k)$ until it sees two consecutive halting machines with $\varphi(x, k+1) < \varphi(x, k)$, stops the dovetailing, and outputs $\varphi(x, k+1+k')$ (ie. it computes $\varphi(\cdot, \cdot)$ but starting from k+1). Then, if $\varphi(x)$ is $n-c.e.$ (and not $n+1$-c.e.), it is also $n-1$-c.e., and by induction it is just approximable.

So the definition doesn't seem to make sense. Am I missing something?


texts: NP-Completeness of Certain Bounded Degree Graphs

texts:
I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems.

1) Is the set of all (G, k) where G is a graph with maximum degree of at most 4 and contains an independent set of size at least k in polynomial time or NP-complete?

2) Is the set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k in P or NP-complete?

Since both Independent Set and Clique are NP-Complete, my first instinct is to say that 1) and 2) are both NP-complete. However, due to the bounded degree restriction, that is likely not true. I am not quite sure what I should be reducing from. Since if I were to attempt to show they are in P, I would have to reduce from something in P and I don't know anything that are remotely similar except Clique and Ind. Set, but like I said, those are NP-complete. I would really appreciate any help I can get with those two proofs. Any proof or hint would be very welcome!


texts: Are there any concrete (or a rich source of) examples of application of $p$-adic numbers in computer science?


texts: Temporally Flat One-Way Quantum Computing

texts:
I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum Computing research as originated by Raussendorf & Briegel. One just needs to prepare a multi-partite entangled state as described by a graph, and then perform sequential measurements on each node or qubit (adaptive measurements for deterministic computations).

Another excellent aspect of this approach is that Clifford circuits can be implemented in a single-round of measurements as shown by Raussendorf, Browne and Briegel. These circuits can be classically simulated (efficiently) as shown by Gottesman and Knill so it is an interesting connection between classical simulation and temporal resources.

However, not all temporally flat Graph State MBQC circuits (consisting of one round of measurements) are believed to be simulatable classically. For example, families of circuits in the quantum circuit model consisting of commuting gates called IQP circuits as introduced by Shepherd and Bremner can be implemented in single time-step in MBQC. These IQP circuits are believed not to be classically simulatable (in computational complexity terms, it would lead to a collapse of the polynomial hierarchy).

See also a nice description of a class of circuits implemented in one time-step here. Given that commuting/diagonal unitaries can have some interesting behaviour but non-commuting circuits be classically simulatable. It would be interesting if there were non-commuting circuits that can be implemented but not yet shown to be classically simulatable.

Anyway, my question is:

  Are there other interesting circuits that can be implemented in a single time-step in MBQC?

Though I would prefer relations to computational complexity or classical simulation, I would find anything interesting.

Edit: After Joe's excellent answer below, I should clarify a couple of things. As Joe said (and somewhat embarrassingly I have said in one of my own papers), single measurement-round MBQC circuits are in IQP. To be more precise, I am interested in interesting circuits in the problems in IQP that can be implemented in one round of measurements in MBQC. Clifford circuits are an interesting example. If there any other examples which are classically simulatable that would be extremely interesting. Since simulating IQP circuits is believed to be unlikely classically, it would be interesting to find instances of circuits that are.


texts: Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

texts:
When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:

Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,H_2,\ldots,H_k$ of $\mathbb Z_2^n$ (where $\mathbb Z_2$ is the 2-element field).
Question: For every $x \in \mathbb Z_2^n$, let $n(x) = |\{H_i:x\in H_i \}|$. Is $n(x)$ a multiple of 3 for all $x$? Or, in other words, is every point of $\mathbb Z_2^n$ covered by $0$ modulo $3$ many of the affine subspaces?

Note that there are no conditions on $n$, $k$ and the dimension of the affine subspaces $H_i$.
The problem is clearly in coNP, but unfortunately I am not able to prove anything more about its complexity. My hope is for it to be coNP-complete, since this would have nice implications for our research. But also if it was in P or equivalent to some coNP-intermediate problem this would be a really interesting fact to know.
Two observations:

If we additionally assume that the codimension of all input subspaces $H_i$ is bounded by a constant (e.g. if every $H_i$ is a hyperplane) then the problem is in P. Thus any encoding of a coNP-complete problem would require using subspaces of arbitrary codimension.
I tried to encode the complement of some classical NP-complete problems, but did not succeed. In particular 'covering problems' like the Set cover problem seemed to be a natural choice. But that we count here 'modulo 3' seemed to be an obstacle in this approach.

Thanks for every hint! :) In particular references to possibly related problems in the literature would be very welcome!


texts: Let $\mathcal{B} = \{B_1, \dots, B_k\}$ be a set of Mutually Unbiased Bases (MUB) in $\mathbb{C}^n$, i.e. each $B_i$ is an orthonormal basis and for $v \in B_i, w \in B_j, i \neq j $ we have $|\langle v\vert w\rangle| = \frac{1}{\sqrt{n}}$. We are interested in discriminating between arbitrary vectors from $\mathcal{B}$. Is the optimal (worst case or average with uniform prior) POVM measurement identified explicitly anywhere in the literature (e.g. using Holevo criterion), at least for some specific constructions of MUBs?


texts: Properties of "second-order" NP (complete) languages

texts:
Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language:

  $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

It made me think of the following generalization. Let $A$ be a language in $\textsf{NP}$ and fix a corresponding verifier machine $M$. My question is, What is known about the language consisting of members of $A$ that have at least $f(n)$ witnesses (where $n$ is the size of the input and witnesses are relative to the verifier $M$)?

...

More formally: We have a deterministic polynomial-time verifier $M$, so a witness of $a \in A$ relative to $M$ is a string $w$ such that $M(a,w) = 1$. The language under consideration is

  $L_A^f = \Big\{ a \in A ~~:~~ \#\{ w \mid M(a,w) = 1 \} \geq f(|a|) \Big\}$.

In English, $L_A^f$ consists of, for each $n$, the members of $A$ of size $n$ that have at least $f(n)$ witnesses relative to $M$.

Some preliminary observations:

$L_A^1 = A$ no matter what verifier you use.
For any $A$ in NP with verifier $M$, you can make a verifier $M'$ for $A$ such that $L_A^f = A$. Just have $M'$ accept every witness $w$ that is accepted by $M$, plus $f(n)$ padded versions of the witness as well. Then $a \in A$ if and only if it has at least $f(n)$ witnesses relative to $M'$. This shows that if you aren't careful about first fixing the verifier, you can get trivial answers.

Some example questions/directions:

What can we say about "parsimonious" or "minimal" verifiers? For instance, is there an NP-Complete language $A$ and verifier $M$ where $L_A^f$ becomes, say, not NP-Complete, or even trivial or empty, for some small $f$? What about $L_A^2$ (the members of $A$ with at least two witnesses)?
On the other hand what about succinctly-represented families of solutions? Could we have $f = \omega(p(n))$ for all polynomials $p$, and some "reasonable" or "natural" verifier for an NP-Complete language $A$, and yet $L_A^f$ is in NP? (Meaning that the fact that a given $a \in A$ has superpolynomially many witnesses is provable without listing all the witnesses.)
Anything about the above for a specific language $A$ such as SAT would be interesting.

Possibly (slightly) related: Does "Second-X is NP-Complete" Imply "X is NP-Complete"?


texts:
A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$?

Or, maybe, some another common polyhedron representation would help fasten this?


texts: How can I show a Gap-P problem is outside #P

texts:
There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take computing Kronecker coefficients as my example. Usually, the notion of "positive formula" is not precisely defined in combinatorics, but it roughly means "a description as the cardinality of seem reasonably explicit set". Recently, I've been talking to Jonah Blasiak, and he's been convincing me that the right definition of "positive formula" is #P. I'm going to assume that, on this site, I don't need to define #P.

Buergisser and Ikenmeyer show that Kronecker coefficients are #P hard. (They are also always positive, because they are tensor product multiplicities.) But I am reasonably sure that no one knows a way of computing them which even gets them into #P.

So, suppose that I were to actually make an attempt at proving Kronecker coefficients aren't in #P. I assume that what I would do is assume some complexity theoretic conjecture and then reduce Kronecker product to some other problem which is known to be complete for a class larger than #P.

  What conjecture might I assume, and what problem might I try to reduce to?

ADDED: As has been pointed out in the comments, Buergisser and Ikenmeyer show that Kronecker coefficients are in Gap-P, which is pretty close to #P. So it sounds like the questions I should be asking are (1) What are some Gap-P-complete problems I could plausibly reduce to and (2) what are the prospects of showing that Gap-P is not #P? I guess (2) should break up into two parts (2a) do experts believe these classes are different? and (2b) are there any likely strategies to prove it?

I hope that this much editing of the question is not frowned on.


texts: Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph

texts:
tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a group.
I have a directed graph with edge weights $w_{uv}$ between vertices $u$ and $v$ that can be both negative and positive. Edges not present in the graph can be considered to have $w_{uv}=0$.
My goal is to partition the vertices into mutually disjoint subsets $s_1,s_2,\ldots,s_k$ such that $4\leq |s_i|\leq 5$, i.e. the subset sizes are either four or five, the subsets do not all need to be of the same size.
I want the partition that maximizes $\sum_{i=1}^k\sum_{i,j\in S_i} w_{ij}$ (that is, I want to maximize happiness in some sense).
Is there an algorithm that solves this in polynomial time? If not, what if the maximum degree of every vertex is bounded by some constant?
I thought of framing it as an integer optimization problem as follows:
The variables are given by $c_{u,v,i}$ ($u\leq v$) and we have $c_{u,v,i} = 1$ if and only if vertices $u$ and $v$ are both assigned to subset $s_i$.
I then want to maximize $$\sum_{i=1}^k\sum_{1\leq u<v\leq n} (w_{uv}+w_{vu})c_{u,v,i}.$$
Subject to the following constraints:
For each vertex $u$ we need to have
$$\sum_{i=1}^k c_{u,u,i}=1$$
to guarantee that the vertex can only be in one subset.
For each vertex $v$ and each subset $i$ we need
$$\sum_{u=1, u\neq v}^n c_{u,v,i}\leq 5\cdot c_{v,v,i}$$
to guarantee that we only have positive values for $v$ in a single subset and to upper bound the number of other vertices in that subset.
We then add similarly
$$\sum_{u=1, u\neq v}^n c_{u,v,i}\geq 4\cdot c_{v,v,i}$$
to guarantee a lower bound on the subset sizes.
I think I'm not missing anything in this framing but I am wondering for what size of graphs this is a feasible approach and whether I'm missing a simpler approach. I have a greedy approximation approach but I'm curious what else can be done as I did not find many references online (most likely I did not look for the right keywords).


texts: Approximating circuits with polynomial of low degree, can't understand small detail in the proof

texts:
I'm looking at the proof of this lemma:

Lemma For every integer $t>0$, there exists a (proper) polynomial of total degree $(2t)^d$ that differs with $C$ on at most $size(C) 2^{n-t}$ inputs

Where C is a d-depth circuit with OR and NOT gates, and the polynomial is on the field $\mathbb{F}_3=\{-1,0-1\}$.
The construction of the polynomial is inductive:

for all inputs $x_i$ we associate to it the variable $x_i$
suppose a gate has input the polynomials $p_1,...,p_k$, let choose random subsets $S_1,...,S_t\subseteq [k]$, and define $q_i=(\sum_{j\in S_i}p_j)^2$, then the output polynomial is defined as $p=1-\prod_{i=1}^t (1-q_i)$

A polynomial is said to be proper if given inputs in $\{0,1\}$ the output is in $\{0,1\}$. What I don't understand is the observation that if all the $p_i$'s are proper that so is $p$.


texts: Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

texts:
It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$.

Input: a list $P$ of triplets $(a,s,t)$
where $s$ and $t$ are nonnegative integers.
Output: is there an $x\in \mathbb{R}$ such that
$$p(x) =\sum_{(a,s,t) \in P} a x^s(1-x)^t \geq 0?$$

Is this problem $\mathsf{NP}_\mathbb{R}$-hard?


texts: What are problems in SC we don't know to be in NC?

texts:
NC and SC are, roughly, the class of problems decidable by shallow circuits of polynomial size and the class of problems decidable by narrow circuits of polynomial size, respectively.
They are both subsets of P.

As far as I know, we don't know whether either of the two classes includes the other (at least that was the situation in 1989, according to Dymond and Cook's paper "Complexity Theory of Parallel Time
and Hardware").

What are (natural or practical) problems we know are in SC but don't know whether they are in NC?


texts: Understanding the HRU Model (Protection in Operating Systems)

texts:
As of now I am feeling terrible because I have spent the past 10 hours trying to understand this paper titled "Protection in Operating Systems" by Harrison, Ruzzo and Ullman. At this point, any help whether it is asking me to read some other paper or some kind of an explanation is good for me. As this paper is a landmark paper, I wanted to make sure I understand it thoroughly and I did until the paper states the following theorem on Page 7:

  THEOREM 1: There is an algorithm which decides
  whether or not a given
  mono-operational protection system and
  initial configuration is unsafe for a
  given generic right r.

I do not understand the gist of the proof. I have tried looking at lecture notes from every possible class website but apparently everyone skipped this part and just mention the theorem statement as if it were an axiom. Maybe it is obvious to everyone but somehow I am missing the big picture: What is the theorem trying to accomplish?

Specifically, following are the questions that I have been getting over and over again:

  PROOF: The proof hinges on two simple observations.  First, commands can test
  for the presence of rights, but not
  for the absence of rights or objects.
  This allows delete and destroy
  commands to be removed from
  computations leading to a leak.
  Second, a command can only identify
  objects by the rights in their row and
  column of a access matrix....

Why are these observations important? And how does the first statement allow for the removal of delete and destroy commands? I understand that these do not lead to a leak but how is this sentence derived (or implied) by the first?

  Suppose

  $(*) Q_0 \vdash_{c_{1}} Q_1
> \vdash_{c_{2}} ... \vdash_{c_{m}} Q_m$

  is a minimal length computation
  reaching some configuration $Q_m$ for
  which there is a command $\alpha$
  leaking $r$. Let $Q_i =
> (S_i,O_i,P_i).$ Now we claim that
  $C_i$, $2 \leq i \leq m$ is an enter
  command, and $C_1$ is either an enter
  or create subject command.

This is good until the following sentence immediately after the above sentence:

  Suppose not, and let $C_n$ be the last non-enter command in the sequence (*). Then we could form a shorter computation as follows...

And I am lost. Can someone please give me an intuitive explanation of this proof?


texts: Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of the weights is non-negative. Or if you prefer order-theoretic terminology, I have a weighted partial order and I want a linear extension such that each prefix has non-negative weight. What is known about this problem? Is it NP-complete or solvable in polynomial time?


texts: Increasing the capacity to maximize the min cut

texts:
Consider a graph with all edges having unit capacity.
One can find the min cut in polynomial time.

Suppose I am allowed to increase the capacity of any $k$ edges to infinity
(equivalent to merging the nodes on either side of the edge).
What is the optimal way of selecting an optimal set of $k$ edges
(whose capacity will be increased to infinity)
to maximize the min cut?


texts: How is the iteration space of a nested for-loop containing two sequential nested loops represented?

texts:
In a general for loop of the form:

for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
        ...
    for (k = i, k <= n, k++)
        ...
}

What form do the inequalities representing the iteration space take? Or what convex polyhedron represents this?

Background
I am looking at the Dragon Book's chapter on parallelisation. This talks in detail of nested loops of the form:

for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
       ...
}

but not of the form described at the top.

The iteration space of d-deep nested loops can be represented as:
$$
\{ i \in \mathbb{Z}^d \mid Bi + b \geq 0 \}
$$

where B is a $d \times d $ integer matrix and b is a vector of length $d$

My question is basically do I have to do anything different when a loop contains multiple inner loops not nested within each other?


texts: What are some known methods for showing that a class has no complete problems?

texts: The only way that I know of is the way that you can show that $RE \cap coRE$ does not via diagonalization. Mostly curious because if $NP \cap coNP$ has no complete problems then $P \neq NP$. I tried to use that diagonalization method a while ago to no avail but I never really asked about other methods.


texts: Matrix multiplication when one matrix is fixed

texts:
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry

One is allowed to pre-process this matrix as appropriate.

Given another positive integer entried $B$ of size $n\times b$ with $\ell'$ bits per entry, what is the complexity of multiplication $AB$?

Note we already have $(\max(a,n,b))^{2+\theta}polylog(\ell\ell')$ time and space algorithms where $2+\theta=\omega$ and $\omega$ is exponent of matrix multiplication.

The query here is whether we can do take $\theta=0$ or at least have flexibility to take any $\theta>0$ by anything cleverer?
Can we attain $\theta=0$ or at least have flexibility to take any $\theta>0$ with number of operations independent of $\ell$ and $\ell'$ in the $RAM$ model?


texts: Is something like DTIME(poly(n))/log(n) in P? Can the log-length advice be somehow hardwired into a DTM for P?


texts:
In solving a certain game, I've ended up with a set of equalities like these:

a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...

I create 2^N different equation sets, where N is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.

By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.

Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?

Update:

Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant
It is known, that there is an unique solution {a,b,c,...}
All variables are fractions in (0,1).

I can reduce the system by using Max[a,b] = (a+b-|a-b|)/2 and Snowie showed how to eliminate Max[a,b] by adding two inequalities and a binary variable. The complexity still seams to be O(2^N).


texts: The Average-case Complexity of Simplex Algorithm

texts:
I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint.  I know that Smale did some work in the 80's that says that if we fix $m$, then the average complexity is linear in $n$ when $n$ goes to infinity.

However, by duality theory, $m$ and $n$ are symmetric in LP. Also in the 80's, Adler et al. showed that the expected number of pivots is quadratic in $\min \{ m, n\}$. (See ``A Simplex Algorithm Whose Average Number of Steps
Is Bounded between Two Quadratic Functions
of the Smaller Dimension '') And they even showed a quadratic lower bound.

I was wondering if there are any recent development on such average-case analysis.


texts: Linear-time algorithm for getting ends of diametral paths in special sequence of trees

texts:
Recently in my research I have faced with the following subproblem:

  Given a tree $T, |V(T)| = n$ and its vertices are ordered $v_1, \ldots, v_n$ so that $T_i = T_{i-1} - v_i, 1 \le i \le n$ and $T_0 = T$ and every $T_i$ is a tree.

The question is:

  Is there any linear-time algorithm which gives $n$ pairs $v_{i_k}, v_{j_k}$, which are ends of a diametral path in $T_k$ for every $1 \le k \le n$ (any one if there are several ones)?

I think this algorithm can be useful for achieving linear-time recognition algorithms from explicit characterizations of various subclasses of trees.

ALSO, another way to think about it:

  Is there a data structure for a tree, such that we can insert a new leaf and query for a diametral path in amortized $O(1)$ time? (see comment by Chao Xu).


texts: Problems in BQP but conjectured to be outside P

texts:
Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain roots of unity.

Are there any other such problems?


texts: Deciding whether a binary multiplicity automaton has empty language

texts:
Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, they compute a function, $f_A: \Sigma^* \to F$.

I'm interested in a special kind of multiplicity automata, called binary MA :- automaton which computes a value over $Z_2$, and all of the weights associated to the arcs are $1$.

Since the function computed is over $Z_2$, we can discuss the language of the automaton, which is defined as: $L(A) = \{w|f_A(w)=1\}$.

In other words - such automaton $A$ is a NFA, accepting a word $w$ iff the number of accepting paths for $w$ in $A$ is a odd number.

For example, every DFA is a binary MFA.

While it is easy to figure whether a DFA or NFA has an empty language, finding whether a binary MFA's language is empty or not seems harder.

(or, formulated differently, whether a NFA has a word which is accepted by odd number of paths).

It seems that I can find a naive algorithm for the task which runs in $poly(n,|\Sigma|)$ (where $n$ is the number of states), but I'm wondering if it's possible to reduce it to $n^2$ (or maybe lower :) ).

EDIT: if it helps, the actual automaton I have has no cycles (which means $L(A)$ is finite).


texts: Has a result of Book and Greibach on Quasi-Realtime languages been improved?

texts:
Quasi-realtime languages are defined as languages accepted by nondeterministic multitape Turing machines in quasi-real time. Ronald Book and Sheila Greibach have shown in their 1970 paper that every quasi-realtime language can be accepted by a nondeterministic automaton having one stack and one pushdown store. However, at the time it was open if a nondeterministic automaton with two pushdown stores suffices.

Since the mentioned paper is quite old and seems to have received significant attention (at least I deduce so from the number of citations), I would like to ask if there has been any progress on the above mentioned problem. In particular, has anybody proved that two pushdown stores are sufficient/insufficient? Or has anybody improved the result in some other way?


texts: Monotone arithmetic circuit complexity of elementary symmetric polynomials?

texts:
The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit complexity
of this polynomial. A simple dynamic programming algorithm (as well as Fig. 1 below) gives a $(+,\times)$ circuit with $O(kn)$ gates.

 Question:
Is a lower bound of $\Omega(kn)$  known?

A $(+,\times)$ circuit is skew if at least one of the two inputs of each product
gate is a variable. Such a circuit is actually  the same as switching-and-rectifying network (a directed acyclic graph with some edges labeled by variables; each s-t path gives the product of its labels, and the output is the sum of over all s-t paths). Already 40 years ago, Markov proved a surprisingly tight result: a minimal
monotone arithmetic skew circuit for $S_k^n$ has exactly $k(n-k+1)$ product gates. The upper bound follows from Fig. 1:

 But I haven't seen any attempt to prove such a lower bound for non-skew circuits. Is this just our "arrogance", or are there some inherent difficulties observed along the way?

P.S. I know that $\Omega(n\log n)$ gates are necessary to simultaneously compute all $S_1^n,\ldots,S_n^n$. This follows from the lower bound on the size of monotone boolean circuits sorting the 0-1 input; see page 158 of Ingo Wegener's book. The AKS sorting network also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, Baur and Strassen have proved a tight bound $\Theta(n\log n)$ on the size of non-monotone arithmetic circuit for $S_{n/2}^n$. But what about monotone arithmetic circuits?


texts:
I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be a " good parameter ". My definition of good parameter is not clear although, but it simply means if I can come up with an FPT algorithm for that problem using that parameter then it will solve some non-trivial set of instances.

For an example:  If we talk about the parameterization of some graph problem using independent set (I) and vertex cover (V) and some how we get an FPT algorithm of type $g(k)^{f(I)}\text{Poly}(n)$. Will it a good parameterization of the problem.

  Question : When we say a parameter is good for a problem? I can define many parameters for a problem, but the question here is to how to decide it is a good parameter.


texts: Finding assignment-minimum complete k-partite graph cover

texts:
Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs?

I'm assuming this problem is NP-hard.  Is it?

Is there a better term for complete k-partite subgraph (like multiclique or something)?

EDIT: k is not fixed.  The covering subgraphs can each have different values of k.

EDIT 2: When I say "cover", I mean a cover over all the edges of the graph (not over all the vertices).  Furthermore, by "subgraph" I actually mean subgraph, not induced subgraph.
k=1 no-edge subgraphs are useless and can be removed from the solution since they cover zero edges.
By assignment-minimum, I mean find the solution which minimizes the number of assignments of vertices to subgraphs (as in http://dl.acm.org/citation.cfm?id=2275596)


texts: Upper bound on the size of a Concept Lattice (Galois Lattice)?

texts:
A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A |  \forall o \in P \, oIa \}$ and $B'=\{o \in O |  \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on Formal Concept Analysis.

The number of concepts in a concept lattice is bounded by :

$2^{1+\sqrt{|R|}}$ as told in this paper (which mentions a result from this paper in german). Note that their upper bound is tighter - the one I give here is less precise.
$2^{|O|+|A|}$ according to this paper (which is presented as a trivial easy upper bound).

I dont understand why these upper bounds are that large.
Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, Luz


texts: Random walk and mean hitting time in a simple undirected graph

texts:
Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges.

I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, it is shown to be $O(\tau)$, where $\tau$ is the mean hitting time: $$\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), $$ where:

$\pi$ is the stationary distribution $\pi(v)=\frac{d(v)}{2m}$,
$u$ is an arbitrary vertex, and
$H(u,v)$ is the hitting time (AKA access time), i.e., the expected number of steps
before vertex $v$ is visited, starting from vertex $u$.

What is the general upper bound for the mean hitting time? And what is the worst case graph $G$ that maximizes mean hitting time?

To make my question clear, I don't require calculations or a detailed proof (although they may be useful to other people encountering this question in the future). For me personally, a citation would be sufficient.

The paper mentions another algorithm by Broder that works in expected cover time (first time when all vertices have been visited). Then it is said, that mean hitting time is always less than cover time. However it only gives an asymptotic bound of $\Theta(n)$ for most graphs (i.e., expander graphs) to contrast it with $\Theta(n \log n)$ by Broder for most graphs (with a somewhat more inclusive definition of most).

It does give an example of a graph where mean hitting time is $\Theta(n^2)$ and cover time is $\Theta(n^3)$. While this is known to be the worst case for the latter, he does not specifically say anything about the worst case of the former. This would mean that the worst case for Wilson's algorithm may fall anywhere between $O(n^2)$ and $O(n^3)$.

There are two publicly available implementations of Wilson's algorithm that I'm aware of. One is in the Boost Graph Library, while second is in graph-tool. Documentation of the former does not mention running time, while the latter states:

  The typical running time for random graphs is $O(n \log n)$.

Which does not answer the question, and actually seems to be inconsistent with Wilson's paper. But I report this just in case, to save time of anybody with the same idea of consulting implementation documentation.

I had initially hoped that the worst case might be attained by a graph constructed by attaching a path to a clique, due to Lovász, where the hitting time can be as high as $\Omega(n^3)$. However, the probability of this event is about $\frac{1}{n}$ when picking vertices from stationary distribution. Consequently yielding an $O(n^2)$ bound for the mean hitting time in this graph.

A paper by Brightwell and Winkler shows that a subset of lollipop graphs maximizes the expected hitting time, reaching $4n^3/27$. Graph by Lovász is also a lollipop graph, but in this case the clique size is $\frac{2}{3} n$, rather than half. However, care must be taken not to confuse expected hitting time with mean hitting time. This result, like the previous one, refers to expected hitting time for two specific vertices chosen beforehand.


texts: Embedding a graph as a collection of interior-disjoint tetrahedra

texts:
Define a mesh in 3D as a connected collection of tetrahedra with disjoint interiors (so tetrahedra share only k-faces, $k \le 2$). Given an arbitrary graph, is there an efficient procedure to test if it can be embedded as a mesh ?

Here, an embedding is a mapping of vertices of the graph to points in $R^3$ and edges to straight lines such that edges only intersect at vertices, and faces only intersect at edges, and no two faces intersect in their interior.


texts:
What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then minimize an automaton, but

The minimal DFA can actually have more states than the original NFA
Not every weighted NFA is determinizable (in fact, most of them aren't)

My aim, however, is not necessarily to minimize an automaton, but simply reduce its complexity. So, what I'm looking for is a simplification algorithm that works directly with NFA and, while it doesn't guarantee to find the optimal solution, can simplify the automata in some cases significantly, and, presumably, has time complexity polynomial in the number of states. Are there any such algorithms known in literature?


texts:
Is this a known problem?

Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is to find the smallest $B$.

For instance $\{\{a,b\}, \{c\}, \{a,b,c\}\}$ can be obtained from $\{\{a,b\}, \{c\}\}$.

Since it's somewhat similar to set-cover, I suspect it's NP-hard.

Additional remark: $B$ does not have to be a subset of $S$.


texts:
This enquiry is three-sided.
Side 1 - State of the art

Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming sublinear depth?
Which is the best known algorithm for $\oplus \text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\oplus \text{PLANAR-CIRCUIT-SAT}$ assuming sublinear depth?

Side 2 - Clusters of variables
I'm about to implement a $\oplus \text{PLANAR-CIRCUIT-SAT}$ solver, which running time is supposed to be exponential in $d_C + d_V$, where $d_C$ is the depth of the input circuit, and $d_V$ is a quantity which represents to what extent the variables of the circuit are grouped in clusters. Very informally, a high $d_V$ (linear in the number of input variables) means that the wires connecting the input variables to their gates are scattering back and forth all over the circuit, traversing it from left to right, thus such variables are not clustered and somehow exhibit wild/random relationships with no structure. On the very opposite side, a low $d_V$ (constant) means that the gates to which any input variable is connected are near one another, and hence that variables are packed in local clusters, thus exhibiting structure (typical of real-life instances). Less informally, imagine to draw a vertical line which splits the circuit in two parts (not necessarily of the same size), and count how many times such vertical line intersects a wire from any variable to any of its gates: the quantity $d_V$ is the highest number of such intersections for any such vertical line (obviously, the assumption here is that the circuit propagation flow is from bottom to top, not from left to right).

Has $d_V$ been studied in the literature of planar circuits (maybe it already has a widely used name and formal definition which I'm not aware of)? More generally, has the clustering of variables been addressed at all in the theoretical study of the computational complexity of the problem?
Does $d_V$ being sublinear (if not even constant) somehow destroys the expressive power of the planar circuit? Or does it remain $\mathbf{NP}$-complete / $\oplus \mathbf{P}$-complete?

Side 3 - Consequences

Would a subexponential time algorithm for $\oplus \text{PLANAR-CIRCUIT-SAT}$, assuming sublinear $d_C$ only, bring any interesting consequence?
Would a subexponential time algorithm for $\oplus \text{PLANAR-CIRCUIT-SAT}$, assuming both sublinear $d_C$ and sublinear $d_V$, bring any interesting consequence?


texts: Single source multicommodity flow on a path or tree

texts:
Given a graph $G=(V,E)$, a set of terminals $T = \{t_1,\ldots, t_n\}$, and a single source $s$, where $s\in V$ and $T \subseteq V\backslash \{s\}$. Each terminal $i$ is associated with a demand $d_i$ and a utility $u_i$. Moreover, each edge $e \in E$ has a capacity $c_e$.

The objective is to maximize
$$\sum_{i=1}^n x_i u_i$$
 subject to edge capacities:
for all $e=(u,v) \in E$,
$$\sum_{i \text{ is rooted by } v }^n d_i x_i \le c_e$$
 where $x_i \in \{0,1\}$ is a decision variable.

We assume $G$ is a tree (or path for simplicity). This implies that for each demand $i$ there is only a single path. The problem is to decide which demand to select   in order to attain the maximum utility, while respecting edge capacities.

Unsplittable flow is an old problem and has several variations and settings. I'v seen recent research papers considering unsplittable flow on a path (but with multiple sources), as well as older papers considering single source but on general toplogy.

In fact this problem is still NP-hard as it generalizes knapsack. Is there any paper considering this setting: utility maximization, single source (multiple terminals), and tree/path topology)?


texts: Hoeffding's inequality for independent random variables $a_i\le X_i\le b_i$ states that their sum has sub-Gaussian tails, decaying as $\exp(-2t^2/\sum_i (b_i-a_i)^2)$. Question: Are there any interesting applications exploiting the heterogeneous ranges? In all of the applications I'm aware of, either the $X_i$ all have the same range, or else Hoeffding/McDiarmid (and for that matter, Bernstein/Bennett) are simply too crude, and a sharper tool such as Kearns-Saul is called for (see, e.g., Theorem 1(i) in http://jmlr.org/papers/v16/berend15a.html, or Theorem 2.1 in https://projecteuclid.org/euclid.ecp/1465315542; Talagrand's inequality also comes to mind of course). So again: is heterogenous Hoeffding actually ever used?


texts: In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is considered. Consequently, hidden shift functions are injective. Although hardness for rigid structures also give hardness for class as a whole is there any other reason why this is done? Are hardness results like these also generalized for non-injective functions?


texts: Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

texts:
In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:

$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| < 2^{cK(x)+1}$

They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.

It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.

It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?


texts:
In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree remains intact, with $k$ children you still have any of the $k!$ insertion sequences to rebuild the children into a new subtree since any legal BST among the children will work.

Is there a survey article on BST deletion algorithms? Most articles simply talk about the standard textbook BST delete algorithm.


texts: Design of exact algorithms for non-local hard problems

texts:
In the connected dominating set problem (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent to some vertex in $S$. If we drop the connectedness requirement (the usual dominating set problem (DS)), we have exact algorithms that are much faster than the naive brute force method. The trivial algorithm for CDS runs in $\Omega(2^n)$ time and enumerates all the subsets of vertices. To the best of my knowledge, the fastest known exact algorithm for CDS is the one given by Fomin, Grandoni and Kratsch running in $O(1.9407^n)$ time.
It seems both intuitively true, and also generally accepted in the literature, that non-local problems (such as CDS) are harder to solve than local problems (such as DS). The reason seems to be that often exact algorithms are exploiting the local structure of the problem whereas say connectivity is a global property. Another non-local problem is TSP, for which as far as I know, the fastest known algorithm dates back to the sixties and runs in $\Omega(2^n)$ time.
Say for TSP, we do have faster algorithms for special graph classes of course (cubic, bounded-degree, and so on). Also, for many non-local problems on graphs of bounded treewidth we have (I guess possibly even optimal under SETH) algorithms (see the work by Cygan et al). Similarly, I think we can get $O(c^{\sqrt{n}})$ algorithms for non-local problems on planar graphs using a result of Fomin and Thilikos bounding the treewidth of a planar graph, and showing how a tree decomposition of such width can be found in polynomial time. But what about general (undirected) graphs?
It indeed appears that for many non-local problems the best known algorithms are still trivial. For Steiner tree (i.e. find a minimum size subtree of a given graph spanning a given subset of $k$ nodes), we have a $O(1.4143^n)$ time algorithm obtained by combining the $O((2+\epsilon)^kn^{O(1)}$ DP algorithm (for small $k$) with the trivial $O(2^{n-k}n^{O(1)})$ enumeration of Steiner nodes (for large $k$). To the best of my knowledge, finding a polynomial space algorithm faster than $2^n$ is still open.

(1) What other examples of non-local problems besides connected dominating set and Steiner tree do we have such that there is a faster non-trivial exact algorithm for them (on general graphs)?
(2) Is it possible to extract some kind of general algorithmic design techniques from the known fast exact algorithms for non-local problems?


texts:
Almost all regular graphs with degree $k^2$ are $k+1$ colorable.

The near absence (finitude) of adjacent small cycles in random regular graphs as $N$ (the size of the graph) grows may help imply the truth, but any proof looks far away.
The conjecture is empirically true for $k=3$ (i.e. Almost all 9-regular graphs are 4 colorable).

Does this conjecture have a name, or better yet, is it true?


texts: Polytime Computable Distribution vs Polytime Sampleable Distribution

texts:
Many texts on average case complexity claim:

1) Any polytime computable distribution is also polytime sampleable.

2) A polytime sampleable distribution is one where a polytime probabilistic TM generates the distribution on input 1^n.

Now, suppose we have a distribution, where

Prob(0) = 1/3
Prob(1) = 2/3.

Clearly, this distribution is polytime computable. Most texts would this claim that it's also polytime sampleable. However, I don't see how any polytime probabilistic TM can generate the above distribution. [I see how expected polytime proabilistic TM can generate this distribution; but that is not the same as polytime probabilistic TM.]

Question: Where am I going wrong? Am I misunderstanding polytime sampleable, or polytime computable? The distribution defined above, is it

(1) NOT polytime computable (i.e. writing out 1/3 would take an infinite number of bits)
or
(2) It is actually polytime sampleable; since in reality, we only require that the algorithm run in expected polytime?

Thanks!


texts: Steiner tree problem for unweighted graphs

texts: Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number of vertices to connect all the vertices in $C$. (Since we are looking for a subtree, minimizing the number of vertices also minimizes edges.) The unweighted Steiner tree problem should be NP-hard but is there any better (approximation) algorithm for it?


texts:
Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.

Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.

It is not known if $F(x)$ needs $n\log n$ operations in the unbounded coefficient model when $x_i$'s are treated generically as variables.

Supposing each $x_i$ is an integer bounded by $2^b$, can one show computing $F(x)$ still needs $n\log n$ arithmetic operations in the unbounded coefficient model?

Added:
The reason I posted was a few fold. Some questions in the bounded integer $x_i$ model are:

1) We cannot use bit level manipulation on variables $x_i$. However we can do bit level operations on integers $x_i$. Are bit level operations considered valid arithmetic operations when counting the $\Omega(n\log n)$ arithmetic operation?

2) Does one multiplication operation on a word that scales as $O(n)$ bits still count as $1$ arithmetic operation?

3) Is division a valid arithmetic operation?


texts:
Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an external randomness and $U_M$ is a uniform random variable over a set of $M$ points.

  What is the largest value of $M$ for which such an  extractor
  $f$ for source $X$ exists ?

Is there any connection between randomness extractor and the following problem:

  Given two dependent random variables $X$ and $Y$, how many bits we can
  extract from $Y$ that are  almost independent from $X$ (where the
  independence is measured via total variational distance) ?

Thanks


texts: Minimum graph cycle basis respect to non-empty pairwise intersection of cycles

texts:
I'm trying to understand the following problem if anyone can help I'll be very grateful
Instance: undirected, unweighted, connected graph graph $G=(V,E)$.
Question: find a minimum cycle basis $B = \{C_1,\dots,C_\nu\}$ of $G$  (where $\nu = |E|-|V|+1$ is the cyclomatic number) respect to non-empty pairwise cycle intersections. More precisely let $B$ minimize:
$$\sum_{C_i, C_j \in B} \cap(C_i, C_j), i \neq j$$
Where $\cap(C_i, C_j)$ is defined as follows
$$\cap(C_i, C_j) :=
 \begin{cases}
   1 & C_i \cap C_j \neq \varnothing \\
   0 & C_i \cap C_j = \varnothing \\
 \end{cases}
$$
And the intersections considered are: edge intersections.
There is a longstanding theory that describes the problem of minimizing cycle lengths (or weights) instead of cycle intersections. The following survey gives a complete picture:
Cycle bases in graphs characterization, algorithms, complexity, and applications
Kavitha T., Liebchen C., Mehlhorn K., Michail D., Rizzi R., Ueckerdt T., Zweig K.A.
(2009)  Computer Science Review,  3  (4) , pp. 199-243.
I couldn't find a similar treatment of the problem of minimizing intersections. Any comment, suggestion or bibliographic reference will be of great  help.


texts: Are there efficient general Bonferroni-style bounds known?

texts:
A classic problem in probability theory is to express the probability of an event in terms of more specific events.  In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$.  Let's write $AB$ for the event $A \cap B$.

There are then some ways to bound $P[\cup A_i]$, without assuming independence of the finitely many events $A_i$.  Bonferroni gave the upper bound
$$P[\cup A_i] \le \sum P[A_i]$$
(this is sometimes also attributed to Boole), and Kounias refined this to
$$P[\cup A_i] \le \sum_i P[A_i] - \max_j \sum_{i \ne j} P[A_i A_j].$$

The dependence structure of the events can be thought of as a weighted hypergraph with vertices $A_i$, with the weight of an edge representing the probability of the event associated with the intersection of the vertices in the edge.

An inclusion-exclusion style argument considers larger and larger subsets of events together.  These yield the Bonferroni bounds.  These bounds use all weights for edges up to some size $k$.

If the dependence structure is "nice enough", then the Lovász Local Lemma can be used to bound the probability away from the extreme values 0 and 1.  In contrast to the Bonferroni approach, the LLL uses quite coarse information about the dependence structure.

Now suppose relatively few weights in the dependence structure are non-zero.  Further, suppose that there are many events that are pairwise independent yet are not independent (and more generally, it is quite possible that a set of $k$ events is not mutually independent but is $r$-wise independent for every $r < k$).

  Is it possible to explicitly use the dependence structure of events to improve the Bonferroni/Kounias bounds, in a way that can be computed efficiently?

I expect the answer is yes, and would appreciate pointers to references.  I am aware of Hunter's paper from 1976, but it only deals with pairwise dependencies.  Hunter considers spanning trees in the graph formed by ignoring the edges in the dependence structure of size 3 or greater.

David Hunter, An Upper Bound for the Probability of a Union, Journal of Applied Probability 13 597–603.  http://www.jstor.org/stable/3212481


texts: The rank of nodes in the longest directed path of a random DAG

texts:
I am facing this problem for a long time, I wish I can find some help in here.

Let's consider a graph $G(V,E)$ such that an edge between a pair of node $u$ and $v$ exist with probability $p \in O(1)$. Let's assign identifiers for the vertices from 1 to $n$, where $n = |V|$. Now, direct each edge $(u,v)$ towards $v$ if $u > v$. We have what we call a random graph order $P$.

We define $L = (x_1, x_2, \ldots, x_m)$ as the longest directed path in $P$. That is, $x_i > x_{i+1}$ for all $1 \leq i < k$.  It is known that $|L| = \Theta(n)$. Define $\textit{rank}(x_i)$ as the position of $x_i$ in the set ${1, ..., n}$ (that is, the first, the second, ..., the $n$-th element in the total order constructed from the identifiers of $V$).

  Question. If we take any $x_i \in L$, what is expected rank of $x_i$?

My solution was to assume that $|L| = \frac{n}{t}$, and to assume that the path $L$ partitions the graph $G$ into $|L|$ layers. Thus, for the path $L = (x_1, \ldots, x_m)$ the expected rank of $x_i = (n - (t * i)) + \frac{1}{2} * t$. What do you think?


texts: Lower bound for determinant and permanent

texts:
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the following questions :
Grigoriev and Karpinski proved an $2^{\Omega{(n)}}$ lower bound for any depth-3 arithmetic circuit computing the Determinant of $n \times n$ matrices over finite fields (which I guess, also holds for the Permanent). Ryser's formula for computing the Permanent gives a depth-3 arithmetic circuit of size $O(n^2 2^n) = 2^{O(n)}$. This shows that the result is essentially tight for depth-3 circuits for the Permanent over finite fields. I have two questions:

1) Is there a depth-3 formula for the determinant analogous to Ryser's formula for the Permanent?

2) Does a lower bound on the size of arithmetic circuits computing the Determinant polynomial \textit{always} yield a lower bound for the Permanent polynomial?(Over $\mathbb{F}_2$ they are the same polynomials).

Though my question currenly is regarding these polynomials over finite fields, I would also like to know the status of these questions over arbitrary fields.


texts: Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$

texts:
Do we know of any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?

Context: based on Josh's answer to this question, it could be possible that all interesting problems (to humans) lie somewhere in the $\mathsf{NL}$ hierarchy, which collapses due to $\mathsf{NL} = \mathsf{coNL}$, meaning that all of these problems are in $\mathsf{NC}^2$. Yet, I'm not aware of any problems that are in $\mathsf{NC}^2$ but are not contained in a smaller class.

Related to this, are there any useful resources listing problems known to be in $\mathsf{AC}^1$ or $\mathsf{DET}$? The best resource I have found is Cook's paper "A taxonomy of problems with fast parallel algorithms".

Thanks to Josh for suggesting to split this question from here.


texts: Hardness when restricted to an infinite number of far apart instance sizes

texts:
Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance sizes? To be precise, I have an infinite ascending sequence of numbers $n_1, n_2, n_3, \dots$ and want to show that one cannot solve the NP-hard problem in polynomial time when restricted to inputs of sizes $n_i$.
A naive idea to prove the statement would be to take an instance of size $n$, "pad" it to the next largest value $n_i$ and solve it in $n_i^{O(1)}$. However, this creates no contradiction, because it could be that the $n_i$ are spaced so far apart that the next largest $n_i$ is exponential in $n$.
It appears to me that this question is not related to Mahaney's theorem, since for a given $n_i$ we allow all instances of size $n_i$, not just a sparse subset.
I am not fixed on the classes P and NP. A similar hardness result for other classes would also be highly appreciated.


texts: Natural computation based on fundamental forces

texts:
Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers.

What is known about the potential and/or limitations of computing with Maxwell's laws or gravity?

That is, incorporating nature's "quick" solutions to Maxwell's equations or the n-body problem directly into a general-purpose algorithm?


texts:
Let $\alpha$ be a binary relation from $\gamma$ to $\chi$ and $\beta$ a binary relation from $\chi$ to $\rho$. If both $\alpha$ and $\beta$ are rectangular, i.e., they satisfy $\alpha \alpha^{-1} \alpha = \alpha$ and $\beta \beta^{-1} \beta = \beta$, then the composite relation $\gamma = \alpha \beta$ is also rectangular. On the other hand, if a relation is rectangular, then by Theorems 2 and 4 of Ref. 1, it admits a decomposition $\gamma = \alpha' \beta'$. Note that it is possible that $\alpha'\not=\alpha$ and $\beta'\not=\beta$. This decomposition can be obtained via the corresponding relation matrices via, e.g., the algorithm of Ref. 2.

Question: If $\alpha$ and $\beta$ are rectangular and $\gamma = \alpha \beta$, then is it true that, for any decomposition $\gamma = \alpha' \beta'$, $\alpha'$ and $\beta'$ are also rectangular?

I have the feeling that the answer should be affirmative, as I think it is implied by Theorem 7 in Ref. 3. I think it should hold for $n$-ary rectangular relations as well. Is there a way to (dis)prove this?

References:

A. Berman and R. J. Plemmons, Inverses of nonnegative matrices, Linear and Multilinear Algebra 2, 161-172 (1974) [link]
S. L. Campbell and G. D. Poole, Computing nonnegative rank factorizations, Linear Algebra Applied 35, 175–182 (1981) [link]
A. A. Bulatov and V. Dalmau, Information and Computation 205, 651-678 (2007) [link]