texts: Family of functions with properties similar to k-wise independent hash functions

texts:
I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a set of size $\approx \ell$ such that the probability for the last hash value to collide with any former hash value is almost identical for all possible inputs.

More formally, let $k, \ell \in \mathbb{N}$, where $\ell \gg k$ is polynomial in $k$. Now let $\mathcal{S} := \{(x_1, \ldots, x_{\ell}) \in (\{0,1\}^k)^\ell \text{ with } x_i \neq x_j \forall i \neq j\}$ be the set  of all sequences of length $\ell$ of pairwise different elements from $\{0,1\}^k$.

The question then is whether there is a family of functions $ \mathcal{H} := \{h : \{0,1\}^k \to \{0,1\}^m\} $, for some $m = \mathcal{O}(\log(\ell))$ such that

the upper and lower bounds on a collision for the last hash are almost identical, meaning
$$
\max_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]\} -
\min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]
\} \leq 2^{\Omega(k)}
$$
and there is some constant $c \in (0,1]$, such that
$$
c \leq \min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]
\},
$$
independently from $k$ and $\ell$.
Furthermore, a function in $\mathcal{H}$ should be representable by $\mathcal{O}(k \log(k))$ many bits.

While a family of (almost) $\ell$-wise independent hash functions would fulfill conditions 1 and 2, all such families I am aware of would not fulfill condition 3 since they require at least $\Omega(\ell)$ many bits to represent a function from the family.

There is already this question on this Stackexchange, but it is only concerned with the lower bound and the size of the representation, not with the difference between upper and lower bound. There are also several publications that show that in many cases $k$-wise independence suffices to achieve results very close to full independence:

Schmidt, Jeanette P.; Siegel, Alan; Srinivasan, Aravind, Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math. 8, No. 2, 223-250 (1995). ZBL0819.60032.

Dietzfelbinger, Martin; Rink, Michael, Applications of a splitting trick, Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 354-365 (2009). ZBL1248.68166.

Celis, L. Elisa; Reingold, Omer; Segev, Gil; Wieder, Udi, Balls and bins: smaller hash families and faster evaluation, SIAM J. Comput. 42, No. 3, 1030-1050 (2013). ZBL1275.68075.

However, the publications mostly consider the probability in a balls into bins experiment for the maximal load of a bin to be greater than a threshold. While there is some similarity between the two questions, I fail to preciesly map my question to the maximum load of a bin.


texts: maximum weighted 2D coverage problem by a rectangle

texts:
Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$.
Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a axis-parallel rectangle with a fixed size that can translate in the plane.
The question is how to preprocess the points so that, for all possible positions of the rectangle, it is efficient to determine the largest weight of the
subset of points that can be covered by the rectangle at the same time.

Question: what are the best running time and algorithm for finding the largest weight of the subset of points? Is $O(n \log n)$ possible?

I thought this might be an easy question to answer, but I failed to find any proper reference to this question. Any thought or reference will be appreciated.


texts: Faithful functors vs forgetful functors: exact category-theoretic defs?

texts:
In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the incidence relations.

For each pair of objects $x,y$ of $C$, we may then define a map $F_{x,y}$ that takes any morphism $m : x \rightarrow y$ to a morphism $F(m) : F(x) \rightarrow F(y)$. I understand that $F$ is called faithful if every such mapping $F_{x,y}$ is injective, which means intuitively that the relational structure of the category is preserved, although the objects may not be.

There is a related notion of forgetful functor for which I couldn't find a precise definition, so is there anyone willing to help? I mean, is it just the opposite of faithful or is it the combination of unfaithfulness with some other implicit property?


texts: Is the Chi-square divergence a Bregman divergence?

texts:
Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as
$\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$?

If so, what is the potential function $\phi(x)$ from which it is generated?
If not, does there exists a Bregman divergence which bounds Chi-square divergence from above?


texts: Detecting infeasibility of System of Linear Inequalities

texts:
Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a basic feasible solution. If one cannot be found then the problem is infeasible.

Are there any other methods to detect infeasibility of a the system?


texts: Unary language examples between L and NP

texts:
I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $.
What I found after some search(e.g., Complexity zoo for unary languages):

It is not known whether there is a NP-Complete unary language.
There are many known results for automata models and sub-logarithmic space.
There seems no Zoo-style reference yet.

For example, is there any unary language in $ NL $ but not known in $ L $, in $ P $ but not known in $ NL $ or log-space alternating hierarchy?
Or, what are "the hardest" unary languages in $ NP $?


texts:
Define a "problem" to be an algorithm $A$ accepting a natural number and returning 0 or 1 which returns $1$ on at least one $n \in \mathbb{N}$. Any such $n$ is called a "solution" to $A$

Define a "universal problem solver" to be an algorithm $U$ accepting a problem and returning one of its solutions. For example, $U$ can work by looping over all natural numbers and running its input on them until $1$ results (it only has to halt on valid input)

I'm interested in exploring performance bounds on universal problem solvers

Given $U$ a universal problem solver and $A$ a problem, denote $t(U, A)$ the time it takes $U$ to produce output upon accepting input $A$

A universal problem solver $U$ is called "efficient" when for any universal problem solver $V$, we have

$$t(U, A) < t(V, A) + t_V $$

Here $t_V$ depends on $V$ but doesn't depend on $A$

  Do efficient universal problem solvers exist?

EDIT: I realized it is possible to change the definitions of "problem" and "universal problem solver" into something slightly more elegant and essentially equivalent. A "problem" is an algorithm without input returning 0 or 1 (which halts). A "universal problem solver" is an algorithm accepting a problem and returning its result. It's more or less a universal Turing machine

Old definition can be reduced to new definition, since given $A$ a problem in the old sense, we can construct $B$ a problem in the new sense which just applies the trivial old-sense universal problem solver to $A$ (the solver described in the text above)

New definition can be reduced to old definition, since given $B$ a problem in the new sense, we can construct $A$ a problem in the old sense which just computes $B$ and compares the input to the result

The trivial example of a new-sense universal problem solver is an algorithm which simply runs its input


texts: Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

texts:
I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup \text{PSPACE-complete}$.

Is it known any such a problem ?

(It would be very nice to have examples of $\text{PSPACE}\cap\text{coNP-hard}$ combinatorial games with these properties, but any other kind of example would be high appreciated)


texts:
This question may have an obvious answer ... but here's the question anyway. Intuitively, it is the following plausible statement - "a machine with a subroutine A which in turn has a subroutine B is the same as a machine with a subroutine A which has access to subroutine B".

To define this problem formally, I'll use some unconventional notation. When I say $A^B$, I am giving $A$ an oracle for a $B-Complete$ problem. e.g $NP^{NP}=NP^{SAT}=\Sigma_2$. With this "new" notation, it's possible to define $A^{B^C}$, and so on. My question is, is

is this a valid way of thinking about oracles?
is $(A^B)^C = A^{(B^C)}$

For example, $(NP^{NP})^{NP} = \Sigma_2^{NP} = NP^{\Sigma_2}=NP^{({NP}^{NP})}$

I can't think of any obvious counterexamples to this rule. Anyone?


texts:
It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\mathcal{C}$. It is not clear to me if the PAC learning algorithm (which uses these many samples) is proper or improper? In the textbooks of Kearns and Vazirani as well as Anthony and Biggs it seems like the PAC learning algorithm is improper (i.e., the output hypothesis does not lie in $\mathcal{C}$)

Could someone clarify if a similar upper bound holds for the proper PAC learning setting as well?  If so, could you give me a reference where this is explicitly mentioned and also contains a self-contained proof?
Recently Hanneke improved this bound by getting rid of the $\log(1/\varepsilon)$ factor. Could someone clarify if the $\log(1/\varepsilon)$ is known to be removable for the Proper PAC learning setting? Or is it an open question still?


texts: Optimal partition according to partition cardinality

texts:
Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.

We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.

Can the minimum number of partitions be found in polynomial time?
If so, how to know what other partition cost functions admit polynomial algorithms as well?


texts: Can consume/produce be modeled in linear logic?

texts:
Question is whether it is possible to model in linear logic
two modes of access to a resource. I know that two modes
of resources are possible, i.e:

$!r \vdash$      r is infinitely available
$r \vdash \quad$       r is only once available

But what if I don't want to decide whether r is infinitely or
only once available. And the query, i.e access, should
decide, so:

$*r \vdash r \quad \quad \quad \quad \quad \quad$ r is only checked (like it were !r)
$*r \vdash consume(r)$  r is consumed (like it were r alone)

Can I model a consume(r) and a normal r access in linear logic?
Similarly I would like to have produce(r) operator, which then
asserts the form *r of a resource.


texts: Bounding Rademacher Averages, with and without chaining

texts:
One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma:
$$
R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}
$$
where $\|\cdot\|$ is the Euclidean norm.

Then, using Sauer's Lemma, one can obtain
$$
R_n(A)\le C\max_{a\in A}\|a\|\sqrt{\frac{V\ln\frac{n}{V}}{n}},$$
where $V$ is the (empirical) VC-dimension.

Using chaining and a bound on covering numbers, one can get rid of the logarithmic factor and obtain
$$
R_n(A)\le C'\sqrt{\frac{V}{n}}.
$$

Looking at the proof that uses chaining, I can't seem to find a way to have $\max_{a\in A}\|a\|$ in the second bound. Is it even possible?

