texts:
I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.

Given an $N$ we want to factor, we choose a random $x$ which has order $r$.

The first step involves setting up the registers and applying the Hadamard operator. The second step a linear operator is applied. The third step the second register is measured (I believe this step can be performed later instead). The fourth step the discrete Fourier transform is applied to the first register. Then we measure the first register.

Here's where I'm a little hazy:

We get a measurement in the form $\mid j , x^k \textrm{mod} N \rangle $.

From this we can find the convergents of the fraction $ \frac{j}{2^q} $ , the convergents are possible values of the order $ r $. Here do we just try all the convergents $ < N $ and if we don't find $ r $ as one of the convergents do we just start again?

Also how does the probability for possible values $ j $ differ? They way I see it they should all have the same probability but Shor's paper says this isn't the case?

Just a little confused as some papers seem to say different things.

Thanks.


texts: Why SHA-224 and SHA-256 use different initial values?

texts:
Wikipedia - SHA-2 says

  SHA-224 is identical to SHA-256, except that:

  the initial variable values h0 through h7 are different, and
  the output is constructed by omitting h7.

RFC3874 - A 224-bit One-way Hash Function: SHA-224 says

  The use of a different initial value ensures that a truncated SHA-256
  message digest value cannot be mistaken for a SHA-224 message
  digest value computed on the same data.

My questions:

Is the above quoted reason the only reason why SHA-224 and SHA-256 use different initial values?
Why is it important to make sure that a SHA-256 message digest value cannot be mistaken for a SHA-224 message digest value?
If we use the same initial values for both hash functions, will the security of either hash function worsen? If yes, how?


texts: Regular Tree Languages are closed under quotient?

texts:
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees, and doesn't give a reference for this specific fact.

I'm wondering if someone can point me to a formal definition of the quotient operaiton on tree languages, and a proof that they are indeed closed under this operation.


texts: High Dimensional Volume (HDV) estimator for Entropy estimation

texts:
I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data points in the $M$ dimensional joint space.

The HDV estimators based on the equation as below:

\begin{aligned}
H(X) ≈ −ψ(k) + ψ(N) + \frac{1}{N}{\sum_{i=1}^{N}{logB_m(r^{i}_{x^m})}^m}
\end{aligned}

$X$ is the random variable, $H(X)$ is the entropy of $X$, $ψ(.)$ is the digamma function,  $k=1$ for HDV estimator, $N$ is the number of observations, $B_m$ is the volume of m-dimensional unit ball $r^{i}_{x^m}$ is the minimum distance in each dimension:

