texts: To what extent supervised learning ERM learn first-order knowledge

texts:
Suppose I have a collection of (hidden) first-order rules:
$$
\mathcal{R}: \{ Q_i(x) => P_i(x) \}_{i=1}^{k}
$$
all defined over $x \in \mathcal{X}$.

I can use these rules and (automatically) generate a large collection of (training) data for my supervised system: $
\mathcal{D}: \{(x_i, y_i)\}_{i=1}^{n}
$, say for $y_i \in \{-1, +1\}$, and run a supervised system on this sampled data, and test on a heldout set.

If my rules are compatible (not contradictory) a rule-based system should be able to get a perfect score on the sampled set.
However, I am not sure how would a supervised do on this.

Are there any possibility/impossibility on the ability of supervised systems for learning first-order rules (possibly with some assumptions) and based on finite samples?

This is basically the reverse of rule-learning, in which the goal is to learn some rules $\mathcal{R}$, given a training data $\mathcal{D}$.

I did a little bit of Googling but didn't get anything directly relevant (all I found was algorithms for first-order rule induction or training supervised systems that use 1st order rules as features). That said, it's possible that I am missing some results on this. Would appreciate any thoughts on this.


texts: Fault-tolerant programming languages / paradigms?

texts:
I've been passively thinking for a long time, what could be the foundation for programming systems that can tolerate their own and other systems' bugs (not even speaking of environmental conditions such as hardware errors).

The thing is, I don't believe that it's possible to eradicate programming errors, and the fabric of current programming languages and systems is too brittle - a system can completely stop operating because of an off-by-one-error or a race condition (or a distributed race condition between several systems), which seems stupid if you think about it - we don't see the universe halt because of an explosion somewhere, or a society halt because of a typo in a law.

Therefore, it seems to me that type systems, formal verification are not the way to go - they merely protect the brittle systems instead of making them robust. Neither are fault-tolerant distributed protocols, since they assume that at least the protocol is implemented perfectly correctly, and that participants aren't making the same error.

I wonder, what has the PL community invented so far in this area?

Is there hope for a solution, or is this problem equivalent to building "strong AI" (could be, since living systems recover from transient errors by having goals and employing intelligence)?


texts: Is it a bad idea to critique someone's paper in my first publication?

texts:
I am currently facing a situation that I am not sure how to handle.

Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in a very reputable journal (IEEE Transactions on Information Theory) that proposed a new algorithm that consists of $2$ sub-algorithms, $A_1, A_2$ that are both used to solve the problem. Here is the caveat, Algorithm $A_1$ was shown to eventually converge without any run time gurantee (shown to converge with finite number of steps), while $A_2$ was shown to take $O(n^5)$.

My paper is essentially replacing $A_1$ with a new algorithm which is guaranteed to terminate correctly in $O(n\log n)$, hence bringing the overall time complexity when combined with $A_2$ to $O(n^6\log n)$.

So far, so good. I am fairly certain the paper can get accepted into the same journal since the new algorithm is highly non trivial and provides lots of new insight on the problem. However, 2 weeks ago, I was wrapping up everything and decided to give algorithm $A_2$ another read as well as its proofs. That's when I faced some problems.

One of the proofs in that paper is faulty, beyond repair. The author did a very big jump, and I managed to come up with a counter example essentially showing that the theorem he "proved" is false. I tried to fix his algorithm, but I couldn't. So I tried approaching it from a new perspective using his method, and I managed to get a new algorithm that replaces the faulty $A_2$, but it ran in $O(n^6)$.

Here is my problem, my advisor thinks I should definitely include this in my paper as I've essentially replaced both algorithms $A_1, A_2$. However, If I just say I have an $O(n^6)$ when there is an $O(n^5)$ known, its going to raise eye brows. The only way I can pass this is if I actually take jabs at $A_2$ and show that its actually wrong, but I feel that "attacking" a paper in my first publication is a really bad idea.

Any ideas?

EDIT: Contacted the author and he acknowledged the mistake. He agreed to be mentioned in the new paper and he showed quite the interest in the $O(n\log n)$ algorithm. He also contacted IEEE Transactions to see if they can add a correcting note. This went way smoother than I thought it would. Thanks everyone!


texts: Reference for a circuit lower bound for slightly superexponential time

texts:
It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem.

My question is following: do we know any non-trivial lower bounds for any of the following classes?

$Time(2^{n \sqrt{\log(n)}})$
$NTime(2^{n \sqrt{\log(n)}})$
$Time(2^{n \sqrt{\log(n)}})^{NP}$

Instead of $n \sqrt{\log(n)}$ could be any function in $o(n \log{n})$. After $n \log{n}$ the straightforward diagonalization should start working.


texts: Faster join of treap-like data structures with approximately the same size

texts:
Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $T_1$ and $T_2$ in time $O(1+|h(T_1) - h(T_2)|)$, where $h(T)$ denotes the height of a tree $T$ (as long as trees store their height).

This is also possible for red-black trees, and I assume many other kinds of balanced trees as well.

Is this possible for treaps or treap-like data structures? What if we leave out $t_r$?

The treaps paper in Algorithmica shows how to do this in $O(\min(h(T_1),h(T_2)))$ expected time. If there is a way to perform O(1) expected join on treaps (or treap-like data structures) with roughly the same size (or root priority), I think it might be possible to use a trick of Kaplan & Tarjan of bootstrapping the spines in order to make treaps (or treap-like data structures) with doubly-logarithmic join.


texts: What are interesting algorithmic questions for groups in table representation?

texts:
I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{NP}$ and $\text{co}\mathcal{NP}$ and even for groups whose derived series has length two, we don't how to do isomorphism in $\mathcal{NP}$ $\cap$ $\text{co}\mathcal{NP}$.

Question 1 : What are the interesting algorithmic questions to answer about nilpotent group class or its sub-class   ( which is non-abelian ) other than isomorphism problem?

Question 2 :  What are interesting questions to answer about groups when given in the table representation other than isomorphism? A non-interesting question is to find the intersection of two group or to find the order of any element. Testing membership is also not interesting as the input given is a table.


texts: Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?

texts:
For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}_{y\in Y}({\chi_s(y)})$.
The question I have is, do there exist distributions that can be efficiently computed such that at most polynomially many Fourier coefficients are non-zero?


texts: How to prove that a circular prop is uninhabited?

texts:
Consider the following inductive definition of "ElProp" in coq:

Inductive El : Set :=
  | R1 : El
  | R2 : El
  | R3 : El.

Inductive ElProp : El -> Prop :=
  | C1 : ElProp R1 -> ElProp R2
  | C2 : ElProp R2 -> ElProp R1
  | C3 : ElProp R3.

Observing that "(ElProp R1)" is uninhabited, I state the following theorem:

Theorem excircular : ElProp R1 -> 1>2.

I expect the theorem to be valid, much like the following theorem:

Theorem exfalso : False -> 1>2.

Since there are no inhabitants in "False", inverting "False" is enough to prove "exfalso". But how do I prove "excircular"? In general, how can we prove that circular propositions are uninhabited?


texts: Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification

texts: Who was the first person to show that a language is in NP if a certificate for the language can be verified in polynomial time?  Do we have a paper that formally proves this?  When did the TCS community start de-emphasizing non-determinism in favor of verifiability? I cannot, for the life of me, find a good reference for this beyond texts like Papadimitriou and Arora and Barak.


texts: Are there any "two-sided" strong blenders?

texts:
My question is related to explicit extractors and strong blenders. We can define explicit strong blender in a straight forward way.

I want to know if there are any known explicit strong blenders $\small\text{BLE}$ such
that

$$\: (X,Y) \mapsto \small\text{BLE}\normalsize(Y,X) \:$$

is also a strong blender?


texts:
I have a question about a answer of a question which is proposed in this stack exchange.

The Past Question

One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma.

Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.

My question is about upper bound of Threshold function which is a natural generalization of majority function.

The formal definition of the threshold function is the following one.

DEFINITION:

$THR(x_{1},...,x_{n})=
  \begin{cases}
    1 & a_{1}x_{1}+\cdots +a_{n}x_{n} \geq t \\
    0 & otherwise
  \end{cases}
$

We assume that each weight $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$

QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?

Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .

Answer

Kristoffer Arnsfelt Hansen said that:

1.$General$ $weight$ $threshold$ $gates$ can be computed by polynomial size depth 2 circuits built from $majority$ $gates$. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.

My Question

$majority$ $gates$ is a monotone gate which is computes a monotone function. A monotone functin does not decreace its function value by increasing the number of "1"s in the input 0-1 bit string. However, $General$ $weight$ $threshold$ $gates$  is NOT a monotone function. For example, we can check the function which output 1 if and only if $2x_{1} -5x_{2} + 3x_{3} \geq 3.5$ is not a monotone function because increasing the value of  $x_{2}$ brokes the monotone property.

My question is :

For a givern arbitrary threshold function $THR:\{0,1\}^{n}\rightarrow \{0,1\}$ with arbitrary real number weights and with no monotonicity, can we construct a constant depth circuit with $poly(n)$ threshold gates such that for any gate, any weight of the gate is integer number and is at most $poly(\Delta) $, where $\Delta$ is fan-in of the gate?


texts: Stable recovery of signals by $\ell_1$ optimization

texts:
Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \leq \epsilon$.

