texts: Union of two matching to maximize the number of cycles

texts:
Given $G$, $C$ and $M$, where $G$ is a graph with maximum degree $3$, $C$ is a hamiltonian cycle of $G$, and $M$ is a matching of $G$.

Let $\mathcal{N}$ be the set of all matching of $C$ with size $|M|$. We want to pick a $N\in \mathcal{N}$, such that the number of cycles in $M\cup N$ is maximized. Here we also define edges in $M\cap N$ to be cycles.

Is this problem NP-hard?

A cool way to visualize the problem is consider $n$ points on a circle and some endpoint disjoint chords between the points. We want to connect adjacent points with disjoint arcs to maximize the number of cycles.


texts: Fourier expansion of boolean functions and affine subspaces

texts:
Let $f:\mathbb{F}^n_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v \in V$. Let $W$ be the quotient subspace $\mathbb{F}^n_2/W$ so that $dim(W)=t$ and $\mathbb{F}^n_2=V+W$. Let $\pi_V:\mathbb{F}^n_2\rightarrow V$ and $\pi_W:\mathbb{F}^n_2 \rightarrow W$ be the projection maps to $V$ and $W$. Then:

$$f|_V(v)=\sum_{i=1}^r \hat{f}(\alpha_i)(-1)^{\langle v,\pi_V(\alpha_i)\rangle},$$

where $rank(f)=r$. In particular, as $f$ is constant on $V$, it must be the case that for every non-zero $\alpha_i$ there exists some $\alpha_j$ such that $\pi_V(\alpha_i)=\pi_V(\alpha_j)$, or equivalently $\alpha_i+\alpha_j\in W$.

I reported exactly the piece of the proof that I don't completely understand, could somebody explain me these two points:

Why do we need to assume that $V$ is a linear subspace?
Why there must be $\alpha_i$ and $\alpha_j$ satisfying the property above?


texts: On the coloring number of small graphs with small cliques

texts:
Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i.e $\chi(G)\le C(k)$.

Using Mycielski's graphs, one can show that this number should be at least $k+\log k$.

It is known that for any integer $c$ there is a triangle-free graph that has chromatic number $c$. However in all these constructions, as far as I know, the size of these graphs is a rapidly increasing function of $c$.

I conjecture that $C(k)=\Theta(k)$ and I would be really grateful for any helpful references related to this question.


texts: Are k+1 heads better than k for multiread finite automata?

texts:
Consider the deterministic (resp. non-deterministic) one-way finite automaton that is defined in the usual way except that it has k heads and in each step can decide which head to move. (It is allowed to run until all heads reach the end-marker of the input.) These automata are denoted by k-DFA (resp. k-FA) and it was shown in several papers that k+1 heads are better than k, i.e., their is a language that can be recognized only with more heads. Probably the simplest of these arguments is by Yao and Rivest (http://people.csail.mit.edu/rivest/pubs/YR78.pdf).

However, notice that if we allow the k-headed automata to read the input k+1 times, then it can also recognize the language given as a counterexample. (Here define reading t times as you would like to - when the first reading is finished, start the second one etc. OR run the machines in parallel t times from t different starting states and then take some boolean function of their final states.)

So my question:
Is there a language that can be recognized by a k+1-headed automaton but by no k-headed automaton that is allowed to read the input t times? (Here t can depend on the language but not on the input.)

Note: Please do not link me to papers asking if I have seen it! I have read many related things...


texts:
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the full Complexity Zoo Diagram. Does the hierarchy play any role in current research anymore? I found only little references to Chomsky here at cstheory.stackexchange, and in Complexity Zoo the names Chomsky and Schützenberger are not mentioned at all.

Is current research more focused on other means of description but formal grammars? I was looking for practical methods to describe formal languages with different expressiveness, and stumbled upon growing context sensitive language (GCSL) and visibly pushdown languages (VPL), which both lie between the classic Chomsky languages. Shouldn't the Chomsky hierarchy be updated to include them? Or is there no use of selecting a specific hierarchy from the full set of complexity classes? I tried to select only those languages that can be fit in gaps of the Chomsky hierarchy, as far as I understand:

REG (=Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (=Chomsky 2) ⊊ GCSL ⊊ CSL (=Chomsky 1) ⊊ R ⊊ RE

I still don't get where "mildly context-sensitive languages" and "indexed languages" fit in (somewhere between CFL and CSL) although there seems to be of practical relevance for natural language processing (but maybe anything of practical relevance is less interesting in theoretical research ;-). In addition you could mention GCSL ⊊ P ⊂ NP ⊂ PSPACE and CSL ⊊ PSPACE ⊊ R to show the relation to the famous classes P and NP.

I found on GCSL and VPL:

Robert McNaughton: An Insertion into the Chomsky Hierarchy?. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. S. 204-212, 1999
http://en.wikipedia.org/wiki/Nested_word#References (VPL)

I'd also be happy if you know any more recent textbook on formal grammars that also deal with VPL, DCLF, GCSL and indexed grammars, preferable with pointers to practical applications.


texts:
After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations.  However, the one issue I have run into is the large overhead associated with the initial creation of a large finger tree.  Because building is defined as a sequence of concatenation operations you end up building a large number of finger tree structures that are unneeded.

Due to the complex nature of 2-3 finger trees I see no intuitive method for bootstrapping them, and all my searches have come up empty. So the question is, how could you go about bootstrapping a 2-3 finger tree with minimal overhead?

To be explicit: given a sequence $S$ of known length $n$ generate the finger tree representation of $S$ with minimal operations.

The naive way to accomplish is successive calls to the cons operation (in the literature the '$\triangleleft$' operator).  However, this will create $n$ distinct finger tree structures representing all the slices of $S$ for $[1..i]$.


texts:
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The first world presented is Algorithmica, in which P = NP, "or some moral equivalent" such as NP being contained in BPP, or NP = RP ≠ P.
The remaining four worlds are all variants where P ≠ NP, and they are "morally" different, with differences between the algorithmic applications of hardness differntiating the worlds.

It seems to me that there is a large landscape inside Algorithmica, and I'm wondering:

  has anyone written about Algorithmica in more detail?

The best reference I have found so far is a blog post by Richard Lipton from 2009 which briefly explores Algorithmica but doesn't go into much detail.

Although it seems unlikely that we are living in Algorithmica, understanding that landscape might still motivate interesting work.
For instance, it might highlight precisely what the world would have to look like for quantum factoring to be rendered irrelevant, or if quantum factoring is ignored, where classical factoring might still be challenging.
See the related question Status of Impagliazzo's Worlds? for a discussion focused on the other parts of the landscape, including Boaz Barak's summary of a 2009 workshop about Impagliazzo's multiverse.


texts:
I am confused. I think I've read two usages of the word "impredicative" in type theory:

When people talk about the "impredicative" version of Martin-Löf's type theory, which they say it is inconsistent. Apparently they call it impredicative because of Type : Type.
When people talk about the "impredicative" Prop in CoC. Apparently they call it impredicative because you can quantify over Prop and get Prop stuff.

Is it the case? One notion of impredicativity implies the other? Is there no problem (i.e. inconsistency) by assuming "Prop impredicative"?


texts: Finding a minimal DFA whose language has a desired intersection with another

texts:
Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$.

I would like to find another regular language $C$ such that $B = A \cap C$ that minimizes the size of $M_C$ (the minimal DFA corresponding to $C$).

In general $M_C$ can be much smaller than $M_B$. e.g. if we let $B$ the set of strings in $A$ that have even length, $M_C$ can be a two-state machine, while $M_B$ may be about as complex (or more) as $M_A$.

This feels like it should be an easy application of existing automaton minimization algorithms, but I'm not seeing it if so.

What looked liked the obvious thing to try to do is to to try and distinguish strings using an analogue of the Myhill-Nerode theorem, with the distinguishing relationship being that $x, y$ are distinct if there is some $s$ such that $xs, ys \in A$ but $xs \in B \neq ys \in B$, but the problem is that the corresponding indistinguishability relation is no longer transitive (I think) - Given $a$ indistinguishable from $b$ indistinguishable from $c$, there might be $s$ such that $as, cs \in A$ with $as \in B \neq cs \in B$, but $bs \not\in A$, so $s$ cannot be used to distinguish $a$ from $c$.

I think this arises from some genuine ambiguity in the problem - unlike normal DFA minimization, there's no reason to expect $M_C$ to be unique - two non-equivalent machines could represent languages $C \neq C'$ such that $A \cap C = A \cap C'$. It might be that those ambiguities don't matter and you can just resolve them arbitrarily, but I haven't been able to convince myself of that.

The problem is at least "reasonably tractable", as the corresponding decision problem is in NP, because such an automaton has size at most $|M_B|$, and we can determine whether a given automaton is a solution by testing its equivalence with the intersection automaton with states $M_A \times M_B$, and testing equivalence is in $P$. There's almost certainly some nice transformation into SAT or ILP that I haven't worked through yet because I'm hoping for a better solution.

Is this some well studied problem? Or can it be reduced to one?


texts:
If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time.

Assume that $\textbf{E} = \textbf{NE}$. Is it true that there is an algorithm of finding a certificate in exponential time for every language from $\textbf{NE}$?


texts: Improving boolean circuits w.r.t. a probability distribution

texts:
This is a reference request. Consider the following problem on boolean circuits [ 1 ]:

Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$.
Task: Find one or more equivalent Boolean circuits $B'$ that 'perform better'
than $B$ if the inputs are as given by $\mathbb{P}$.

What has been
done that looks like it is related, even loosely?  Naturally, there
are numerous ways we can understand things like "perform better", e.g. fewer gates, fewer gates of a specific type, less depth. Minimally, the new circuit(s) should
produce the same output (with the edge case that if the probability
of an input is 0 then $B$ and $B'$ don't have to agree on that input).

Here is an analogy that feels similar: Huffman coding [ 2 ],
which gives an optimal coding for any specific probability of
character occurrence. Similarly, it would appear to be possible to
specialise a boolean circuit to a probability distribution on inputs.

Boolean circuits and their complexities have been
formalised in many ways, and I'm not particularly attached by any
specific definition: my exact use case is unlikely to have been
considered already. At the same time, all existing approaches
are probably full of interesting ideas that might be adaptable to my
use case.

Wikipedia: Boolean circuit
Wikipedia: Huffman coding


texts: Complexity of Knapsack-type problem with applications to computational workflows

texts:
Consider the following problem:

Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer.  Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a subset $AS$ of $A$ so that the weight of $AS$ is less than $W$ and the value of $AS$ (the sum of the value of its items) is maximized is the 0/1 Knapsack Problem

Now, consider a deviation from it where the items in $A$ have certain dependency relationships between each other, and these dependencies can be captured by a directed acyclic graph $G(A, E)$.  The value of the set $AS$ is no longer the sum of the value of the items in $AS$. For each item in $AS$,  its value depends on which other items are also in $AS$.

More formally, this is how we calculate the value of an item $v$ in $AS$.  Let $a$ be the a closest ancestor of $v$ in $G$ that is also in $AS$.  Then the contribution of $v$ to the value of $AS$ would be its own value, plus the value of all the ancestors in the path between $v$ and $a$. (Since this is a DAG, there could be many of these ancestors. See formalization below).

This problem has important applications in computational workflow systems where you have limited storage, and you want to optimize the computational time of running a workflow (represented by a DAG) by storing some of the intermediate datasets for future use.

My questions

The problem is obviously NP-Hard because the Knapsack problem can be reduced to it. I have a feeling that it is likely that no pseudo-polynomial algorithm exists for it. Do you know of a problem that I could use to reduce to my problem to confirm those feelings? Or do you think that it is possible to produce a pseudo-polynomial algorithm for this?

EDIT: FORMALIZATION ON HOW TO COMPUTE VALUE OF $AS$

To succinctly define the value of $AS$ I will add to the notation from above a little bit. Let $v(z_i)$ be equivalent to $v_i$ from above. Then $v(z_i|AS)$ reads: value of node $z_i$ given answer set $AS$.

If $z_i \in AS$, then $v(z_i|AS)=0$.
Otherwise, if $z_i \not\in AS$, $v(z_i|AS) = v(z_i) + \sum_{z_j \in parents(z_i)}{v(z_j|AS)}$

Those two definitions are enough to then say that:

$value(AS) = \sum_{z_i \in AS}{v(z_i|AS-\{z_i\})}$

END OF EDIT


texts:
I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ and $B$ separately)

EDIT: (I have added the second question here since it was closed as a duplicate of this question. Note that  the optimal algorithm for the low rank version $p \ll n$ will not work for this.)

In general, if we have two full rank square matrices, what is the most efficient way to find SVD of a product of two matrices say A×B ? (Is it possible to find the SVD without explicitly multiplying them out?).

Is there a relation between the SVD of the product A×B and the SVD of the individual matrices (A and B) ?

Back to the first question:

One efficient way to get the Singular Value Decomposition when $p \ll n$ is to do a reduced QR on $A$ and $B$ i.e.

$A = Q_A R_A$ and $B = Q_B R_B$.

The above can be done in $\mathcal{O}(p^2n)$ cost.

I could then compute the svd of $R_A R_B^T = U_1 \Sigma V_1^T$ which is $\mathcal{O}(p^3)$.

Hence this will give me $$AB^T = (Q_A U_1) \Sigma (Q_B V_1)^T$$

The total cost is $\mathcal{O}(np^2)$.

However, I am wondering if there are other efficient ways to go about doing this to reduce the coefficient infront of $p^2n$. If I am right, the coefficient infront of $np^2$ is $3$ if we go about doing QR. The reason why I am interested in minimizing the coefficient is that my $n$ is really ginormous. So if I were to implement it, a cost cutting on the coefficient of the $\mathcal{O}(n)$ could be significant.

I am wondering if we could exploit the fact that the left singular vectors must span $A$ and the right singular vectors span $B$

i.e. we know that if $AB^T = U \Sigma V^T$, then

$$A = U \alpha \text{ and } B = V \beta$$

and we want $\alpha \beta^T$ to be diagonal and $U$,$V$ needs to be unitary.

EDIT What I essentially want is an exact rank $r<p$ approximation to the product $AB^T$ in the form $U_r V_r^T$. I am not looking for approximate or probabilistic algorithms.


texts: Criteria to determine if a complement of a graph has odd-holes

texts:
Is there any graph theoretic result for recognising graphs whose complement has no odd holes ?
I know about perfect graphs but they have the extra criteria being odd-hole free.


texts: Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

texts:
It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles.

  What are the best known upper bound and lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs? Given a cubic Hamiltonian graph, What is the complexity of finding the number of Hamiltonian cycles? Is it #$P$-hard?


texts: O(N) leader election on torus with orientation and non-positional identity

texts:
I'm really confused by this. Apparently there is a deterministic algorithm that does leader election on a torus with orientation and non-positional identity using only O(N) messages.  I'm unable to find to find any description of this algorithm, and I still don't understand how it is even possible.

On a general graph with sense of direction you should be able to do leader election using O(N log N) messages.  On complete graphs with sense of direction you do it with O(N) messages, because you have constant (1 message) communication with distant nodes.  But how could you do that on a torus?

Here are some relevant details: The system is asynchronous.  All processes start simultaneously.  Each node has a "sense of direction"; that is, each node knows which of its neighbors are north, east, south, or west.  Finally, each node has a unique ID (not related to its position in the torus).


texts:
Can you please suggest possible approaches for the following problem:

Find a path through graph vertices so that the distance (sum of edges weights) between two vertex $i$ occurrences would be no more than $D_i$. It is obviously infinite, so I want to have a generator for this path.

Thanks in advance.


texts: Consequences of $NP=coNP$ and $P\ne NP$?

texts:
We know that if $P=NP$ then the whole PH collapses.
What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?)