\begin{aligned}
r^{i}_{x^m} = min(||x^i_m-x^{'i}_m||)
\end{aligned}

where $x^i_m \neq x^{'i}_m$ and $x^i_m , x^{'i}_m \in D$

My question is that when it is applied to estimate the entropy of Gaussian distribution with mean = 0 and standard deviation = 1, the theoretical result of entropy is around 1.4189. I cannot get the result because $−ψ(1)≈ 0.5772156$ (Euler-Mascheroni constant), $ψ(N=1000)≈ 6.9072$ (Say 1,000 of data points) and I think that $\frac{1}{N}{\sum_{i=1}^{N}{logB_m(r^{i}_{x^m})}^m}$ cannot be negative as it is about distance and volume. What is wrong of my understanding?


texts: Simultaneous time-space complexity of directed reachability on bounded diameter graphs

texts:
Is directed reachability on a graph with bounded diameter (e.g. diameter $O(n^{1/2})$) known to be solvable simultaneously in polynomial time and sublinear space? Is anything known if the diameter is poly-logarithmic?

Informally, is this promise problem when we know the graph has bounded diameter easier to solve in sublinear space? There has been significant work over the past few decades on trying to beat BFS/DFS for restricted graph classes (e.g. planar, bounded-genus graphs [2]), but to the best of my knowledge getting polynomial time and sublinear space simultaneously on general directed graphs remains open [1].

[1] http://cse.unl.edu/~vinod/papers/reach_survey.pdf

[2] https://www.cse.iitk.ac.in/users/rtewari/papers/highgenus_fsttcs.pdf


texts: CLRS's Fibonacci Heap size(x) analysis has a flaw?

texts:
In CLRS's Introduction to Algorithms 3rd edition P.525, when it analyzes the size($x$)'s lower bound, there is a sentence that I quote as "because adding children to a node cannot decrease the node’s size, the value of $s_k$ increases monotonically with $k$". But in fact, I think I can give a counterexample to show that $s_k$ does not necessarily increase monotonically with k.

In the following graph, the degree of the node with key 1 is 2, and there is no other node with degree of 2. So $s_2=8$. Similarly, $s_3=6$. But now $s_3$ is less than $s_2$ which means $s_k$ is not monotonically increasing with $k$ at all.

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

The heap can be derived from an unordered binomial subtree by executing a series of cuts and cascading-cuts.

I want to know whether the above structure is a valid Fibonacci heap. If so, then it is also a valid counterexample.


texts: Cases of Linear programming known to be in $NC$?

texts:
Linear programming is $P$-complete.

However are there special situations where we know an $NC$ algorithm?


texts: I dreamt of a data structure, does it exist?

texts:
I haven't managed to find this data structure, but I'm not an expert in the field.

The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):

An array of length 1 is a merge-array.

An array of length 2^n (for n > 0) is a merge-array iff:

the first half is a merge-array and the second half is empty
or
the first array is full and sorted, and the second half is a merge-array.

Note that if the array is full, it is sorted.

To insert an element, we have two cases:

If the first half is not full, insert recursively in the first half.
If the first half is full, insert recursively in the second half.
After the recursive step, if the whole array is full, merge the
halves (which are sorted), and resize it to the double of its original
length.

To find an element, recurse in both halves, using binary search
when the array is full. (This should be efficient since there are
at most $O(\log(n))$ ascending fragments).

The structure can be thought as a static version of mergesort.

It's not clear what one should do to erase an element.

Edit: after improving my understanding of the structure.


texts:
There is a sound theory of overloading operators and functions realized by type classes in Haskell, and to rougher extent by traits in Rust, etc.

In mathematics however, there are many situations where one set carries the same structure in multiple ways, like the integers being a monoid under both addition and multiplication.

We normally just give these different names, but potentially one wants to abstract some tougher mathematical function, or a proof done in the type system.

In principle, one could do this the way mathematicians do it, by applying a type class to a type that associates the operations to the base type, as opposed to just the set itself with a fixed association.

Is that the "right" or "only" way to gain this flexibility?  Or is there something else?

In particular, there are a bunch of languages like Scala that do overloading of overloading rules in a rather dangerously complex ways, well even incoherent instances in Haskell probably.  It'd be interesting if there were clearer "more parametric" way to achieve the ends that motivates those design decisions.


texts:
I would like to prove (or disprove) the following conjecture:

Conjecture: a two counter automata (2CA) cannot decide the following language:

$L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$

A 2CA can easily check if the binary representation has even or odd length (just keep dividing by two and update an "even length" flag after each division); in the same manner it can check if the ternary representation has even or odd length (just keep dividing by three and update an "even length" flag after each division).

But in order to calculate one of them it must destroy its input, and cannot recover it to calculate the other; so it seems that there is no way to decide $L$.

Do you know a technique that can be used to prove the conjecture?
Or can you disprove the conjecture building a 2CA that decides $L$?

I tried the same approach followed by Ibarra to prove that a 2CA cannot decide $\{n^2\mid n \geq 1\}$, but it seems not the right way.

Note: for simplicity a 2CA is equivalent to a program with one variable $c$  that initially contains the input and the following instruction set:

INC: add one to the variable;
DEC: decrement $c$ (only if it is greater than zero);
JZ  $lab$: if $c$ is zero jump to label $lab$ otherwise continue;
MUL $K$: multiply $c$ by the costant $K$;
DIV $K [, lab_0, lab_1,...,lab_{K-1}]$: divide $c$ by the constant $K$ and store the  quotient to $c$ ($c = \lfloor c / K \rfloor$); possibly jump to different labels according to the remainder ($c \bmod K$);
GOTO $lab$: unconditional jump;
HALT Accept|Reject: halt and accept or halt and reject.

For example a program to check if the binary representation of $n$ has even length is:

   loop: JZ even   // test if n = 0
         DIV 2
         JZ odd    // test if n = 0
         DIV 2
         GOTO loop
   even: HALT Accept
    odd: HALT Reject

(we can build an equivalent 2CA)


texts: Logical Reations for an Impredicative System in a Predicative MetaTheory

texts:
Logical Relations for Impredicative languages like System F seem to rely critically on impredicativity of the ambient logic. Specifically, the interpretation for the forall-type will be defined in terms of all typed relations. In an impredicative system (like CiC/Coq) that's fine, but it seems to be impossible in a predicative system (like Agda).

How can this be done? For example, how would you prove normalization for System F in Agda? Do you have to build your own impredicative universe?


texts:
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature contains thousands of such reductions.
This induces a directed graph over problems: $P' \longrightarrow P$ if $P'$ was reduced to $P$.
First question: Is there a way to collect (large parts of) this graph? Maybe web sites or publications listing many reductions in a suitable way?
This graph may contain interesting information on how we work, the importance of some problems, and maybe on problems themselves. For instance, problems with a very large in-degree are very often used for reductions. Cycles indicate proofs of complexity completeness. The sets of problems reduced to a same problem (the in-neighbors of this problem) may also be interesting. The out-degree of problems will be low in general, but not always, and this also brings information. The transitive links in this graph are also interesting, although trivial since reduction is transitive.
Second question: What information shall we obtain from this graph, in your opinion?
Notice that I am talking of the graph of reductions that have been proved in the literature, not all possible reductions, which would lead to a much simpler graph because of transitivity.


texts: Forms of types in the calculus of constructions

texts:
In the usual presentations of the calculus of constructions (CC) with two kinds Prop and Type such that Prop:Type and impredicative on Prop, it is easy to show the following result:
every closed term A such that $\Gamma \vdash A:\kappa$ (where $\kappa$ is a kind) reduces to a product, namely $A \rightsquigarrow^* \forall x^C.D$.

The easy proof relies on the size of the longuest path from $A$ to its normal form, namely on strong normalization of CC (lexicographic induction on the length of the longuest path to normal form, and height of the derivation).

In "Benthem Jutting, Typing in Pure Type Systems, 1993, Information and computation" there is the following result for all pure type systems:
if $a \in T_S$ and $\Gamma \vdash a:A$ then $A \rightsquigarrow^* \forall x_1^{C_1}\ldots\forall x_n^{C_n}.s$ where $s$ is a sort and $T_S$ is almost the "set of types".

We can think prove first statement using the second: if $\Gamma \vdash A:\kappa$ then $\Gamma, x:A \vdash x:A$ and then $A$ reduces to a product. Unfortunately $T_S$ does not contain the variables.

The question is: is there a proof of the first statement not relying on the strong normalization of CC ?

My guess is that the answer is no: $A$ can $\beta$-reduces to an application, that can reduces to an application, ... The only way to know if it eventually reduces to a product is to effectively $\beta$-reduce it, and in the worst case to normalize $A$.


texts: Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

texts:
Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem？ In other words, could the Tarski–Seidenberg theorem subsume Buchberger's algorithm and Wu's method?

Actually, algorithms of both Buchberger and Wu may be just deduced from variants of Hilbert's Nullstellensatz.


texts: Sampling from a family of hash functions, not uniformly at random?

texts:
Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we sample hash functions from these families uniformly at random.

Are there any instances of an algorithm or data structure sampling from a family of hash functions in a way that isn’t uniformly at random? For example, do any randomized algorithms or data structures sample from hash families using other distributions to, say, bias where elements end up hashing or to introduce some correlations among hashed values?


texts: String distance communication complexity

texts:
Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ and $0\leq t\leq n$ holds. The problem interpolates somewhere between an equality function and set disjointness problem.

What is the deterministic and randomized communication complexity for $(\alpha,t)$-String distance?

Consider $t$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $t\leq|x\oplus y|$ or not.

What is the deterministic and randomized communication complexity for $t$-String distance?


texts:
Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c<d<p$, is 'Is $\mathsf{Perm}(M)\bmod p\in\{c,\dots,d\}$?' $\mathsf{PP}$-complete?

What if $p$ is $O(\log n)$ bits or even smaller?

Without the ${}\bmod p$ it is known to be $\mathsf{PP}$-complete.


texts: Size bound on Büchi automaton for complement

texts:
For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by
$$
\begin{array}{llll}
 u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' \in Q \mbox{ we have a path} \\
& & \mbox{from $s$ to $s'$ labeled by $v$ iff we have} \\
& & \mbox{such a path labeled by $w$ and} \\
& & \mbox{we have such a path which passes through a state from $F$} \\
& & \mbox{labeled by $v$ iff we have such a path labeled by $w$}.
\end{array}
$$
for $u, v \in A^{\ast}$. Now setting
$W_{ss'} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$}\}$ and $W_{ss'}^{F} := \{ w \in A^{\ast} \mid \mbox{there is a path labeled $w$ from $s$ to $s'$ going through a state in $F$}\}$ we have
$$
 [w]_{\sim_{\mathcal A}} = \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}}} W_{ss'} \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}}} A^{\ast}\setminus W_{ss'}
 \bigcap_{\substack{s,s'\in Q \\ w \in W_{ss'}^F}} W_{ss'}^F \cap \bigcap_{\substack{s,s' \in Q \\ w \in A^{\ast} \setminus W_{ss'}^F}} A^{\ast}\setminus W_{ss'}^F.
$$
This equivalence is defined here and also in the the chapter Automata on infinite objects by Wolfgang Thomas in the Handbook of Theoretical Computer Science, Volume II. In this book it is said

  Let us consider the complexity of the complementation process and the equivalence test. Given a Büchi automaton with $n$ states, there are $n^2$ different pairs $(s,s')$ and hence $O(2^{2n^2})$ different $\sim_{\mathcal A}$-classes. This leads to size bound of $O(2^{4n^2})$ states for the complement automaton.

As in the above formula, for each set $W_{ss'}$ (and $W_{ss'}^F$) we can decide wether it occurs in the intersection (and hence determines if one complement $A^{\ast}\setminus W_{ss'}$ and $A^{\ast} \setminus W_{ss'}^F$ occurs) we have $2^{n^2}\cdot 2^{n^2}$ options (different then $|Q^{2^{2Q}}|$ which would be given by the identification of the classes with functions $f : Q \to 2^Q \times 2^Q$ in the wikipedia article).

  But why does this lead to a size bound of $O(2^{4n^2})$ for the complement automaton?

I do not see how to get a complement automaton such that this size bound could be easily seen?


texts: What is the relationship between quantum tomography and quantum error correction?

texts: To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?


texts: How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

texts:
I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says,

  Since errors of the various measured quantities are inversely
  proportional to the square root of the number of measurements, this
  number will be determined from the needed resolution.

I would like to know the reference of the statement that - errors of the various measured quantities are inversely proportional to the square root of the number of measurements.

Thanks.


texts: Understanding the goals you can reach with different programming models and languages

texts:
I come to ask this question here, because Meta told me this place was probably best for it.
Reference: https://meta.stackexchange.com/questions/114043/

I've read this article many a times and ran in to it again today: Signs that you're a bad programmer

And the 2nd paragraph is something I've been thinking about a lot recently:
2. Poor understanding of the language's programming model

There's a plethora of programming languages out there, and a lot of programming models. I learned programming in college. With some basic Java, PHP, Javascript and C#. These are all either scripted or OOP.

There are several more models and several more languages that implement those models.

Recently, I first tried out Ruby, and I never got beyond the basic stuff. Make an array, make a string, do substrings, etc...

My main problem was: why was I doing this? Why use a different tool when I already have one. You read so much stuff about how great certain languages are, but I feel I don't understand the goal of Ruby. Or its goals, if it has multiple.

Take PHP for example: you can use it to power websites, but also just to be a script that responds to a server request with some text-data.

Then there's other models. Why do I use them and in what situations? Why prefer them over other models, etc...

Does anyone know of a website or wiki that specializes in this? Because that would be really helpful.


texts:
What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market?
Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances.

I know HCP is a NP-hard problem but is 5000 node the best that researchers can produce so far?  Is no researcher / commercial entity interested in producing a better one (maybe solve 50000 node instances?) because a HCP is non-monetizable unless it can solve billions node instances (crack RSA and what nots)?


texts: What kind of language is needed to recognize an ordered list? [multihead automata, apparently]

texts:
I'm considering the problem of recognizing a language (over alphabet 0-9 and space) containing strings like "1 2 3 4 5 6" and "14 15 16 17" but not "1 3".

This came up while working on a common parsing task where elements needed to be in an ordered list.  It struck me that while parsing the rest of that language was regular, this part was clearly irregular -- it can recognize, for example, the language A1A2 where A is an arbitrary string 0-9.  In fact it seems to be content-sensitive (and not context-free by the pumping lemma).

My first question: is there a (reasonably well-known, i.e. not defined just for this problem) class of languages between context-sensitive and context-free that describes its expressive power better?  I've read about Aho's indexed languages, but it's not obvious (to me!) that these are even in that class, powerful though it is.

My second question is informal.  It seems that this language is easy to parse, and yet it is very high on the hierarchy. Is it common to come across similar examples and is there a standard way of dealing with them?  Is there an alternate grouping of classes of languages that is incompatible with inclusion on the 'usual' ones?

My reason for thinking this is easy: the language can be parsed deterministically, by reading until you get to the end of the first number, checking if the next number follows, and so forth. In particular it can be parsed in O(n) time with O(n) space; the space can be reduced to $O(\sqrt n)$ without too much trouble, I think.  But it's hard enough to get that kind of performance with regular languages, let alone context-free.


texts: Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching

texts:
I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is that I should not have a length 3 path ( meaning if m in [m,n] is included in other edges then n should not happen on other edges than [m,n] )

I have read that this problem can be reduced to a minimum cost weighted bipartie perfect matching, but I could not find the way to do that.

The relation is not straightforward to me since a node m can be connected to different nodes in the right hand partie and vice versa.


texts: Is it hard to find optimal addition chains?

texts:
An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and  each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$.  The length of the addition chain is $n$; the target of the addition chain is $x_n$.

What is known about the complexity of the following problem: Given an integer $N$, what is the length of the shortest addition chain whose target is $N$?  Is it NP-hard?

Wikipedia points to a 1981 paper by Downey, Leong, and Sethi that proves the following related problem is NP-hard: Given a set of integers what is the minimum length of an addition chain that includes the entire set?  Several authors apparently claim that this paper proves the single-target problem is NP-hard, but it doesn't.


texts: Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?

texts:
Consider a regex language with the greedy quantifier $*$, the nongreedy quantifier ${*}?$, ordered alternation, and character classes. (This is essentially a sublanguage of PCRE without backreferences, look-around assertions, or some of the other fancier bits.)

A match $[a_0,a_1)$ for for a regex $R$ on a string $s = s_0\dots s_n$ is a half-open interval over $\mathbb{N}$ such that $s_{a_0}\dots s_{a_1-1}$ is accepted by $R$.

We give a recursive definition of what makes one match better than another. A match $a = [a_0,a_1)$ for regex $R$ on a string is better than another match $b = [b_0,b_1)$ if $a_0 < b_0$ or, if $a_0 = b_0$ and:

If $R$ is a character class: Character classes have unique matches, so all
matches at the same position for $R$ are equal. Hence this case is impossible.
If $R = ST$:

The leading portion of $a$ is a better match for $S$ than the leading
portion of $b$, or
The leading portions of $a$ and $b$ are equally good matches for $S$, and
the trailing portion of $a$ is a better match for $T$ than the trailing
portion of $b$.

If $R = S|T$:

$a$ is a match for $S$ and $b$ is not, or
$a$ and $b$ are equally good matches for $S$ and $a$ is a better match for $S$ than $b$ is, or
$a$ and $b$ are not matches for $S$ but are matches for $T$, and $a$ is a
better match for $T$ than $b$ is.

All other syntactic forms reduce to the above three for purposes of match
priority:

$R = S{*}$: $R \equiv S^0|S^1|\dots$
$R = S{*}?$: $R \equiv \dots|S^1|S^0$

These infinitary patterns are used for purposes of match priority only---they are not part of the match language under consideration.

The "better" relation is a weak linear order over all possible matches for a
given pattern.

Call two regexes $S,T$ match-equivalent if, for every finite input string, the set of pairwise disjoint best matches for $S$ equals the set of pairwise disjoint best matches for $T$.

Q: Is it the case that for every regex $S$ containing the nongreedy quantifier ${*}?$ there is a match-equivalent regex $T$ which contains no nongreedy quantifiers?

Edit: This is a complete rewrite of the question to clarify what was being
asked.


texts: network flow using minimum number of nodes

texts:
In a standard Ford-Fulkerson setting (directed graph $G$ with a source $s$ and a sink $t$), consider the problem of achieving a given amount of flow using the minimum number of nodes in the graph.

The familiarity with the problem discussed here: Laying paths on a network using minimum number of links/edges seems to suggest that this problem might also be NP-hard. I can split every node in $G$ into two nodes and add an edge of unit cost between them, and assign zero cost to all the original edges. Cap-SNDP (http://www.cis.upenn.edu/~sanjeev/papers/ipco11_capacitated.pdf) on this new graph is equivalent to finding the minimum number of nodes in $G$ required to support the desired flow.

1) Is this problem known to be NP-hard?

2) If I restrict attention to layered graphs, does it change anything about the complexity/approximability? (A layered graph is one in which all $s-t$ paths have the same number of edges.)