It may not change much in theory, but it does in practice, and (in my opinion), it intuitively makes sense that the bound should depend on it.


texts: Amortized time and worst case (non-amortized) separation

texts: Assume a reasonable computation model (thinking about pointer machine or RAM model), is there a problem where there is a clear separation between amortized and worst case complexity? Say, if amortization is not allowed and only worst case for each operation is considered, the time complexity will be (provably) higher. Notice that this is different from random self-reducibility.


texts:
Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets such that most pairs of sets form bipartite expanders (the number of sets in the partition and the expansion parameter depend on the approximation parameter):

http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma

There are versions of this lemma for "well-behaving" sparse graphs, see, e.g.:

http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf

http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf

What surprises me about these formulations is that they only guarantee that most pairs of sets in the partition form bipartite expanders, and these bipartite expanders may be empty. So, in general sparse graphs, it's quite possible that all edges between different parts in the partition of the vertices don't belong to an expander.

I wonder whether there are formulations that give that most edges between parts are from an expander, or whether there's no hope for such a formulation.


texts: Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

texts:
Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ conjecture.
So my question is:

As long as the $\mathsf{P}\neq\mathsf{NP}$ conjecture is not proven, can/should one consider it as a law of nature, as indicated in the quote from Strassen?
Or should we treat it as a mathematical conjecture
that maybe proved or disproved someday?

Quote:

"The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure are so grotesque, that
their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures."
[Volker Strassen's laudation
to the Nevanlinna Prize winner, Leslie G. Valian, in 1986]

I ask this question when reading the post Physics results in TCS?.
It is perhaps interesting to note that computational complexity has some similarities to (theoretical) physic: many important complexity results
have been proved by assuming $\mathsf{P} \neq \mathsf{NP}$, while in theoretical physic results are proven by assuming some physical laws.
In this sense, $\mathsf{P} \neq \mathsf{NP}$ can be considered something like $E = mc^2$.
Back to Physics results in TCS?:

Could (part of) TCS be a branch of natural sciences?