Now we solve the so-called $P_1^\epsilon$ optimization question to get, $\hat{x} := \min \Vert x \Vert_1 \text{ s.t } \Vert {D}x - y \Vert _2 \leq \epsilon$.

Then under certan RIP conditions on D  and some constant $C$ it follows that, $\Vert x^* - \hat{x} \Vert \leq C \epsilon$. Can someone kindly reference me the exact theorem and proof of this statement?

Are there more general forms of such a result?
I would be glad to get some references in that direction too.


texts: Word length using entropy : Maximum entropy criteria

texts:
The question is based on research paper  titled, Markovian language model of the DNA and its information content
In the supplementary document, the Authors show how they determine the word length of DNA sequence using entropy. A word is a consecutive occurence of DNA symbols. The optimal word length is selected as the one which produces maximum entropy out of all the different length words. But it is not quite clear to me from the plot, if they are using Shannon's entropy rate to plot the curve or just entropy. This is because in the text they mention that the plot is entropy but th formula they have used is of the entropy rate. So, my question is what is the correct way to determine word length using entropy concept.

Consider a toy example for which the implementation in Matlab is given:

A sequence of data of length $N$ can be subdivided into equal sixed blocks each of length (size) $l$. For each block, $w$, we can calculate the entropy known as the block entropy. Considering, entropy calculation by varying the size of the blocks ie., the window size is different. The entropy of the entire sequence is $H_N = 1.99$.  I then create subwords using different sized windows : Window = [1,2,4,6,8,10,12]  This gives Shannon's entropy for each sub-word (block) as

$H_w =   \{H_1 = 1.99119952705784, H_2 = 3.20880064685926, H_4= 4.97725978596446, H_6= 6.10391179247315, H_8= 6.40200948312778,H_{10}=6.44186057426463, H_{12} =  6.45326152085405\}$
 respectively.
Out of these entropy values for each block the maximum entropy value is, maxEntropy = 6.4638 for block of size blksze = 12.

General questions, not specific to topic of DNA or text sequence data : My confusion and questions are

Based on these values of block entropy, is it possible to determine what is the optimal length $l$ of the sequence ? For which value of sequence  length $l <N$ would the entropy of this sequence $H_l$ converge towards the entropy of $H_N$? Please correct me where wrong.
Can entropy of the whole sequence be less than the block size? For equiprobable occurrece of symbols, $H_N \le log2(4)= 2$ this is the theoretical value. But, when the block size 12 I got entropy for $H_{w} = H_{12} = 6.45326152085405$ which is greater than $H_N = 1.99$. I don't know if this result is correct and what I should expect theoretically.
Is my implementation correct? How to infer the plots?

Details:

Consider a source that emits codewords consisiting of adjacent symbols of length $l$. The sequence length is $N > l$. If the source is binary ($n=2$ symbols), then I have $N(w) = n^l$ possible words of length $l$. Each word is associated with a probability and I need to estimate the probability numerically since it is unknown.  Let, $n=4$ and the alphabet set is $A = {1,2,3,4}$.  Let the symbol sequence be $s =[2, 3, 4, 1, 2, 2,1, 3,2, 1, 2, 4,\ldots]' $ and $N$ denotes the number of elements in the sequence.

A block of size $l$ is defined as a segment of $l$ consecutive elements of the symbol sequence or in other words a concatenation of several symbols. If $w$ is  a symbol sequence of size $l$, then $N(w)$ denotes the number of blocks of $s$ which are identical to $w$.

$p(w)$ is the probability that a block from $b$ is identical to a symbol sequence $w$ of size $l$ i.e.
$$p(w) = \frac{N(w)}{n-|w|+1}$$

Let, a symbol sequence of length $N = 10$ be $s = \{1,3,4,1,2,1,1,3,4,2\}$, here the alphabet set is $\mathcal{A} = \{1,2,3,4\}$ and the number of symbols $|\mathcal{A}| = n = 4$. Each symbol can be represented by 4 bits.


texts: What is the complexity of #satisfiable instances of k-SAT ?

texts:
To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was:

  Consider the 3-SAT problem on n variables.  The number of possible distinct clauses is:

  $$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$

  The number of problem instances is the number of all subsets of the set of possible clauses: $I = 2^C$.  Trivially, for each $n \ge 3$, there exist at least one satisfiable instance and one unsatisfiable instance. Is it possible to calculate, or at least estimate, the number of satisfiable instance for any given n?

I was wondering what the complexity of the problem of counting the satisfiable instances of k-SAT on n variables is.


texts: Automated transformation into spigot algorithm?

texts:
Is there any research on transforming 'standard' algorithms into spigot algorithms?

I'd be happiest with automated transformations, but happy to learn about any research in this area.

For my purposes, I'd like to be able to transform a Haskell function into a spigot algorithm to improve garbage collection behavior.


texts: The number of maximal subsets with sum less than $m$

texts:
I've met this problem.
I would like to know to which complexity class it belongs.
Input

a set of positive integers $I$,
an integer $m$,
an integer $n$.

Question
Is the number of $S \subseteq I$ such that

$\sum_{s \in S} s \leq m$, and
$\forall e \in I \setminus S,\ e+\sum_{s \in S} s > m$

less than or equal to $n$?


texts: Is an infinite incomputable sequence random wrt a computable measure?

texts:
Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in the sense of Martin-Löf?

Or $\mu$-random is some weaker sense?

Clearly, $\omega$ is $\mu$-random for $\mu$-almost all sequences. So the question is what happens with the sequences from that set of measure zero.


texts: Partially filled jigsaw puzzle with six types of tiles

texts:
This is a slight variation of the question Are 'zero-one' jigsaw puzzles NP-complete? asked on cs.stackexchange.com.

What is the complexity of the following problem?

Input: an $n\times n$ Jigsaw puzzle with the six simple types of tiles shown in the figure below. $k$ tiles are already placed on the board and cannot be moved.
Question: can we correctly complete the puzzle placing the remanining $n^2 - k$ tiles on the board (tiles can be rotated).

The original question on cs.stackexchange is a particular case in which $k = 4n-4$ and the initial tiles are placed only on the border.


texts:
One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:

$K(n)$ is the Kolomogorov complexity of the string $h_{<2^n}$ of length $2^n$ whose $k$-th bit is 1 iff the $k$-th program halts
$C(n)$ is the minimal size of a Boolean circuit solving the halting problem for programs of size at most $n$
$T(n)$ is the time complexity of the halting problem made solvable by introducing an extra-tape into our Turing machine on which an infinite bit-string is written in the initial state. For example the bit-string can be an infinite look-up table: the $k$-th bit is 1 iff the $k$-th program halts. This allows a simple look-up algorithm to solve the halting problem but the complexity would be $O(2^n)$

$K$ is at most $O(n)$ since we can construct a program which encodes the longest-running program of length $n$ and checks whether the input program halts before that one. $C(n)$ is at most $O(2^n)$ because we can construct a "look-up table" circuit and $T(n)$ is at most $O(2^n)$ as noted above

What other bounds on $K$, $C$, $T$ can be found? In particular, are $C$ and/or $T$ less than exponential?

EDIT: Actually, $K(n) = n + O(1)$. To see this, consider $H_n$ an algorithm solving the halting problem for all inputs of length at most $n$ and $P$ the following program.

$P$ runs $H_n$ on $P$ itself. If result is "halts", it goes into an infinite loop. If result is "doesn't halt", it terminates.

$H_n$ fails to evaluate $P$'s halting correctly therefore the length of $P$ is greater than $n$. On the other hand $P$ is only longer than $H_n$ by a constant so $H_n$ can't be much shorter than $n$.

EDIT: If the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma_2$). To see this consider $S \subset \{0,1\}^*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q_x$: "Loop over all $p \in \{0,1\}^*$, halt if $V(x,p) = 1$". The size of $Q_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice

Note that $C$ is polynomial iff $T$ is polynomial. Consider $R_n$ a family of circuits solving the halting problem. Then we can construct an infinite-advice program $H$ for solving the halting problem by encoding $R_n$ as advice. This yields

$$T(n) = O(n \, C(n) \ln C(n))$$

On the other hand if we have $H$ an infinite-advice program solving the halting problem, we can construct a circuit $R_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so

$$C(n) = O(T(n)^2)$$

EDIT: If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy

EDIT: It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial


texts: Computed circuit complexity of decision problems

texts:
Has anyone explored what is the circuit complexity of classic decision problems such as Primes or Graph-Isomorphism for small input size $N$?

While most people are interested in the how the scaling goes as $N \to \infty$, I think it would also be interesting to see how this grows for small N. Sure, we now know Primes is in P, but it would be neat to see how it grows, and maybe even sharp changes in the growth rate of the graph as the inputs get large enough that a different algorithm becomes more efficient.

There is even the (unlikely) possibility that someone could extract from a sequence of circuits a general algorithm.

It seems like this approach could answer different questions than are usually asked about $N \to \infty$.  With the advances of algorithms knowledge (SAT solvers, etc.) and super computing power, concrete answers could be obtained for small $N$.

Are there any references or lists of results for people explicitly computing circuit complexity of decision problems for small $N$?

If there are people working on this, what algorithms do they currently use to solve the minimal circuit problem (given a boolean function and set of gates, output a circuit using the minimal number of gates necessary)?


texts: How important is knowing how to program for TCS?