Thanks in advance.


texts:
I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my writing. Until now, he has been happy to help me formalize my arguments and proofs but this is clearly something I am struggling with.

Any advice on how to be more formal while writing papers? The obvious answer is to read a lot of papers and try to re-create proofs by writing them down. I seem to do that relatively well but the writing itself is a problem for me.


texts:
The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows:

  A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an algorithm $A_\epsilon$ and $N_\epsilon > 0$, such that $A_\epsilon(I) \leq (1+\epsilon)OPT$ for $OPT(I) \geq N_\epsilon$.

I have two questions:

Is Asymptotic PTAS contained in APX?
If problem $\Pi$ is APX-Hard, does it imply that $\Pi$ is not Asymptotic PTAS (suppose $P \neq NP$)?

I know above are true if we replace Asymptotic PTAS with PTAS (which are common-sense now). But I can't figure out how the definitions of Asymptotic PTAS and APX give answers to above questions..


texts: Super-polynomial time approximation algorithms for MAX 3SAT

texts:
The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. So, Can we do better than $7/8+ \epsilon $ if we allow super-polynomial algorithms?  What approximation ratios can we achieve  with quasi-polynomial time algorithms ( $n^{O(\log n)}$) or with sub-exponential time algorithms($2^{o(n)}$)? I'm looking for references to any such algorithms.


texts:
I am looking for resources (preferably a handbook) on advanced topics in algorithms (topics beyond what is covered in algorithms textbooks like CLRS and DPV).

The type of material that can be used for teaching a topics in algorithms course like
Erik Demaine and David Karger's Advanced Algorithms course.

Resources that would give an overview of the field (like a handbook) are preferable,
but more focused resources like Vijay Vazirani's "Approximation Algorithms" book are also fine.


texts: Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

texts:
"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference

where may proof of  this theorem   be found, and what is the the computational complexity of the computably isomorphic maps?


texts:
In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question, and a hard one at that.  Let's consider the more general question of finding (the size of) a largest H-free set in a graph, where H-free means that it does not induce a subgraph that contains a copy of the fixed graph H as an induced subgraph.

For fixed graph H, given input graph G, is it NP-hard to determine the size of a largest H-free set in G?

Is there a sensible way to construct a "table" of graphs H (or classes of H), so as to fill in the entries with correct yes or "no" answers to the above question?  (Let's pretend that "no" = P, and even that a "no" entry means there is a polytime algorithm to generate a largest H-free set.)

Failing that, are there non-trivial classes of H for which the answer is yes? ... no?

I was digging around, looking into two queries about generalised/H-free chromatic numbers --- here and here --- when it occurred to me that the (ostensibly simpler) "dual" problem of an H-free analogue of independence number might also be open.  I am aware of classical papers on a related problem for random graphs, cf. e.g. Erdos, Suen and Winkler (1995) or Bollobas and Thomason (2000), which are in a still very active line of research.  So perhaps there is already some work that I have not seen yet addressing this more basic question and that a rough internet search did not uncover (hence the reference-request tag).


texts: Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)