Clarification:
(c.f. Suresh's answer below)

Is it legitimate to say that the $\mathsf{P}\neq\mathsf{NP}$ conjecture in complexity theory is as fundamental as a physical laws in theoretical physics (as Strassen said)?


texts: complexity of checking if a subspace is a Euclidean section of L1

texts:
If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have

$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$

for some small $\epsilon >0$, then we say that $X$ is an almost-Euclidean section of $\ell_1^n$, and (the matrix whose image is) X is useful in compressed sensing. A random subspace works excellently, and there is a huge research program devoted to the explicit construction of such spaces.

Is it known what is the complexity of approximating the "Euclidan-sectionness" of $X$? That is, given a subspace $X$, say presented via a basis, consider the problem of finding the unit (in $\ell_2$ norm) vector in $X$ of smallest $\ell_1$ norm.

  What is the complexity of this problem? Are hardness of approximation results known?

Apart from specific applications, these seem to be interesting problems. Is it known what is the complexity of finding the vector of maximum $\ell_1$ norm among the unit vectors of a given subspace?


texts: Algorithms for Nash equilibrium computation.

texts:
I searched the forum to see if this has been asked before, and while algorithmic game theory is discussed, I couldn't find this particular issue addressed.  I am trying to figure out what the best known algorithm is for computing approximate (mixed-strategy) Nash equilibria in a finite n-person game.  Of course, this algorithm would be PPAD.  I am more interested in speed/efficiency than perfect accuracy of the algorithm.

Thanks,
Philip


texts: Reducing $n$ in $(n,k)$ secret sharing while keeping it effective

texts:
Assume Bob wants to share a secret with Alice.
Assume he can only send messages using a one-sided channel which is insecure and unreliable.
Unreliable, meaning: Alice only gets messages sent over this channel with probability $P$.
Insecure, meaning: Mallory the bad guy can read any message sent over this channel with probability $P'$.

Assuming $P>P'$, Bob can use $(n,k)$-secret sharing when $P>k/n>P'$.
As Bob increases $n$, the probability that Alice receives a correct message increases and that Mallory receives a correct message decreases.
This is because the mean of secret shares Alice and Bob get remains $P n$ and $P' n$ respectively, while the standard deviation drops as $n$ increases.

But there is more than one way to do this. For example, Bob and Alice could choose a relatively small $n$, transfer TWO secrets s.t. their XOR is the original secret. In this case Mallory's probability of learning the original secret will be squared, and decrease much faster than Alice's.

So my question is: Is 'classic' secret sharing ALWAYS the best way (giving the smallest possible $n$ for a given $P$ and $P'$)? I could not find a counter-example yet.


texts: How to find the exact period of Blum-Blum-Shub random number generator?

texts:
I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product of two large primes that are congruent to 3 (mod 4).

Is there any way to determine the exact period of BBS?


texts: Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?

texts:
Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ($d = O(1)$) circuits?

We know that every function computable by a $\mathsf{NC^1}$ circuit can be computed by a size $2^{O(n^\epsilon)}$ depth $d$ circuit (using AND, OR, and NOT gates, unbounded fan-in) (for every $0 <\epsilon$ there is a $d$ and $d$ can be taken to be $O(1/\epsilon)$).

The question is:

  is there a reason that would make the existence of such circuits for general polynomial size circuits unlikely?


texts: Threshold for non-zero quantum capacity of depolarizing channels

texts: In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was greater than 0.80944. What I want to know is the lowest value known for the fidelity such that quantum communication is still possible. Does anyone know the current state of the art with respect to this problem?


texts: Number of solutions for a system of linear equations over a finite ring

texts:
Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and
$b\in R^{m}$.

Questions:

What is the complexity of counting the number of solutions to the system of equations $Ax = b$? Can it be done in polynomial time?
More generally, let $R$ is a finite set and $(+,\cdot)$ be binary opeartions such that $(R,+)$ and $(R,\cdot)$ are (not necessarily commutative) semigroups. What is the complexity of counting the number of solutions to a system of linear equations $Ax=b$?

Note that it is well known that the answer to Question 1 is affirmative if the the ring $R$ is a finite field.


texts: Omitting parameters in primitive recursive functions

texts:
will replacing the usual schema of primitive recursion:
$$
f(0,\vec x) = c (\vec x)\\
f(n+1,\vec x) = g(f(n,\vec x), n, \vec x)
$$
by the form:
$$
f(0,\vec x) = c(\vec x)\\
f(n+1,\vec x) = g(f(n,\vec x))
$$

lead to the same class of primitive recursive functions?


texts: Is $\{a^n b^m : 1 \le m \le 2^{2^n}\}$ a permitting-context language?

texts:
A random permitting-context grammar is a context-free grammar $(N, \Sigma, P, S)$ equipped with a function $p : P \rightarrow 2^N$. The rule $A \rightarrow x$ can be applied to $uAw \Rightarrow uxw$ if every symbol in $p(A\rightarrow x)$ appears in $uw$. A forbidding-context grammar is similar, except  equipped with a function $f : P \rightarrow 2^N$, and a rule application is allowed if no symbol from $f(A\rightarrow x)$ appears in $uw$.

$\{a^n b^m : 1 \le m \le 2^n\}$ is a random permitting-context language (RPCL), though $\{a^n b^m : m = 2^n\}$ is not (as can be proved by Ewert and Van der Walt's pumping lemma for RPCLs). In a permitting grammar we can allow the  nonterminals of some type to double, but we can't force it.

  It seems obvious to me that one can't get more than exponential
  growth, but I can't see how to prove it (the pumping lemma certainly
  doesn't help, since it will just increase the number of $a$'s). Is
  there a known result that helps here?

  I'm also interested in superexponential growth in forbidding languages
  (e.g. is $\{a^{2^{2^n}} : n \in \mathbb{N}\}$ an RFCL).


texts: Writing a paper as a single author in 1st person singular

texts:
I am writing papers in theoretical computer science sometimes being a nonanonymous single author. Earlier, I used the 1st person plural in such papers, e.g.:

  We will show that the complexity classes X and Y coincide.

I am neither a native English speaker nor extremely good at English. Recently, I've gotten an advice from a native English speaker (who is into science but not a computer scientist) to use the 1st person singular instead:

  I will show that the complexity classes X and Y coincide.

He claimed that this style is widespread in "Nature" and other toplevel journals. I'm not used to this style of writing at all; sentences in the style "I have shown that Γ is well-defined on ℂ \ ℤ⩽0" inside proofs seem very unnatural to me.

Which style is more appropriate for theoretical computer science papers?

It is very clear to me that this question is strongly biased by the area (otherwise, I'd have asked ell.se or referred to https://academia.stackexchange.com/q/2945/7734), so I'm asking at cstheory. My question is addressed to mature theoretical computer scientists who are also native English speakers with a perfect command of English.


texts: A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

texts: I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative examples preferably with drawings, and reasonably self-contained. It can be inside a book, an article, lecture notes, website, whatever. Possible languages: English, French, German.


texts: Reductions of hard problems to physical models

texts:
I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes.

For example, max-2-sat can be reduced to energy minimization in an Ising model.  I would like to find more examples of this type of reduction.


texts: Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

texts: Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say that the problem P is NP-hard?


texts: Do problems have to be statable in $\Pi_1$ to use Levin's universal search to find short proofs if P=NP

texts:
In If P=NP, could we obtain proofs of Goldbach's Conjecture etc.? it talks about the hypothetical world where P=NP and using the proof of it to prove a problem/theorem assuming that it has a short proof.

But what exactly is the restriction imposed on problems/theorems? Do they have to be describable in $\Pi_1$ to use Levin's universal search?

If so, can the question like Navier-Stokes existence and smoothness problem be statble in $\Pi_1$?


texts: Constructing Orbits of the Automorphism of a Graph Group in Bliss

texts:
I'm using the Bliss package for graph isomorphism and canonization. The program is working great for the type of graphs I'm interested in. In one of the applications I need to compute the orbits of the automorphism group of the graph. What is the best way to do that in Bliss?

PS: I understand that some people may think that this question is off-topic because it asks about a specific software. But since bliss is a highly specialized software that is used mostly by TCS people (at least consciously) I think that this site is the best one to ask this question. I also think that this may be useful for other researchers interested in graph isomorphism.


texts: What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"

texts:
In Blum's "On the Size of Machines" he uses the word 'uniform' in several places.
For instance, in Theorem 1, he writes

Let $f$ be any recursive function. Then there exists $i,j\in \mathbb{N}$, both uniform in $f$,$g$ such that...

What does the word 'uniform' mean in this context?
In addition, is there a reference that defines what it means when one says a variable is uniform in a function?
Blum's paper is available at this link.


texts: Foundational textbook(s) for Complexity and Computability on Real Numbers

texts: It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological properties of continuous sets. I could not find any, except "Recursive Analysis" by R.L. Goodstein but I dont have any feedback on that book. I would also like to ask for suggestions regarding a book on Complexity over Real Numbers which again deals with the connection between the complexity and the topology of a set. The only book I found on the net was "Complexity and Real Computation" by Lenore Blum et al but I am not sure if that is the book which I am looking for. Thanks in advance.


texts: Algorithm for finding smallest set and instanciation for a given constraint system

texts:
I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:

x1 != x2
x3 != x4 or x5 != x6

and I need to find the smallest set $A$ such that $x_1, \dots x_n \in A$, and of course an instanciation of those variables.

Note that I'm not working with numbers, so I don't have any other sorts of inequalities (like $x_i \leq x_j$, etc.), only $x_i \neq x_j$.

Has this problem a name ? Is there a specific algorithm for this problem ?

I was planning to use a SMT solver for this, replacing $A$ by $\mathbb{N}$ and adding the constraint $\forall i, x_i \leq k$ while minimizing $k$. This works fine but I feel like it's a bit too much.

Thanks for your help!


texts: Lower bound for testing closeness in $L_2$ norm?

texts:
I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:

Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, test (whp) whether

$D_1=D_2$
or $\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon$

Batu et al. [BFR+00] showed that $O\left(\frac{1}{\epsilon^4}\right)$ samples were sufficient, but I haven't found any mention of a lower bound?

I reckon one could always show a $\Omega(\frac{1}{\epsilon^2})$ lower bound by reducing the task of distinguishing a fair vs. $\epsilon$-biased coin to this problem (simulating a distribution supported on only two points, and answering the queries of the tester according to the iid coin tosses), but that still leaves a quadratic gap...

(Another point I'd be interested in is a lower bound in estimating (up to an additive $\epsilon$) this $L_2$ distance — again, I have found no reference to such result in the literature)

Thanks for your help,


texts: Path finding on graph with state dependent edge costs

texts:
I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i.e. accepting drawbacks on sub-paths if this leads to a better overall rating of the full path from A to Z.

I know a problem is that it is impossible to determine whether a path is the best one or if there are better ones without expanding every single possible path.
But maybe there are algorithms around that can handle such problems.
Ideally one can define a threshold in time or rate of cost improvement for a solution to control runtime and optimality as required. Maybe I need a metaheuristical approach?

Background:

As I started with a much simpler problem, that could be easily solved by A* I will outline my thoughts from there on.
A* is able to find the best path only if every sub-path is optimal itself. But in some circumstances, the best path may contain parts that are not optimal if examined stand-alone. This can be the case if edge costs are dependent on the state of a moving entity.
As a practical example I tried to simplify my application as good as possible. In reality it is much more complex in space and state.

A vehicle travels from A to Z, the cost function depends on the fuel burnt. At some node the following edge has additional costs depending on the weight (say a bridge). The higher the vehicle's mass, the higher the costs. A* will find the path with fewest fuel consumption from start to the node before the bridge.
But it may be better to use a path on which more fuel will be consumed to lower the vehicle's mass and thus the cost to travel over the bridge which will in turn reduce the overall costs.

This little graph visualizes such a problem.

(A) -- 1 -- (B) -- 1 -- (C) -- 1 + c -- (Z)
  \                     /
   \-------- 1 --------/

c = 10 * m
m(t) = max(0, 10 - t)

m represents the mass of the vehicle and t the time, which is 0 at the beginning and increases by 1 after each step.
As one can see, the best path from A to D must contain C. So while A* will find the path A-C-Z with costs of 92 (A -- 1 --> C -- 1 + 10*9 --> Z), a better one would be A-B-C-Z with costs of 83. If loops are allowed it even can be reduced to 20 (A-B-C-B-A-B-C-A-B-C-Z)


texts: Does Hadwiger conjecture imply that NP = coNP?

texts:
(Disclaimer: I suspect the answer is no, but I fail to see why)

Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture:

The point is that if in a given graph $G$ some-one gives you four connected subgraphs $G_1$, $G_2$, $G_3$, $G_4$ (here illustrated with grey boxes) such that for each of the six combinations $(i, j)$ there is at least one edge in $G$ connecting a vertex in $G_i$ to one in $G_j$, then the conjecture claims that there is no 3-coloring of the big graph $G$.

Suppose that Hadwiger's conjecture is true. Wouldn't this put 3-coloring in coNP? At least to me it seems that once someone gives you $G_1, G_2, G_3, G_4$ their connectedness and existence of 6 edges connecting the four subgraphs can be checked in time quadratic in the number of vertices of the big graph $G$.

But if indeed 3-coloring is in coNP, wouldn't that put all of NP in coNP thus making these complexity classes equal?

This seems wrong, my impression was that both Hadwiger's conjecture and $NP \neq coNP$ are widely believed, so most likely something is wrong with my reasoning above.

But what?


texts: What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

texts:
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is the best we found?


texts: Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

texts:
What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$?

The "redundancy" of a code is the difference between the block length and message length. Nonexplicitly, it's easy to show that there exist binary codes with distance $d$, block length $n$, and redundancy $O(d \log(n/d))$. When $d \leq n^{1 - \Omega(1)}$, the nonexplicit bound is $O(d \log n)$, which can be matched explicitly using e.g. Reed-Solomon codes. When $d = \alpha n$ with $\alpha$ a sufficiently small positive constant, the nonexplicit bound is $(1 - \Omega(1)) \cdot n$, which can be matched explicitly using e.g. Justesen codes.

What about in the middle? E.g., what if $d = n / \log n$? The nonexplicit redundancy bound is $o(n)$. Is there an explicit code matching it up to a constant?


texts:
Recently I stumbled upon quite an interesting theoretical construct. A so called  Gödel machine

It's a general problem solver which is capable of self-optimization. It's suitable for reactive environments.

As I understand, it can be implemented as a program for universal Turing machine, although it's requirements go far beyond hardware currently available. I couldn't find many details, though.

Can such machines be built in practice? Are they at least feasible in our Universe?


texts:
The Watts-Strogatz model describes a mechanism of generating small-world networks.

The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. After that, a rewiring is performed in which each link present in the network has a probability $p$ of changing one of its endpoints to a new random node. The closer $p$ to 1, the more random is the network.

Is there a similar small-world model for bipartite graphs? That is, is there a mechanism for generating random bipartite graphs that possess the usual properties of small-world networks (a.k.a., the maximum of the minimum distance between any pair of nodes scales no higher than as the logarithm of the number of nodes)?


texts: Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

texts: I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $> 10^{40}$), making this method unappealing. Also, you don't have access to the factorization of $n$, or to $\phi(n)$, so no clever tricks there. Are there any algorithms which run sublinear in $c$? What if I let you pick whatever special values of $a, b, c$ you like, subject to the constraint that none are zero or $\pm 1$, and also $c$ must be above some threshold $M$?


texts: Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?

texts:
Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can be factored efficiently. The algorithm proceeds as follows:

Suppose that $B$ is a machine that returns a square root of any given square $a \in \mathbb{Z}_n$. $B$ may be adversarial and randomized, and is only constrained by the requirement that $B(a)^2 = a$ when $a \in \mathbb{Z}^*_n$ is a square. Then, provided one has private coins, you can interact with $B$ to factor $n$, by picking a uniformly random $y \in \mathbb{Z}_n^*$, and using the fact that with probability $1/2$, $\text{gcd}(B(y^2) + y, n) \in (1,n)$.$[2]$

This does not work if $B$ has access the coins you flipped to draw $y$, since it could just return $y$.

Question: Is there a different protocol that also works if your coins must be public?

Thoughts:

This is superficially similar to $IP[k] \subset AM[k+2]$, but I don't think it is possible to reduce to this fact by using the decision problem version of factorization, since in that context the provers are much stronger than just polynomial time machines with access to $B$. The ideas used there could still be useful.
I don't think that asking for the square roots of a random set of residues in $\mathbb{Z}_n^*$ would be useful, since I can simulate this (if adversarial $B$ gives a random square root) by sampling random $x \in \mathbb{Z}_n^*$ and squaring them.
Perhaps there is a efficiently computable set of quadratic residues whose square roots would provide important information about $n$?

$[2]$: For completeness, the calculation follows from the observation that under the isomorphism $Z_n \cong Z_p \oplus Z_q$, the four square roots of $y^2$ are $(\pm x \mod p, \pm x \mod q)$, and from the point of $B$ $y$ could have been any of them. In two of the four cases for $y$, $x +y \in \{ (2x, 0), (0, 2x) \}$, so is either divisible by $p$ but not $q$, or vica versa. In both cases, we have that $x + y$ is not a multiple of $n$, and the gcd with $n$ is $\geq \min (p,q)$. ($p$ and $q$ are both odd.)


texts: Modal logics axiomatised with nesting depth one which are unlikely to be in PSPACE?

texts:
I am looking for modal logics, which are axiomatised by a finite set of axioms of modal nesting depth one, and whose satisfiability / derivability problem is unlikely to be in PSPACE. Without the restriction on the modal nesting depth this is not a problem, see for example PDL. But it seems that in proving for example EXPTIME-hardness by reduction to some kind of tiling problem or acceptance problem for Turing machines, one would need some kind of transitivity, which is axiomatised in depth two. There are also undecidable logics with a binary modality (Kurucz et al.: Decidable and undecidable logics with a binary modality, 1995), but these typically require associativity, which is depth two as well. In Conditional Logic, again it seems that we need depth two for EXPTIME-hardness (Friedman, Halpern: On the Complexity of Conditional Logics, 1994).

  Can we get EXPTIME-hardness with
  axioms of nesting depth one?

Background: We are trying to find generic decision procedures of a good complexity for logics axiomatised with nesting depth one.


texts:
Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,...,N$ by removing certain edges such that the overall sum of the remaining edge weights across all $N$ sets is minimized. In addition, I would like to set constraints that would force certain pairs of vertices to be in disjoint sets.

Formally speaking, if each set $G_i$ has $M$ edges $e_j, \hspace{2pt}j=1,...,M$, then:

$$min \sum_i^N\sum_j^Me_j$$

and $\mathbb{P}$ is the set of constraints which disallows certain pairs of nodes $v_k$ and $v_l$ from being assigned to the same set:
$$v_k \in G_k,v_l \in G_l \hspace{2pt} \land \hspace{2pt} k \neq l, \hspace{3pt}\forall (k,l) \in \mathbb{P}$$

I've searched around for this, and most minimum cut algorithms only seem to offer bipartite splits. I also looked into s-t cut algorithms, but in my case rather than having a single source and sink I have multiple such pairs that I want to keep in disjoint sets.

Additional Information I'm trying to model segments of walking trajectories as graph nodes. The edge weights denote the dissimilarity score between two trajectory segments (conversely, if I use the similarity score then I require the maximum cut). The constraints will be used to ensure that two trajectory segments that overlap in time must never be assigned to the same set.


texts:
I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1

INC ri   ; ri <- ri + 1
DEC ri  ; ri <- r1 - 1
JNZ  address    ; if (r0 != 0) then jump to <address>. Else, skip.
LDR ri, address  ; load value at <address> into ri
STR ri, address  ; store the value in <ri> to <address>

What interesting programs can I make using this instruction set using no more than 16 instructions (the range of my address space).

So far, the best I have is "check if memory contains an odd value in the range 0-7"

Also, does it help if I add the following instruction:

JLT address ; if (r0 < 0) then jump to <address>. Else, skip.


texts:
All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science.

You are involved in the creation of a new Museum of Computing, chartered to educate, entertain, and inspire the general public in a wide variety of computing/computer science/communication/mathematics topics.  Though history and celebrity can be part of the exhibits, this is not a history museum.  Instead, visitors learn about timeless concepts that enable computing, from the hardware layer on up.  Budget is not specified but ideas should be durable and practical for high volumes of visitors in permanent installations, with minimal staffing/disposable materials similar to the world's best science centers.

What exhibits would you include?


texts: Languages and their operations: determining equivalence

texts:
I'm currently taking a subject on theoretical computer science. This is not a homework question.

I'm having trouble figuring out to show the equivalence or disprove the equivalence. Consider any two languages $A$ and $B$. Is the following statement true or false?

$A^* \cup B^* = (A \cup B)^*$

Honestly, I use the above example mainly to ensure my question is less subjective. However I'm more concerned about the generalised approach to determining whether languages are equivalent (or subsets of each other and such) when operated on by various operators (kleene star, union, intersection, difference, concatenation). If I know that they are not equivalent I can basically just start bruteforcing for counter-examples, however I can't really think of any structured and consistent approach to answering questions such as the above.

Thanks.


texts: Low barrier to entry Computational Complexity problems

texts:
I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to focus on such topics to get momentum in thinking about Computational Complexity research problems. Are there exercises in particular texts that are good warm up or moderately hard problems in those topics to get started?

I have studied most topics in CS, the basics of applied math/calculus, introductory combinatorics, and introductory information theory. I have not studied linear algebra, abstract algebra, probability. I am happy to learn more about each topic gradually, but I am looking for some initial area in complexity that requires few of those topics, to get a foothold in understanding some topic deeply.


texts: Complexity of a variant of the Mandelbrot set decision problem?

texts:
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$  where $c$ is a complex number

Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded and some number $P^n_c (0)$ has a complex magnitude greater than 2 (but less than $m$) for some integer $n$ > $k$}

Assume $k$ and $m$ are integers given in unary encoding

  Is there an efficient algorithm in the real computing model (i.e the Blum-Shub-Smale model) for deciding set $M$ ?

Essentially, I'm asking if there exists efficient algorithm that decides whether the sequence is UNBOUNDED such that breakaway occurs at a number of iterations more than K.

UPDATE: The problem is in $NP$ since there is a polynomially verifiable certificate of membership.

  So, Is there an efficient algorithm or is it $NP$-hard to decide set $M$?

The problem went through major changes for these reasons:

1-For the problem to be interesting, "<" was changed to ">" in the definition.

2-I wanted the problem to be in $NP$, so I introduced parameter $m$.

Also, the bounty may be awarded to the first person who poses an $NP$-complete problem related to Mandelbrot Set


texts:
I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am just ignorant of, in which case I apologise, and would be grateful to be set right.

The property is as follows:

Take a graph $G=(V,E)$ on $n$ vertices, where $V$ is the vertex set and $E$ is the edge set. Let me define two families of subsets of vertices, $A_i$ and $B_i$, with the relationship that $B = V \setminus A$. I require that $A_0 = V$ and $A_n$ is the empty set. Each intermediate $A_i$ is obtained from $A_{I-1}$ by removing one vertex (according to some strategy). The property I care about is $\max_i |\{(a,b): a\in A_i, b\in B_i,(a,b) \in E\}|$, minimised over all strategies for choosing $A_1 \ldots A_{n-1}$ according to the rules above.

$A_i$ and $B_i$ can be thought of as the $i$th step in a process of moving vertices of the graph from one side of a partition (the $A$ side) to the other (the $B$ side). Thus the property I am concerned with has an operational interpretation as the maximum number of edges that need to cross the partition at any one point in time as we move the graph from one side to another, minimised over all strategies for moving vertices across the partition.

Aside from computing the value of this property, an algorithm for determining the optimal strategy would also be helpful.


texts: Finite state transducer with infinitary outputs or without emphasis on acceptance?

texts:
1)  Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols?  In other words, one where the transduction relation is a subset of $\Sigma^* \times \Gamma^\omega$ (as opposed to $\Sigma^* \times \Gamma^*$)?

For example, the definition of an FST given on Wikipedia involves a transition relation $\delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{\epsilon\}) \times Q$, which might first seem to permit infinite streams of output.  However, the transduction relation is defined inductively (basically, the reflexive-transitive closure of $\delta$), thereby ruling out infinitary outputs.