texts:
Coming from a more mathematical background, I never really learned how to code.
I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code, but I don't really know any programming language.
I can imagine that someday I may have to implement some algorithms for my work, but then can I wait for this moment? Or is there something more?
How important is knowing how to code in TCS (in fields where programming is not directly involved)?
Are there reasons which could bring a CS theorist (for example) to know how to code? Is it worth spending a lot of time learning how to code? And if there are, is there a category (functional, imperative, object-oriented...) of programming language that would be more suited?


texts: On Equivalence of "gen-CONF" problem and "DH-exp-inv" problem

texts:
Let $g$ be a generator of a group of prime order $p$; $a,b ∈_R Z_p^+$

Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z_p$

And an algorithm $\mathcal{B}$ which on the same inputs, $g,g^a,g^{ab}$, outputs $a^{-1}$

Can I claim the algorithms $\mathcal{A} \equiv \mathcal{B}$?

While it's trivial to construct $\mathcal{A}$ using $\mathcal{B}$, can we also construct a $\mathcal{B}$ using $\mathcal{A}$?


texts:
Horn-SAT (conjunction of Horn clauses) is P-complete and XOR-SAT (conjunction of xor clauses) is in P. This means that there is a reduction from XOR-SAT to Horn-SAT weaker than a polynomial reduction.
I am looking for such a reduction; can anyone help me? Thank you.


texts: Is it possible to generate a collision free hash function from an equality function?

texts:
I'm wondering if it's possible to go from an arbitrary equality function:

Eq :: (obj, obj) -> bool

to an identity/collision-free hash function:

Id :: obj -> int

Where Id has the properties:

Eq(a, b) implies Id(a) == Id(b)
!Eq(a, b) implies Id(a) != Id(b)

This would be extremely helpful since it would allow indexable key-generation via Id(obj) for arbitrary types without the need to implement a hash function for those types (only an equality function).

So, basically, I'm looking for something with the signature:

F :: ( (obj, obj) -> bool ) -> (obj -> int)

That is to say,

F :: Eq -> Id

My intuition is that there's no purely functional way to do this (where Eq, Id, and F are all stateless), but I've been unable to prove this and would like confirmation.

It is of course possible to achieve this with a stateful Id function that keeps track of all previously Id'd objects and compares them to any input with Eq to determine if an id should be reused. This, however, seems to perform poorly after being executed on a large number of objects - linear time and space proportional to the number of unique objects operated on is the best I can do.

Is there in fact a purely functional way to achieve this that I'm missing? If not, is there an efficient stateful solution?


texts: How to derive a monoid's append from category theory

texts:
As I understand, a monoid $M$ is just a special kind of category; it has only one object and its morphisms can be composed through a composition operation. In principle, if $a$ is the object of the category, the composition operation should have the following signature:

$$
\circ:  (a \rightarrow a) \times (a \rightarrow a) \rightarrow (a \rightarrow a)
$$

However, in functional programming languages, the monoid's append has a different arity; for example in Haskell you have:

class Monoid a where
    mempty  :: a
    -- ^ Identity of 'mappend'
    mappend :: a -> a -> a
    -- ^ An associative operation

Ideally, categorical composition and mappend should be related i.e., we should be able to extract one from the other. But I cannot see why.


texts: Criteria for being below the least fixed point

texts:
Given a complete partial order $(D,\, {\leq})$ and a Scott-continuous function $F\colon D \rightarrow D$ and some fixed point $X = F(X)$.

Are there any criteria that ensure that $X = \mathsf{lfp} F$ where $\mathsf{lfp} F$ is the least fixed point of $F$?

Furthermore, are there any criteria that ensure that $Y \leq \mathsf{lfp} F$ for an arbitrary point $Y$?


texts:
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by

$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$

Notice that $f_p(A) = 0$ if and only if $A$'s columns are linearly dependent.
Therefore $f_p(A)$ can be seen as a measure of the linear independence of $A$'s columns:
the larger $f_p(A)$ is, the more independent $A$'s columns are.

When $p=2$, $f_2(A)$ equals the smallest singular value of $A$ and can be computed by doing SVD. When $p\neq 2$, is there any known algorithm than can compute $f_p(A)$? Or if this problem has not been studied before for the $p\neq 2$ case, is it likely to be of interest?


texts: A bounded-independence variant of the Berry-Esseen theorem

texts:
I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is mentioned there is a so-called "derandomized version'':

  If $X_{1},\ldots,X_{m}$ $C$-nice (that is, has bounded third moment), 3-wise independent., then $X_{1}+\ldots+X_{m}$ is $O(C)$-nice.

I am not sure whether the above is a statement regarding the third moment of the sum of 3-wise independent random variables, or there is indeed some variant of the Berry-Esseen theorem in the case of bounded independence.

Inspecting the proof, I see how 3-wise comes into play, however I could not find any source that discusses bounded-independence variants of this theorem. Are there any?


texts: Good examples for how to write well in TCS

texts:
I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples off the top of my head

  What are the best examples of quality mathematical writing you've seen
  ?

Rules:

I'd prefer TCS papers as far as possible. Our style is different enough from standard math papers that I think it's better to focus on TCS (also why I'm asking here and not on MO)
it would help if you mentioned what exactly you thought the paper did well. Not all exposition is good at everything - some papers have great proof outlines, some use notation really effectively and others convey intuition masterfully.
if possible, please link to the paper.

I'm hoping this can become a resource, like many of our other broad questions. I'm marking it CW for that reason.


texts: An intuitive justification - Metric Embedding Based Approximation Algorithms

texts:
Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course  offered at CMU .

I had a very basic question from the very  first lecture  of this course which I would like to get more intuition about. On page, $5$, the notes say that this technique can be used in a straightforward way to give an $\alpha$ approximation algorithms for problems like TSP if (say) the following hold.

(i) The metric embeds into a tree.
(ii) The embedding has distortion at most $\alpha$

What I am not sure about is whether the solution generated by using the embedding is even valid - because for all I know, it could be that the TSP solution on the tree uses only from among those edges which were contracted.

To be more precise, I feel more comfortable accepting that if we have got a mapping $f$ from the  original space $(X,d)$ to the tree metric $(V, d')$ which expands all the pairwise distances, then I can use the TSP solution on this tree as an approximate solution to the TSP problem on the original metric with approximation factor same as the expansion of the mapping $f$. I am not sure about how approximation factor can be the same as (or even related to) the distortion of the mapping $f$.

Thanks
-Akash


texts: What is the strongest known lower bound against SIZE(n)?

texts: What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But are there existential results saying, e.g., that $\text{EXP} \not \subset \text{SIZE}(n)$?


texts: What are examples of how non-uniformity can be useful?

texts:
I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that all languages have non-uniform circuits.

In particular, I'm interested in ways that objects known to exist via the probabilistic method and other non-constructive (or not-constructive-enough) proof methods can be leveraged using non-uniformity. I'd prefer the examples to be natural, not contrived. To be clear, a circuit for a contrived problem could be something like: given some language $L \in P$, I create a polynomial size circuit by computing some really hard function $f(|x|)$ using my advice and asking whether $f(|x|)^{n/|f(|x|)|} \oplus x \in L$.


texts: Looking for easy applications of fractional cascading

texts:
I want to give a couple of talks on fractional cascading, one of which will focus on applications.  I'm looking for applications that make use of the full version of fractional cascading, not just the simple search-in-k-sorted-lists version.

The applications presented in the original companion paper require a lot of machinery in addition to fractional cascading and are therefore not suitable.  My audience is general CS people who don't have specialized data-structures or computational-geometry knowledge.

Any help will be much appreciated.


texts: What are some good introductory books on type theory?

texts: I'm recently studying Haskell and programming languages.  Could someone recommend some books on type theory?


texts: Verifying Shor's quantum error correction code

texts: I know that Shor's 9 bit code can correct phase or bit flip, but I'd like to show that it can correct any type of error on a single qubit. I know that an arbitrary error can be expressed with the error base (phase flipe and bit flip), but I'm lacking the understanding of how does this assist me in deducing that any arbitrary error can be corrected?


texts: Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula

texts:
Please mind that I sometimes lack formal mathematical knowledge and English is not my first language, so I might miss the right words. Please change the tile if needed. Also, I have choosen this site as for me the question is loosely related to complexity.

Assume there is a randomly generated propositional formula f that includes n_total number of boolean variables.

I am not interested in all boolean variables, but only in a small subset of n boolean variables of the formula f (thus n < n_total). I want to find all possible combinations that the subset of n boolean variables can take that are part of some model of f.

What is the expected number of SAT calls that are needed to calculate all the combinations of the n boolean variables that I am interested in?

Exmaple:

Assume my formula f has 50 boolean variables and I am only interested in a subset of three (thus n = 3) boolean variables a1, a2, a3. What different truth values can a1, a2 and a3 take where the result is an assigment that is part of a model of f?

Naive solution:

a1 a2 a3
0 0 0
=>  check with a SAT solver, if the formula f has a model where all three variables a1, a2, a3 are false.

a1 a2 a3
0 0 1
=> check with a SAT solver, if the formula f has a model where a3 is true and a1 and a2 are false

a1 a2 a3
0 1 0
==> check with a SAT solver, if the formula f has a model where a2 is true and a1 and a3 are false

... etc. ...

a1 a2 a3
1 1 1
=> check with a SAT solver, if the formula f has a model where a1, a2 and a3 are true

Concerning the naive solution,
If I am interested in a subset of n boolean variables of f, all the combinations of the n variables can be calculated with 2^n and thus 2^3 = 8  SAT calls.

Optimizations over the naive solution:
My preliminary ideas: But what if two variables a1 and a2 are "xor", thus can never be true together in a model of f. In the set of the variables I am interested in (a1...a3 in the example), I can first try to find two boolean variables that are "xor". Or perhaps check all combinations of two variables whether they are "xor" and then proceed.

If I am interested in the expected number of SAT checks, is there an improvement over the 2^n number of checks of the naive solution? Assume the propositional formula f is randomly generated and has random characteristics.


texts: Is there an additive time hierarchy theorem?

texts:
I would like something like this to be true:

  Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), there is a language in $TIME[f(n)]$ that is not in $TIME[f(n) - g(n)]$.

Is anything like this known?  Can this be proven under any reasonable assumptions?  Would this have any interesting consequences?

By $TIME[f(n)]$, I mean the set of problems solved by a Turing machine that halts in exactly $f(n)$ steps or less - not to be confused with $O(f(n))$ or less, in which case the conjecture is trivially false when $f(n) >> g(n)$.


texts: Minimum spanning tree, but with an unusual objective function

texts:
This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.
If we have a rooted tree $T = (V,E)$ with root $r$, I first label the edges of the tree in the following way:
Starting from the root (let's say it has degree $d$), we will label the edges going to its subtrees $T_1, \ldots, T_d$ in decreasing order of size. The size of a tree is the number of nodes it has. So for example, the edges incident on the root will receive labels in $\{1,2 \ldots, $d$\}$ such that the edge with label 1 goes to the largest subtree, the edge with label 2 goes into the second largest subtree etc, and the edge with label $d$ goes into the smallest subtree.
We then label the rest of the edges in a similar way, by treating each vertex as a root of its subtree and labeling its edges in decreasing order of size of the subtree below it.
Given this labeling, if I look at a vertex $v$ in the tree, consider its path to the root. The cost of this vertex is the sum of the labels of the edges along this path.
The total cost of the tree is the sum of the costs of its vertices. Let us call the cost of a tree $\phi(T)$.
My goal is to come up with an algorithm for this problem: Given a general graph $G$, and root node $r$, find a spanning tree of $G$ which minimizes $\phi(T)$.


texts: Arithmetic complexity of matrix powering

texts:
Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables.

We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be exponentially large in $n$ and $m$ at least when $n=m^2$.

Could it be possible that the smallest circuit size can be polynomial while formula size is exponential at least for case $n=m^2$?

Do the answers differ much if we seek monotone circuits and formulas?


texts: Resources for mathematicians hoping to learn more computer science

texts:
Background:

I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g. recursion theory, lambda calculus, but the underlying CS is brushed under the rug. My main areas of interest - set theory and category theory - also have applications in computer science, but so far I've only studied them from the point of view of pure mathematics.

Problem:

My lack of any computer science background sometimes makes it difficult to see the motivation or intuition behind what is going on, or how it could be applied. I get by, but I feel like it would be healthier to branch out a little bit... it occurs to me that, for the benefit of my future research, I should learn some computer science.

Most CS books I've looked at haven't been very suitable for my purposes, either being too basic and untechnical, or presupposing the kind of CS background that I don't have. They seem to be aimed at people who are quite computer-savvy but who have little in the way in mathematical background - my situation is the opposite.

Question:

  What books or other resources are there which could help a mathematician-turned-logician in their goal of gaining a working knowledge of (theoretical) computer science?

I'm looking for something more wholesome than a few seminar talks and more in-depth than The New Turing Omnibus, but I don't have the time or resources to do another undergraduate degree. (It may be that I'm asking for something that doesn't exist.)

Sorry if the question is too vague or ill-posed. I felt it was more suitable here than on MSE but I'll be happy to migrate it if needs be.


texts: Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?

texts:
In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so interested in lower bounds, and I am very interested in program structuring techniques involving cool math.

The only related work I know is Fiore's work on lambda-definability for lambda calculus with coproducts, which uses Grothendieck topologies (roughly speaking) to model splitting and pasting the branches of if-statements together as coverings of programs. It's very interesting seeing a related idea arise in complexity theory! However, in this (and the followup work Balat and di Cosmo did with Fiore), they didn't need any serious machinery of algebraic topology, since they were more focused on decidability than efficiency.

However, binary decision diagrams (BDDs) (sort of the restriction of this problem to first-order) are extremely focused on efficiency, and I'm curious whether whether the cohomological approach nicely models any of the heuristics people use when building BDD libraries?


texts: Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?


texts:
Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that
$$\max_{v\in V}\frac{||v||_2}{||v_I||_2}$$
is minimum, where $v_I\in \mathbb{R}^m$ is the projection of $v$ to the coordinates indexed by $I$.

My question is:

Is this problem NP-hard?
If $k$ is a constant, $m$ can be unbounded, is this problem still NP-hard?
If it is NP-hard, what is the best (or any) approximate ratio we can achieve?

Any references in the literature will also be welcome.

Edit: This problem is equivalent to the following submatrix selection problem: let $V$ be a $k\times n$ matrix such that the row vectors of $V$ are orthonormal, find a submatrix $V'$ of $V$ by selecting $m$ columns from $V$, such that
$$\sigma_{\min}(V')\text{ is maximum},$$
where $\sigma_{\min}$ is the smallest singular value. Follows are (partial) answers to the question:

question 1 is NP-hard even for $k=m$, (slightly modified) reduction from X3C as in this paper
question 2 is still open. (I would be appropriated if one could provide any references)
For approximation, one can achieve the approximation ratio of
$$\frac{\left(1-\sqrt{\frac{k}{m}}\right)^2}{\left(1+\sqrt{\frac{n}{m}}\right)^2},$$by this paper, this gives a $\Omega\left(\frac{\epsilon m}{m+n}\right)$ bound for $m\ge (1+\epsilon)k$. When $m=k$, one can achieve $\Omega\left(\frac{1}{k(1+\epsilon)}\right)$ bound for any $\epsilon>0$, by using a local search algorithm by this paper.
The hardness of approximation is unknown, even for $m=k$.


texts:
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a planar graph can easily be computed by finding an embedding and taking the faces of the graph as the cycle basis.

I am interested in the more general algebraic problem. Let $V$ be some $n$-dimensional vector space over $\mathbb{Z}_2$ that has a 2-basis. That is, there exists a set of linearly independent vectors $\{b_1,\dots,b_n\}$ such that the matrix $B$, whose columns are these vectors, contains at most 2 non-zero entries in each row. If I am given an arbitrary basis for $V$ is there an algorithm to find 2-basis?

I'm not concerned with the running time, so I'd still be interested in seeing an inefficient approach. Are there any planarity testing algorithms that solve the algebraic problem? Has this problem been studied in any other contexts?


texts:
If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and wait for repeating one.
If we reached repeating state, we got to know that the program will loop inifinitely and will never terminate.
We just need a CPU/computer with bigger RAM for the task.

If so, does it mean that halting problem exists only for TM with infinite tape/RAM, so it is not possible to write down all tape states?


texts: is factoring harder than deciding if all prime factors lie in a particular residue class?

texts: Let $n$ be a large positive integer.  Suppose I want to know if all the prime factors of $n$ are congruent to, say, 3 mod 8.  Is this any easier than just factoring $n$?


texts: Complexity of counting m-cycles in a graph with n nodes

texts:
G is a planar graph with n nodes.
What are the complexity of following problems?

1-A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m< n)
2-B: complexity of counting all m-cycles in G, (Complexity of #A).

3- what is the complexity of A and B if G is an arbitrary given graph?

Pointing to books and papers is also useful...


texts: Simple example of halting-unprovable Turing machine

texts:
Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system?

Specifically, I'm curious whether there exists an example simple enough that the state transition of the Turing machine can be drawn as a reasonably-sized diagram.


texts:
I know that graph contractability is NP-complete: given $G=(V_1,E_1)$ and $H=(V_2,E_2)$, can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions?

Consider the following variant of the contractibility problem.  Each node in the input graph is labeled with a unique bit-string of arbitrary length.  The similarity of two nodes is defined to be the length of the longest common prefix of their labels; the weight of an edge is the similarity between its endpoints.  At each step, we are allowed contract any maximum-weight edge $(u,v)$ and label the new node with the longest common prefix of the labels of $u$ and $v$.  (There may be several maximum-weight edges.)  However, we must also preserve label uniqueness; if some other node already has the new label, we cannot contract the edge $(u,v)$.  Our goal is to minimize the total length of the node labels.

Are the following problems NP-hard?

Given a labeled graph $G$, find a sequence of legal contractions that minimizes the total length of all node labels in the resulting graph.
Given two labeled graphs $G$ and $H$, is there a sequence of legal contractions that transforms $G$ into $H$?


texts: obvious property of big O, big Omega, and big Theta

texts:
I'm trying to determine under what conditions the following statement is true.

The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$

where $O$ means "asymptotically bounded above (not necessarily tightly) by", $\Omega$ means "asymptotically bounded below (not necessarily tightly) by" and $\Theta$ means "asymptotically bounded both above and below".

I can't seem to find it stated outright in any of the books or wikipedia articles.

I'm sure there are counterexamples where we can construct weird functions to contradict the statement, but I'm wondering whether the statement is true for all "ordinary" functions we "typically" encounter (of course, it would be necessary to rigorously define "ordinary" here).


texts: Max flow: either saturate an edge or avoids

texts:
Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half through another edge.

Can this be formulated as a max flow problem with a polynomial time solution or is this problem hard?


texts: Taking Square Roots of Matrices over Z/nZ

texts:
Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n?  More specifically, suppose I generate a random matrix M, and square it.  Can a probabilistic polynomial time algorithm output M with reasonable probability?

If the matrix is diagonalizable, then does diagonalizing and taking the square roots work?  What if the matrix isn't diagonalizable, or if the diagonal has entries which aren't squares? What does this imply about square roots of the matrix?

Edits:

Also at:  https://math.stackexchange.com/questions/52474/taking-square-roots-of-matrices-over-z-nz

Clearly the problem is hard in the worst case, since the identity matrix has exponentially many square roots.  So I guess the question is what to do in the average case.


texts: Efficiently finding the minimum number of transpositions needed to sort a list

texts:
I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are.

For example, the list [1, 1, 2, 0] requires 2 transpositions:

[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2

The list [0, 1, 0, 0] requires 1 transposition:

[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3

The list [2, 2, 2, 2] requires 0 transpositions because it is already sorted.

Some meta information:
1) The list may have repeated elements, so simply using the Cayley distance between the sort and the identity permutation will not work.
2) This Math Overflow question is related.


texts: Connection between algebraic logic and computational complexity of logics?

texts:
I'm learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a given logic might help the study of the logic itself from a computational point of view.

In particular, is there any example of a complexity (or decidability) result for the satisfiability problem for some logics that was obtained by reasoning about its algebraic semantics?

For example, the semantics of propositional logic can be given in terms of boolean algebras. Is there any connection between them and the fact that SAT is decidable and $NP$-complete?


texts: Recovering a parse forest from an Earley parser?

texts:
I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date.  However, the algorithm in its traditional sense is a recognizer and not a parser, meaning that it can detect whether a string matches a particular CFG but not produce a parse tree for it.  My question is how to recover not a parse tree, but rather the parse forest of all possible parses of the given input string.

In Grune and Jacob's "Parsing Techniques: A Practical Guide" they illustrate an algorithm that can be used to recover a parse forest from the result of the Earley recognizer, but it is based on Unger's parsing method, whose runtime is O(nk + 1), where k is the length of the longest production in the grammar.  This means that the runtime is not a polynomial in the size of the grammar.  Moreover, Earley's original paper on the algorithm, which suggests an algorithm for recovering parse forests, is incorrect (see, for example, page 762 of this article by Tomita), although many sources still cite it as the appropriate way to recover the parse forest.

My question is whether it is possible, in polynomial time, to recover a parse forest for a given input string.  I have found a paper here that provides an algorithm for producing cubic-size parse forest representations for any parse using a simulation of a PDA, so this seems like it should be possible, but I have yet to find any way to do this.  Ideally, I'd like to do this without converting the input grammar to CNF (which would indeed solve the problem), since the resulting parse forest would be pretty messy.

Thanks for any help you can offer!


texts: Test set and benchmarks for linear programming

texts:
I am searching for test instances and benchmarks for linear programming, in particular, when solved by a simplex method and implemented with floating-point arithmetic.

This includes test suites, to verify my implementation of the simplex method, and benchmarks to measure the performance. The performance measure relevant for me is the number of steps on the vertex graph, rather than absolute clock time. Therefore medium size instances that do not induce to much ill-conditioning would suit me best.


texts: What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?

texts:
I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of

Counting the number of distinct s-t cuts in a oriented graph

It says that due to this consequnce, the cuts of an unweighted graph can be listed in polynomial time, but the claim is unreferenced.


texts: Why is differential privacy defined over the exponential function?

texts:
For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies

$$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.


texts: What is the complexity of decomposing 2k-regular multigraphs into k-stars?

texts:
Imagine we have a graph, which is 2k-regular, and we want to decompose it into copies of k-stars. Then we could just at first decompose the graph into 2-factors, orient each of the factors and then we can easily decompose the graph into stars: put a center in any vertex and choose k outgoing edges.

I would like to ask about the case of multigraphs (so that we can have now multiple edges between the same pair of vertices, but without loops). It is easy to construct examples, when we cannot find a decomposition. What is known about the complexity of a problem of deciding whether a 2k-regular multigraph has a k-star decomposition?


texts: Quantum complexity of TQBF with an untrusted oracle

texts:
This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics.
Let $L$ be the language of true, fully alternating totally quantified boolean formulas with some number $n$ of variables and circuit size $s = \operatorname{poly}(n)$.  The classical complexity of $L$ is $\tilde{O}\left(2^{0.793n}\right)$, and the quantum complexity is $\tilde{O}\left(2^{n/2}\right)$.
Now we assume we have access to an untrusted oracle for all subnodes of a particular formula $F \in L$.  That is, if the oracle is honest it will give the correct value of $F$ where any prefix of quantified variables is replaced by a chosen assignment of $\{0,1\}$ values.  We seek an algorithm which is correct for all oracles, untrustworthy or not, and ask for its worst-case complexity conditional on the oracle being honest.
In the classical case, I believe alpha-beta pruning is the optimal algorithm, and achieves complexity roughly $\tilde{O}\left(2^{n/2}\right)$.  (I'm not certain of this, so confirmation would be appreciated.)  Note that this matches the quantum complexity if we don't have an oracle.
Question: What is the quantum complexity of $L$ given an untrusted oracle, where complexity is measured conditional on the oracle being honest?
Motivation: The goal here is to model the situation where we have some particular TQBF, such as arising from chess or go, where there is enough structure that efficient, accurate heuristics are available but not enough structure to turn those heuristics into a rigorous proof of the game value.  In practice the heuristics would not be perfect (as in the honest oracle case), so this question is trying to get at a lower bound for the practical situation.


texts: What is the computational complexity of determining the mixing time of a Cayley graph?

texts:
Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles.  Numberphile has a nice series of videos of Diaconis explaining the proof.

I suspect that there's some interactive proofs to show the above.

Given a group $G$ having order $O(\exp n)$ and representation $\langle S \vert R\rangle$, consider the Cayley graph $\Gamma=\Gamma(G,S)$ on the $O(\exp n)$ vertices.

Suppose Merlin tells me that, starting from the identity and choosing  generators $g\in S$, a random walk on $\Gamma$ will converge to the stationary distribution $\pi$ rapidly, in time $t=O(n)$.  But I am suspicious, and I need to be convinced.

  Can I challenge Merlin to find a word of length less than or equal to $t$ in the group $G$ that equals a particular element of $G$ of my choosing, such that the word hashes on to a string of my choosing?

Here I have specialized to groups and Cayley graphs, which may be a red herring; any large, well-defined graph with a configuration space having nice enough properties may also be interesting.  Also, I haven't formalized mixing time, but I think most reasonable definitions are polynomially related.


texts:
Consider the problem

\begin{equation}
\min_{x\in X, y \in Y} f(x,y)
\end{equation}

Can I solve the problem by iteratively solving the following two sub problems?

\begin{equation}
x_{k+1} = \arg\min_{x\in X} f(x,y_k)
\end{equation}

\begin{equation}
y_{k+1} = \arg\min_{ y \in Y} f(x_k,y)
\end{equation}

If yes, is there any books/papers talking about this kind of approach?

Thanks


texts: Consequences of $NP\subseteq P/poly$ to $BQP$

texts:
A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$.

It is not known if $NP\subseteq BQP$.

In general, what are the consequences of $NP\subseteq P/poly$?

How does $NP\subseteq P/poly$ affect $BQP$?


texts: Fast Hamiltonian Cycle finding Algorithm

texts:
We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there is an open source implementation of the algorithm, we can contribute to the testing of that code.We have a graph which has at least 10 Hamiltonian Cycles and we want to use that to find a specific Hamiltonian Cycle (How easy/hard is that will be our question).

Abstract of Broder et al's  paper (from citeseer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1661 )

Consider a random graph G composed of a Hamiltonian cycle on n labeled vertices and dn random edges that "hide" the cycle. Is it possible to unravel the structure, that is, to efficiently find a Hamiltonian cycle in G? We describe an O(n 3 log n) steps algorithm A for this purpose, and prove that it succeeds almost surely. Part one of A properly covers the "trouble spots" of G by a collection of disjoint paths. (This is the hard part to analyze.) Part two of A extends this cover to a full cycle by the rotation-extension technique which is already classical for such problems.

Questions:

qn1) Has any one implemented Broder et al's algorithm?

qn 2) Are there recent paper better than Broder et al's algorithm –

qn 3) If there are 10 to 15 Hamiltonian cycles in a graph do their algorithm find all of them fast? –

A. Broder, A. M. Frieze and E. Shamir, "Finding hidden Hamiltonian Cycle," Random Structures and Algorithms , 5, 2006


texts: Series-parallel extension of a partial order respecting a given total order

texts:
Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.

An $O(n^3)$ dynamic programming algorithm suggests itself, solving the problem in increasing intervals of $R$, starting from empty intervals and terminating with the whole $R$. Is it possible to solve the problem in subcubic time?


texts: Does $P\neq NP$ imply any larger separation?

texts:
I've asked a similar question in cs.se, but didn't get a satisfying answer.

Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem?

Obviously, it means $\omega(n^c)$ for all $c>0$, but can we give a better lower bound?
For example, is it possible that $P\neq NP$ and $NP\subset DTIME(2^{logn\cdot log^*n})$, where $log^*n$ is the iterated log function?


texts: What are some standard books/papers on Information Theory?

texts:
I have started Information Theory classes just recently and was wondering what would be a standard book to purchase. I know I can go for basic introductory books but I also like to purchase standard books that I can use throughout my career for future reference purposes. I get some threads in forums about introductory books or basic books on information theory, but I can't find any about standard books on information theory.
P.S.:By standard book I mean like Cormen is for Algorithms


texts: Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

texts:
Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD).

Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a set $S$ in ${\cal C}$, returns a member of $S$.