In shorter words, what would be the consequences of $NP=coNP$ and $P\ne NP$ ?


texts:
It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic approximation algorithms for this problem?

In some real world applications, the cost function does not satisfies the triangle inequality even in a weak sense. Also, the constraint of not having more than $k$ medians cannot be violated and the above approximation ratio is the ratio of solution cost over optimal cost.


texts:
The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify the definition as follows:

  A language $L$ is in $iPCP(r,q)$ such
  that there exists a verifier who
  tosses $r$ coins and queries $q$
  locations of a proof $\pi$ such that:

  If $x\in L$, then there exists a $\pi$ that makes the verifier accept
  with probability at least $3/4$.
  If $x\notin L$, then for every proof $\pi$, the verifier accepts with
  probability at most $1/4$.

There is an easy reduction from $3SAT$ to $\text{Max}2SAT$ (problem 5 in this) that gives a simple $iPCP$ for $3SAT$. And by definition, the class is closed under complement so it includes $coNP$ as well. Therefore, it is unlikely that there is a way to convert an $iPCP$ to a $PCP$ with the same parameters (well, that would at least mean $coNP = NP$).  (thanks to Peter Shor for pointing this out)

Have such incomplete PCPs been studied earlier?


texts:
I'm wondering if someone can give me the intuition behind why strict positivity of inductive data types guarantees strong normalization.

To be clear, I see how having negative occurrences leads to divergence, i.e. by defining:

data X where Intro : (X->X) -> X

we can write a divergent function.

But I'm wondering, how can we prove that strictly positive inductive types don't allow for divergence? i.e. is there some induction measure that lets us construct a proof of strong-normalization (using logical relations or similar)? And where does such a proof break down for negative occurrences? Are there any good references that show strong normalization for a language with inductive types?


texts: Small circuits for circuit evaluation problem

texts:
Let $\mathsf{CircuitEval}_{s, n}$ be the function which maps an $s$-gate circuit $C$ on $n$ bits and an $n$-bit string $x$ to $C(x)$. Assume that circuits are encoded as an acyclic sequence of assignments $k := g(i, j)$ where $i, j, k$ are wire labels.

I know this is a bit of a funny question, but what is the best known upper bound on the circuit complexity of this problem? There is an $O((s + n)^2)$ single-tape TM computing this function, and so by the Fischer-Pippenger simulation, size $O((s + n)^2 \log(s + n))$ should suffice. The quadratic comes from having to seek back and forth. Is it possible to do better? Is it possible to do in size $O(s + n)$?


texts: Efficient compilation of interaction combinators with infinite cell types to usual interaction combinators?

texts:
It is known that interaction combinators can implement any interaction net system efficiently. Now, let us define a modification of interaction combinators, which, instead of two types of fan cells, has an infinite number of fan-cells, labelled with unique integers. That system works exactly like the previous: two nodes with identical labels annihilate; two nodes with different labels duplicate. In other words, interaction combinators are a subset of that system, with only 2 possible ids.

How can you compile that new system to the former, without losing efficiency?


texts: Enumerating all s-t paths with cost exactly k

texts:
Is there a known algorithm for the following problem?  Given a simple weighted directed graph, a pair of vertices $s$ and $t$, and a real value $k$, enumerate all simple paths from $s$ to $t$ with cost exactly $k$.

I've heard of uniform search, but I'm not really sure if it can solve my problem.

I just read that finding one $s$-$t$ path with a given cost is NP-hard in general.  If all weights are $1$ and $k$ is one less than the number of vertices, this becomes the Hamiltonian Path Problem.


texts: Lower bound of checking graph connectivity on stream

texts:
I would like to check the status of the space lower bound for solving connectivity problem on stream in $p$ passes. The $\Omega(n/p)$ was stated in the literature but it seems to be for a slightly different problem. Did I miss something? Details below.

Given a graph $G$ of $n$ vertices in a stream (edges are presented one by one in a streaming manner), we want to check whether $G$ is connected. What is the minimum space an algorithm needs to solve this problem when it is allowed to read the stream for $p$ passes?

Feigenbaum et al. showed $\Omega(n)$ space for one pass algorithms for a class of problems that includes this problem (see Section 5.1) and stated that the $\Omega(n/p)$ space lower bound for connectivity was proved by Henzinger et al.. However, the only lower bound for "connectivity" problem is actually for the "$s$-$t$ connectivity" problem: given vertices $s$ and $t$, we want to check if $s$ and $t$ are in the same connected component (Theorem 6). The proof of this cannot be used for the connectivity problem since there might be many vertices incident to no edge.