texts:
I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is
$$\exists x \forall y ((y \ge 1 \land y \le 2) \implies ((\neg x)\land(y * y \ge 1)).$$
I found that Z3 can handle the sort of formulas. However, the heuristics for handling quantifiers in Z3 seem not tuned for problems where universal variables range over finite/bounded domains. Are there any other efficient tools for checking the sort of formulas?
This question describes tools for 2QBF, but 2QBF only supports SAT formulas (i.e., only supports Boolean variables). The formulas in my question include integer variables.


texts: In what fields does a knowledge of formal semantics prove useful?

texts:
(If this is better for programmers SE, let me know, but I imagined you guys would have more thorough answers)

I'm a mathematics major, but I have a pretty deep interest in CS (especially in compiler design, reverse engineering, etc).

This site recommended a book on formal semantics. I imagine that a knowledge of semantics is useful there (but I'm not quite sure how, yet). Are there other fields in which this knowledge is directly useful, other than academic treatments of programming languages?


texts: Can Curry-Howard prove a theorem from the types in your program, that has nothing to do with your program?

texts:
The following link states:

  Curry-Howard means that any type can be interpreted as a theorem in some logical system, and any term can be interpreted as a proof of its type.
  This does not mean that those theorems have anything to do with your program. Take the following function:

swap : forall a,b. (a,b) -> (b,a)
swap pair = (snd pair, fst pair)

  The type here is forall a,b. (a,b) -> (b,a). The logical meaning of this type is (a and b) => (b and a). Note that this is a theorem in logic, not a theorem about your program.

My question is: Can Howard-Curry prove a theorem from the types in your program, that has nothing to do with your program?


texts:
In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.

This answers my question with k=1. Is anything known about a similar result for another fixed k?


texts: Reference request for the relationship between approximating degree of Boolean functions and learning algorithms

texts:
This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean function into a learning algorithm.

Have there been other works in this line? What are the most recent things we know about such conversion from approximate degree to learning algorithms?


texts:
Is NP in $DTIME(n^{poly\log n})$?
Is NP in $DTIME(n^{poly\log n})$?


texts: Kleinberg Rubinfeld Short Paths in Expander Graphs for Hypergraphs

texts:
In the 1996 paper "Short Paths in Expander Graphs" by Kleinberg and Rubinfeld, the authors show a randomized polynomial-time algorithm for finding an embedding of a graph $H$ into a graph $G$, if $G$ is a regular expander on $n$ nodes and $H$ is a graph on at most $cn / \log^k n$ nodes and edges, where $c$ and $k$ are constants.

I have searched for a while for an extension of this result to hypergraphs, with no luck. I was wondering if anyone was aware of a similar result for hypergraphs?


texts: Difficult On Average Cases for 3MaxSAT and 3SAT Approximation Algorithm

texts:
1.Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP.

2.Its also experimentally known that 3SAT has the most difficult known cases when the clause to literal ratio is approximately 4.2.

Q1. Is there a similar result for 3MaxSAT where the approximation algorithm for satisfying some 7/8+e of clauses becomes on Average difficult if 3MaxSAT has some specific format (like 3SAT in 2.) ?

Q2. Is there a benchmark set available for 3MaxSAT approximation algorithms for such cases?

Q3. Is there a similar approximation hardness result for 3SAT (like 3MaxSAT in 1.) if informed that the given 3SAT is satisfiable? Is just the clause to literal ratio is sufficient to represent completely the hardest cases for such approximation algorithms too?


texts: What is the following variation on Set Cover known as?

texts:
What is the following variation on set cover known as?

Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in one of the selected subsets.

Note: It is not hard to see that this problem is NP-Complete:  Given a normal set cover problem (S, C, K), make three copies of S, say S', S'', and S''',  then create your subsets as S''', |S| subsets of the form {a'} U {x in S'' | x != a} U {a'''}, |S| subsets of the form {a''} U {x in S' | x != a} U {a'''}, {a', a'' | a in C_i}.  Then we can solve the set cover problem with K subsets iff we can solve the pair cover problem with K + 1 + 2 |S| subsets.

This generalizes to triples, etc.  I would like to be able to not waste half a page proving this, and it is probably not obvious enough to dismiss as trivial.  It is certainly sufficiently useful that someone has proved it, but I have no idea who or where.

Also, is there a good place to look for NP-Completeness results that are not in Garey and Johnson?


texts: Polynomial algorithm for correlated equilibrium

texts:
I searched through the web for a polynomial algorithm for correlated equilibrium.
I found a lot of papers by C.H. Papadimitriou that proposes a solution using the ellipsoid algorithm.

Is there a simpler algorithm to get the correlated equilibrium, or a paper to start from?


texts: Applications and benchmarks for binary quadratic program algorithms

texts:
I have an algorithm that on all examples I was running finds an  arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.

Question:  Is there any practical application this algorithm can be used? What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?

I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or  here, if link works.

PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it.

PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.


texts: Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

texts:
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the number of maximal cliques in a $(2C_4, C_5,P_5)$-free graph with respect to the number of vertices.
In a $(2C_4, C_5,P_5)$-free graph, the largest induced cycle is of length 4, and no two induced 4-cycles are edge-disjoint.
Is there a paper that mentions such result?


texts: Recursion Schemes for Static Analysis (AST)

texts:
In the process of creating an AST analysis framework one of the challenges is creating good reusable functions and to avoid too much boiler-plate code. To that end catamorphisms seem like a good fit, as described here:

Catamorphisms (1-7)

Is there other interesting recursion schemes and techniques that are beneficial for AST analysis like catamorphisms?

In particular with application within the constraints of the F# programming language.


texts: Advanced techniques for determining complexity lower bounds

texts:
Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.

Beyond the "simpler" techniques, such as reducing to sorting or an EXPTIME-complete problem, what techniques have been used to prove lower bounds for the time complexity of a problem?

In particular:

What are the "cutting-edge" techniques that have been developed in the last decade?
Can techniques from Abstract Algebra, Category Theory, or other branches of typically "pure" mathematics be applied? (For example, I often hear mention of the "algebraic structure" of sorting, without any real explanation of what this means.)
What are significant but lesser-known results for lower-bound complexity?


texts: Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$

texts:
Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$?
(Set cover).

All upper bounds that I am aware of are

 dynamic programming $\mathcal{O}^*(2^n)$
 poly-space Measure and Conquer $O(2^{.305(m+n)})$
 slightly better $M\&C$ exp-space bound exponential in $m+n$.

Thanks.
AW


texts: When was first line detection algorithm created and when line detection problem was posed?

texts:
I wonder when was first line detection algorithm created (first used in practice and refrenced by any publications) and when line detection problem was posed (I know it can look like generaal edge detection problem but it is quite more complex than that)?

Well... some students (including me) were trained that line detection is achevable by Hough transform. Wiki history page talls us that The Hough transform was patented as U.S. Patent 3,069,654 in 1962 and assigned to the U.S. and he used it scince 1959...   and that is not even problem posting - thats like a solution... so... What shall I do? Who posted the problem, formalized it?

BTW: Here (IEEE library) search results sorted by date (oldest -> newest)... (I see Straight-line detection with diodes: this 1934 year)


texts:
I want to encode a logic into Coq. The semantics of the logic are very complex and I just want to encode the syntax, axioms, inference rules. I use deep embedding, but I can't use notation like:

Axiom nxc:forall (p q:formula),
 chop (next p) q->  (next (chop p q)).(it is wrong)
,true.

They need type prop, but my type is formula. How can I make them unify?

Theorem nxn:forall (p:formula),
derivable (Fnext p)-> derivable(Fneg (Fnext (Fneg p))).

To prove this, I have to give all the axioms. I can't use the axioms of and (in Prop). This would be a very tedious work. Any suggestions?

This is part of the code.

Require Import Setoid.
Variables (state : Set).
CoInductive stream : Set :=
    cons_str : state -> stream -> stream.
Inductive formula :Set:=
  |ftrue:formula
  |ffalse:formula
  | For : formula -> formula -> formula
  | Fneg: formula -> formula
  | Fnext: formula -> formula
  | prj : list formula -> formula->formula.

Definition derivable : formula ->stream-> Prop.
Admitted.

Definition model_p (f :formula) := forall pi : stream, derivable f pi .
Notation "'|- f" := (model_p f) (at level 100, no associativity) .

Notation "p '|| q" := (For p q) (at level 76, right associativity) .
Notation "! p" := (Fneg p) (at level 71, right associativity) .
Notation "f 'prj g" := (prj f g) (at level 77, right associativity).
Notation "'x g" := (Fnext g) (at level 73, right associativity).

(************************derived  formulas  ********************)

Definition and(p q: formula) : formula :=!(!p '|| !q).
Notation "p '&& q" :=(and p q) (at level 74, left associativity).

Definition imp(p q: formula) : formula :=!p '|| q.
Notation "p '==> q" := (imp p q) (at level 79, no associativity) .

Definition iff (A B:formula) :formula:= ( (A '==>  B) '&& (B '==> A)) .
Notation "p <'==> q" := (iff p q) (at level 79, no associativity) .

Definition empty := ! 'x ftrue .

Definition chop(p:formula)(q:formula):= (cons p (cons q nil)) 'prj (empty).
Notation "p ; q" := (chop p q) (at level 75, right associativity).

Axiom t2 :forall(p q:formula),('|-('x p '&&  'x q) )<->('|-('x(p '&& q))).
Theorem tt2 :forall(p q r:formula),('|-('x p '&&  'x q) ; r)->('|-('x(p '&& q))
; r).
intros.
rewrite t2 in H.


texts: Reduction graph to planar bounded treewidth and bounded diameter graph

texts:
We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.

Let $H$, the planarizing gadget, be planar graph with four
distinguished vertices $u,u',v,v'$ on the outer faces.

Take graph $G$ drawn on the plane. Add new vertex $S$,
adjacent to all vertices of $G$. So far the diameter is
at most two.

Replace each pair of crossing edges $(u,u'),(v,v')$ by
new copy of the gadget $H$.

The resulting graph $G'$ is planar with diameter $D = 2\max(d(u,u'),d(v,v'))$
where $d$ is the distance in $H$.

The treewidth of $G'$ is $O(D)$, which is constant for fixed $H$,
for reference see here.

Similar reduction with specially chosen $H$ is used to show
NP-hardness of problems for planar graphs.

  What is wrong with this reduction?

Correctness of the reduction is unlikely, because for
bounded treewidth graphs a lot of graph invariants are
computable in polynomial time and choosing suitable
gadget $H$ might give relation between invariants
of $G$ and $G'$, implying $P=NP$.

Another reference claims
"bounded genus graphs of bounded diameter have bounded treewidth".


texts: Subclasses or characterizations of modular or pseudo-modular planar graphs

texts:
We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined in the following link: http://www.graphclasses.org/classes/gc_203.html.

I am wondering if there are interesting examples of planar graphs which are modular or pseudo-modular, or an interesting characterization of planar graphs which have these properties.


texts:
I am trying to solve an optimization problem. I need some help in getting the results or survey on related issues. The question is a bit general but any help in identifying the correct sources would help.

Are their any good survey work/tutorial/book that could provide information on the known algorithms and complexity results for $L_{0}$, $L_{1}$, $L_{2}$ optimization and also the relation among them for both sparse and general solutions?


texts: Partition a graph into node-disjoint cycles

texts:
Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The edge set of a graph can be partitioned into cycles if and only if every vertex has even degree."

My Problem: I wonder has anybody studied the partition a graph into node-disjoint cycles. That is, partition the vertices $V$ of a graph $G$ into $V_1, V_2, \cdots, V_k$, and each subgraph induced by $V_i$ is hamiltonian.

Is it NP-hard or easy?

More related problem:
Partition into triangle is NP-complete. (Page 68 of "Computers and intractability")

Thank you for your advise in advance. ^^


texts: Where can you find job postings for faculty positions in CS theory?

texts:
What are the best resources for finding job postings for faculty positions in CS theory?  Is there one website or mailing list in particular that is fairly comprehensive?  I currently have the impression that one has to use a variety of resources to get a comprehensive, worldwide list of job postings.  Is this the case?

This question is related to how to get a job, though the question I'm asking here is, how do you find out about a job?


texts: Generalization bounds for multiclass learning when the output is vector space?

texts:
There are plenty of results for muli-class learning with with fixed discrete labels:
$$
\text{Standard multi-class classification:}
\begin{cases}
f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ s.t. X \subset \mathbb{R}^{d_x}
\end{cases}
$$

I was wondering if there are any results which study multi-class learning with (countable, possibly finite) vector-valued outputs.

$$
\text{Vector-output multi-class classification:}
\begin{cases}
f: X \rightarrow Y_{vector} = \{y_1, y_2, y_3, ..., y_k \}, \\
s.t.
X \subset \mathbb{R}^{d_x},
y_i \in  \mathbb{R}^{d_y}
\end{cases}
$$

One may suggest that this is another problem: metric-learning between $X$ and $Y$ space:
$$
\text{Standard metric-learning problem:}
\begin{cases}
f: X, Y \rightarrow [0,1], \\
s.t.
X \subset \mathbb{R}^{d_x},
Y \subset  \mathbb{R}^{d_y}
\end{cases}
$$

However all the results I came across in the metric-learning study the functions on one single vector space (as in unsupervised metric learning). In addition, vector-output multi-class classification is much more restricted (easier to learn?) than metric learning, since in what I am asking, the number of possible output vectors is fixed (unlike metric learning).


texts: What exactly did Lenstra prove on mixed integer linear program?

texts:
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes arguments of Khaichayan and Von zur Gathen and Sieveking). However I understand from the line '..we indicate an algorithm for the solution of this problem that is
 polynomial for any fixed value of $n$, the number of integer variables' that the complexity is polynomial if number of integer variables is fixed. I am interested in complexity with fixed number of integer variables and polynomial number of real variables.

Suppose we have $A\in\Bbb Z^{m\times(n_1+n_2)}$ and $B\in\Bbb Z^m$ and asked to find $X\in\Bbb Z^{n_1}\times \Bbb R^{n_2}$ in $AX\leq B$ then what is the complexity with with which we can find $X$?

Can we find $X$ in $O(n_1^{cn_1}((n_2+1)m)^cL)$ arithmetic operations on $O(L^c)$ bit words where non-negative $c$ is fixed and $L$ is number of bits needed in any entry of $A$ or $B$?

The above scaling is consistent with case $n_1=0$ (Real Linear Programming) or $n_2=0$ (Integer Linear Programming).

  I am interested in case of $n_1$ is fixed and $n_2=O(L^c)$.

Is there a down to earth explanation of what Lenstra is doing?
What is the space requirement?
What is a good reference for this type of mixed integer linear program?


texts: Is equivalence of unambiguous context-free languages decidable?

texts:
It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free grammars. For this reason, I would like to ask if it is known whether the problem remains undecidable while restricting oneself to unambiguous context-free languages. That is, given two context-free grammars that are a priori granted to be unambiguous, is it decidable whether they are equivalent or not?

I find this problem a little intriguing, since it is known that equivalence is decidable for deterministic context-free languages, though this result is far from trivial... On the other hand, there might be some simple reason for undecidability that I have been overlooking.


texts: Complexity of factoring in number fields

texts:
What is known about the computational complexity of factoring integers in general number fields? More specifically:

Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?
Is it known that primality over number fields is in P or BPP?
What are the best known algorithms for factoring over number fields? (Do the $\exp \sqrt n$ and the (apparently) $\exp n^{1/3}$ algorithms extend from $\mathbb{Z}$?) Here, factoring refers to finding some representation of a number (represented by $n$ bits) as a product of primes.
What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?
Over $\mathbb{Z}$ it is known that deciding if a given number has a factor in an interval $[a,b]$ is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?
Is factoring in number fields in BQP?

Remarks, motivations and updates.
Of course the fact that factorization is not unique over number fields is crucial here. The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by this earlier TCSexchange question. I presented it also over my blog where Lior Silverman presented a thorough answer.


texts: What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?

texts:
The following is not believed to be true:

  $\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Can you help me see where the argument breaks down?

The directed reachability problem is complete for $\mathsf{L}$.
I argue that it is in $\mathsf{L}$-uniform $\mathsf{NC^1}$.

The directed reachability problem over configuration graphs of
deterministic log-space Turing Machine is complete for $\mathsf{L}$.

The directed reachability problem is in $\mathsf{MSO}_2$:

  given $s$ and $t$,
  let $P$ represent the free $\mathsf{MSO}$ variable for the edges in the path.
  We need to verify that $P$ contains a directed path from $s$ to $t$
  which can be done by verifying that the in-degree and out-degree (in $P$)
  of every vertex incident on an edge in $P$ is $1$ except for $s$ and $t$
  which have in-degree,out-degree = $0,1$ and $1,0$ respectively.

Every forest is a graph of tree-width $1$.
In particular the configuration graph of
a deterministic log-space Turing Machine is a bounded tree-width structure.

From Elberfeld, Jakoby, and Tantau's
Logspace versions of the theorems of Bodlaender and Courcelle:

  $\mathsf{MSO}$ formula over bounded tree-width structures
  can be evaluated in log-space.

The proof goes something like this:
For a given structure size $n$,
a bound on the tree-width of the structures $w$, and
a $\mathsf{MSO}$ formula $\varphi$ with vocabulary $\tau$,
construct (in $\mathsf{L}$) construct a $\#\mathsf{NC}^1$ circuit $C$.

The circuit $C$ given a structure $M$ of size $n$ and tree-width at most $w$,
counts the number of "satisfying" assignments of $\varphi$ on $M$.

(The histogram tabulating
the number of assignments to the free second order variables in $\varphi$
parameterized on the sizes of the sets of values taken by the the variables).

I think the circuit $C$ only depends on the vocabulary $\tau$,
the tree-width bound $d$, and the size of structure $n$.

The proof proceeds by evaluating the circuit in $\#\mathsf{NC}^1 \subseteq \mathsf{L}$ but we don't need that part.

For us it suffices to observe that from Nondeterministic $\mathsf{NC^1}$ Computation
by Caussinus-Mackenzie-Therien-Vollmer:

  every $\#\mathsf{NC}^1$-circuit can be interpreted as
  counting the number of proof-trees of a $\mathsf{NC}^1$-circuit.

Thus the corresponding circuit outputs $1$ iff
the input structure satisfies the $\mathsf{MSO}$ formula.

From the above it seems that log-space is at least in logspace-uniform $\mathsf{NC}^1$


texts: Polynomial algorithms for UPB (Unextendable Product Bases)

texts:
Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$ such that:

a) all $\vert v_i \rangle$ are mutually orthogonal

b) there is no product vector orthogonal to all $\vert v_i \rangle$

c) basis is nontrivial, i.e. doesn't span $H$

(such bases are of interest in quantum information)

Questions:

Is there a polynomial algorithm (in $n$) for finding UPBs? (note that in general there is no upper bound on the size of UPB, so a priori it might be exponential in $n$)
Is there a polynomial algorithm for checking if a given product basis is a UPB? (i.e. is unextendable)

Or is the problem NP-complete?


texts: Is there a candidate for a natural problem in $P/poly - P$?

texts:
I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(n)}:n\in \omega$}, which clearly has simple non-uniform circuits, but is not computable uniformly at all, but this is not the kind of functions I am interested in.

Is there a function that we know it can be computed non-uniformly but we don't know if it can be computed uniformly (or at least proving that it can not be computed uniformly is not obvious)?
How can non-uniformity of circuits be used for computing functions that are not known to be computable uniformly (with almost the same amount of resources)?

Please note that I don't want pathological functions like uncomputable one mentioned above, I want natural functions that people are really interested in computing and it is plausible that can be or could have been computed uniformly.
Edit:
I know that $BPP \subseteq P/poly$. So an answer which is not a derandomizations result is more interesting for me.
Edit 2:
As András Salamon and Tsuyoshi Ito have said in their answers, $Sparse \subset P/poly$, and there are interesting problems in $Sparse$ that are not known to be in $P$, so formally they have answered what I have asked, but that does not help with what I am really interested in since the reason that they are in $P/poly$ is the possibility of hard coding a sparse language into the circuit. A language which is not sparse would be more interesting.


texts: Reference for Dudley's chaining integral

texts:
Dudley's chaining integral is commonly used to bound Rademacher complexities.
I recall seeing several papers give this as the reference

@ARTICLE{MR512411,
  author = {Dudley, R. M.},
  title = {Central limit theorems for empirical measures},
  journal = {Ann. Probab.},
  year = {1978},
  volume = {6},
  pages = {899--929 (1979)},
  number = {6},
  coden = {APBYAE},
  fjournal = {The Annals of Probability},
  issn = {0091-1798},
  mrclass = {60F05 (28C20 60B10 60F17)},
  mrnumber = {MR512411 (81k:60029a)},
  mrreviewer = {P. R{\'e}v{\'e}sz}
}

but I don't think the result in question actually appears in that paper.
Could anyone point me to the definitive reference?


texts: Partition graph into complete disjoint subgraphs while maximising sum of edge weights

texts:
Has this problem been studied?

We start with a complete, simple, undirected graph with edge weights. The problem is to delete edges so as to partition the graph into complete disjoint subgraphs while maximizing the sum of the edge weights over the whole graph (deleted edges not being counted).

There is no constraint on the size or number of subgraphs in the solution.

Note this is interesting only if there are negative edge weights. Otherwise the solution would be to take the whole graph.

Clearly we would like to delete all the negative-weight edges while keeping all positive-weight edges, but the requirement that disjoint subgraphs be complete makes a trade-off between these goals.

I have seen discussion of similar graph partitioning problems but not this exact one. (Eg it is a bit like the maximum clique problem, but here I want to put every node in a disjoint clique, in the optimal way). I am guessing it is NP-complete. I am interested to know where to start looking for efficient heuristics.


texts: Technical lemma about curves used in original proof of PCP theorem

texts:
I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn't figure it out myself.

In page 67 (when proving a claim that is used for soundness of local decoding of low degree polynomials procedure), the writers use a "fact" A.9 (regarding "Well   Distribution Lemma in Curves") that is located in page 156.

The proof is very short and I cannot grasp it.

Moreover, the statement seems to be incorrect by the following example:

Let $S=\{x_1\}$, then $\forall$ curve $C\in P(\langle x_1,\dots,x_k\rangle)$ we have $|C\cap S|\geq 1$ as $C$ is a multiset, so
$$\mathbb{E}\left[\frac{|C\cap S|}{|C|}\right]\geq\mathbb{E}\left[\frac{1}{|C|}\right]>\frac{1}{|\mathbb{F}|^m}=\frac{|S|}{|\mathbb{F}|^m}$$
Maybe, I miss something in the statement of the lemma...

I will appreciate any help in understanding this problem.


texts: Are there any heuristic-free NP complete problems?

texts: Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in polynomial time? (Assuming $P \neq NP$)


texts: Clustering formalizations other than K-means for separable data

texts:
Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended a lecture by Dr. Adam Meyerson and he referred to that type of data as "separable data".

What are some clustering formalizations, other than K-means, that could be amenable to clustering algorithms (approximations or heuristics) that would exploit natural separability in data?


texts: Nearly Optimal Sparse Walsh-Fourier Tranform

texts:
In the recent paper: Nearly Optimal Sparse Fourier Transform[Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price], the authors show an $O(k \log n)$-time algorithm for the problem of computing the discrete Fourier transform of an $n$-dimensional signal that has at most $k$ non-zero Fourier coefficients.

Is there a similar result for the Walsh-Fourier transform (or is it possible to use the same algorithm for a multidimensional DFT of size $2^n$) ?


texts: Does approximation degree of AND depend on error?

texts:
Denote $\underline{x}\triangleq x_1,\dots,x_n$.

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $p_\epsilon(\underline{x})\in\Bbb R[\underline{x}]$ be minimum multilinear multivariate polynomial such that $|p_\epsilon(\underline{x})-f(\underline{x})|\leq\epsilon$ at every $\underline{x}\in\{0,1\}^n$.

Can following strict inequality hold for any boolean function $f$

$$deg(p_\epsilon)<deg(p_{\tilde\epsilon})$$ when $0<\tilde\epsilon<\epsilon<\frac{1}2$?

For example if you consider $AND(x_1,\dots,x_{1000})$, can you actually prove that there is a different approximation degree to approximate $AND(x_1,\dots,x_{1000})$ within error $\frac{1}3$ compared to error $\frac{1}{1000^{1000^{1000^{1000}}}}$?


texts:
What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array?

In 1D, it is just a string matching problem, KMP does it in linear time.

In 2D, this paper shown it can be done in linear time with little extra space.

Can this problem be solved in linear time worst case for any fixed dimension?


texts: Does there exist a complexity class such that the number of accepting paths is a prime number?

texts:
#P asks the total number of accepting paths.
PP asks at least half of paths be accepting.
Parity-P asks the number of accepting paths be even.
UP asks the number of accepting paths to be one.
Are there any other Complexity Classes like this? For example, does there exist a complexity class where the number of accepting paths is a prime number?


texts: Resources to find the "best" algorithm for a problem?

texts:
There are many question that pose a none obscure problem and ask for the "best" algorithm, whatever "best" means.

For example, Given a graph, decide if its edge connectivity is at least n/2 or not,

The normal process is to search the literature with every single name of the problem, and find a recent paper. Usually the "best" result will be the one of the references. A more recent approach is to ask the question here.

Are there websites specifically dedicated with information like this? A database of problems and list of algorithms with their complexities? I am imagining an OEIS for problems instead of integer sequences.


texts: Reference for fundamental theorem on tree rotations

texts:
Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:

Let A and B be binary search trees. Then A and B are linearly equivalent if and only if they are connected by a sequence of tree rotations.

I noticed this result when I was first learning about data structures long ago and wanted to understand the special status of tree rotations more deeply.

The proof is simple and intuitive: Rotate the least element up to the root position along the leftward spine. By the order invariant, this rearranged tree cannot have a left subtree. Now recurse on the right subtree. The result is a normal form for testing linear equivalence.

While it's a basic theorem, I've never come across it in the literature. I would greatly appreciate a reference for the next time I need to use this result.

(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)


texts: How do models of hypercomputation overcome the Halting Problem?

texts:
Hypercomputation refers to models of computation that are not possible to simulate using Turing machines.  (Hypercomputers are not necessarily physically realisable!)  Some hypercomputers have access to a resource that allows the Halting Problem for standard Turing machines to be solved.  Call this a "superpower": a hypercomputer with a superpower can decide whether any standard Turing machine terminates.

  What kinds of "superpowers" do hypercomputers use?

Ed Blakey's thesis sets up a formal framework to classify some of the major kinds of resources used in hypercomputing, but it does not try to provide a comprehensive survey of superpowers.  I am not interested in a list of hypercomputers (there is a nice list in the Wikipedia article), but in understanding what "special sauce" each model uses, perhaps thought of as a unique kind of resource.

This question is inspired by How fundamental is undecidability?.  Also related is What would it mean to disprove Church-Turing thesis? which generated lots of interesting discussion, and Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines?.


texts: Restricted read twice BDDs and context free grammars

texts:
Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1]

Quote:

Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled,
and a formal language L ⊆ Σ∗ , the formal-language-constrained shortest/simple path problem con-
sists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) ∈ L.
Here l(p) denotes the unique word obtained by concatenating the Σ-labels of the edges along the
path p.
(1) We show that the formal-language-constrained shortest path problem is solvable efficiently
in polynomial time when L is restricted to be a context-free language (CFL).

Can this be used for restricted read twice BDDs (Binary Decision Diagram)?

Consider BDD where every variables occurs twice and the order of all paths root->T is restricted to:

1 .. n n .. 1 (this is palindrome)

Treat the BDD as edge labelled digraph where the true edge of variable is labelled as +variable and the false edge as -variable.

Some paths in the digraph are "BDD inconsistent" - if a variable takes both values.

Looks like CFG constraint can help to find "consistent" paths.

It is possible to construct CFG that accepts all palindromes and only palindromes (over the alphabet U {+variable,-variable}.

Finding a path from the root to "true" constrained by the above CFG will give a consistent satisfying assignment - the first half of the path is correct because a variable occurs only once and the second part is the reverse.

Is this correct (computer experiments suggest it is)?

A different grammar may give different restriction.

Is this published somewhere?

To my humble knowledge this is one of the very few examples of read twice BDD supporting poly-time SAT query.

EDIT: The problem I am trying to solve is to find types of read twice BDDs which allow polytime SAT query with the help of CFGs. The above construction gives example for the case when the order of the variables is restricted to a palindrome, hence the (possibly incorrect)  description "restricted" (because of the restriction of the order). I am not familiar with CFGs.

Discussion about an extension (almost sure impossible) of this at math.SE

Example: Simple read twice BDD on x,y. The concatenation of edge labels give the palindrome word: "+x -y -y +x"

Thank you.

[1]
FORMAL-LANGUAGE-CONSTRAINED PATH PROBLEMS∗ CHRIS BARRETT† , RIKO JACOB‡ , AND MADHAV MARATHE†


texts:
this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. have seen similar problems in the literature but not this one in particular.

will write it in terms of bit-vectors because thats easiest for me.

  let there be a set of bit-vectors of size $n$, $v_1, v_2, v_3, ... , v_n$. consider the bitwise XOR operation. given a target vector $v_0$. find a subset of vectors such that the bitwise XOR of the set equals the target vector. what is an efficient (or ideally, optimal) algorithm to find a subset?

the brute force algorithm enumerates the powerset of size $2^n$ and lists the 1st subset found. (slightly?) more efficient would look at 1-positions in the target and exclude subsets that do not have at least 1 vector with a 1 in a 1-position of the target.

the subset may or may not exist. it may or may not be unique.

closely related questions: (1) find the smallest subset, (2) output T/F depending on whether such a subset exists.

have a suspicion one of these problems is NP complete.

looking for references, insight etc. it would be interesting to know if there are "hard" vs "easy" inputs etc

as I wrote on the other question this seems closely related to the subset sum problem (see eg garey & johnson ref) which is known to be NP complete but this seems to have "slightly" less complexity because its simpler to compute a vector bitwise XOR than a binary sum (the sum can have more binary digits).

the problem also seems closely connected to bin fu's recent question [2]

[1] https://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors

[2] Algorithmic Vector Problem


texts: On a possible probabilistic log-rank conjecture

texts:
The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M_f (a,b)$ is the function value $f(a,b)$.

The log-rank conjecture asserts that for the communication complexity $CC(f)$ it holds that $ CC(f) = (\log rank (M_{f}))^{O(1)}$.

Given $k\in\Bbb N$, is it known whether
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{p(k)}$$
where the probability is over $0/1$ matrices $M_f$ of fixed rank $rank (M_{f})=r$, for a polynomial $p(x)\in\Bbb Z_{\geq0}[x]$ or
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{n^k}$$
where the probability is over $2^n\times 2^n$ $0/1$-matrices $M_f$ of fixed rank $rank (M_{f})=r$ ?


texts: Is there any theory that allows to compute the computational complexity boundaries like this?

texts:
I recently had an interview, at which I was asked to solve the following problem: you have a sorted array of integers, and you need to find if there are 3 numbers that sum to 0. The brute force solution gives $O(n^3)$ complexity. Given that it is sorted, we can iterate over 2 numbers, and the third one using binary search. It gives $O(n^2\log(n))$ complexity. In fact, there exist a solution with $O(n^2)$ complexity, but apparently this is the best what we can get.

I was thinking is there a way to show in advance that $O(n^2$) is the best, and I came up with the following considerations. They are based on the postulate that if the solution of a problem contains $I$ amount of information, then the minimum amount of operations required to get it is $O(2^I)$. Indeed, if we have $n$ equally probable independent answers, i.e., $I=log(n)$, the only way to solve the problem is to try each of them, i.e. spend $O(n)$ operations. Here are the considerations applied to the problem above.

1) Let us imagine that the array is unsorted. In this case any combination of 3 digits can be a solution, and therefore the amount of information in the answer is $3\log(n)$.

2) Let us assume that the best sorting algorithm has a complexity $O(n\log(n))$, so we can consider that $\log(n\log(n))$ is the amount of information it gives us about the array. Or in other words, the entropy of the array was decreased on this amount.