Axiom of Determinacy: Let $S$ be a set of infinitely long bit strings. Alice and Bob play a game where Alice picks a 1st bit $b_1$, Bob picks a 2nd bit $b_2$, and so on, until an infinite string $x = b_1 b_2 \cdots $ is constructed. Alice wins the game if $x \in S$, Bob wins the game if $x \not \in S$. The assumption is that for every $S$, there is a winning strategy for one of the players. (For example, if $S$ consists only of the all-ones string, Bob can win in finitely many moves.)

It is known that these two axioms are inconsistent with each other. (Think about it, or go here.)

Other mathematicians pay little or no attention to the use of these axioms in a proof. They would seem to be almost irrelevant to theoretical computer science, since we believe that we work mostly with finite objects. However, because TCS defines computational decision problems to be infinite bit strings, and we measure (for example) the time complexity of an algorithm as an asymptotic function over the naturals, there is always a possibility that the usage of one of these axioms could creep into some proofs.

What is the most striking example in TCS that you know where one of these axioms are required? (Do you know any examples?)

Just to foreshadow a bit, note that a diagonalization argument (over the set of all Turing machines, say) is not an application of the Axiom of Choice. Although the language that a Turing machine defines is an infinite bit string, each Turing machine has a finite description, so we really don't require a choice function for infinitely many infinite sets here.