So, my question is, for the specific version of connectivity that I stated, is there any lower bound known for $p$-pass stream?


texts: Is there a computation class describing FOR-programs, what are the limitations?

texts:
I've written an unpublished paper that describes FOR-programs.

FOR-programs are programs that only contain bounded for loops and basic operations (assignment, addition, multiplication, etc.). A bounded for loop is a for loop with a bound on the number of times that it can loop. This bound is fixed before entering the for loop for the first time and is not changed until the loop completes.

Is there a complexity class that captures this type of programs? Since the number of for loops in a program is known in advance, the time complexity is of course limited to $O(n^k)$ with $k$ nested for loops. Thus, all FOR-programs run in polynomial time. Are there additional limitations to this class of programs?


texts: Bisecting a set of points into two optimal subsets

texts:
I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm hoping for something faster than a general k-means clustering algorithm given that k=d=2. Can anyone point me in the direction of a good algorithm for this?

An exact solution not necessary if we have a good approximation.

Thanks!


texts:
Let $L$ be a language in P/poly.  There is then a deterministic polynomial-time Turing machine $M$ with polynomial-sized advice that decides $L$.  Consider the language $A(M)$ of all advice strings given to $M$ for instances in $L$.

  Is $A(M)$ in P/poly?

Edit 2: For $A(M)$ I am envisaging a specific, unique advice language; the existence of some advice language is guaranteed by the definition of $L$, so for $A(M)$ pick any such language, such as the lexicographically smallest.  Note that $A(M)$ is not necessarily decidable.

A handwaving (non-)argument for believing this goes something like this.  Every unary language is in P/poly, since a single bit of advice is enough to indicate whether the input is in the language or not.  In some sense advice languages are "sparsifications" of their associated languages; the advice language $A(M)$ contains a sparser representation of some of the information contained in language $L$, tweaked for the specific machine $M$.  (The advice language could be exponentially sparser, if every string is an instance of the problem, but for sparse languages the advice language may actually be polynomially denser.)  So it would seem to make sense that sparsifications of languages in P/poly could also be in this class.

Moreover, is there a general relationship between the complexity of $L$ and that of $A(M)$?

These seem like basic questions, so pointers to relevant literature would be appreciated if these are well-known.  A counterexample for the handwaving above would also be useful!

Edit: removed a sentence that wasn't even wrong, and based on the comments from Robin and Tsuyoshi, redefined the advice language to depend on $M$ only, as $M$ already depends on $L$.

Edit 3: I think Hrushikesh captured the essential problem here, so I am accepting the answer; Tsuyoshi also said essentially the same thing in a comment.  In short, $A(M)$ can be arbitrary.  Any language can be fed as advice to $M$ by waiting until the input instances of the decision problem are large enough for the next piece of advice to be within the polynomial bound.  This also means that I should really have asked the question in terms of a decision problem (where there are both YES and NO instances), not a language, to avoid the case where there are only finitely many YES instances.


texts: Strategy for grammar derivation of a formal language