3) Subtracting one from another, we get $3\log(n) - \log(n\log(n)) = 2\log(n) - \log(\log(n))$. This is the amount of information in the solution of the problem.

4) According to the postulate, the algorithm complexity must be at least $O(2^{2\log(n) - \log(\log(n))}) = O(n^2/\log(n))$. This coincides with the fact that there exist a solution with the complexity $O(n^2)$, but not $O(n\log(n))$.

What do you think? Could you advice me to read something similar?


texts: Was the reduction in Shor's algorithm originally discovered by Shor?

texts: This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was it previously known?  Is there a paper that describes the reduction that pre-dates Shor, or is it simply a so-called "folk result?"  Or was it simply another breakthrough in the same paper?


texts: Flajolet analyzed Wegman's Adaptive Sampling for estimating distinct values (species) in a stream (population), giving an unbiased estimator for mean and specified the standard error to be approximately $1.2/\sqrt(n)$ where n is the number of samples. Another way of estimating the number of distinct values is by using Bernoulli sampling over uniformly hashed value of the target attribute. In this case, the standard error should be $\sqrt{pq/n}$. The obvious advantage of Adaptive Sampling is the number of samples retained is at most n whereas Bernoulli sampling would require $Np$ samples ($O(N)$ in $N$, the actual number of distinct values). Is my analysis correct? For some reason, I cannot accept the Bernoulli sampling can be more accurate than Adaptive for fixed sample size, $n$. Thoughts?