2)  Relatedly, the definitions of FSTs that I've seen include a subset $F \subseteq Q$ of accepting states.  Is there a name for the class of (deterministic) FSTs in which $F = Q$, i.e., in which all input strings are accepted and the emphasis is placed on the output?

Any references that you can point me to would be greatly appreciated!


texts: Implications of Riemann Hypothesis variants in TCS

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

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

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

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


texts:
I know the definition of the independent set problem in graph theory.  An independent set cannot contain any two adjacent vertices.

How about if you allow no more than $k$ pairs of adjacent vertices?  Does this more general problem have a name?  Are there techniques for solving it?  In particular, are there any techniques for solving it with linear programming?


texts: What is known about solutions to sparse integer linear programming problems?

texts:
If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what is known about the solution space?  I am less concerned with an efficient solution (although please indicate if one is known) than with knowing how small the minimum of the objective function can be, as a function of the number of variables and number of constraints, and the number of variables per constraint.

More concretely, the program is something like

minimize t
  subject to
for all i, x_i is a positive integer
x1 + x2 + x3 - t < 0
x1 + x4 + x5 - t < 0
...
x3 + x6 - t     ≥ 0
x1 + x2 + x7 - t ≥ 0
...

If a concrete question is needed, then is it the case that the minimum solution obeys t <= O(max{# of variables, # of constraints}), with the constant in the O() depending on the sparseness?  But even if the answer is no, I am more interested in knowing what kind of textbook or paper to study for a discussion of such issues, and if there is an area of study devoted to this kind of thing but I just don't know the terms to search for.  Thank you.

Update: With further reflection (and thinking through the rather simple reduction of 3SAT to ILP, which uses constraints with three variables), I realize that the issue of coefficients is critical (if there is going to be an efficient algorithm).  More precisely, all x_i variables have 0 or 1 coefficients (with at most three 1 coefficients in any one constraint), and all t variables have -1 coefficients, and all comparisons have variables on the left and 0 on the right.  I updated the above example to clarify.


texts: Is there a planar 4-regular graph that is 3-acyclic colourable?

texts:
A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).

Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me that no planar 4-regular graph is 3-acyclic colourable (might be even true for 4-regular graphs in general).

Am I wrong?
Is this already studied? (I admit I couldn't find any).


texts:
$\text{Mod}_k\text{P}$ is the class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."

For constant $k$, one can find the number of accepting paths of an NP machine mod $k$ by querying a $\text{Mod}_k\text{P}$ oracle with $0$,$1$,$2$,$\ldots$,$k-1$ accepting paths added to the original NP machine. Are there more interesting functions one can compute with oracle access to a $\text{Mod}_k\text{P}$-complete problem?  For instance, does $\text{P}^{\text{Mod}_k\text{P}} =\text{P}^{\#\text{P}}$? It is clear that $\text{P}^{\text{Mod}_k\text{P}} \subseteq \text{P}^{\#\text{P}}$.

For $k=2$, we have that $\text{Mod}_k\text{P} = \oplus \text{P}$, and certain hard problems (like computing the permanent) become easy mod 2.  Therefore, we might expect the power of $\text{P}^{\text{Mod}_k\text{P}}$ to depend on $k$.


texts:
Here is a problem I've never seen, in a model similar to the PAC model. It asks a similar question to PAC learning, but wishes to optimize, rather than learn. I wonder if this problem is known, has any name, or has ever been solved.

Input: A Random Oracle to function $f:[0,1]^n \rightarrow [0,1]$ from a concept class $C$. Additionally, $n$ points $x_1,\ldots,x_n$ in the domain.

Goal: Select an $i$ such that $E[f(x_i)]$ is as large as possible. We assume the function $f$ is randomly distributed amongst all functions in the class $C$ that agree with all the samples we have drawn.

One way to solve this problem is to draw many samples from $f$, create a hypothesis $h$, and choose the $x_i$ whose $h(x_i)$ is largest. There are two problems with this:

$h$ might not be representative of the set of all $f$'s that agree with the samples we've drawn.
To solve our problem it is not clearly necessary to learn $f$: for some classes $C$ might be a more efficient way to select a good $i$ without trying to learn $f$.

An example setting is where $C$ is the set of linear classifiers. In that case it should probably be quite easy to solve the problem. But what about other, more complicated classes?

The real version I'm interested in is that of agnostic learning of linear functions? we assume the function $f$ is somewhat correlated with a linear function, and the goal is to choose an i which maximizes $E[f(x_i)]$ to the best of our ability.


texts: Are there non-constructive proofs of existence of "small" Turing machines / NFAs?

texts:
After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines without actually building it.
Formally:
suppose we are given some language $L\subseteq \Sigma^*$ and fix some computation model (NFAs / turing machine/ etc.).
Are there any non-constructive existence results showing a $n$-state machine for $L$ exists, but without the ability of finding (in $poly(n,|\Sigma|)$ time) it?
For example, is there any regular language $L$ for which we can show $nsc(L)\leq n$ but we don't know how to build a $n$-state automaton for?
($nsc(L)$ is the non-deterministic state complexity of $L$, i.e. the number of states in the minimal NFA that accepts $L$).

EDIT: after some discussion with Marzio (thanks !) I think I can better formulate the question as follows:

Is there a language $L$ and a computation model for which the following holds:

We know how to build a machine that compute $L$ that has $m$ states.

We have a proof that $n$-states machine for $L$  exists (where $n << m$), but either we can't find it at all or it'd take exponential time to compute it.


texts: What is a substantial contribution to software design, with respect to authorship?

texts:
Background

I am a biologist. I wrote and am about to submit a manuscript that describes a statistical analysis of computer model; it is a statistical methods and modeling paper.

After my manuscript was written, a collaborator with a background in CS started to develop the code for their own project. In the process, they substantially improved the code, making it more logical, more readable, more adaptable. However, it still reproduces my original analysis unchanged and the manuscript itself has not changed.

The collaborator has not asked for, and I have not offered, authorship, but another co-author asked me to consider it.

I am uncertain about whether his contributions merit authorship, and my primary concern is that authorship reflects intellectual contribution.  On the one hand, the manuscript itself has not changed. On the other, the software that was described by and will be released with the paper has changed.

I would like to collaborate with this and other computer scientists more in the future, but I would like to better appreciate what constitutes an intellectual contribution.

Question

Both with respect to this case, and more generally, how can I determine when a collaborator's contribution meet both of the two following criteria of authorship (from the Committee on publication ethics):

substantial contribution to conception and design, or acquisition of data, or analysis and interpretation of data;
drafting the article or revising it critically for important intellectual content;

?

update: it is clear from further consideration and the answers in below that the contribution justifies authorship, so I will offer it.


texts: The Goemans-Williamson algorithm in the $SOS$ framework

texts:
If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, where $L = I - A/d$, equals $4E(S,\bar{S})/d$. So trying to maximize $\langle x,Lx \rangle$ over $x \in \{1,-1\}^{|V|}$ maximizes the number of edges crossing across the cut, $(S,\bar{S})$.

With this set-up the Goemans–Williamson algorithm is stated in the sum-of-squares (SOS) literature as the claim that there exists a polynomial-time algorithm such that one can output a vector $z \in \{ \pm 1 \}^{\vert V \vert }$ such that $\langle z,Lz \rangle \geq 2n(1-f_{GW}(\epsilon))$ where $f_{GW}(\epsilon) \leq 10\sqrt{\epsilon}$ provided one is given a degree-2 pseudo-distribution such that $\tilde {\mathbb{E}} [x_i ^2] =1, \tilde {\mathbb{E}} [\langle x, Lx \rangle ] \geq 2n(1-\epsilon)$

So naturally the question arises as to from where does one get such a degree-2 pseudo-distribution? The implicit claim seems to be that there exists a "degree-2 SOS algorithm" which when run on these constraints $\{ x_i^2 =1, \langle x, Lx\rangle = 2n(1-\epsilon)\}$ will generate this "degree-2 pseudo-distribution". This apparently seems to be set up to be a semidefinite programming (SDP) question and hence one basically has to solve a SDP to get this pseudo-distribution!

So what is the advantage of the SOS point of view here if one has to anyway run a SDP to get this degree-2 pseudo distribution?
Also can someone point out an explicit reference about what exactly is this "degree-2 SOS algorithm" which will run on these constraints to give me the "degree-2 pseudo-distribution"?


texts: Chernoff-type Inequality for pair-wise independent random variables

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


texts: Complexity of computing invertible functions with reversible circuits

texts:
Consider an invertible function that maps an $N$ bit string $x$ to an $N$ bit string $f(x)$. Let us use $F(x)$ to denote the inverse of the function $f(x)$, such that $F(f(x)) = x$.

Suppose that I know a circuit with ${\rm poly} \, N$ reversible Boolean logic gates that can compute this function. However, it also produces an additional output string $g(x)$ (with may be a copy of the input, for example).

Given this scenario, I have two questions that I believe to be equivalent.

Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit that only outputs $f(x)$?
Does the existence of an efficient reversible circuit to output $f(x)$ that also outputs $g(x)$ imply the existence of an efficient reversible circuit to output $F(x)$ (and may or may not also output some $G(x)$)?


texts: Delaunay triangulation when some triangles have been pre-specified?

texts:
I have an implementation of the Bowyer-Watson algorithm for Delaunay triangulation which works well -- given a set of 2D points, it computes a set of triangles to fill the areas between the points.

Recently I was requested to fulfill a new requirement -- the ability for the user to explicitly specify one or more triangles in advance, and have the result of the algorithm include those triangles (as well as "filling out" the rest of the graph around those triangles, as usual).

AFAICT the Bowyer-Watson algorithm doesn't lend itself to handling this well -- is there some trick by which I could make it work?  Or if not, is there some other triangulation algorithm or approach that would be appropriate here?


texts: Evidence that there is some problem in BQP distinct from BPP?

texts: Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be any classical collapse results if these problems are in BPP. Is there reason to think BQP is certainly a class different from BPP?


texts: Combining Cost Calculations (TSP, VRP style problems)

texts:
I'm currently writing a few varieties of nearest neighbour style solvers for the following:

TSP (Travelling Salesmen Problem)
VRP  (Vehicle Routing Problem)
VRPTW (Vehicle Routing Problem with Time Windows).

What I'm trying to do is to tweak my 'Cost' calculations used in determining the closest neighbour. I don't really have any documents on these, (and my understanding of mathematical notation isn't that great) so I'm hoping someone might be able to help.

I've currently got:

TSP Cost = Distance between Node1 & Node2.
VRP Cost = Distance between Node1 & Node2.

VRPTW Cost = {
var x = Node2.StartOfTimeWindow - CurrentTime
var y = Time between Node1 & Node2;
var z = Math.Max(x,y);
cost = z * (Node2.EndTime - CurrentTime); }

I'd like to introduce:

VRP : Taking the Node2.Quantity into account, based upon the Quantity left in the current Vehicle.

VRPTW: Include VRP quantity check and additionally take into account a set of skills. For example if a Node requires 'Plumbing & Electrical', then it should have a lower cost to visit than a Node requiring no skills (e.g. visit a node with more difficult criteria first).

I'm not quite sure how to introduce these though. For the quantity check for example, should I simply do (cost - Node2.Quantity/Vehicle.Quantity). or would it be better to multiply (cost * Vehicle.Quantity/Node2.Quantity)? Or is there a better way to achieve this?

Any help is much appreciated.


texts: BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

texts:
I read the paper

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

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

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

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

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

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

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


texts: Goldberg&Tarjan: How to find a blocking flow in a graph

texts:
I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking flow or a flow of value Delta." They all refer to Goldberg & Tarjan for finding a blocking flow. There are two things I don't understand:

How am I supposed to find a flow of value Delta?
But more important: how can I find a blocking flow?

Regarding questions 2: I read the two papers (the one by Goldberg & Tarjan "A New Approach to the Maximum-Flow Problem" and the one about dynamic trees - both were not that hard to understand). Every paper/report/book about Goldberg & Rao refers to the paper by Goldberg & Tarjan and highlight that Goldberg & Rao do not use the push/relabel algorithm but find blocking flows. But in my opinion, Tarjan only explains the push/relabel algorithm, I cannot find anything about blocking flows.

T. Cormen, "Introduction to algorithms", 3rd edition
The asymptotically fastest algorithm to date for the maximum-flow problem, by Goldberg and Rao, runs in time $O(min(V^{2/3}, E^{1/2}) E \lg{(V^2/E + 2)} * \lg{C})$, where $C = \max c(u,v)$. This algorithm does not use the push-relabel method but instead is based on finding blocking flows.
A. Goldberg & S. Rao, "Beyond the Flow Decomposition Barrier" (the original paper)
Using the blocking flow algorithm of Goldberg and Tarjan [1988], we get an $O (\Lambda m log(n^2/m)\log{U})$ bound.


texts: Finding the shortest distance in a dynamic graph

texts:
I have a non-weighted directed graph G with edges E and vertices G. Edges can be added or removed, and therefore vertices can be added.

For instance, if I have a graph with 4 nodes: 0, 1, 2, 3 and if I add the edge 3 -> 4, it means the node 4 will be added. Nodes cannot be removed.

I am studying the problem of determining the shortest distance (just distance, not path) in this dynamic graph. I am very newbie in this problem, but as I know it would be still an open problem.

What is the fastest algorithm for this problem so far?

Thank you very much


texts: Software package for decomposing quantum circuits

texts: Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?


texts:
An addition chain for $n \in \mathbb{N}$ is a sequence of natural numbers
$$1 = a_0,\ldots,a_l =n$$
such that each $a_t$ is the sum of two previous elements in the sequence. The length of minimal addition chains for natural numbers has been studied intensely.

I wonder if "graph addition chains" have been studied, most probably under different names. For a graph $G$, a graph addition chain could be a sequence of graphs
$$G_0,\ldots,G_l =G$$
such that $G_0$ is contained in some set $\mathcal{F}$ of elementary graphs, and each $G_t$ is some sum of two previous elements. Depending on $\mathcal{F}$ and the sum operation, one could ask about the length of minimal graph addition chains (if they exist).

As an example, set $\mathcal{F} = \{K_{k+1}\}$ and let the sum operation be the $k$-sum of graphs. Graph addition chains with these parameters produce partial $k$-trees, and we ask to construct partial $k$-trees using the minimal number of $k$-sums. For $k=1$, graph addition chains for path graphs correspond to addition chains for natural numbers, making this problem already $NP$-hard.

I would be thankful for any references to algorithmic and structural results about this or related concepts.


texts:
We all know that element distinctness in the comparison based model cannot be done in $o(n\log n)$ time. However, on a word-RAM, one can possibly achieve better.

Of course, if one assumes the existence of a perfect hash function that can be computed in linear time, we get a linear time algorithm for element distinctness: just keep hashing the numbers one by one and return 1 if there is a collision.

However, there are two issues: 1) most constructions of perfect hash functions that I could find used randomness and 2) I cannot find a discussion of the pre-processing time anywhere, i.e., the time required to decide what hash function one is going to use based on the input set of numbers.

Fredman et al.'s "Storing a sparse table with $O(1)$ worst case access time" does resolve the first issue by providing a hash function with $O(1)$ access time in the worst case, but says nothing about the second issue.

So to sum up, here's what I want:

Design an algorithm that given a set $S$ of $n$ numbers (each number being $w$ bits long) on a word-RAM with word length $w$, finds a hash function $h:S\rightarrow \{1, \ldots , m\}$ in $O(n)$ time, where $m = O(n)$. The function $h$ should have the property that for any $j \in \{1, \ldots , m\}$, the number of elements of $S$ that map to $j$ is a constant and computing $h(i)$ should take $O(1)$ time in a "reasonable" word-RAM model, i.e., the model should not allow "exotic" functions on words to be evaluated in $O(1)$ time.

I will also like to know if there are algorithms to solve element distinctness on the word-RAM that do not use hash functions at all.


texts: Inference in typed lambda calculus theories

texts:
I'd like to do automated inference, say solving word problems or reducing to normal form, in an equational theory of the typed lambda calculus (with product and unit types). Equivalently, in category-theoretic language: I'd like to do inference in a cartesian closed category presented by a finite set of generators and relations. I would be interested in any references on this topic.

I understand that inference in this setting is generally undecidable. However, I wonder whether there is any literature that either gives useful conditions under which exact inference is possible or proposes heuristic algorithms for approximate inference.


texts:
Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are actually true solutions. Question: Is $A'$ PP-complete?

This works if $A$ is #Sat, since MajSat is PP-complete. My approach so far: If $A$ is #P-complete, then there is a reduction from #Sat. So it should be possible to adapt this reduction to obtain a reduction from MajSat to $A'$. However, I ran into the problem that the reduction from #Sat to $A$ often requires a Turing (or Cook) reduction and it seemed far from clear how to obtain a many-one reduction from it.


texts:
$k$-Vertex Cover:

Given a graph $G = (V, E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$,
the $k$-Vertex Cover problem determines if there exists a subset of vertices $V'$ of $V$ of size at most $k$, such
that every edge of $E$ has at least one vertex in $V'$.

Can we solve $k$-Vertex Cover problem in $f(k)+c\log|V|$ space where $c>0$ is some constant?

yes. (proof given in link page number 126 and Theorem 2.3).
Can you give Simple proof?

Can we get all mimimum vertex covers of size $k$ from this proof with in
 $f(k)+c\log|V|$ space?

There is an other method (bounded search tree method proof given in [link] (http://www.mrfellows.net/papers/CCDF97_AdviceClasses.pdf) page number 127 proof(2)) to show that k-Vertex Cover problem is in parameterized Log space.

Other method goes as follows:
There are 2^k possible vertex covers. Think $P$ is at most $k$ length 0's and 1's bit string. For each value of $P$, we can generate the vertex set of size at most $k$ and it may become potential vertex  cover.  Clearly we can say $P$ is the path in bounded search tree.
For generating for all $P$'s need 2^k space.
Now we need to find vertex cover for given $P$ and $P$ is at most $k$ length 0's and 1's bit string.

Function $F(P,1)$ returns us first vertex by choosing the lex least edge and then the lex least vertex and this function will take constant space.

Function $F(P,2)$ returns us vertex of lex least edge not connected to the first one ($F(P,1)$).

$F(P,2)$ needs output of $F(P,1)$ and enumerate edges to find the lex least edge not connected to the first one.
$F(P,2)$  needs one logspace

Function $F(P,3)$ returns us vertex of lex least edge not connected to $F(P,1)$ and $F(P,2)$.
But we are not store the output of $F(P,1)$ and $F(P,2)$.
We need to enumerate the edges and find the  lex least edge not connected to  $F(P,1)$ and $F(P,2)$.
For this for each edge, we call $F(P,1)$ and $F(P,2)$ sequentially and check whether edge connected to $F(P,1)$ and $F(P,2)$.
For each edge we need one logspace and $F(P,2)$ one logspace
$F(P,3)$ needs two logspace

Similarly $F(P,i)$ returns us vertex least edge not connected to $F(P,1) \cdots F(P,i-1)$.
we are not store the outputs of $F(P,1) \cdots F(P,i-1)$. We need to call sequentially.
We need to enumerate the edges and find the  lex least edge not connected to  $F(P,1) \cdots F(P,i-1)$.
For this for each edge, we call $F(P,1) \cdots F(P,i-1)$ sequentially and check whether edge connected to $F(P,1) \cdots F(P,2)$.
So $F(P,i)$ needs (i-1)  logspace

Clearly $F(P,k)$  needs k.logspace. But algorithms should takes only $f(k)+c\log n$ space?.

Am I missing something?. Please help out this process where it went wrong?


texts: What's the difference between reduction strategies and evaluation strategies?

texts:
From the evaluation strategy article on Wikipedia:

  The notion of reduction strategy in lambda calculus is similar but distinct.

From the reduction strategy article on Wikipedia:

  It is similar to but subtly different from the notion of evaluation strategy in computer science.

What is the subtle distinction between evaluation strategies and reduction strategies that these two articles hint at? Are they just two similar concepts from different domains?


texts: Explicit type system with infinite non-cumulative universe hierarchy

texts:
Is there an open-source proof assistant or at least an explicit set of rules written down somewhere for a type system with an infinite non-cumulative universe hierarchy and unique typing?
I want to see the rules for the universe lifting function spelled out.


texts: Minimum chordless odd-cycle graph completion: is it NP-hard?

texts:
The following interesting problem came up in my research recently:

INSTANCE: Graph $G(V, E)$.

SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that the completed graph $G'(V, E')$ has the property that every edge in $G'$ is contained in a chordless odd cycle.

MEASURE: The size of the completion, i.e., $|E' - E|$.

So far, we were able to prove that a modified version of this problem is NP-complete, where instead of requiring that "every edge in $G'$ is contained in a chordless odd cycle" we require the stronger property that "every edge is contained in a triangle (cycle of length 3)". (Note that this is not equivalent with the MINIMUM CHORDAL GRAPH COMPLETION problem.)

The former is easily seen to be a generalization of the latter, but this far all my efforts to prove it failed. Could anyone come up with a pointer/reference/etc.?


texts: When can partial spectral sparsifiers be combined?

texts:
A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining them at the end.  To give two examples:

The original paper by Spielman and Teng works roughly by partitioning the graph into parts of good expansion and $\le |E|/2$ edges going between the parts, then building a sparsifier of each part, and then recursing on the "remainder" graph to depth $\log n$ to get the rest.  Implicitly, one then combines these partial solutions at the end for a full solution.
This paper by Jambulapati and Sidford builds spectral sketches, which are data structures (not subgraphs) that can approximate Laplacian quadratic forms $x^T L x$ with probability $\ge 2/3$ for any given $x$.  As they mention, one can easily amplify this probability to $p$ by computing $\log (1/p)$ sketches and taking their median.  This critically uses that they sketch with data structures, not graphs, and it raises the question of whether a similar probability amplification is possible for subgraphs with this property.

Formalizing the question, let $G = (V, E, w)$ be a graph and let $H_1, H_2$ be reweighted subgraphs such that, for some $X_1, X_2 \subseteq \mathbb{R}^n$ we have
$$x^T L_{H_i} x \in (1 \pm \varepsilon) x^T L_G x \qquad \text{for all } x \in X_i.$$

  I imagine that this does not imply generally that one can reweight $H_1 \cup H_2$ so that the above equation holds for all $x \in X_1 \cup X_2$.
  Is this accurate, and is there a nice example that demonstrates this?
  Are there natural additional assumptions we can make about $G, H_1, H_2$ so that this combination of $H_1, H_2$ does work in general, e.g. to enable recursive computation techniques like in the first paper?


texts: Perfect fractional matching of uniform hyper graph

texts: Are there necessary and sufficient conditions for a uniform hyper graph to have a perfect fractional matching ?


texts: Generating random graphs using the preferential attachment model with degree bounds

texts:
I am interested to know the structure of random graphs generated by the preferential attachment model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its degree, the edge is added if and only if the degree of the vertex does not exceed some upper bound.

What will be the vertex degree distribution of such a graph? What will be the size of the largest (giant) component, diameter and the average path length? Any reference will be highly appreciated.


texts: One-way functions with respect to various resource bounds

texts:
Informally, one-way functions are defined with respect to PTIME algorithms. They are computable in polynomial time but not invertible in average-case polynomial time. The existence of such functions is an important open problem in theoretical computer science.

I'm interested in one-way functions (not necessarily for cryptographic applications) defined with respect to different resource bounds. Such resource bounds could be LOGSPACE or bounded nondeterminism.

  Is there a candidate (natural) problem which is one-way with respect to LOGSPACE algorithms? Is there a candidate (natural) problem which is one-way with respect to nondeterministic linear time algorithms ($\text{NTIME(n)}$)?

I'm fine with worst-case hardness of invertiblity with respect to the above resource bounds.


texts: On analogies between parallel complexity and polynomial time hierarchy structure?

texts:
Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$?

Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), potential analogies such as (perfect matching in BPNC as to something else in BPP etc) between $\mathsf{NC}$ hierarchy and $\mathsf{PH}$ hierarchy?


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

  Has anyone attempted to provide a CSG for SAT?

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

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

Clarification:

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

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

Perhaps a better, more precise, question is whether:

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

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

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


texts: Lee's algorithm for synthesis of ranking functions in size-change termination proofs

texts:
Consider the following statement that appeared in Lee's Ranking functions for size-change termination (SCT).

  Let $G$ satisfy the SCT condition.

  There is an effective procedure to construct a $G$-ranking function
  expressed using only min, max and lexicographic tuples of program
  parameters and constants.

I'm interested mostly in the computational side of it. Has this been implemented before? If so, in which systems?

In fact, Lee's preliminary algorithm was made more practical by subsequent revisions in joint work with Ben-Amram and Codish. There remains the question of whether their claimed complexity is aceptable in current verifiers and whether it has already been tested in practice.


texts: What is the difference between an Ontology and Knowledge Representation (KR)?

texts:
From my understanding an Ontology is a description of how a real object can be understood or represented (such as a chair being a collection of atoms, a piece of furniture part of a larger collection of other furniture belonging in a room or perhaps a description of how the components of a chair are related to each other).

On the other hand I think KR is the digital representation of an Ontology (such as a struct, class, graph, tree or other model).

I am quite certain that I am wrong and I am finding it hard to answer this question on my own.

Could someone clarify the difference for me? Thank you.


texts:
It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, e.g., analysis of the popular AdaGrad algorithm and its many relatives.

In the case of a linear program with feasible region $R = \{ x \mid Ax \leq b \}$, we can simply bound the extreme points of $R$ in terms of the coefficients of $A$ and $b$ (see e.g. Thm. 10.6 here). According to pg. 48 #3 of this paper, similar bounds do not exist for semidefinite programs.

I'd like to know if there is any way to find such a bound for a generic SDP that is less expensive than solving it directly. If not, are there any large classes of SDPs for which this is possible? (e.g. it's easy to find bounds for the standard MAX-CUT relaxation or, more generically, SDPs with feasible regions of the form $\{ X \mid {\rm diag}(X) = b, X \geq 0\}$, by looking at the spectrum of the coefficient matrix)


texts: Formal representation of algorithm using recursive algebraic data types

texts:
I have an algorithm written in Haskell which I am describing in my thesis. In the code for the algorithm I have a recursive data type similar to this:

  data Data = A Int | B Data | C Data

Now I am thinking about how to explain this in a formal way, in a way that feels natural and clear. Note that B and C contain the same data.

The only reasonable alternative I have come up with is to use some kind of tagged union, like this:

Let $Data$ be a recursively defined set given by:

Let $i$ be an integer. Then $\langle \mathcal{A}, i \rangle \in Data$.
Let $d \in Data$. Then $\langle \mathcal{B}, d \rangle \in Data$.
Let $d \in Data$. Then $\langle \mathcal{C}, d \rangle \in Data$.

With this definition I write functions over $Data$ like this:

$$
func(\langle \mathcal{A}, i \rangle) = \cdots \\
func(\langle \mathcal{B}, d \rangle) = \cdots \\
func(\langle \mathcal{C}, d \rangle) = \cdots \\
$$

And predicated about is like this:
$$
Pred(\langle \mathcal{A}, i \rangle) \text{ holds if ... } \\
Pred(\langle \mathcal{B}, d \rangle) \text{ holds if ... } \\
Pred(\langle \mathcal{C}, d \rangle) \text{ holds if ... } \\
$$

This representation is very close to the Haskell source code, which is good, but it feels rather unnatural to mathematicians.

Is there a more elegant and natural way to do this?

EDIT:
Thanks for the replays, sorry if I am being unclear.

I am writing a master's thesis in CS about alias analysis. The text should be comprehensible for students on master level in CS with a background in algorithms (does master level mean the same in the USA? In EU you get this degree after 5 years of study including an 1 term thesis project).

I have used this paper as a starting point, implemented that algorithm in Haskell and made some extensions. Now I want to describe my extension in a way that is similar to the paper in formulation and level of formalism. However I use a recursive algebraic data type in my extension and I'm not sure about the most natural and clear way to represent it.

EDIT: The example $Data$ above is intended to have finite values only.

EDIT:
I see that my question is very similar to this: Formal Representation of Haskell Data-Types

Except that I'm also interested in how to represent recursive data types.

EDIT: Summary of the alternative suggestions I have received

Tagged tuples (my example above and  Andrej Bauer's alternative)
Function applications (Shahab's first alternative)
$$
  data(a(d)) = \dots
$$
Objects with special notation / operators (Shahab's second alternative)
$$
  \langle d \rangle = \dots
$$
Un-data-type-ization (yatima2975's alternative)

Transform into non-recursive form. Works only for data types with one recursive element.
"the Cartesian product of finite strings over {B,C} and the integers"

I think all of the have advantages and disadvantages.


texts:
Does anyone know if there is a centralized source of Canadian positions advertised by universities for computer science? I conjecture that this might exist since there are websites advertising math jobs for Canada, plus websites advertising CS jobs in general (CRA, Higher Ed). Additionally, there exists at least one such opening currently.

This is a special case of a previously studied problem, where it was asked on cstheory without the Canadian constraint.


texts: What is the power of general poly-size permutation branching programs?

texts:
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions functions are permutations (without any restriction on the width).  We know from Barrington's famous result and from the fact that arbitrary poly-size branching programs capture exactly logspace that
$$\mathsf{NC}^1\subseteq\mathsf{PPBP}\subseteq\mathsf{L}/\mathsf{poly}.$$
In the closing section of his 1989 paper, Barrington briefly considers this question and observes that $\mathsf{PPBP}$ is known to contain $\mathsf{L}$-complete problems under $\mathsf{NC}^1$ reductions. This suggests that the first inclusion above is strict but fails to yield a characterization of $\mathsf{PPBP}$ in terms of a well-known class, because it is not known whether $\mathsf{PPBP}$ is closed under $\mathsf{NC}^1$ reductions (right?).

Has any improvement on understanding the power of permutation branching programs been made since Barrington's work?

Edit: Just for completeness, this is Barrington on what I call here $\mathsf{PPBP}$ (second paragraph of Sect. 8 of his paper "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in $\mathsf{NC}^1$", Journal of Computer and System Sciences, 38(1):150-164, 1989):

The power of general poly-size permutation BPs (no restriction on width) was mentioned as an open problem in [Barrington's Ph.D. thesis].  Cook and McKenzie [a 1986 tech report] have just shown that [the word problem for permutation groups] is complete for log space under $\mathsf{NC}^1$ reductions [...]  A poly-size PBP can be constructed to solve this problem, given an appropriate definition of recognition of a language by a PBP.

The fact that he never explicitly says that poly-size permutation BP are equivalent to poly-size BP led me to assume that having an $\mathsf{L}$-complete problem in $\mathsf{PPBP}$ was not known to be enough to get $\mathsf{PPBP}=\mathsf{L}/\mathsf{poly}$ (e.g., lack of closure under reductions).


texts: Codes that are both locally testable and locally decodable

texts: Are there any known constructions of binary locally testable codes with very low (e.g., independent of the length of the codeword) query complexity and "good" rate (e.g., mapping strings of length $k$ to strings of length $k^{1+c}$, for a small constant $c$) that are also locally decodable (even if the query complexity for decoding is very large (but still sublinear))?


texts: Scaled down and scaled up versions of Impagliazzo-Wigderson Therem

texts:
A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP.

When can we change $P$ with some complexity class $C$ such that the same result works? In other words, for which complexity classes the following statement is true?

Statement: If some function in $E$ requires circuits of size $2^{\Omega(n)}$ then $C= BP-C$.

Here $BP-C$ is the bounded probabilistic version of $C$.

In particular does it work for formulas? I.e. for $C$ equal to logspace uniform $NC_1$ ? In this case the statement would be:

If some function in E requires formulas of size $2^{\Omega(n)}$ then $NC_1 = BP-NC_1$


texts: Type-theoretic interpretation of Skolemization

texts:
What is the type-theoretic interpretation / equivalent of Skolemization?

Skolemization converts some formula into Skolem normal form. The two formulae are equisatisfiable with each other.

Or, to say it in type-theoretic terms: There is a program having some type iff there is a program having this type in Skolem normal form.

How do these programs relate to each other?


texts: Church-style CoC with axiom for induction over Church-encoded unit, is it consistent?

texts:
If we start with the Calculus of Constructions, and then use the following definitions for the Church-encoded Unit:

UnitType = (t : *) -> t -> t
Unit = \(t : *) (x : t). x

And the add the following construct indUnit:

G |- P : UnitType -> *
G |- pu : P Unit
G |- u : UnitType
--------------
G |- indUnit P pu u : P u

With reduction rule:

indUnit P pu Unit ~> pu

Basically this adds induction over the Church-encoded unit type.

Is this consistent?
If we change the reduction rule to:

indUnit P pu x ~> x (P x) pu (if x is a closed term)

Is it still consistent?

It seems to me that this is consistent.


texts:
I came up with this problem while thinking about an optimizing compiler.

Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. There is an edge in $G_H$ whenever the hyperedges $e_1$ and $e_2$ have a vertex in $G$ in common.

I would like to know what I can say about the Cheeger constant of $G_H$.

In fact I have a family $H_n$, so this will go into whether there is a nonzero lower bound that works for all the $G_{H_n}$.


texts: Consequences and state-of-the-art of NP ≠ ZPP?

texts:
Consider the complexity classes $\mathsf{NP}$ and $\mathsf{ZPP}$. Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply $\mathsf{P} = \mathsf{NP}$. For example, there are many inapproximability results depending on $\mathsf{NP} \neq \mathsf{ZPP}$, but what evidence do we have for believing they would indeed be not equal?

In other words, what would be the consequences of $\mathsf{NP} = \mathsf{ZPP}$? Is it safe to claim that likewise for $\mathsf{P}$ and $\mathsf{NP}$, many theorists also believe $\mathsf{NP}$ is not equal to $\mathsf{ZPP}$?


texts: Programming language supporting infinitary rewriting of regular term graphs?

texts:
Do any practical programming languages support term graph rewriting of infinite but regular terms? For example the toy language CoCaml [1] supports computations on infinite regular streams. Coq supports coinduction [2] but not infinitary rewriting, as far as I can tell. By "infinite regular term graph", I mean those inhabitants of coalgebraic datatypes that can be defined in terms of finitely many equations.

[1] Jean-Baptiste Jeannin, Dexter Kozen, Alexandra Silva (2017)
CoCaml: Functional Programming with Regular Coinductive Types
[2] Yves Bertot, Ekaterina Komendantskaya (2008)
Inductive and Coinductive Components of Corecursive Functions in Coq


texts: Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is the VC-dimension of all such possible binary functions induced by some $k$ points and some labeling of these points?


texts: Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients

texts:
Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time $(d\log{n})^{O(1)}$ time using $2^{O(d)}n^{O(1)}$ or  even $2^{d^{O(1)}}n^{O(1)}$ number of processors?

Notice, that I am not interested in the sequential complexity of this problem which is well studied with polynomial in $n$ (and exponential in $d$) algorithms known.

Also, Lin-Kriz and Pan prove that the problem is $\mathsf{NC}$ equivalent to Euclidean GCD (and therefore not known or expected to be in $\mathsf{NC}$) but I think their reduction from EGCD to this problem uses large numbers while I stipulate that the coefficients are small integers.


texts: What's the meaning of the class indicator matrix when transforming the class label matrix into it in canonical correlation analysis?

texts:
When using canonical correlation analysis (CCA), we can integrate the dataset and label information via transforming the class label matrix Y into the class indicator matrix T. Such as: $T = (YY^T)^½Y$ in [this article on LS CCA][1].

While for the numeric dataset and the binary dataset, the binary dataset can be viewed as the class label matrix and transformed into the class indicator matrix. After that, should I use the CCA?

Though without this transformation, [the CCA can be used][2], I'd like to know how to explian this kind of transformation once using it on the binary dataset (not label matrix). Thank you.


texts: Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

texts:
I am interested in the following problem.

Node Multiway Cut on Planar Graphs with terminals on the outer face

Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which are all incident on the outer face of G.
Question: Is there a set of vertices $X \subseteq V(G)$ of size at most $k$ such that all vertices of $S \setminus X$ belong to different connected components of $G - X$?

Informally, the problem asks whether all terminals can be separated with k vertex deletions, knowing that all terminals lie on the outer face. If we replace vertex deletions by edge deletions, then this is known to be possible in polynomial time by considering multiway cuts in the planar dual, and relating them to certain kind of Steiner trees ( Efficient Algorithms for k-Terminal Cuts on
Planar Graphs, http://www.springerlink.com/content/2b0lxbc4ytqgxj0k/ ). Since the edge-deletion version reduces to the vertex-deletion version, the edge-deletion version seems easier; no reduction in the reverse direction is known.

The question is: is Node Multiway Cut on Planar Graphs with terminals on the outer face NP-complete? The reason I am interested in this problem is that it would provide me with a starting point for another complexity lower bound if this is indeed NP-complete.


texts: In Ulf Norell's thesis he mentions that Agda is based on Luo's UTT. However, I can't find a way to use Prop there. Is there any way to do so?


texts: Difference between syntax and semantic error in programming languages

texts:
When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, but type checking is considered as part of semantic analysis.

My intuition tells me that, by setting more constraints on the language syntax, some semantic errors can become syntax errors. And my question is if there are any intrinsic differences between syntax and semantics? Or are they just checking performed on different levels, for example syntax checking is a rather local checking while semantic checking is global? Is there anything fundamental that makes semantics checking different from syntax checking? Is it possible to embed all semantic checking within syntax? Are there any theories related to these questions?

It may also be the case that my intuition is wrong - if that's the case, please also explain to me why that is wrong.