texts:
I wonder, whether there is any strategy/ies for grammar derivation of a formal language. I'd be thankful, if you give me some hints, tips on how should one "think" trying to find a grammar. I'm interested in all types of grammar, but mostly in Typ-3 (regular grammar and it's languages).

For example, I need to find a grammar for $a^{n}b^{n}c^{n}$ language. And my questions are:
- can we decide at first sight, which grammar we should use? If yes,
- how should we find the right amount of variables?

I know, that this language can be generated by Typ1-Grammar (context-sensitive). And I have it's grammar (or one of possible grammars). But I would like to learn how to be able to find it by myself. I'll be thankful to you if you can help me..


texts:
It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \cap coUL$. Cho and Huynh defined a parametrized knapsack problem and exhibited a hierarchy of problems between $L$ and $NL$.

I am looking for more problems that are intermediate between $L$ and $NL$ i.e., problems that are :

known to be in $NL$ but not known (or unlikely) to be $NL$-complete and
known to be $L$-hard but not known to be in $L$.


texts:
The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, given a set of clauses each with two literals, is there a set of literals such that each clause has exactly one literal from this set.

The Complexity of Making Unique Choices: Approximating 1-in-k SAT by Guruswami and Trevisan gives a method for approximating Max 1 in 2 Sat. They state monotone (no negated literals) Max 1 in 2 Sat "admits an e-approximation in polynomial time".

I would like to find an exact algorithm for the Max monotone 1 in 2 Sat problem.


texts: What should I read to learn about the different models of computation used in algorithm and especially data structure analysis?

texts:
Are there any good surveys? Courses? Lecture notes?

I'm especially interested in material with practice exercises, if any is available.

Thanks!


texts:
Integer programming is NP-hard.

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

Integer programming in fixed parameters is P.

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


texts: What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

texts:
It is common to define $P$-completeness with respect to log-space many-one reductions.

I am looking for a complexity class $C \subseteq \mathsf{L}$ such that
there are $\mathsf{P}$-complete problems w.r.t. many-one $C$-reductions.

  What is the smallest known many-one reduction class $C$
  such that HornSAT is complete for $\mathsf{P}$ under $C$-reductions?

The question was originally posted on CS with no answer.


texts: Simple and cache-oblivious tries on fixed-length strings

texts:
Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory transfers and $O(k\log A)$ letter comparisons, where $B$ is the block size?

By predecessor problem I mean the problem of maintaining a set under insertion, deletion, and predecessor, where predecessor(k) finds the largest key in the set that is $\leq k$.

Ternary search trees achieve the letter comparison bound and are very simple, but can require $\Theta(k\log A)$ memory transfers.

String B-trees do better than the I/O bound I'm looking for, but they are not simple, and the cache-oblivious ones are even more complex and do not achieve the I/O bound in the worst-case. (String B-trees might achieve the comparison bound I'm looking for; I'm not sure.)

My intuition is that by fixing the size of the keys and relaxing the I/O bound, a simpler structure might be possible.


texts: Predict user's future location - location awareness mobile computing

texts:
This question is a part of an online course (Mobility Data Management) that I am currently auditing. A part of the project is to implement a system that can predict user's future location. This kind of application has recently got some interests from database and mobile application developers.

This is the problem statement: Assume that we are given a road network G (V,E), the recent motion history (trajectory) T, and current instant velocity v of a user, a temporal duration dt, and (optional) a historical trajectory database D of other users’ movements. Our goal is to estimate user’s location after dt.

I found that the following paper has a good description about what a road network and the trajectory data is: http://www.sis.pitt.edu/~xliu/papers/ceus.pdf

Does anyone has an idea on how to formulate a simple solution of this mobility awareness problem (predicting user's future location), and how to start the implementation (how you formulate the problem in an OOP way, such as: what classes are needed to represent the problem correctly). I cannot find the correct tags for this question, probably the moderator can add new tags such as: graph-networks, mobility-data, trajectory, etc.


texts: Why isn’t information-probability relationship linear?

texts:
I am completely new to information theory.
I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it is sub-linear?
As the formula goes,
$$
I(E) = -\log p(E).
$$


texts: Is the cutting lemma true with O(r) lines?

texts:
The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the interior of any region is intersected by $O(n/r)$ lines. For more see e.g. Matousek's book Lectures on Discrete Geometry or this post.

My question is whether the plane can be divided by $O(r)$ lines (into $O(r^2)$ regions) such that the interior of any region is intersected by $O(n/r)$ of the original lines.


texts: Equivalent formulation of complexity theory in Lambda Calculus?

texts:
In complexity theory the definition of time and space complexity both reference a universal Turing machine: resp. the number of steps before halting, and the number of cells on the tape touched.

Given the Church-Turing thesis, it should be possible to define complexity in terms of lambda calculus as well.

My intuitive notion is that time complexity can be expressed as the number of β-reductions (we can define away α-conversion by using De Brujin indexes, and η is barely a reduction anyway), while space complexity can be defined as the number of symbols (λ's, DB-indexes, “apply”-symbols) in the largest reduction.

Is this correct? If so, where can I get a reference? If not, how am I mistaken?


texts: What is the fastest algorithm to compute rank of a rectangular matrix?

texts:
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?

I am aware it can be solved through linear matroid intersection, which implies
an $O(mn^{1.62})$ time deterministic algorithm and an $O(mn^{\omega-1})$ time randomized algorithm. Is there an $O(mn^{\omega-1})$ time deterministic algorithm that more directly reduce the problem (or Gaussian elimination) to matrix multiplication?


texts: Computational hardness for sampling a uniform matching

texts:
A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one exists), so that the distribution of $M$ is arbitrarily close to uniform in total variation distance. This is sufficient to give a randomized approximation scheme for the number of perfect matchings of $G$.

Since Valiant has shown that the permanent of a binary matrix is $\#\mathsf{P}$-hard, we do not expect to be able to compute the number of perfect matchings of a bipartite graph $G$ exactly. I suspect that generating a uniformly random perfect matching of $G$ is also hard, but I do not know of any complexity theory evidence for this. So my question is:

  Is there any evidence that sampling a uniformly random perfect matching $M$ of a bipartite graph $G$ is computationally hard?

The important bit that differentiates between this question and the JSV result is that the distribution of $M$ is required to be exactly uniform. Any computational hardness here would have to be conditional, because if we could compute the number of perfect matchings in any bipartite graph, then we could also sample a uniformly random matching.

More generally, how does one show conditional hardness for sampling problems?


texts: Chromatic number of G+v where G is a cograph

texts:
Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.

Notations:

Denote by $\chi(G)$ the chromatic number of a graph $G$.
Let $V(G)$ denote the vertices of $G$. For any vertex $v\in V(G)$, denote by $N(v)$ the neighbors of $v$ and $N[v]=N(v)+v$ the closed neighborhood of $v$. Let $A\subseteq V(G)$, denote by $\langle A \rangle_{G}$ be the induced subgraph of $A$ of $G$.
Let $G$ be an undirected simple graph, and $H=G+v$ be a graph such that $G=H-v$, i.e., $G$ is the graph obtained by deleting $v$ from $H$. This type of notation is introduced in the paper Parameterized complexity of vertex colouring. For a graph class $\mathcal{F}$, let $\mathcal{F}+kv$ denote the graphs which can be built by adding at most $k$ vertices to a graph in $\mathcal{F}$.

Question 1:
Is the following statement true?

$\chi(G+v)=\chi(G)+1$ if and only if $\chi(\langle N(v) \rangle)=\chi(G)$, where $G$ is a cograph.

The "if" direction is easy, because $\chi(G+v) \le \chi(G)+1 $ and $\chi(\langle N[v] \rangle) = \chi(\langle N(v) \rangle) + 1$.
For general simple graph $G$, the "only if" direction is not true. For example, let $G$ be a $P_4$ (path of 4 vertices) and $G+v$ be a $C_5$ (cycle of 5 vertices).

Question 2:
If the proposition in question 1 is false. Is it easy to determine $\chi(G+v)$, where $G$ is a cograph.

Update: Jim showed than cograph+v is a subset of the class of perfect graph. Also he actually proved another more general theorem.

For any perfect graph $G$, $\chi(G)=\chi(G-v)+1$ if and only if $\chi(\langle N(v)\rangle) = \chi(G-v)$.


texts: Hierarchies in NP (under the assumption that P != NP)

texts:
Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.

Is there any evidence of more such 'layers' in NP? i.e. A hierachy of more than three classes starting at P and culminating in NP, such that each is a proper superset of the other?

Is it possible that the hierarchy is infinite?


texts: Are there decidable problems for which for no algorithm we can give time bounds?

texts:
Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?

I arrived at this question because I was thinking about the following:

Assume we
have a recursively enumerable, but undecidable problem. Assume further that I is
a "yes"-instance of the problem. Then for no algorithm which identifies the
"yes"-instances of the problem we can give a time bound in terms of the size n
of I. For if we could give such a time bound, we could decide the problem, as we
could simply conclude that I is a "no"-instance when the time bound is exceeded.

Since we cannot give a time bound for recursively enumerable, undecidable
problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we
cannot give a time bound.


texts: A small C-like language that turing machines can simulate

texts:
I am looking for a small language that helps 'convince' students that turing machines are a sufficiently general computing model. That is, a language that looks like the languages they are used to, but is also easy to simulate on a turing machine.

Papadimitriou uses RAM machines for this job, but I fear that comparing something strange (as a turing machine) to another strange thing (basically, an assembly language) would be too unconvincing for many students.

Any suggestions would be most welcome (specially if they came with some recommended literature)


texts:
I am writing my master's thesis in CS and I am working with alias analysis. The thing that I am interested in is intraprocedural, flow sensitive must- and may-alias analysis for Java-like languages.

I am searching for texts that describe the basics of this subject in a detailed way but has been unable to locate anything really suitable.

I have survived a number of text books on compilers and static analysis but not found anything there.

I have found many papers where alias analysis is used, but most of them are focused on the problem to which alias analysis is applied and do not describe the alias analysis algorithms in detail. Others focus on C which is not suitably because of the added complexity of general pointers.

The best text I have found is the paper Compositional Pointer and Escape Analysis for Java Programs by Whaley and Rinard. It is a brilliant paper and a good starting point but it doesn't discuss alias analysis specifically.

The problem seems so general so I expected there to be some canonical algorithms available to solve it.

Does anyone have any pointers to texts on this subject?


texts: Purely functional uniquely-represented deques

texts:
There are a number of purely functional deques that support $O(1)$ operations at each end. None that I know of are "uniquely represented" - deques with the same number of items can have different shapes.

In the imperative case, doubly-linked lists are uniquely represented deques with constant-time operations.

Hoogerwoord, in "A Logarithmic Implementation of Flexible Arrays", showed that Braun trees have logarithmic deque operations, and they are purely functional and uniquely represented.

Is there a deterministic uniquely represented purely functional deque with $o(\log n)$ operations?


texts: Find an approximate argmax using only approximate max queries

texts:
Consider the following problem.

  There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query is specified by a set $S \subseteq \{1,\cdots,n\}$ and the corresponding answer is $\max_{i \in S} v_i$. The goal is to use as few queries as possible.

This problem is easy: We can use binary search to find the argmax with $O(\log n)$ queries. i.e. Build a complete binary tree with $n$ leaves corresponding to indices. Start at the root and walk down to a leaf as follows. At each node, query the maximum value in the right and left subtrees and then move to the child on the side with the larger answer. Upon reaching a leaf, output its index.

The following noisy version of this problem has come up in my research.

  There are $n$ unknown values $v_1, \cdots, v_n$. These can be accessed with queries in which a set $S \subseteq \{1, \cdots, n\}$ is specified and a sample from $\mathcal{N}(\max_{i \in S} v_i,1)$ is returned. The goal is to identify $i_* \in \{1, \cdots, n\}$ such that $\mathbb{E}[v_{i_*}] \geq \max_i v_i - 1$ using as few queries as possible. (The expectation is over the choice of $i_*$, which depends on both the coins of the algorithm and the noisy query answers.)

Suppose we try to solve this using the same binary search strategy as before (but with noisy answers). It is reasonably easy to show that this achieves $\mathbb{E}[v_{i_*}] \geq \max_i v_i - O(\log n)$ and that this is tight in the worst case. We can reduce the error to the desired $1$ by repeating each query $O(\log^2 n)$ times and using the average (which drives down the variance). This gives an algorithm using $O(\log^3 n)$ queries.

Is there a better algorithm? I conjecture that $O(\log^2 n)$ queries suffice. And I believe I can prove a $\Omega(\log^2 n)$ lower bound. Also, the problem becomes easy -- i.e. $\tilde{O}(\log n)$ queries via binary search -- under the promise that there is a $\Omega(1)$ gap between the largest value and the second-largest value.
If it helps, you can assume all the values are between $0$ and $O(\log n)$.


texts: Coherence spaces and full completeness for the implicative fragment of linear logic

texts:
Linear logic isn't complete for coherence space semantics since $1$ and $\top$ get identified. But it is, I believe, complete for the fragment of linear logic whose only connective is $\multimap$.

I was wondering if there's a full completeness result for theories in the fragment of linear logic whose only connective is $\multimap$? I think this is equivalent to asking: is the term model of $\lambda$ terms whose variables only get bound exactly once (over some signature, modulo $=_{\eta\beta}$) a coherence space?

Since the system I'm interested in is very limited, I was also wondering if there are any simpler structures for which full completeness holds?


texts: Does k-Median problem become any easier when L = C?

texts:
In the $k$-median problem, $L$ defines as set of feasible facility locations and $C$ defines a set of client locations in a metric space.
The current best approximation guarantee for the problem is $2.675$ due to Byrka et al.  Do we have any better approximation guarantees for the problem when $L=C$? If not, is it possible to show that the same $(1+\frac{2}{e})$ hardness of approximation holds when $L = C$?

I am aware that the $k$-center problem admits a $3$-approximation in the general case. And, that it can be improved to $2$-approximation when $L = C$. Moreover, both these bounds are tight in their respective cases. I am hoping for a similar behavior for the $k$-median problem. Any help is appreciated. Thanks.


texts: Randomness versus Quantumness in factorization

texts:
The best deterministic factorization algorithm that is currently known runs in $O(N^{\frac{1}4+\epsilon})$ arithmetic steps.

Randomness and quantumness improves upon this.

I believe Quadratic/Number field sieve run in randomized subexponential time. What is it that quantumness provides that sieve techniques cannot provide? What exact barrier does Shor's algorithm break that randomness cannot?


texts:
I'm reading Arora and Barak's book "Computational Complexity", Chapter 19.4 "Local Decoding and Hardness Amplification". And I'm confused with the following question:

Let $f:\{0,1\}^n\rightarrow\{0,1\}$, then $f$ can also be viewed as a binary string of length $N=2^n$. Using some Error Correcting Code $E:\{0,1\}^N\rightarrow\{0,1\}^M$ with distance $2\rho$ and we get $g=E(f)\in\{0,1\}^M$, let $m=\log M$, then $g$ can be viewed as a function $g:\{0,1\}^m\rightarrow\{0,1\}$. In principle, if $g$ can be computed for $1-\rho$ fraction of $\{0,1\}^m$, then we can compute (maybe not efficiently) $f$ for all $\{0,1\}^n$.

If this can be computed efficiently for some $E$, we're done with some worst-case hardness to mild hardness reduction. So we define Local Decoder for $E:\{0,1\}^N\rightarrow\{0,1\}^M$ handling $\rho$ errors to be an algorithm $D$ given random access to a string $v\in\{0,1\}^M$ such that $\triangle(v,E(u))<\rho$ for some $u\in\{0,1\}^N$, and an index $i$, runs for $poly(m)$ time and output $u_i$ with probability $\geq2/3$.

But here's the problem, Local Decoder is a probabilistic algorithm correct with probabilistic at least $2/3$ for every index, but what we require is a deterministic circuit that correct for every index.

To make it more clear, Local Decoder means we have PPT $D$ that $Pr_r[D(x,r)=f(x)]\geq2/3$ for every $x\in\{0,1\}^n$. $2/3$ here is arbitrary, but we can't find some fixed $r$ that $D$ will be correct for every $x$.


texts: Is Solomonoff Induction in $\mathsf{P/poly}$?

texts:
Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(L)_n=\chi_L(s(L)_{<n})$$

Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$

A language $U$ is called a "universal predictor" when

$$\forall L \in \mathsf{R} \, \forall n>>0:s(L)_n=\chi_U(s(L)_{<n})$$

A famous example is Solomonoff induction

It is easy to see $U \notin \mathsf{R}$ by considering $L = U^c$. The question is

  Is there a universal predictor $U \in \mathsf{P/poly}$?

More specifically

  Is Solomonoff induction in $\mathsf{P/poly}$?

It is not hard to see that a positive answer would imply $\exists A \in \mathsf{TALLY}:\mathsf{R} \subset \mathsf{E}^A$ ($A$ is s.t. $U$ is Cook-reducible to $A$ and we have $\mathsf{R} \subset \mathsf{E}^A$ since it is possible to apply $U$ to the sequence $\chi_L(n)$ to decide $L$ in exponential time). This implication seems surprising but I don't see why it's necessarily false

EDIT: Actually such $A$ exists:

$\lbrace w | \exists i,j \in \mathbb{N} : i \in L_j$ and $|w| = f(i,j) \rbrace$

Here $f : \mathbb{N}^2 \rightarrow \mathbb{N}$ is a bijection computable in polynomial time and $L_j$ is the $j$-th recursive language (I'm using an arbitrary enumeration of the recursive languages)

However a universal predictor in $\mathsf{P/poly}$ implies a stronger statement, namely, that there is $A \in \mathsf{TALLY}$ and some fixed polynomial $p(n)$ such that all languages in $\mathsf{TALLY} \cap \mathsf{R}$ can be computed in time $p(n)$ given an oracle for $A$

EDIT: The answer to the first question is positive. Showing this is equivalent to constructing a Turing machine with a special tape on which some fixed (input-independent) infinite string is written in the initial state s.t. this machine computes a universal predictor in polynomial time. To do this, imagine the special tape to be 2-dimensional. In row $i$ of the tape write infinite computable sequence number $i$ (i.e. computed by program $i$). The predictor then works as follows. Given an input of length $n$ it compares it to the first $n$ infinite computable sequences. The first sequence which matches the input is used for the prediction. If no sequence yields a match the predictor outputs $0$.


texts: Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

texts:
What is the best known query complexity of Goldreich-Levin learning algorithm?
Lecture notes from Luca Trevisan's blog, Lemma 3, states it as $O(1/\epsilon^4 n \log n)$.
Is this the best known in terms of dependence on $n$? I will be particularly grateful for a reference to a citable source!

Related question: what is the best known query complexity of Kushilevitz-Mansour learning algorithm?


texts:
Problem:

Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also fulfills f(v, e1, e2) = f(v, e2, e1)

For an Eulerian Path we then define the overall cost as the sum of costs of all path-neighboring edges and the vertex in-between.

The goal is to obtain an Eulerian Path that has a minimal total cost. This has to be done somewhat efficiently, so testing all paths is not an option. Ideally answers should outline an algorithm.

Background:

The goal is to find a path that is "smooth". An example here is the B point in the image below. The flow is a lot smother if we go clockwise through the loop when coming from C.

Thoughts:

I think it is important to understand how many variations exist for an Eulerian Path and how we would obtain them.

There exists one very obvious variation, which is changing the direction of the path. We don't need to consider this variation since f(v, e1, e2) = f(v, e2, e1)
For any vertex with 0,..,n incoming and n,..,0 outgoing path segments, the path can be altered by swapping the ith incoming with the ith outgoing edge for i in 0,..,n. However this needs some alterations when the start/end vertex is included as well. Maybe we can just ignore it. Example: Point B and D
We can further swap "inner pairings with outer pairings", i.e. ith incoming and ith outgoing can be swapped with jth incoming and jth outgoing respectively for i, j in 1,..,n. Again we need to ignore start/end edge. This rule only applies if >= 6 edges join in a single vertex.

It becomes more difficult when the cycles from the vertex overlap, because then we can swap between them as well. Or do we not need to consider this at all? It's getting complicated and I'm no longer sure about correctness. So I’m kind of stuck.

Can we somehow convert this into an optimization problem?
Are there any papers on this topic? I couldn't find any.
Should I approach the problem completely different?
Can we somehow achieve minimal cost while executing Fleury's or Hierholzer's algorithm?

Edit (Aug 7 '17)

This presentation seems very interesting: https://www.cs.rochester.edu/~stefanko/Talks/EULER.pdf Unfortunately I wasn't able to find a paper accompanying it. At least counting Eulerian Cycle is #P-Complete.

Considering finding a minimum Eulerian Cycle for simplicity and using the idea of the Hierholzer's algorithm, we can find all simple cycles in the graph efficiently using e.g. http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

We would then need to find the edge-disjoint edge cycle cover. But this still doesn't guarantee a minimal path or Eulerian Cycle, because we still have to fuse the sub-cycles together.

Edit (Jan 7 '18)

I've started looking at solving this for an Eulerian Cycle since we have to consider fewer edge cases and the cycle problem is easily converted into the path problem (see here).

There have been suggestions to solve this by optimizing for each node. However, as the next example shows (colors indicate Eulerian Cycle), the local optima "battle" for each other. The top node uses the local optima, however if we were to use the optimum for both nodes we would obtain two circles and no longer have an Eulerian path.

I'm thinking maybe we can break the Eulerian Cycle into several "locally optimal" walks and then fuse them together again (efficiently we could find those walks using the Hierholzer's algorithm and following the lowest cost edge). Not guaranteed to be optimal though I think (or is it if we fuse them optimally?).

What's next?
I'll try to save up for a bounty to give this question some more exposure.

Edit (Nov 6 '18)

Still looking for an answer. I will try to implement my technique suggested above next. I'm no longer looking for a perfect algorithm, but one that approximates the solution.


texts:
Notations

$\le$ is used for subgroup
$G = \langle A \rangle  $ means group $G$ is generated by set $A$
$P$ means polynomial time in input size.
$\Omega = \{1,2,3,\cdots,n\}$ is a input domain
Sym($\Omega$) means symmetric group on $\Omega$

Given: $G = \langle A \rangle, H = \langle B \rangle \le \text{Sym}(\Omega)$, where $G$ normalizes $H$.

Find : $C_G(H) = \{g \in G \mid gh =hg, \forall h \in H\}$

Question : Is it in $P$? Give an polynomial time algorithm if answer is yes. I know that If we drop the normal condition from the above problem then problem will not be in $P$. Also note that computing normaliser of subgroup $H$ is in P.


texts: correlation in an almost independent set of random variables

texts:
Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that are separated by at least one site are completely independent. For example:
$P(X_1, X_2, X_4, X_7) = P(X_1,X_2)\cdot P(X_4, X_7) = P(X_1,X_2)\cdot P(X_4)\cdot P(X_7)$.

In other words, whenever we look at a multi-variable dist', we can "break" it into blocks of contiguous variables.

Finally, assume that for any subset of $k<n$ variables, $\{X_{i_1}, \ldots, X_{i_k}\}$, we have $\Pr(X_{i_1}=X_{i_2}=\ldots=X_{i_k}=0) > 0$.

In that case, can I find a lower bound on $P_n\equiv \Pr(X_1=X_2=\ldots=X_n=0)$ ?

In particular, I would like to know, if there is a threshold $\delta_0$, such that for every $\delta>\delta_0)$, it must be that also $P_n>0$, and how this threshold depends on $n$.

A simple use of Lovaz local lemma says that if $\delta>7/8$ then indeed $P_n>0$. But I think that it can be improved. For example, for $n=3$, a direct calculation shows that for $n=3$, it is impossible that $P_3=0$ unless $\delta < (\sqrt{5}-1)/2 \simeq 0.61$.

Can you think of any method to attack this problem?


texts:
I have a problem where I want to find the maximum flow from $s$ to $t$, such that, for an edge $e \in E$, $f(e) = 0$ or $f(e) = c(e)$. Where $f(e)$ is the flow in the edge and $c(e)$ its capacity. Basically, if a solution uses an edge, this edge is saturated.

I know this is an NP-hard problem, but I would like to know if there is any similar problem in the literature. Searching on Google I could only find algorithms for the All-or-Nothing Multicommodity flow problem, but I guess that my problem is simpler. I don't need to solve this optimally, approximation algorithms or heuristics are fine.

Thanks!


texts: Lowerbound for the minimum distance between points in a "nice" triangulation

texts:
Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. That is, every face is a triangle.

Suppose that the resulting triangulation has the property that the smallest angle is greater than some constant $\phi$.

Given this, can we compute a lowerbound $f(n)$ on the minimum distance between the points?


texts: What can be some bachelor thesis ideas in Quantum random walks?

texts:
Note: Cross-posted on Quantum Computing Stack Exchange.

I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the applications of quantum walks to quantum algorithms. What can be some bachelor thesis ideas in quantum random walks? Can anybody suggest a starting point?


texts: In a random perfect matching of a regular bipartite graph, are all edges equally probable?

texts:
Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the case that, for arbitrary edges e and e', the probability e is in M is the same as the probability e' is in M?

Stated differently, I am asking the following: Is it the case that, for an edge e of a regular bipartite graph G, the number of perfect matchings that include e does not depend on e?


texts: we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?


texts:
I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is one that, for a true solution OPT, returns $OPT' \in [OPT - \epsilon, OPT + \epsilon]$. For an $\epsilon$-multiplicative algorithm, we have $OPT'' \in [OPT(1 - \epsilon), OPT(1+\epsilon)]$. While I can see the differences between these (for instance, if true OPT = 10 and $\epsilon = 0.1$, then in one case, the error is $\pm 0.1$, while in the other, it is $\pm 1$), I would like to know the answers to the following questions:

1) Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative (example, as stated in https://arxiv.org/pdf/0801.1987.pdf)?

2) When is one type of accuracy more important or relevant than the other?

3) How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to $\epsilon$-additive accuracy in time $T$, is it possible to say how fast it will be for $\epsilon$-multiplicative accuracy? (and vice versa)?


texts: Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

texts:
We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new sequence $s_r$ at each round $r\ge 1$ and the goal is to find the sequence closest to $s_r$ in $S$, possibly in an approximate way. The distance between two sequences is the Euclidean distance. How can we preprocess and organize the information of the sequences in $S$, to solve this problem focusing on the trade-off between time complexity and distance minimization?
I guess we can use sampling and randomized algorithms/data structures. Is there in the related literature any solution already found for this problem?


texts: Rigorous security proof for Wiesner's quantum money?

texts:
In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank has access to a giant table of random numbers, and that banknotes can be brought back to the bank for verification.  In Wiesner's scheme, each banknote consists of a classical "serial number" $s$, together with a quantum money state $|\psi_s\rangle$ consisting of $n$ unentangled qubits, each one either

$$|0\rangle,\ |1\rangle,\ |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2},\ \text{or}\ |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}.$$