texts: About switching from a computer scientist to a mathematician

texts: What is the possibility for a computer scientist to change his field into a pure mathematician ? and what's the most smooth way to do it ? any examples for people who could make it ?


texts: 2-hop distributed coloring in the CONGEST model

texts:
Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$.

A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \implies c(u)\neq c(v)$.
Intuitively, this is a valid coloring for $G^{\le 2}$.

Finally, assume that the degree of each vertex is bounded by $\Delta$.

A known result is that one can color $G$ using $\Delta^2$ colors in $O(\log^* n)$ rounds.
As the degree in $G^{\le 2}$ is bounded by $\Delta^2$, it would make sense to try to color it (and thus, compute a 2-hop coloring for $G$) using $\Delta^4$ colors.

However, simulating each iteration of the coloring algorithm may require $\Omega(\Delta)$ communication rounds in the CONGEST model (as we are allowed to communicate only on $E$).

  Is there an algorithm that computes a 2-hop coloring for $G$, using $\text{poly}(\Delta)$ colors, with a runtime independent or sublinear in $\Delta$? What about $k$-hop coloring for some $k=O(1)$?


texts: Why is lambda calculus so "function" oriented?

texts:
I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function?

It seems it has something to do with the evolution of Logic (See History of the Function Concept) and trying to "nail down" what was really meant by a function. Going through the history - FO-logic, intuitionistic logic, combinatory logic, lambda calculus etc., I still am a bit unsure about why did Church go with the function-oriented view of things. I know he was trying to work on a system for foundations of logic/math which led to the creation of $\lambda$-calculus. But what I wish to understand is his thinking and reasoning that led to the use of functions as the vehicle of choice, for getting there.