(I put a lot of tags because I have no idea where the examples will come from.)


texts: Complexity of extracting a coefficient of a polynomial in multiple variables

texts:
I'm looking for efficient algorithms for problems of the following type:
Let's say we have the variables $x_1,...,x_n$.
Over these variables, we are given a function $p_1\cdot ... \cdot p_m$, consisting of $m$ polynomials $p_1,...,p_m$, each of which is a multivariate polynomial itself, of the form
$$
\sum_{\matrix{0\le i_1\le k\\...\\0\le i_n\le k} }a_{i_1,...,i_n} x_1^{i_1}\cdots x_n^{i_n}
$$
, where $k$ is the highest degree appearing in any of the polynomials $p_1,...,p_m$.
How do we efficiently extract a coefficient from $p_1\cdot ... \cdot p_m$?

Efficient in this case is relative, as the problem is  #P-complete via MacMahon's Master Theorem (it reduces the problem of calculating the permanent to extracting a coefficient of a function as given above).
Nevertheless it's a popular function, implemented in many CAS-systems, and with many applications in e.g. combinatorics.
I'm interested in both efficient algorithms (with complexity bounds) as well as theoretical complexity bounds.


texts: Packing rectangles into convex polygons but without rotations

texts:
I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps.  In my problem you are not allowed to rotate the rectangles and can assume that they are oriented parallel with the axes. You are just given the dimensions of a rectangle and the vertices of the polygon and asked how many identical copies of the rectangle can be packed into the polygon.  If you are allowed to rotate the rectangles this problem is known to be NP-hard I believe. However, what is known if you cannot? How about if the convex polygon is simply a triangle?  Are there known approximation algorithms if the problem is indeed NP-hard?

Summary so far (21 March '11). Peter Shor observes that we can regard this problem as one of packing unit squares in a convex polygon and that that problem is in NP if you impose a polynomial bound on the number of squares/rectangles to be packed.  Sariel Har-Peled points out there is a PTAS for the same polynomially bounded case.  However, in general the number of squares packed can be exponential in the size of the input which only consists of a possibly short list of pairs of integers.  The following questions appear to be open.

Is the full unbounded version in NP?
Is there a PTAS for the unbounded version?
Is the polynomially bounded case in P or NPC? And my personal favourite, is the problem any easier if you just restrict yourself to packing unit squares into a triangle?


texts: Determining if a function is constant or not using period finding

texts:
Consider an arbitrary boolean function

$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$
which we write as:

$$f(x_1, x_2 ... x_n) $$
where each $x_i$ is a boolean variable

We note here that the function in question can be evaluated in constant time (is given by a constant time oracle).

The task is to determine whether this function is constant on all inputs or not.

We can consider the set of integers $Z$ modulo $2^n$ and look at their binary representation: noting that each digit in this binary representation corresponds to a value for one of the functional variables thus we write out $f$ as

$$f((Q \mod 2)_2, \frac{(Q \mod 4)_2}{2_2}, \frac{(Q \mod 8)_2}{4_2} ... \frac{(Q  \mod 2^n)_2}{2^{n-1}_2})) $$

Where $n_2$ means convert n to binary and division is integer division

We note that if this function is periodic with period = 1, then it must be constant. Can a Quantum Fourier Transform be employed to calculate the period of this function or merely test that the period is not equal to 1?


texts: Tradeoff Bounds for Halfspace Range Counting

texts: What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff.  According to Matousek's seminal 1993 paper (Theorem 6.2, Range Searching  with Efficient Hierarchical  Cuttings), we can do range counting for queries that are the intersection of $p$ halfspaces, for $1 \le p \le d+1$, using a data structure of size $O(m)$, for $n \le m \le n^d$, in $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ time.  For $p=1$ this is $O(n/m^{1/d})$ time.  However, Agarwal's survey on range searching (Table 36.3.2) claims the bound is $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$.  What is the correct statement of the bound?  Alternatively, what am I misunderstanding?  Finally, is there any hidden log term when $m=n^d$?


texts:
Recursion utilizes some self similar nature of an object (some representation of the given problem) to produce some quantitative measure (output) on the object through some algorithm (utilizing the self similar nature).

Can one represent algorithms as fractals (such a representation is not possible is not obvious nor how the representation should be if one exists) of some measurable information of the object the algorithm works on?

Has the tools used in the study of fractals provided any illuminating examples for lower or upper bounds for recursive complexity of algorithms?

I am looking for examples and references along the lines of whether algorithms can be treated as fractals and tools about fractals can be used to prove results about algorithms.

just added Would we be compelled to redefine some essential property of Sierpinski triangle if Walsh Transform or Sierpinski triangle transform is shown to be fully linear?
http://en.wikipedia.org/wiki/Walsh_matrix


texts: Implementations of Undirected Disjoint Paths

texts:
I'm looking into the Undirected Vertex Disjoint Paths problem:

  Given a list of tuples of vertices (s_i, t_i)

  Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects the given vertices. If they exist.

I'm in particular interesting in implementing a solution to this this for grid meshes. A situation that comes up in many pen+paper puzzles. I know this will be NP hard in the list of tuples, but hopefully not in the size of the graph.

I know about the Robertson-Seymour theorem, and its complications. However I'm wondering if the required minors might be well known for say planar graphs or meshes?

I also found mentions that Schrijver has made a more approachable polynomial algorithm, but I haven't been able to find mentions of complexity in terms of implementation.

Can anyone point me in a good direction?
I'd be interested even in solutions for just two pairs.


texts: Algorithms to generate consecutive primes

texts:
The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates two consecutive primes. For instance, 43 and 47 are consecutive primes.

The input is two positive integers $x$ and $y$ and I want two consecutive primes $p_1,p_2 \gt x$ and $|p_1-p_2 |\lt y$.

  What deterministic algorithms are known for generating consecutive prime numbers given $x$ and $y$?

Also, It would helpful to determine the complexity of the decision version:

INPUT: positive integers $x$ and $y$

QUESTION: Are there consecutive primes $p_1, p_2 \gt x$ and $|p_1-p_2| \lt y$?


texts:
Tactics are supposed to represent inference rules in a system, and it might seem unnecessary at first to formalize the semantics of tactics; nevertheless, modern theorem provers can have pretty complicated tactics which have complex semantics.

My question is, thus, has there been any work on the formalization of tactics in interactive theorem proving, either for Coq-style or LCF/HOL-style theorem provers?


texts:
Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$  represent a variable assignment and $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses satisfied by a variable assignment to $\varphi$. Then define Median-SAT as the problem of computing the median value of $f_{\varphi}(t)$ over all $t \in \{ 0,1 \}^n$.  For example, if $\varphi$ is a tautology then the solution to Median-SAT will be $m$ since regardless of assignment every clause will be satisfied. However in the case of $\overline{SAT}$ the solution to Median-SAT could be anywhere between $0$ and $m-1$.

This question arose when I was pondering two natural extensions of SAT, MAX-SAT and #SAT, and what the difficulty of the resulting problem would be if they were put together. For MAX-SAT we have to find a particular variable assignment to maximize the number of variables satisfied by $\varphi$. For #SAT we have to count how many assignments satisfy all $m$ clauses of $\varphi$. This variant winds up mainly as an extension of #SAT (and in fact of #WSAT), but retains some of the flavor of MAX-SAT in that we count the number of satisfied clauses rather than just deciding whether they're all satisfied or not.

This problem seems harder than #SAT or #WSAT. For each variable assignment #SAT decides the Boolean problem of whether that assignment satisfies $\varphi$ or not whereas Median-SAT determines "to what extent" $\varphi$ is satisfied in terms of the number of clauses that an assignment satisfies.