The bank remembers a classical description of $|\psi_s\rangle$ for every $s$.  And therefore, when $|\psi_s\rangle$ is brought back to the bank for verification, the bank can measure each qubit of $|\psi_s\rangle$ in the correct basis (either $\{|0\rangle,|1\rangle\}$ or ${|+\rangle,|-\rangle}$), and check that it gets the correct outcomes.

On the other hand, because of the uncertainty relation (or alternatively, the No-Cloning Theorem), it's "intuitively obvious" that, if a counterfeiter who doesn't know the correct bases tries to copy $|\psi_s\rangle$, then the probability that both of the counterfeiter's output states pass the bank's verification test can be at most $c^n$, for some constant $c<1$.  Furthermore, this should be true regardless of what strategy the counterfeiter uses, consistent with quantum mechanics (e.g., even if the counterfeiter uses fancy entangled measurements on $|\psi_s\rangle$).

However, while writing a paper about other quantum money schemes, my coauthor and I realized that we'd never seen a rigorous proof of the above claim anywhere, or an explicit upper bound on $c$: neither in Wiesner's original paper nor in any later one.

So, has such a proof (with an upper bound on $c$) been published?  If not, then can one derive such a proof in a more-or-less straightforward way from (say) approximate versions of the No-Cloning Theorem, or results about the security of the BB84 quantum key distribution scheme?