texts: Decomposition based on approximate separators in graph

texts:
Suppose I want to find vertex subset $S$ of graph $G=(V,E)$ such that any simple closed walk that visits vertices both in $S$ and in $V\backslash S$ has length $\ge g$

The idea is to relax requirements of tree decomposition to get bag-graph of large girth instead of a tree, and form an approximation algorithm based on this decomposition.

Does this come up in any literature?

Clarification
Bags in the context of tree decomposition are sets of nodes. Taking bags produced by tree decomposition algorithm and connecting any pair of bags that are not disjoint gives a tree.

This trade-off idea is briefly mentioned in Koller's "Graphical Models" book where she calls it "Cluster Graph" and defines it similar to a tree decomposition except that the graph formed by connecting overlapping bags is not restricted to be a tree. In the context of probabilistic inference, this approach gives a way to trade off cost and accuracy, with exact tree decomposition-based approach as a special case.

Since quality of approximation improves with girth of such graph while complexity increases with size of bags/clusters, a natural question is when it's possible to find a "(relaxed?) tree decomposition" where largest bag size is bounded above and girth is bounded below


texts:
I suggest the following definition of $\mathsf{\Pi_2 L}$  (similarly to the certificate definition of $\mathsf{NL}$):

A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic Turing Machine $M$ and polynomials $p$ and $q$ such that

$$x \in L \Leftrightarrow \forall z \in \{0,1\}^{p(|x|)} \exists y \in \{0,1\}^{q(|x|)} M(x, z, y) =1.$$
Here $x$ is placed on its input tape and $z$ and $y$ are placed
on its special read-once tapes, and $M$ uses at most $O(\log |x|)$ space on its read/write tapes for every
input $x$. We can read $z$ and $y$ simultaneously.

What can we say about this complexity class? Since $\mathsf{NL} \subseteq \mathsf{P}$
we have  $\mathsf{\Pi_2 L} \subseteq \mathsf{coNP}$. Can we say something else about this class? An example of a language from $\mathsf{\Pi_2 L}$ is here: Is unary $\Pi_2$-SUBSETSUM coNP-complete?


texts: Is it possible to find if a sequence exists in polynomial time in the following problem?

texts:
I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no sucess.

Here is the problem:

You have a sorted set $\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\}$ of positive integers pairs.

$(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i = A_j \land B_i < B_j)$
$(A_i, B_i) = (A_j, B_j) \Leftrightarrow A_i = A_j \land B_i = B_j$

The following operation can be applied to a pair: Swap(pair). It swaps the elements of the pair, so $(10, 50)$ will become $(50, 10)$

When a pair in the set is swapped, the set automatically gets sorted again (the swapped pair is out of place and it will get moved into its place in the set).

The problem consist on see if there is a sequence that, starting on some pair, swaps the entire set, with the following condition:

After a pair is swapped, the next pair to be swapped has to be either the successor or the predecesor pair in the set.

It would be great to find a polynomial time solution to this problem, or a reduction of an NP-Complete problem into it.

Note:
It's already a decision problem. I don't want to know which the sequence is: only if a sequence exists.

Example of how the set gets sorted after swapping a pair

$\textbf{(6, 5)}$
$(1,2)$
$(3,4)$
$(7,8)$

If I swap the first pair, it becomes to: $(5,6)$, and after sorting the set (placing the sorted pair in its new position), we have:

$(1,2)$
$(3,4)$
$\textbf{(5,6)}$
$(7,8)$

Then I have to swap either the $(3,4)$ (predecessor) pair or $(7,8)$ (sucessor), and repeat the process until all pairs are swapped (if possible).

Important:
You cannot swap an already swapped pair.
If there is a sequence of 'swap' operations, then all pairs has to be renamed to once and only once.

Example where isn't possible to swap all pairs

$(0, 0)$
$(1, 4)$
$(3, 2)$
$(5, 5)$


texts: Unit distance representation of a graph through Semidefinite Programming

texts:
I would like to ask on the number of different drawings of the unit distance representation of a graph, found through a semidefinite program (see www.cs.elte.hu/~lovasz/semidef.ps , p. 20-22). Since we find the Gram matrix, there should be not just one unique unit distance representation having the SAME dimension and SAME radius of course (after analyzing the Gram matrix in vectors, since one Gram matrix may give many pairs of matrices multiplied together).

So, do we have any information on a bound of the possible different drawings of a graph obtained by this SDP? Is it polynomial for example? Thanks


texts: Explaining Applicative functor in categorical terms - monoidal functors

texts:
I'd like to understand Applicative in terms of category theory.

The documentation for Applicative says that it's a strong lax monoidal functor.

First, Wikipedia page about monoidal functors says that a monoidal functor is either lax or strong. So it seems to me that either one of the sources is wrong, or they use the terms differently. Can anybody explain that?

Second, what are the monoidal categories of which Applicative are monoidal functors? I assume that the functors are endo-functors on the standard Haskell category (objects = types, morphisms = functions), but I have no idea what is the monoidal structure on this category.

Thanks for help.


texts: How many disjoint edge-cuts a DAG must have?

texts:
The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that the minimal size of
a monotone nondeterministic branching program for the
STCONN problem is $\Theta(n^3)$.

Let $G$ be a DAG (directed acyclic graph)
with one source node $s$ and one target node $t$.
A $k$-cut is a set of edges, whose removal destroys all $s$-$t$ paths
of length $\geq k$; we assume that there are such paths in $G$.
Note that shorter $s$-$t$ paths need not be destroyed.

Question:
Does $G$ must have at least (about) $k$ disjoint $k$-cuts?

If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because
we have the following known min-max fact (a dual to
Menger’s theorem) attributed to Robacker$\ast$.
An $s$-$t$ cut is
a $k$-cut for $k=1$ (destroys all $s$-$t$ paths).

Fact:
In any directed graph, the maximum number of edge-disjoint $s$-$t$ cuts is equal to the minimum length of an $s$-$t$ path.

Note that this holds even if the graph is not acyclic.

Proof:
Trivially, the minimum is at least the maximum, since each $s$-$t$
path intersects
each $s$-$t$ cut in an edge.
To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$.
Let  $U_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and
let $E_r$ be the set of edges leaving $U_r$.
It is clear that the sets $E_r$ are disjoint, because the sets $U_r$ are such.
So, it remains to show that each $E_r$ is an $s$-$t$ cut.
To show this, take an arbitrary $s$-$t$ path $p=(u_1, u_2, \ldots,u_m)$
with $u_1=s$ and $u_m=t$. Since $d(u_{i+1})\leq d(u_i)+1$, the sequence
of distances $d(u_1),\ldots,d(u_m)$ must reach the value
$d(u_m)=d(t)$ by starting at $d(u_1)=d(s)=0$ and increasing the value by at
most $1$ in each step. If some value $d(u_i)$ is decreased , then we must
reach value $d(u_i)$ latter. So, there must be a $j$ where a jump
from $d(u_j)=r$ to $d(u_{j+1})=r+1$ happens, meaning the edge $(u_j,u_{j+1})$
belongs to $E_r$, as desired. Q.E.D.

But what if there are also shorter (than $k$) paths? Any hint/reference?

$^{\ast}$
J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network,
Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan-
uary] 1956.

EDIT (a day later): Via a short and very nice argument,
David Eppstein answered the original question
above in negative: the complete DAG $T_n$ (a transitive tournament) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting structural fact, for $k$ about $\sqrt{n}$. A cut is pure if it contains no edges incident to $s$ or to $t$.

Every pure $k$-cut in $T_n$ contains a path of length $k$.

This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap
"too much". Hence, a relaxed question (the consequences for STCONN would be the same):

Question 2:
If every pure $k$-cut has $\geq M$ edges, does then the graph must have
about $\Omega(k\cdot M)$ edges?

The connection with the complexity
of STCONN comes from the result of Erdős and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K_m$ in order to destroy all paths of length $k$.

EDIT 2: I now asked Question 2 at mathoverflow.


texts: Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range

texts:
I have a set of n real numbers.  I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u].  Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets whose variance falls within r.  Not only that, but I want to do this in an efficient manner.  That is, the time for choosing a particular subset should be polynomial in n and k.