I realize that this problem is somewhat arbitrary; computing the average or mode number of clauses satisfied by each variable assignment seems to capture the same quality. Probably many other problems do too.

Has this problem been studied, perhaps under a different guise? How hard is it compared to #SAT? It's not clear to me a priori that Median-SAT is even contained in FPSPACE, although it does seem to be contained in FEXPTIME.


texts: Reusing 5-independent hash functions for linear probing

texts:
In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (Sufficiency: "Linear probing with constant independence", Pagh et al., necessity: "On the k-Independence Required by Linear Probing and Minwise Independence", Pătraşcu and Thorup)

It is my understanding that the fastest known 5-independent families use tabulation. Picking a function from such a family may be expensive, so I would like to minimize the number of times I do so while still preventing algorithmic complexity attacks as described in Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks". I'm less worried about timing attacks (i.e. adversaries with stopwatches). What are the consequences of reusing the same function:

When growing a hash table that is too full?
When shrinking a hash table that is not full enough?
When rebuilding a hash table that has too many "deleted" bits set?
In $k$ different hash tables that may contain some keys in common?
In $k$ different hash tables that contain no keys in common?


texts:
Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's Contributions to Computer Science.

  What are Grothendieck's major influences on theoretical computer science?


texts: Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

texts:
This question was originally posted on mathoverflow. Having obtained no answers after one month, I've decided to cross-post it here.

Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an odd number of hyperedges. Let $E_w$ be the number of distinct edge induced subgraphs of $H$ having $w$ vertices and an even number of hyperedges. Let $\Delta_w = O_w - E_w$.

Let $b_w$ be the number of bits required to encode $\Delta_w$, i.e. $b_w = log_2 \ \Delta_w$.

Let $b = \displaystyle\max_{\substack{w}} b_w$.

I'm interested in how $b$ grows. I would like to determine the best possible upper bound for $b$ which is expressible as a function of only $n$, $m$ and $k$. More precisely, I would like to determine a function $f(n,m,k)$ having both the following properties:

$b \leq f( n, m, k )$ for any $k$-uniform hypergraph $H$ having $n$ vertices and $m$ hyperedges.
$f(n,m,k)$ grows slower than any other function which satisfies the 1st property.

In general both $O_w$ and $E_w$ are exponential in $m$, therefore I expect that their difference $\Delta_w$ is not exponential in $m$ and thus that $b \in o( m )$.

However for the moment I've no clue on how to try to prove this.

  Questions

  How does $b$ grow with respect to $n$, $m$ and $k$?
  Are there any relevant results in the literature?
  Any hint on how to try to prove $b \in o(m)$?


texts: Which matrix of Q values is being used here?

texts:
This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task

In section 2.1, equations (5) and (6), I am wondering which Q values are being used to adjust the weights of the restricted boltzmann machine:

Option 1: the Q values generated by the original MDP

Option 2: the approximate Q values obtained by calculating the (negative of the) free energy of the RBM

Follow up question: When considering states $(s^t, a^t)$ and $(s^{t+1}, a^{t+1})$, how do we determine which values of $a^t$ and $a^{t+1}$ to use? Are these the optimal actions from the original MDP, or are these to be obtained through the alternating Gibbs sampling mentioned later on...(which doesn't make sense, since we would not have weights required for this CD)

Thanks for your help


texts: Testing isomorphism of asymmetric graphs

texts:
While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.

But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)?

Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 401-411).


texts: Universal Approximation Theorem — Neural Networks

texts:
I posted this earlier on MSE, but it was suggested that here may be a better place to ask.

Universal approximation theorem states that "the standard multilayer feed-forward network with a single hidden layer, which contains finite number of hidden neurons, is a universal approximator among continuous functions on compact subsets of Rn, under mild assumptions on the activation function."

I understand what this means, but the relevant papers are too far over my level of math understanding to grasp why it is true or how a hidden layer approximates non-linear functions.

So, in terms little more advanced than basic calculus and linear algebra, how does a feed-forward network with one hidden layer approximate non-linear functions? The answer need not necessarily be totally concrete.


texts:
Question: How do 'tactics' work in proof assistants? They seem to be ways of specifying how to rewrite a term into an equivalent term (for some definition of 'equivalent'). Presumably there are formal rules for this, how can I learn what they are and how they work? Do they involve more than choice of order for Beta-reduction?

Background about my interest: Several months ago, I decided I wanted to learn formal math. I decided to go with type theory because from preliminary research it seems like The Right Way To Do Things (tm) and because it seems to unify programming and mathematics which is fascinating. I think my eventual goal is to be able to use and understand a proof assistant like Coq (I think especially being able to use dependent types as I am curious about things like representing the types of matrixes). I started off knowing very little, not even rudimentary functional programming, but I'm making slow progress. I've read and understood large chunks of Types and Programming Languages (Pierce) and learned some Haskell and ML.


texts:
Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems highly unlikely to me, but I cannot find a counterexample.

Note that if we require that $A$ has low rank just over one characteristic (say $\mathbb{F}_2$) then the Hadamard matrix shows an exponential gap (i.e. rank $r$ over $\mathbb{F}_2$; rank $2^r$ over the reals), which is tight. However, this example does not seem to carry over when we require low rank in two different characteristics.

Update 6/9:
Li Qian gave a super-polynomial separation: a matrix $A$ with rank $r$ modulo 2 and modulo 3, but rank approximately $r^{\log r}$ over the reals. So I guess the real question is: is this the largest separation?

To build it, consider first boolean functions $f:\{0,1\}^n \to \{0,1\}$. Take the $2^n \times 2^n$ matrix $A$ given by $A_{x,y} = f(x \wedge y)$, where $x \wedge y$ is the bit-wise AND. The rank of $A$ (in any field) equals the number of monomials in the polynomial representation of $f$, which is essentially controlled by the degree of $f$.

Let $n=k^2$. Take

$$f(x_1,\ldots,x_n)=MOD_2(MOD_3(x_1,\ldots,x_k),MOD_3(x_{k+1},\ldots,x_{2k}),\ldots,MOD_3(x_{n-k+1},\ldots,x_n))$$

where $MOD_p(\cdot)$ is the boolean function which returns 1 if its input hamming weight is divisible by $p$. Then one can check that $f$ has degree $O(\sqrt{n})$ modulo 2 and modulo 3, but linear degree over the reals. This translates to a matrix $A$ with rank $n^{O(\sqrt{n})}$ modulo 2 and modulo 3, but rank $2^{\Omega(n)}$ over the reals.


texts: Proof that quantum computers can't easily invert permutations

texts:
Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(1)$ is even and $0$ if $\sigma^{-1}(1)$ is odd. This is the famous permutation inversion problem and it can be proven that this problem requires an exponential number of queries to the permutation oracle. There are many ways to prove this lower bound, like using the hybrid argument, or the adversary method, or showing this problem is equivalent to Grover's search. I am specifically looking for a hybrid argument.
I found one here (Theorem $3.6$), but it deals with random permutation oracles instead of a fixed oracle. I don't think that condition should be necessary. Also, the proof seems very complicated. Can someone provide a simplified treatment?


texts: Examples/Textbooks on amortized analysis of algorithms

texts: I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized analysis.


texts: Error in paper "Some NP-complete geometric problems"?

texts:
The paper in question:
M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .

This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree Problem, by reducing Exact Set Cover by 3-sets to these problems.

On page 3 (labeled page 12), right above Equation (2.2), it is stated that the number of crossovers is $q < 3nt$. In the example figure (Fig. 6) on page 4 however, this is clearly not true, as the number of crossovers $q=26$, whereas $3nt=18$ (as the number of subsets $t=3$, and the size of the set to cover $3n=6$).
I would understand if $q<3(3nt)$, is this an error?

PS: even if it's an error, it would likely not change the NP-completeness proof(s). I only ask to better understand the reasoning behind them.


texts: Solving linear program with 1 quadratic constraint complexity

texts:
Consider the following linear program,

$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \geq 0
$$
where $c_1, c_2$ are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form $\vec{y}M\vec{y}^T$ where $M$ for my problem is not positive semidefinite (and thus, non-convex) which is perhaps evidence of hardness

Listing specific questions below:

Can this problem be transformed into a linear program by taking logarithms?
Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem?

Edit : Cross posted question at math.stackexchange


texts: Prove Post Correspondence Problem Non-Recursive Without Reduction

texts:
Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are indices $i_1, \dots, i_k \in \{1\dots n\}$ such that $\alpha_{i_1}\cdot \dots \cdot \alpha_{i_k} = \beta_{i_1}\cdot \dots \cdot \beta_{i_k}$.

It is well known that PCP is not computable in any Turing-equivalent machine model. Usually, this fact is proven by reducing the Halting Problem (HP) to PCP, i.e. describing how to create a PCP instance $\Pi$ for an arbitrary Turing machine $M$ and an input $x$ such that $\Pi$ has a solution if and only if $M$ terminates on $x$.

Arguably, undecidability of PCP is more useful than of HP because it is removed from the notion of computation itself and therefore might be understood without having to read up on Turing machines (or equivalent models) first. Also, it is a more natural choice for many reduction proofs for not computation-related problems, e.g. in formal language theory.

It seems only fair to ask:

  Is there a proof for undecidability of PCP that does not employ
  reduction to HP (or similar problems)?