Update: In light of the discussion with Joe Fitzsimons below, I should clarify that I'm looking for more than just a reduction from the security of BB84.  Rather, I'm looking for an explicit upper bound on the probability of successful counterfeiting (i.e., on $c$)---and ideally, also some understanding of what the optimal counterfeiting strategy looks like.  I.e., does the optimal strategy simply measure each qubit of $|\psi_s\rangle$ independently, say in the basis

$$\{ \cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle, \sin(\pi/8)|0\rangle-\cos(\pi/8)|1\rangle \}?$$

Or is there an entangled counterfeiting strategy that does better?

Update 2: Right now, the best counterfeiting strategies that I know are (a) the strategy above, and (b) the strategy that simply measures each qubit in the $\{|0\rangle,|1\rangle\}$ basis and "hopes for the best."  Interestingly, both of these strategies turn out to achieve a success probability of (5/8)n.  So, my conjecture of the moment is that (5/8)n might be the right answer.  In any case, the fact that 5/8 is a lower bound on c rules out any security argument for Wiesner's scheme that's "too" simple (for example, any argument to the effect that there's nothing nontrivial that a counterfeiter can do, and therefore the right answer is c=1/2).

Update 3: Nope, the right answer is (3/4)n!  See the discussion thread below Abel Molina's answer.


texts: What is the best known gap between ZPP and Deterministic communication complexity?

texts: I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?


texts:
A hylomorphism consists of an anamorphism followed by a catamorphism.
Is it possible to express linear regression as a hylomorphism?


texts:
In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due time and processing time such that the total time in which no job is processed is maximized. A schedule is given by start times $x_j\in S_j:=\{r_j,r_j+1,\ldots,d_j-p_j+1\}$. For instance, for five jobs with $(r_j,d_j,p_j)$ equal to
\[(1,3,3),\ (20,22,3),\ (10,11,2),\ (1,18,5),\ (8,26,5)\]
and a time horizon of 30, the first three jobs are fixed starting at times $x_1=1$, $x_2=20$ and $x_3=10$, and for the last two jobs it is optimal to start both of them at the same time $x_4=x_5\in\{8,9,10\}$. The objective value (number of time periods without any job) is
\[30-3-5-3=19.\]

The straightforward binary program for $n$ jobs looks as follows ($y_t$ is the indicator variable for the activity of the "plant" machine suggested in the comment by András Salamon)
\begin{align*}
\text{minimize}\ \sum_{t=1}^Ty_t&\\
\text{subject to}\qquad \sum_{t\in S_j}x_{jt} &=1 && j\in[n], \\
y_t-\sum_{t'\in S_j\cap[t-p_j+1,t]}x_{jt'} &\geqslant 0  && t\in[T],\ j\in J_t,\\
x_{jt}&\in\{0,1\} && j\in[n],\ t\in S_j,\\
y_t &\in\{0,1\} && t\in[T].
\end{align*}
Here $J_t=\{j\ :\ r_j\leqslant t\leqslant d_j\}$ denotes the set of jobs that can be "active" at time $t$. Interestingly, the constraint matrix is not totally unimodular in general, but the LP relaxation seems to have always integer optimal solutions. Writing down the dual also yields a problem which can be interpreted combinatorially, but so far I haven't been able to turn this into an integrality proof.

One can look at variants of the problem where the number of jobs that can be processed simultaneously is bounded, or there is a given partition of the job set such that no two jobs from the same part can be processed at the same time.
Has this kind of objective function been studied in the scheduling literature? Or is there any other related problem?


texts: Explanation of 1-generic to prove undecidability of halting problem

texts:
This question is about an answer in question

  Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

Bjørn Kjos-Hanssen answer states that:

  You can first show that the halting problem (the set $0'$) can be used
  to compute a set $G\subseteq\mathbb N$ that is 1-generic meaning
  that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a
  finite prefix of $G$. Then it is easy to prove that such a set $G$
  cannot be computable (i.e., decidable).

I have trouble understanding this sentence as I am new to forcing. For example, what does "finite prefix" mean here? Can someone explain this sentence? (I know what $\Sigma^0_1$ means.)

Can someone explain the general idea behind forcing? I am also looking for easy to read introductions articles and books about forcing.

edit: So, how can we prove that each $\Sigma_1^0$ fact about $G$ being decided by a finite prefix leads to the fact that $G$ cannot be computable?


texts: Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

texts:
Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience.

So, Iet $X = (X,d)$ be a Polish space, equipped with the Borel sigma-algebra and $P_0,P_1$ be probability distributions on $X$. Let $\mathcal M(X,X)$ be the measurable maps $X\rightarrow X$, and for each $T \in \mathcal M(X,X)$, let the measure $T_{\#}P_k$ be the push-forward of $P_k$ by $T$.  For $\varepsilon \ge 0$, let $\mathcal T_\varepsilon$ be the set of all $T \in \mathcal M(X,X)$ such that $\sup_{x \in X}d(T(x),x) \le \varepsilon$. Define $\alpha_\varepsilon$ via the optimization problem

$$
\alpha_\varepsilon := \min_{T \in \mathcal T_\varepsilon} TV(T_{\#}P_0, T_{\#}P_1).
$$

Note that by the data-processing inequality, it holds that
$$
0 \le \alpha_\varepsilon \le TV(P_0,P_1) \le 1.
$$
Unfortunately, this bound is presumably very loose as it is independent of the parameter $\varepsilon$.

Question

Is there a nontrivial upper bound on $\alpha_\varepsilon$ in terms of $P_0$, $P_1$ and $\varepsilon$ ? My wild guess (and hope!) is something of the form
"$\alpha_\varepsilon \le g(\varepsilon)TV(P_0,P_1)$",
where $g_\varepsilon:[0,1]\rightarrow [0, 1]$ is a nontrivial function such that $g_\varepsilon(t) < t$ for $t \in (0, 1)$.
Same question for the special case $X=(\mathbb R^p,\|\cdot-\cdot\|_\infty)$. Note that in this case, $\alpha_\varepsilon$ can be written as
$$
\alpha_\varepsilon := \inf_{T_1,\ldots,T_p \in \mathcal M(\mathbb R^p,\mathbb R) \text{ s.t } x_j - \varepsilon \le T_j(x) \le x_j + \varepsilon\;\forall j \in [\![p]\!]} TV(T_{\#}P_0,T_{\#}P_1)
$$
Same question for the Hamming cube $X = (\{0, 1\}^p, d_{\text{H}})$. In this case, we can rewrite
$$
\alpha_\varepsilon = \inf_{T:\{0, 1\}^p \rightarrow \{0, 1\} \text{ s.t } \sum_{j \mid T(x)_j \ne j} 1 \le \varepsilon,\;\forall x \in \{0, 1\}^p} TV(T_{\#}P_0,T_{\#}P_1)
$$


texts: Is it possible to boost the error probability of a Consensus protocol over dynamic network?

texts:
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a randomized $\delta$-error Monte Carlo protocol for Consensus in this setting, is it possible to use this protocol as a black box to obtain another Consensus protocol with smaller error?

Note that for problems with deterministic outcome (such as Sum), this can be done by repeatedly executing the protocol and taking the majority as the answer. However I am unable to figure out how for Consensus, so I wonder whether this is actually impossible to do.

--- Details ---

Dynamic Network.
There are $n$ nodes on a dynamic network over synchronous setting (thus the protocol will proceed in rounds). Each node has a unique ID of size $\log(n)$. There are edges connecting pairs of nodes, and this set of edges may change from round to round (but remains fixed throughout any particular round). There may be additional restrictions to the dynamic network that allows the problem to be solved by some protocol (such as having a fixed diameter), but it is irrelevant to our discussion.

The only information known to each node is their unique ID. They do not know $n$ or the topology of the network. In particular, they do not know who their neighbors are in the current round (neighbors are nodes that are adjacent to them with an edge). The only way to figure out the neighbors is after receiving messages from them.

How nodes communicate.
The only method of communication between nodes is by broadcasting messages under the $CONGEST$ model (D. Peleg, "Distributed Computing, A Locality-Sensitive Approach"). More specifically, in each round, every node may broadcast an $O(\log n)$ sized message. Then, every node will receive ALL messages that were broadcasted by all of its neighbors in that particular round in an arbitrary order. In particular, nodes may attach their IDs onto their messages, since their IDs are of size $O(\log n)$.

Binary Consensus.
The binary consensus problem over this network is as follows. Each node has a binary input ($0$ or $1$), and each must decide either $0$ or $1$ under the the validity, termination, and agreement for consensus with $\delta$ error:

validity means that for $z \in \{0, 1\}$, if all nodes have $z$ as its initial input, then the only possible decision is $z$.
termination means that each node must eventually decide.
agreement means that all nodes must have the same decision.
The error rate means that under worst case input and worst case network, the probability that the protocol does not satisfy any of the three conditions is at most $\delta$ over average coin flips of the protocol's coin.

Question. For a particular set of dynamic networks, suppose we have a lower bound on the average number of rounds incurred by any randomized $\delta$-error protocol $P$ for solving binary consensus under this settings such that $\delta < \frac{1}{3}$, under worst case dynamic network from this set, worst case nodes' inputs, and on average coin flips of the protocol. Does this bound automatically hold for any $\delta'$-error protocol for $\delta < \delta' < \frac{1}{3}$?.


texts: Problems outside of P that are not P-hard

texts:
While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.

A problem is $\mathsf{P}$-hard if any problem in $\mathsf{P}$ is reducible to it with $\mathsf{L}$ (or if you prefer $\mathsf{NC}$) reductions. A problem is outside of $\mathsf{P}$ if there does not exist a polynomial time algorithm to solve it. This means that there should be problem that are outside $\mathsf{P}$ but are not $\mathsf{P}$-hard. If we asume that FACTORING is outside of $\mathsf{P}$, then Peter Shor's answer suggests that FACTORING could be such a problem.

Are there any known problems (natural or artificial) that are known to lay outside $\mathsf{P}$ but not be $\mathsf{P}$-hard? What about under assumptions weaker than the factoring assumption? Is there a name for this complexity class?


texts:
To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.
I am looking for such examples that satisfy the following criteria:

The software/hardware using the algorithm should be in wide use right now.

The example should be specific.
Please give a reference to a specific system and a specific algorithm.
E.g., in "algorithm X is useful for image processing"
the term "image processing" is not specific enough;
in "Google search uses graph algorithms"
the term "graph algorithms" is not specific enough.

The algorithm should be taught in
typical undergraduate or Ph.D. classes in algorithms or data structures.
Ideally, the algorithm is covered in typical algorithms textbooks.
E.g., "well-known system X uses little-known algorithm Y" is not good.

Update:
Thanks again for the great answers and links!
Some people comment that it is hard to satisfy the criteria
because core algorithms are so pervasive that it's hard to point to a specific use.
I see the difficulty.
But I think it is worthwhile to come up with specific examples because
in my experience telling people:
"Look, algorithms are important because they are just about everywhere!" does not work.


texts: Polynomial convergence to optimal move of the UCT algorithm. Missing proof?

texts:
This is a question regarding the theoretical convergence guarantees of the UCT algorithm, a popular variation of the Monte Carlo Tree Search algorithm (used in games, planning, reinforcement learning, etc.)
There are two original references, both from 2006, and from the same authors.
[1]. http://ggp.stanford.edu/readings/uct.pdf
[2]. http://old.sztaki.hu/~szcsaba/papers/cg06-ext.pdf
The first one states, roughly:

Theorem 5 [1]:  UCT converges to the optimal move at a polynomial rate.

However, it provides no proof due to "lack of space" (most proofs in the paper are omitted). The second paper seems to study the exact same algorithm and states, roughly:

Theorem 6 [2]: UCT converges to the optimal move.

In this case the proof is included. However, below the proof the authors state that they are unable to provide convergence rate estimates.
Now, UCT is widely cited via reference [1] to converge to the optimal move at a polynomial rate. My two questions are the following:

Is the proof of polynomial rate convergence available somewhere?
Why do Theorem 5 from [1] and Theorem 6 from [2], together with the comment below it, disagree about the convergence rate?


texts: Conditional Results on Bounded Depth Circuit Hierarchy

texts:
$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.

$AC$-hierarchy is $\bigcup _{i =0}^{\infty}  AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with AND OR NOT gates. $ACC$-hierarchy is obtained by adding $AC$-hierarchy  modulo gates computing the number of $1$'s in a input mod $q$ is $0$ or not for fixed integer $q$. $\mathsf{TC}$-hierarchy is $\bigcup _{i=0}^{\infty}  TC^{i} $ , where $TC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with threshold gates. We consider classes of nonuniform circuits

I am interested in conditional results saying that if I were a bird, then blah blah...

More specifically, let $\mathcal{A,B}$ be large compleixty classes satisfying
$\mathcal{A} \subseteq  \mathcal{B}$ and let $H^{i}$ be the $i$^th level of a bounded depth circuit hierarchy $H$. Is there a result saying that if $H \supseteq  \mathcal{B}  $ then $H^{i} \supseteq \mathcal{A} $ for a fixed  $i$ ?

More concretely, is there a well know complexity class $\mathcal{L} $ with the result that if $\mathsf{NEXP} \subseteq H$ then $\mathcal{L} \subseteq  H^{0}$ ?


texts: Teaching end-course material in a computational-models course

texts:
As TAs in an undergrad course on computational models, every year we are faced with a dilemma of what material to teach in the last few weeks of the course.

To be specific, our typical syllabus is as follows (basically the first few chapters of Sipser):

Finite Automata: DFA, NFA, determinization, Myhill-Nerode, etc.
Turing Machines: computability (RE,R, mapping-reductions, undecidability results).
Complexity classes: P, NP, PSPACE, karp-reductions, Savitch's theorem, Time/Space Hierarchy theorems.

Now comes the question of what to do next (usually we have about 3 weeks left).

Option 1: NL, coNL, logspace reductions and the Immerman Zzelepcsényi theorem.

Option 2: Randomized complexity (RP, BPP), but in a very low level, since probability is not a prerequisite for the course.

Option 3: Communication complexity - describing a communication model with some very initial results, describing IP and trying to prove $IP=PSPACE$, but usually only getting up to $coNP\subseteq IP$.

Option 4: Kolmogorov complexity. (we haven't tried this one yet).

Other options are welcome.

The question, to be as precise as possible, is as follows:

Assuming that at least 50% of the undergrads are not interested in theory, and that most of them will not continue to grad school, what would be most fitting, so as to teach  interesting material (i.e. less definitions, more theorems), while keeping it somewhat relevant to other disciplines in CS (or, heaven-forbids, the industry)?

My personal answer: I think that NL is a good option - theoretically it is interesting since we have some impressive results (NL=coNL), and practically it is interesting since many exponential time algorithms can be composed with NL algorithms to produce PSPACE algorithms (e.g. NFA universality). On the other hand, one might argue that it is more important to get acquainted with randomized algorithms.


texts:
I apologise if this is off-topic.

It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was quite a useful resource.


texts: Can a Penrose tile cellular automaton be Turing-complete?

texts:
This question was based on an incorrect premise ... see Colin's comment below. Forget it.

This was inspired by the discussion on this Math Overflow question. First, I need to define our terms.

In a Penrose tiling, there are generally several different legal patterns of tiles which will cover a given region. A Penrose tile cellular automaton should be some rule that deterministically takes a Penrose tiling $T$ to a Penrose tiling $T'$, where each tile in $T'$ is deterministically given by looking at the tiles in a radius $r$ around the corresponding spot in $T$. You should be able to implement these by having a set of rules of the form: when a region of shape $S$ is covered by a pattern $X$ of tiles, replace it with a pattern $Y$ of tiles. In order to do this deterministically, you either have to make sure no two of your replaceable regions can overlap or have some priority ranking on these replacement rules. But certainly you can ensure this, and define lots of different Penrose tiling cellular automata.

What does it mean for a Penrose tiling celluar automaton to be Turing-complete. Here's what I think it should mean (although I won't insist on it in the answers): the halting problem should be reducible to the behavior of such an automaton. Let's take some canonical Penrose tiling $T_0$ that provides constraints on our starting position. We  start with an input $G$ to a universal Turing machine, and we'd like to decide whether the machine halts on input $G$. I would like some computable map from $G$ to a starting Penrose tiling $S$ such that $S$ differs from $T_0$ on only a finite set of tiles. We then run the Penrose tiling cellular automaton, starting with $S$, and wait for some finite canonical configuration $C$ at position $0$ in the Penrose tiling. I want configuration $C$ to appear at position $0$ if and only if the universal Turing machine halts on input $G$.

The strange thing about Penrose tiling cellular automata is that every finite legal configuration of tiles appears infinitely often in every Penrose tiling of the plane. Thus, our universal Penrose tiling is not only computing the behavior of our universal Turing machine on input $G$, it's also simultaneously carrying out the first steps of every other possible computation. This makes me doubt whether Penrose tiling cellular automata could be Turing complete. On the other hand, if they're not Turing complete, what is the class of computations that Penrose tiling cellular automata can perform?


texts:
The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions:

$1\le Q[i] \le n$ for all $i$
$Q[i] \ne Q[j]$ for all $i\ne j$
$Q[i]-i \ne Q[j]-j$ for all $i\ne j$
$Q[i]+i \ne Q[j]+j$ for all $i\ne j$

Each integer $Q[i]$ represents the position of a queen on the $i$th row of an $n\times n$ chessboard; the constraints encode the requirement that no queen attacks any other queen. It is easy to prove that there are no solutions when $n=2$ or $n=3$, and closed-form solutions are known for all other values of $n$.  Thus, as a decision problem, the $n$-queens problem is completely trivial.

The standard backtracking algorithm for constructing an $n$-queens solution speculatively places queens on a prefix of the rows and then recursively determines whether there is a legal placement of queens on the remaining rows.  The recursive subproblem can be formalized as follows:

Given an integer $n$ and an array $P[1..k]$ of integers, is $P$ a prefix of an array $Q[1..n]$ that describes a solution to the $n$-queens problem?

Is this more general decision problem NP-hard?

Several nearby questions are known to be NP-hard, including Latin square completion [Colbourn 1984], Sudoku completion [Yato and Seta 2002], and a different generalization of $n$-queens [Martin 2007], but this specific question seems to have escaped any serious attention.

Related cstheory.se questions:

Is the N Queens problem NP-hard?

Is the half-filled magic square problem NP-complete?


texts: Is there a 'very fast growing' hierarchy that would capture System F?

texts:
Particular ordinals in slow-growing and fast growing hierarchies can capture the expressiveness of many predicative type systems.

Is there a hierarchy of function that could possibly capture impredicative System F?


texts: Efficient generation of permutational invariant quantum states

texts:
Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one:
$$
|\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-1)\rangle,
$$
where $\pi$ runs over all permutations of the symmetric group $S_n$, e.g.
$$
|\psi_3\rangle = \frac16\left(|012\rangle+|021\rangle+|201\rangle+|210\rangle+|201\rangle+|210\rangle\right)
$$
be generated efficiently, i.e. in polynomial time? If so, how?

Choose $n$ to a power of $2$ if you need...


texts:
What is a simple toy research programming language that has simple denotational semantics (including numbers or reals) that is used often to demonstrate certain properties of programming languages, or other things?

I am looking to demonstrate an idea on a programming language, and I don't want it to be complex in syntax, and I also want it to have easy to understand denotational semantics.

I don't need a working implementation of the language. Just the syntax and denotational semantics for the syntax.

Thanks.


texts:
I was wondering about the self-information, the information content . If I have data and I measure different words in it, their probability and take the average mean of that, what is the lowest and what is the biggest outcome?

$$I(data) = \frac{\sum_{i=1}^{n} - log(P(word_i))}{n}$$

The summed up probability is one, but how does that change with the logarithm? It seems, if one word is very unique and another word takes up the rest of the data in a big quantity, than the information content is higher:

$$\frac{(-\log 0.9999) + (-\log 0.0001)}{2} > \frac{(-\log 0.9) + (-\log 0.1)}{2}$$

Does that mean, if one of the words limits to zero, that the information content becomes infinite? Does that make sense, seems strange.


texts: A Combinatorial Problem on Extremal Set Theory

texts:
Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?

(i) $\forall S\in \mathcal{F}$, $|S|=a$.

(ii) $\forall S_1,S_2\in \mathcal{F}$, $|S_1\triangle S_2|\ge b$, where $S_1\triangle S_2$ means the symmetric difference between two sets.

(iii) $\forall T \subseteq [n], |T|\ge c$, $\exists S\in \mathcal{F}$, such that $|S\cap T|\ge 0.5a$.

As mentioned below by Aryeh, a trivial case can be $\mathcal{F}=\{S_1,S_2\}$ with $S_1=[n/2]$ and $S_2=[n]-S_1$, where we have $a=c=n/2$ and $b=n$. Basically the problem asks under what condition of $a,b$ we can get $c=o(n)$.

Any known results or related ideas about nontrivial sufficient (no need to be necessary of course) condition of $a,b,c$ is appreciated.

This combinatorial problem rises from a communication game, and may have concrete connection with error-correcting codes.


texts: What is a zipper, and how does it relate to a tree-like structure?

texts: I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers be generalized to any data structure?


texts: Successful application of branch-and-bound methods for NP-hard problems

texts:
Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to suggest that it's more than just "one method" for solving these problems.

Anecdotally, I've heard that some of the best heuristics for SAT and integer programming come from branch and bound, so my question is:

  Can someone point me to any references detailing effective uses of
  branch and bound for NP-hard problems ?


texts: Is gaussian smoothing possible in less operations than O(N log N)

texts:
Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window):

$$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n $$

One can implement this operation (computing y for given x) via FFT in $n \log(n)$ operations.

The question I am interested: is $n \log(n)$ really a limit? If yes, how can I prove this? If not - how do I write a faster implementation?

Example If I had laplacian kernel instead of gaussian,
$$y_i = \sum_{j = 1}^{n} x_j e^{|i - j|}, \qquad i = 1, 2, ..., n, $$
I would be able to compute this in $O(n)$ operations.


texts: Best resources for string searching or pattern matching exercises

texts: I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.


texts: Arithmetic coding, the termination symbol, and the empty string

texts:
Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as
$[0, P(a), P(a)+P(b), 1]$.

Strings consisting of a bunch of $b$'s and $c$'s ending with an $a$ (the termination symbol) are valid for encoding. Strings with an $a$ in middle are considered invalid for encoding.

So its easy to construct strings with encodings lying in the interval $[P(a), 1)$. But does arithmetic coding assign any string an encoding in the interval $[0, P(a))$? Would the empty string qualify as being encoded to a bitstring lying in $[0, P(a))$? Since the empty string can be thought of as the string "$a$" or as just the termination symbol.

Since devoting space to encoding the empty string would seem pointless why not have the first division of the unit interval be
$[0, (P(b)-P(a))/(1-P(a)), 1]$ which corresponds to mapping $[P(a), P(a)+P(b), 1]$ to fill up the unit interval. Then subsequent refining divisions would use $[0, P(a), P(a)+P(b), 1]$ as usual.


texts: Topological properties of Delaunay triangulations

texts:
Do Delaunay triangulations satisfy any extra topological conditions over normal planar triangulations?

In other words, if $T$ is a topological triangulation of the plane, when does there exist points $x_i \in \mathbb{R}^2$ s.t. their Delaunay triangulation has topology $T$?


texts: Electrical engineering student interested in Theoretical computer science

texts:
I am sophomore studying electrical engineering and I have immense interest in pure mathematics and theoretical computer science. I have studied abstract algebra ,real analysis and little bit of topology and discrete math too. I am also an enthusiastic coder .

What is the 'roadmap' for an engineer interested in theoretical computer science and the best books for an undergrad student , which I should study in order to go ahead in this field ?


texts: How to get started with program synthesis

texts:
I am a CS Major, I am a programmer with 10 years of experience. i want to get to know about program synthesis. there are no video tutorials / courses available online.
i have researched about Emina Torlak, Ras Bodik, who offer courses here https://courses.cs.washington.edu/courses/cse507/14au/sched.html

Any pointers / materials ?


texts: Inherent limitation of Switching Lemma for finer lower bounds

texts:
The Switching Lemma is the one of the classic and most basic tools to prove concrete circuit lower bounds. We will only consider AC$^{0}$ circuits.

The Switching Lemma claims that we can get a shallow circuit by restricting most input wires at random. More precisely,

  Lemma (Håstad’s switching lemma)
  Suppose $f$ is expressible as a $k$-DNF, and let $\rho$ denote a random restriction that assigns random
  values to $t$ randomly selected input bits. Then for every $s$,
  $$Pr[f|\rho \text{ is not expressible as $s$-CNF} ]\leq (\frac{(n − t)k^{10}}{n})^{s/2}$$
  where $f|\rho$ denotes the function f restricted to the partial assignment.

My  question is about the reason why this lemma is NOT applicable to derive finer lower bounds of constant depth $d$ circuit complexity. For example, the PARITY function has a bound of $2^{\Omega (n^{1/(d-1)})}$.  Why do we fail to obtain  bounds such as $2^{\Omega (n^{1/(\sqrt{d})})}$,$2^{\Omega (n^{1/(\log{d})})}$, or stronger $2^{\frac{n}{\text{polylog}(n)}}$ for some boolean function?

It seems that the number of remaining so called star variables, which are not be fixed by restrictions, is too small to be considered as "an input size".

  Let $F(s(n),C)$ be the Maximum number of star variables to reduce a circuit with depth $d$ and size $s(n)$ and $n$ input wires to a depth-$2$ circuit, that is, DNF or CNF. Let $F(s(n))=\min_{C} F(s(n),C)$. What are upper bounds and lower bounds as tight as we can at this moment for the following concrete $s(n)$s?

  $s(n)=F(2^{Cn^{1/(\sqrt{d})}})$ or $F(2^{Cn^{1/(\log{d})}})$ or $F(2^{\frac{n}{\text{polylog}(n)}})$


texts: Communication complexity of finding common element of two subsets

texts:
Suppose that Alice receives a subset $S \subseteq \{1,\dots,n\}$ and Bob receives $T \subseteq \{1,\dots,n\}$.  It is promised that $\lvert S \cap T \rvert = 1$.  What is the randomized communication complexity of determining the common element $S \cap T$?

My interest in this is as follows.  The zero-communication cost of this problem is $\log n$ since Alice and Bob can just guess $S \cap T$ using public coins and abort if they guess wrong.  However, I can't think of an $O(\log n)$ cost communication protocol.  Since it is not known whether zero-communication cost is much less than randomized communication cost, I am thinking that I am missing something obvious here.

Zero-communication cost is defined as follows.  After Alice and Bob receive their inputs, they must not communicate at all.  However, they share public coins, and they are allowed to answer with "abort".  If neither party aborts, they must provide the correct answer with $2/3$ probability.  The zero-communication cost is the negative log of the probability of not aborting.  In arxiv:1204.1505 it is shown (among other things) that nearly all known lower bounds on communication complexity are in fact lower bounds for zero-communication.

Update: @Shitikanth showed that the communication complexity is $\Omega(n)$.  So, apparently this gives a gap between communication cost and zero-communication cost.  But arxiv:1204.1505 seems to give the impression that no such gap is known.  What am I missing?


texts: Matching problems that are easy for bipartite graphs but hard for general graphs

texts: Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?


texts: Families of LDPC codes with constant error fraction corrected

texts:
I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.

For example, I know that Sipser and Spielman proved that there is an algorithm that can correct a constant fraction of errors for expander codes (in Expander codes, 1996).

But, is there any equivalent theorem for other families of LDPC codes (like regular LDPC or irregular LDPC, for example)? References would be useful.

Thanks!


texts: How to introduce recursion to Simply Typed Lambda Calculus while at the same time keeping strong normalisation?

texts:
Suppose you have a version of the STLC with one base type, similar to:

 data Tree = Branch Tree Tree | Leaf

Now, suppose you want to add recursion to that language, while still guaranteeing termination. Someone suggested a "Recur" primitive, which can only be applied at sub-expressions of pattern matches, making the following legal:

id (Tree a b) = Tree (id a) (id b)
id Leaf = Leaf

This is obviously terminating, so that sounds like a good idea. Now, mind that function:

foo (Tree (Tree a b) c) = foo (Tree a c)
foo (Tree a b) = Tree (foo a) (foo b)
foo Leaf = Leaf

Now this function is obviously terminating, but it includes a recursion that is not applied directly to a sub expression of a pattern match, namely, foo (Tree a c), so you can't express it on the suggested system. My question is: is there a more general way to introduce recursion that will still guarantee termination without making some valid cases illegal?