Note that n is large enough that I cannot brute-force the problem.  That is, I cannot just iterate through all k-element subsets and find which ones have a variance that falls within r.

Is there a way to do this?


texts: Origin of simulation relations for compiler correctness

texts:
Leroy uses simulation relations as a means of showing compiler correctness; the basic idea is that a simulation relation is an asymmetric binary relation between states in two different small step semantics such that initial states are related, and the relation is preserved under a single step in the first semantics by a finite sequence of steps (or sometimes none) in the second. This can be augmented with notions of trace inclusion, and then determinism proofs allow trace equivalence to be shown from the existence of a simulation.
Chlipala covers this in his text (which is where I first learned about it), but there are no citations, and I'm not sure whether the method is due to Leroy or if it has earlier origins.


texts: Is it possible to determine if a reduction is correct?

texts:
Suppose we have an arbitrary term, x, in Lambda Calculus, or in an equivalent turing-complete system. Suppose we ask an oracle what is the normal form of that term, and it answers y. Is it possible to determine, in finite time, if the oracle answer's ir correct?

Secondary question: is there any system (non-turing complete, perhaps) where that would be possible?


texts: Choosing subsets of a set such that the subsets satisfy a global constraint

texts:
We have a set of items $I = \{i_1, i_2, ..., i_n\}$.  Each of these items has what we call a p value, which is some real number.  We want to choose a subset of $I$, call it $I'$, of size $m$ (for some $m$ with $1 \le m \le n$) such that the average of the p values of the items in $I'$ falls within some specified range, $[p_l, p_u]$.  (For example, we might require an average p value between 0.70 and 0.74.)  Moreover, we want to do this efficiently.

We hope to do this in O(n) time, but any polynomial time algorithm is good enough.  We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average p-value constraint.

Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.

Is there a way of doing this?


texts: Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?

texts:
Context: For fun and perhaps for actual use, I'm making my own programming language that would compile to Typed Racket, a statically-typed Lisp dialect. One of the major features I want to implement is rampantly persistent data structures in the standard library. Persistent dictionaries are basically a solved problem (AVL trees, red-black trees aren't much slower than hash tables), I'm now trying to find a good solution for persistent vectors.

In Okasaki's famous Purely Functional Data Structures, "skew binary random access lists" were introduced. Apparently, they have $O(1)$ prepend, $O(1)$ index to first and last, and $O(\log n)$ random access and update. By my own little microbenchmarks, this data structure is one of the fastest ways to implement a persistent vector: in particular it seems to be much faster than hash-trie based methods like the one used by Clojure, or things such as Braun trees. In fact, indexing near the beginning is only around 2x slower than Lisp linked lists' car operation! In addition, prepend and modification near the front is extremely fast, which allows these lists to be used in places where linked lists are idiomatic (implementing map by recursion on the remaining portion for example). Clojure's hash tries, to put it vulgarly, suck really bad when appended to in a loop due to copying a 32-pointer block over and over, and thus Clojure also uses a primitive linked-list data type. I want to avoid that.

In the same book, "catenable lists" that have $O(\log n)$ append were discussed, but these lists have $O(n)$ performance on update and index.

Bagwell and Rompf's RRB-Trees: Efficient Immutable Vectors gives a modification to the Clojure-style persistent hash trie that allows $O(\log n)$ append (and surprisingly, range) while preserving $O(\log n)$ indexing. However, I'm not that keen to adopt a hash-trie for my standard persistent vector, since that would mean giving up the incredibly fast performance of skewed binary random access lists. Hash-tries are fine for implementing dictionaries, but I feel that they would be too slow for a general array/list datatype.

Is there a data structure with $O(1)$ car and $O(\log n)$ updating, like Okasaki's skewed binary random access lists, while having sublinear append?

Edit: Herp derp, skewed binary RA lists don't have $O(1)$ access to the middle


texts: The complexity of the dominating set problem in specific subclasses of chordal graphs

texts:
I am interested in the complexity of the dominating set problem (DSP) in some specific graph classes which are subclasses of chordal graphs.

A graph is an undirected path graph if it is the vertex-intersection graph of a family of paths in some undirected tree. Let UP be the class of undirected path graphs.

A graph is an EPT graph if it is the edge-intersection graph of a family of paths in some undirected tree. An EPT graph may not be chordal, but let CEPT be the class of chordal EPT graphs.

A graph is a (rooted) directed path graph if it is the vertex-intersection graph of a family of directed paths in some rooted directed tree (i.e. all arcs directed away from the root). Let RDP be the class of (rooted) directed path graphs.

We have $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

It is known that the DSP is linear-time solvable for graphs in RDP but NP-complete for graphs of UP [Booth and Johnson, 1981]

I am interested in special graphs which correspond to vertex-intersection graphs of families of undirected paths in caterpillar-like trees of maximum degree 3.
More precisely, these "caterpillars" are built from a path in which each second vertex has a pendant degree-one-vertex attached to.
Let us call this class cat-UP.

Moreover, my special graphs can also be constructed as the edge-intersection graphs of some families of undirected paths in specific trees of maximum degree 3.

So my questions are:

1) Is the complexity of the DSP for graphs of cat-UP known ?
(note that the reduction in [Booth and Johnson, 1981] produces a host tree which is of maximum degree 3, but quite far from a caterpillar)

2) What is the complexity of DSP for graphs of CEPT ? And for graphs of CEPT arising form a host tree of maximum degree 3 ?
(this is not known to ISGCI)

3) Is there any complexity result for the DSP in a closely related graph family ?


texts: Circuit lower bounds and kolmogorov complexity

texts:
Consider the following reasoning:

Let $K(x)$ denote the Kolmogorov complexity of the string $x$.
Chaitin's incompleteness theorem says that

  for any consistent and sufficiently strong formal system $S$, there
  exists a constant $T$ (depending only on the formal system and its language) such
  that for any strings $x$,
  $S$ cannot prove that $K(x) \geq T$.

Let $f_n$ be a Boolean function on $n$ variables s.t. the Kolmogorov complexity of its spectrum is at most $k$.
Let $S(f_n)$ be the circuit complexity of $f_n$, i.e. the size of the minimal circuit computing $f_n$.

A (rough) upper bound on for $S(f_n)$ is
$$S(f_n)\leq c\cdot BB(k) \cdot n$$
for a constant $c$ and $BB(k)$ is a busy beaver function (the maximum possible steps a halting Turing machine with a description of size $k$ can perform).
(For every $1$ in the spectrum, construct the minterm of the corresponding
truth assignment, and take OR of all these minterms together.)

Suppose now for an infinite family of Boolean functions
$L = \{f_n\}_{n}$, we have a formal proof that
$L$ requires superlinear size circuits, i.e.

$$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$$
where $g(n)\in \omega(1)$.

If we take $n$ to be sufficiently large, we will have
$$g(n) > c\cdot BB(T)$$

In particular this would be a proof that the Kolmogorov complexity of the spectrum
of $f_n$ is at least $T$, which is impossible.

This leads to two questions:

1) There should be something wrong in the above reasoning.
Mainly because it would make superlinear circuit lower bounds formally not provable.

2) Do you know of similar approaches to show barriers for lower bounds, that is, showing that certain types of (circuit) lower bounds are formally unprovable?


texts: Relation between the running time of Turing machines with different symbol sets

texts:
In Arora and Barak's Computational Complexity, Claim 1.5 says that if a function $f$ is computable in time $T(n)$ by a Turing machine with alphabet $\Gamma$ then it is computable in at most time $4\log|\Gamma|T(n)$ by a Turing machine with the symbol set $\{0,1,\rhd,\Box\}$ where $\rhd$ is a special symbol that is used to mark the beginning of each tape and $\Box$ is the blank symbol.

  It seems to me that we can reduce the bound to $3\log|\Gamma|T(n)$. Am I right in this?

It seems to me that the above can be achieved using the same device as discussed in the book: we represent each alphabet of the original Turing machine by a sequence of $k=\log |\Gamma|$ bits. Let's further decide to represent the blank symbol of the original machine by a sequence of $k$ $\Box$s (this is not mentioned in the book). Our new machine has intermediate states where it reads $k$ bits to identify the symbol that would have been read from the tape of the original machine, then moves $k$ steps backward on each tape writing down the representation of the new symbol that would have been written on the tapes of the original machine, then moves $k$ steps to the left or right on each tape to position the head on the beginning of the symbol that would have been read next by the original machine. So a total of only $3k$ steps seems to be required to simulate each step of the original machine.

To take an example suppose $|\Gamma|=16$ and we are simulating a step of the original machine which required reading the symbol represented by abcd, overwriting it by ABCD and then moving the head to the right. This can be accomplished as follows:

We begin at

efgh|abcd|pqrs
     ^

In 4 steps read all the bits of abcd. In the 4th step we know enough to decide that we have to replace d by D. We do that and move back one step

efgh|abcD|pqrs
       ^

In 3 more steps we have replaced abc by ABC and positioned the head at B

efgh|ABCD|pqrs
      ^

In 3 more steps we have moved the head to p

efgh|ABCD|pqrs
          ^

If the original machine had wanted to move left rather than right we would have positioned the head at h after writing A and then would have moved to e in 3 more steps. So actually we need only $3k-2$ steps.


texts: Are there sparsifiers that approximate vertices rather than edges?

texts:
Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph which can be described using as few as $|V|\operatorname{polylog}|V|$ bits - for every $S\subseteq V$ one can still answer the question: "How many edges in $G$ are in the cut $(S,V-S)$ up to a multiplicative $(1\pm \varepsilon)$?".

You're given a dense graph $G=(V,E)$. Can you produce a sparse graph on the same vertex set, where - only knowing the sparse graph - for every $S\subseteq V$, one can still answer: "How many neighbors does $S$ have in $G$ up to a multiplicative $(1\pm\varepsilon)$?


texts: Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

texts:
Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist?

What are these problems called? Where can I find out more?