Note that I want to exclude chains of reductions that end up at HP in the end. Having such an independent proof might open up new ways for students and laymen to understand the underlying issues. Failing that, are there reasons for that lack? Do we need the kind of self-applicability we employ when proving HP not to be computable?

PS: I was unsure wether or not this question should go here or rather onto math.SE. As the proper place might depend on the level of answers, I went with the specialist community.


texts: Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models

texts:
In the POPL'14 paper "Replicated Data Types: Specification, Verification, Optimality" and the book "Principles of Eventual Consistency", the authors propose a formal framework for specifying distributed consistency models via the $vis$ (visibility) and $ar$ (arbitration) relations.

Visibility is an acyclic relation over operations. If an operation $a$ is visible to $b$, it means that the effect of $a$ is visible to the client performing $b$. $...$ We call two updates concurrent if they cannot see each other, i.e., are not ordered by visibility.
Arbitration is used to indicate how the system resolves update conflicts, i.e. how it handles concurrent updates that do not commute. It is a total order on operations. If an operation $a$ is arbitrated before $b$, it means that the system considers the operation $a$ to happen earlier than operation $b$.

A history $H$ (consisting of operations) satisfies a consistency guarantee $\mathcal{P}$ if it can be extended (by adding visibility and arbitration) to an abstract execution that satisfies them. One of the basic consistency guarantees is the return value consistency, which says that, in the context of read/write registers, each read should read from the last write visible ($vis$) to it according to the ordering specified by $ar$.

Given the background above, let us consider a simple consistency guarantee called read my writes:

Read my writes is a property that also applies to a sequence of operations performed by a single client. It guarantees the effects of all writes that were performed by the client are visible to the client's subsequent reads. If a client writes a new value for a data object and then reads this object, the read will return the value that was last written (emphasis added) by the client (or some other value that was later written by a different client).

The book above defines it as
$$\text{RMW} \triangleq (so \subseteq vis)$$ where $so$ denotes the "same session relation".
The CSUR'16 survey "Consistency in Non-Transactional Distributed Storage Systems" defines it as
$$\text{RMW} \triangleq \forall a \in H\vert_{wr}, \forall b \in H\vert_{rd}: a \to^{so} b \implies a \to^{vis} b \triangleq so\vert_{wr \to rd} \subseteq vis$$
where $wr$ and $rd$ denote the set of write operations and read operations, respectively.
However, I think these two definitions too weak to ensure the reads read from the last write, because they have specified only the visibility relation but not the arbitration relation. Without the arbitration order between the previous writes, a read may read from a stale write. Therefore, I think the definition for RMW should contain $so|_{wr} \subseteq ar$.

My questions are:

Are the two definitions for RMW correct? If not, what should it be?

More generally, what is the relationship between visibility and arbitration? Is it always required that $vis \subseteq ar$? If not, what are the consistency models that do not need $vis \subseteq ar$?

Related Post: Confusion about a formal definition of PRAM consistency


texts: Relation between fixed parameter and approximation algorithm

texts:
Fixed parameter and approximation are totally different approaches to solve hard problems. They have different motivation. Approximation looks for faster result with approximate solution. Fixed parameter looks for exact solution with time complexity in terms of the exponential or some function of k and polynomial function of n where n is the input size and k is parameter. Example $2^kn^3$.

Now my question, is there any upper or lower bound result based on the relationship between fixed parameter and approximation approaches or they totally do not have any relationship.For example for a problem $P$ is said to be $W[i]$ hard for some $i>0$ is nothing to do with having c-approximation algorithm or PTAS. please provide some references


texts: Randomized algorithm that "looks" deterministic?

texts:
Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n.  There's no known polynomial time deterministic algorithm.  There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem.  But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are many possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness.  I realize that the question is probably not fully specified...


texts: Can strong NP-hardness really be shown using plain polytime reductions?

texts:
I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I would have thought that you’d have to show that any numbers used in the reduction and the instances of the problem you’re reducing to were polynomially bounded in the problem size.

I then saw that Wikipedia gave the same general instructions for this sort of proof, but I wasn’t really convinced until I saw Garey & Johnson say basically the same thing. To be specific, they say, “If $\Pi$ is NP-hard in the strong sense and there exists a pseudo-polynomial transformation from $\Pi$ to $\Pi'$, then $\Pi'$ is NP-hard in the strong sense,” and “Note that, by definition, a polynomial time algorithm is also a pseudo-polynomial time algorithm."

Of course, I take the word of Garey & Johnson on this—I just don’t understand how it can be correct, which is what I’d like some help with. Here’s my (presumably flawed) reasoning…

There are strongly NP-complete problems, and all these are (by definition) strongly NP-hard as well as NP-complete. Every NP-complete problem can (by definition) be reduced to any other in polynomial (and therefore pseudopolynomial) time. Given the statements of Garey & Johnson, it would therefore seem to me that every NP-complete problem is strongly NP-complete, and, therefore, that every NP-hard problem is strongly NP-hard. This, of course, makes the concept of strong NP-hardness meaningless … so what am I missing?

Edit/update (based on Tsuyoshi Ito’s answer):

The requirement (d) from Garey & Johnson’s definition of a (pseudo)polynomial transformation (the kind of reduction needed to confer NP-hardness in the strong sense) is that the largest numerical magnitude in the resulting instance be polynomially bounded, as a function of the problem size and maximal numerical magnitude of the original. This, of course, means that if the original problem is NP-hard in the strong sense (that is, even when its numerical magnitudes are polynomially bounded in the problem size), this will also be true of the problem you reduce to. This would not necessarily be the case for an ordinary polytime reduction (that is, one without this extra requirement).


texts: Quantum Fourier Transform question regarding measurement

texts: When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first place. For a trivial example, consider addition of two polynomials, using DFT, or even FFT, this is straight forward, but if we consider the same setting in the quantum case, where FFT, or DFTs are substituted with Quantum gates, how can the result of the addition two polynomials be accomplished.


texts: An improper planar coloring with monochromatic component size $\leq 2$

texts:
Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color.  A monochromatic component is defined to be a connected component in the subgraph induced by the set of vertices that receive the same color, and the question is to ask for the minimum number $\lambda$ of colors needed to color a graph such that largest monochromatic component has size no more than $C$.
The traditional coloring can be considered as $[\lambda,1]$-coloring in this setting.   Hence to find the minimum number of $\lambda$ is NP-hard for planar graph in general.

My question is, how about $[\lambda,2]$-coloring of planar graphs, or more generally, $[\lambda,C]$-coloring for $C \geq 2$?

This can be viewed as a dual problem of what is studied by Edwards and Farr, where $\lambda$ is fixed, and one is asked to find the minimum size of $C$.


texts:
For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known.
From a purely theoretical perspective, however,
exactly optimal sorting algorithms (minimizing exactly the number of comparisons)
are only known up to $n=16$ and for particular values of $n$, as detailed in Kuth's The Art of Computer Programming, vol3, § 5.3.1, or Peczarski's New Results in Minimum-Comparison Sorting; Algorithmica'04.

Are there hardness results on the complexity of optimal sorting? In particular the following two problems:

given $n$, compute $S(n)$ the minimal number of comparisons necessary to sort $n$ numbers
given an arbitrary set of $k$ comparisons already computed, find a next comparison that should be asked in an optimal sort
same question, assuming the set of $k$ comparisons is not arbitrary but the result of running the first $k$ steps of an optimal algorithm.

(The last question being one possible formalization for: 'what is
   the complexity of computing an optimal sorting algorithm')


texts: Monotone bijections between lists of intervals

texts:
I have the following problem:

Input: two sets of intervals $S$ and $T$ (all endpoints are integers).
Query: is there a monotone bijection $f:S \to T$?

The bijection is monotone w.r.t. the set inclusion order on $S$ and $T$.
$$\forall X\subseteq Y \in S, \ f(X) \subseteq f(Y)$$

[I am not requiring the reverse condition here. Update: if the reverse condition were required, i.e., $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$, then this would be in PTIME because it amounts to isomorphism testing of the corresponding inclusion posets (which have order dimension 2 by construction), which is in PTIME by Möhring, Computationally Tractable Classes of Ordered Sets, Theorem 5.10, p. 61.]

The problem is in $\mathsf{NP}$: we can check efficiently if a given $f$ is a monotone bijection.

  Is there a polynomial-time algorithm for this problem?
  Or is it $\mathsf{NP}$-hard?

The question can be stated more generally as
existence of a monotone bijection between two given posets of
order dimension 2.

Using a reduction inspired by the answers to this question,
I know that the problem is $\mathsf{NP}$-hard
when dimensions are not restricted.
However, it is not clear
if the reduction would also work when dimensions are restricted.

I am also interested to know about tractability when
the dimension is just bounded by some arbitrary constant (not just 2).


texts: Necessary condition for a graph to be Non-Hamiltonian

texts: Let us denote the edges incident on vertices of valence 2 as "required" as these edges has to be covered by a Hamiltonian circuit, if one exists on that (undirected) graph. Given a graph on which a proper subset of the "required" edges along with two edges incident on a vertex of valency $\geq 3$ form a cycle, can anything related to the Hamiltonicity of the graph be claimed? A few basic rules for the existence of Hamiltonian Cycles is listed here: http://www.mit.edu/~miforbes/ham_cycle.pdf  Can rule (4) be extended in any way to answer this query?