What is the logarithm or root operation in type-space? I was recently reading The Two Dualities of Computation: Negative and Fractional Types.  The paper expands on sum-types and product-types, giving semantics to the types a - b and a/b.

Unlike addition and multiplication, there are not one but two inverses of
exponentiation, logarithms and rooting.  If function types (a → b) are
type-theoretic exponentiation, given the type a → b (or b^a) what does it mean to have
the type logb(c) or the type a√c?

Does it make sense to extend logarithms and roots to types at all?

If so, has there been any work in this area, and what are some good directions on how to comprehend the repercussions?

I tried looking up information on this via logic, hoping the Curry-Howard correspondence could help me, but to no avail.

A type $C$ has a logarithm to base $X$ of $P$ exactly when $C \cong P\to X$. That is, $C$ can be seen as a container of $X$ elements in positions given by $P$. Indeed, it's a matter of asking to what power $P$ we must raise $X$ to obtain $C$.

It makes sense to work with $\mathop{log}F$ where $F$ is a functor, whenever the logarithm exists, meaning $\mathop{log}\!_X(F\:X)$. Note that if $F\:X\cong \mathop{log}F\to X$, then we certainly have $F\:1\cong 1$, so the container tells us nothing interesting other than its elements: containers with a choice of shapes do not have logarithms.

Familiar laws of logarithms make sense when you think in terms of position sets

$$\begin{array}{rcl@{\qquad}l}
 \mathop{log} (\mathop{K}1) &=& 0   & \mbox{no positions in empty container}\\
 \mathop{log} I &=& 1 & \mbox{container for one, one position}\\
\mathop{log} (F\times G) &=& \mathop{log}F+\mathop{log}G &
  \mbox{pair of containers, choice of positions} \\
\mathop{log} (F\cdot G) &=& \mathop{log}F\times\mathop{log}G &
  \mbox{container of containers, pair of positions}
\end{array}$$

We also gain $\mathop{log}\!_X(\nu Y. T) = \mu Z. \mathop{log}\!_X T$ where $Z=\mathop{log}\!_XY$ under the binder. That is, the path to each element in some codata is defined inductively by iterating the logarithm. E.g.,

$$\mathop{log}\mathop{Stream} = \mathop{log}\!_X(\nu Y. X\times Y) = \mu Z. 1 + Z = \mathop{Nat}$$

Given that the derivative tells us the type in one-hole contexts and the logarithm tells us positions, we should expect a connection, and indeed

$$F\:1\cong 1 \;\Rightarrow\; \mathop{log}F\cong \partial F\:1$$

Where there is no choice of shape, a position is just the same as a one-hole context with the elements rubbed out. More generally, $\partial F\:1$ always represents the choice of an $F$ shape together with an element position within that shape.

I'm afraid I have less to say about roots, but one could start from a similar definition and follow one's nose. For more uses of logarithms of types, check Ralf Hinze's "Memo functions, polytypically!". Gotta run...


What is the largest gap between rank and approximate rank? We know that the log of the rank of a 0-1 matrix is the lower bound of deterministic communication complexity, and the log of the approximate rank is the lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So what about the gap between rank and approximate rank of a boolean matrix?

First I'll give some background and define approximate rank. A good reference is the recent survey by Lee and Schraibman Lower Bounds on Communication Complexity.

Definition: Let $A$ be a sign matrix. The approximate rank of $A$ with approximation factor $\alpha$, denoted $rank^\alpha(A)$, is
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j] \leq \alpha} rank(B)$.
When $\alpha\to \infty$, define
$rank^\alpha(A)=\min_{B:1\leq A[i,j]\cdot B[i,j]} rank(B)$.

A result by Krause says that $R_\epsilon^{pri}(A)\geq \log rank^\alpha(A)$ where $\alpha=1/(1-2\epsilon)$ and $R_\epsilon^{pri}$ is the bounded-error private-coin communication complexity of $A$ with error upper-bounded by $\epsilon$.
The above was for background. Now to answer the question, Paturi and Simon showed that $rank^\infty(A)$ completely characterizes the unbounded-error communication complexity of $A$. They also showed that this agrees with the minimum dimension of an arrangement realizing the boolean function whose communication matrix is $A$. The unbounded-error communication complexity of the equality function is $O(1)$. Keep that in mind.
The communication matrix for equality is just the identity, i.e., a boolean matrix with $2^n$ rows and $2^n$ columns with all ones in the diagonal. Let's denote this by $I_{2^n}$. Alon showed that $rank^2(I_{2^n})=\Omega(n)$ which is tight up to a logarithmic factor (with the theorem by Krause we obtain $R_\epsilon^{pri}(EQ)=\Omega(\log n)$).
The identity matrix has full rank, i.e., $2^n$. Thus, we have exponentially large separations for $\alpha=2$ and $\alpha\to\infty$.


Pseudo-Random Function families whose instances have full domain The GGM construction gives (PRF) pseudo-random function families
whose instance's input's are binary strings of a single length.

I've convinced myself that one could get a PRF family whose instances have domain of all finite binary strings by taking a PRF for inputs of length $n$ and an independent PRNG seed,
using the PRNG seed to take a value that is indistinguishable
from being a primes chosen uniformly from $\; [2^{n-1},2^n) \;$,
interpreting the input as a non-negative integer,
reducing that integer mod the value from the PRNG,
expressing the result as a binary string, and feeding that to the PRF instance.

(The PRF instance and PRNG seed could instead be the output of the PRNG on the key.)

However, looking at the construction, I see what would be much simpler and more efficient,
and I think it would still be secure, although I don't understand the
proof well enough to figure out if that can be suitably modified.

  Does the following give a pseudo-random function family from
  a pseudo-random generator that stretches by a factor of 3?

Let $G$ be the generator, and define $H_0,H_\#,H_1$ to return the first,middle,last $n$ bits of $G$'s output. $\;\;$ For all non-negative integers $n$ such that $\: n\lt \text{len}(x) \:$, $\:$ let $b_n$ be the $n$th bit of $x$. $\;\;$ $F_s(x)$ is then defined to equal $\; H_\#(H_{b_{\text{len}(x)-1}}(...(H_{b_2}(H_{b_1}(H_{b_0}(s)))))) \;$.

Here is a proof sketch of the security of your construction.

Let $G: \{0,1\}^k \to \{0,1\}^{3k}$ be the PRG and let $G_0, G_1, G_2$ denote the first, middle, and last third of the output of $G$.

Define the function $F_{x,m}$ as follows:

$\qquad
F_{x,m}(y) =
  \begin{cases}
    rand & \mbox{ if } y<x \mbox{ in lex order} \\
    G_m( rand ) & \mbox{ if } y=\epsilon \\
    G_m( F_{x,b}(y') ) & \mbox{ if } y=y'b \\
\end{cases}$

Here $rand$ denotes a value chosen at random for each $(y,m)$, independent of everything else.

Now $F_{\epsilon,2}$ is your GGM construction instantiated with a random seed. Suppose we picture the GGM construction as a labeling of the edges and vertices of a binary tree. Each vertex is associated with a finite binary string. Each vertex labels its two outgoing edges $G_0(\ell), G_1(\ell)$  and labels itself $G_2(\ell)$, where $\ell$ is the value assigned to its incoming edge. Then $F_{x,2}$ is the result of having vertices $y < x$ assign their relevant labels totally randomly.

Fix an adversary $A$ with running time $p(\cdot)$, to which we give oracle access to a function of this form. We'll consider the sequence of hybrids $F_{\epsilon,2}, F_{0,2}, F_{1,2}, F_{00,2}, \ldots, F_{\omega,2}$, where $|\omega| > p(k)$.  From $A$'s point of view, $F_{\omega,2}$ has output distributed identically to a totally random function.

If $x$ is the successor of $x'$ in lex order, then $F_{x,2}$ and $F_{x',2}$ differ only in one application of the PRG. Thus, successive hybrids are indistinguishable. However, we've proposed an exponential number of hybrids, so we are not yet done! Intuitively $A$ can only "notice" the changes in a polynomial-sized portion of the tree. We formalize this as follows:

Conditioned on the event that $A$ never queries its oracle on a string beginning with $x$, then $F_{x,2}$ and $F_{x',2}$ give identical output distribution. Let $q_x$ denote the probability that $A$ queries its oracle on such a string, and let $\delta(\cdot)$ denote the negligible security error of the PRG. Then we have:

$\qquad\Big|\Pr[A^{F_{x,2}}(1^k) = 1] - \Pr[A^{F_{x',2}}(1^k) = 1] \Big| \le q_x \delta(k)$

Then by a hybrid argument, we have:

$\qquad\Big|\Pr[A^{F_{\epsilon,2}}(1^k) = 1] - \Pr[A^{F_{\omega,2}}(1^k) = 1] \Big| \le \delta(k)\sum_x q_x$

The first expression involves $A$ with oracle access to the GGM function, and the second expression involves $A$ with oracle access to a random function. Now we bound the sum $\sum_x q_x \le p(k)^2$. Since $\delta(k) p(k)^2$ is negligible, the construction is a PRF.


Why does the transformation in the proof for SL=L preserve connectedness of s and t? I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$.
But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ consists of several applications of the zig-zag-product and powering.

They show in Lemma 3.2 that if $s$ and $t$ aren't connected in $G$, then all nodes induced by $s$ arent't connected to any node induced by $t$.
But they don't show that if $s$ and $t$ were connected in $G$ that $s'$ and $t'$, as defined in the proof of the theorems 4.1 and 4.2, are connected in $\tau(G,H)$ for some expander graph $H$.

One can easily find examples were the zig-zag-product or powering destroys connectivity of nodes. So why is here no argumentation needed on why $s'$ and $t'$ will be connected if $s$ and $t$ were? Am I missing something?

I assume that the proof itself is correct since the first versions of the paper were published more than ten years ago.

PS: I'm not 100% sure whether this is a research level question. But I think that it will be hard to get an answer in one of the other forums since it is kind of special question.

EDIT:

I think I found the trick. Proposition 2.2 states that if $\lambda < 1$ is achieved there is a path of some length for every pair of verticies $s$ and $t$. Thus by showing that the spectral expansion of the nodes induced by the connected component of s
is smaller than $1/2$ it is also shown, that the connection isn't lost (if there was one).

The proof of Theorem 4.1 states that:

  Let $S$ be the connected component of $G$, such that $s \in S$.
  By the arguments above, $S \times [N]$ is a connected component of $G_{\mathrm{reg}}$, and $G_{\mathrm{reg}}|_{S\times [N]}$ is non-bipartite. [...]

  By Lemma 3.2 and Lemma 3.3, we have that $\lambda(G_{\exp}|_{S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell}) \leq 1/2$. In particular, we have that $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$ is a connected component of $G_{\exp}$.

In particular, if $t \in S$ then both $s'$ and $t'$ belong to the connected component $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$.

Lemma 3.2 only works when $G$ is non-bipartite and $\lambda(H) \leq 1/2$. Perhaps one of these conditions wasn't satisfied in your examples?


Is End-of-Monotone-Line PPAD-complete? Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS).

Input (via polynomial circuit): Graph on vertex set $0$ to $2^n-1$ such that querying any vertex returns its neighbors (at most two), and $deg(0)=1$.

Output: Either a $v\ne 0$ for which $deg(v)=1$, OR {four vertices, $a<b<c<d$, such that $ac$ and $bd$ are edges OR $ad$ and $bc$ are edges} OR {three vertices, $a<b<c$, such that $ab$ and $ac$ are edges} OR {three vertices, $a<b<c$, such that $ac$ and $bc$ are edges}.
(So this practically says that the graph when drawn naturally behaves like a 'graph of a function', i.e., it intersects every vertical line at most once.)

How hard is this problem?

Your problem is equivalent to End-of-Metered-Line.

This can be shown by reducing your problem to End-of-Potential-Line (see https://arxiv.org/abs/1702.06017). This is a version of End-of-the-Line where the line is equipped with a potential function, and a solution is either the end of a line, or a vertex on the line at which the potential function decreases. This differs from EOML, since the potential is not required to increase by exactly one at each vertex.

We can reduce your problem to EOPL by taking the successor of each vertex to be the neighbor with the larger index, and the predecessor of each vertex to be the neighbor with the smaller index. Any vertex that has two neighbors with smaller indices is the end of a line, and any vertex that has two larger neighbors is also the end of a line. The potential function of a vertex is just its index, which is monotonically increasing along each line.

It was shown in https://arxiv.org/abs/1702.06017 that EOPL is equivalent to EOML, under polynomial-time reductions, and thus is in CLS.

For the other direction, EOML can be reduced to your problem by embedding the potential space into the vertex space using the higher-order bits. In other words, each vertex $v$ in the EOML instance is mapped to the integer $K \cdot p(v) + v$, where $p(v)$ is the potential of $v$, and $K$ is some constant that is larger than the total number of vertices in the EOML instance.

So to answer your question, the problem is unlikely to be PPAD-complete since that would imply PPAD $\subseteq$ CLS.


Unary languages recognized by two-way deterministic counter automata 2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace  0^{2^n} \mid n \geq 0 \rbrace.
\end{equation}

Is there any other nontrivial unary language recognized by 2dca's?

Remark that it is still unknown whether 2dca's can recognize $ \mathtt{SQUARE} = \lbrace  0^{n^2} \mid n \geq 0 \rbrace $?

DEFINITION: A 2dca is a two-way deterministic finite automaton with a counter. A 2dca can test whether the value of the counter is zero or not, and increment or decrement the value of the counter by 1 in each step.

This is only an idea that came to my mind while reading Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of
Turing Machines"; in particular the famous theorem Ia:

Theorem Ia: We can represent any partial recursive function $f(n)$
by a program operating on two integers $S_1$ and $S_2$
using instructions $I_j$ of the forms:
(i) ADD 1 to $S_j$, and go to $I_{j_1}$
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$
That is, we can construct such a program that starts with $S_1 = 2^n$ and $S_2 = 0$ and
eventually stops with $S_1 = 2^{f(n)}$ and $S_2 = 0$

If you have a two way DFA with one counter over a (semi)infinite tape where the input is given in unary: $\$1^{2^n}000...$ then the DFA can:

read the unary input (and store it in the counter);
work on the $0^\infty$ part of the tape and use the distance from the $1$s as the second counter.

so it can simulate a Turing complete two counters machine.

Now, if you have a recursive function $f(n)$ that runs in time $T(n)$ on a standard Turing machine, a two way DFA with one counter that starts on the finite tape $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:

read the unary input (and store it in the counter);
return to leftmost symbol;
divide the counter by 3 until the counter contains $2^n$ in this way: go right looping from states $q_{z_0}, q_{z_1}, q_{z_2}$ and subtracting 1; if counter reaches 0 in state $q_{z_0}$ go to leftmost symbol adding +1 and continue the division loop, otherwise add 1 (if in state $q_{z_1}$) or 2 (if in state $q_{z_2}$) and go to leftmost symbol adding +3 (i.e. recover the previous value of the counter not divisible by 3) and proceed with step 4.;
at this point the counter contains $2^n$;
calculate $2^{f(n)}$ using the $T'(n)$ space available on the right as the second counter (the value of the second counter is the distance from the leftmost symbol $\$$).

So with the special input encoding described above that gives it enough space on the finite tape, a two-way DFA with one counter and unary alphabet can compute every recursive function.

If the approach is correct, it would be interesting to reason about how to choose $T'(n) \gg T(n)$ or when it is enough to pick a large odd $k \gg 2$ and encode the input as $1^m$, $m = 2^n k^n$


Ranking the Difficulty of NP Hard Problems in Practice This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard problems, this is about ranking the difficulty of the same instances.

There is a lot of bibliography on the effect known as Phase Transition. In particular for the case of random 3-SAT formulae in Conjunctive Normal Form (CNF), it is known that there is a value R of the ratio of clauses to variables such that for all r < R the formula can be satisfied with high probability and for r > R the formula is unsatisfiable with high probability. The Phase Transition effect happens near R and it has the remarkable effect that solving the satisfiability problem for those formulas is extremely hard in practice.

Since for proving NP hardness of a given problem it is needed to show that there is a polynomial time Turing-reduction to it of an NP-complete problem and that problems that are NP-complete can be transformed in polynomial time among them, then the following question naturally arises:

Is it possible to rank the difficulty of NP hard problems in practice using the Phase Transition of 3-SAT CNF as an indicator? The intuition is that one problem P1 can be expected to be harder than P2 if its 3-SAT encoding is nearer R (which is known to be near 4.2). Note that this idea does not necessarily bound each particular instance to a particular difficulty, it just ranks them.

There are a number of counter arguments, among them:

The Phase Transition of 3-SAT CNF formula applies to random formulae. However, a particular instance in a different problem has some structure that might be exploited by solvers for that problem ---this was already pointed out by Peter Shor in the aforementioned question.
It might be the case that the particular encoding used for transforming the particular instances in our problem to 3-SAT plays a crucial role in the ratio of clauses to variables leading to misleading values, hence misclassifications ---this concern is raised by Kaveh in the comments to this question.
Serge (according to my understanding from his comment to this question) raises the issue that one might artificially complicate the original NP hard problem so that it results in a 3CNF formula that alters the ratio of clauses to variables while preserving the satisfiability.

As for 1, all problems might share the same class of regularity so that ranking problems (instead of characterizing the difficulty) might apply; as for 2, there are encodings in particular problems which are known to be non-redundant w.r.t the Unit Propagation rule so that those should be preferred and maybe they avoid those misclassifications. An example is Sideris et al., 2010 for the case of Propositional Planning. As for 3, Cheeseman et al., 1991 already considered the issue of whether mappings between problems preserve or not the phase transition effect and their preliminary experiments seem to support their conjecture, provided that one reduces the original NP problem and even that "can be further reduced by applying resolution to the clauses".

Do this all make sense to you? are you aware of any bibliographical references about this? Any guidance would be largely acknowledged!

While it's not inconceivable that the technical obstacles you mention could be overcome somehow, I think that there is very little motivation at present to do so, for the simple reason that (at least as far as I am aware) the difficulty of NP-hard problems in practice seems, empirically, to have little to do with their closeness to the 3-SAT phase transition.

Contrast this with some other ways to rank NP-hard problems in terms of difficulty: There is some empirical correlation between NP-hard problems that are easy in practice and NP-hard problems that are easy to approximate, or that are fixed-parameter tractable (in the sense of parameterized complexity).  Appropriate notions of reduction have been developed in these cases that partially explain the empirical observations.  However, there currently seems to be no empirical indication that most NP-hard problems that are difficult in practice are difficult because of their close relationship to 3-SAT instances near the phase transition.  So it does not make too much sense to develop a theory to "explain" something that does not appear to be true in practice.


Integer Factoring via Lattice Reduction? I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993.  It looks like a probabilistic method with expected polynomial run time (and space) is presented to do integer factorization.

From the paper: "A scenario for factoring $N \approx 2^{512} $ ... The corresponding lattice problem is unfeasible for the presently known lattice reduction algorithms.  We have no experience with lattice basis reduction for lattices with dimension 6300.  Moreover the bit length of the input vectors is at least 1500."

I take this to mean that the algorithm presented is polynomial but the exponent and factors are so large that it makes it computationally impractical for current technology.

Can anyone weigh in on this?  Is this paper legitimate?  Isn't this huge news if it is?  Doesn't this mean that integer factoring is likely in P?  Have people been progressing towards making lattice reduction algorithms more tractable?

I am not an expert in lattice problems, but I do know the exact-case problem, Shortest Vector Problem (SVP), is NP-hard. In this paper, Schnorr appears to reduce integer factorization to some form of the approximation version of Closest Vector Problem ($\gamma$-CVP), where CVP is a generalization of SVP. However, I do not believe there are known polynomial time algorithms for this.

Some known facts about $\gamma$-CVP:

Arora, et al (PDF), show that approximating the closest vector within any constant is NP-hard.

Also, they show that, for $\epsilon > 0$, if you can approximate the closest vector within a factor of $2^{\log^{\frac{1}{2} - \epsilon}{n}}$ in polynomial time, then any problem in NP can be solved in quasi-polynomial time.

Dinur, et al (ACM Citation), later strengthened the inapproximability result to:

For $\epsilon > 0$, approximately finding the closest vector within a factor $n^{\frac{\epsilon}{\log\log{n}}}$ is NP-hard.

Although I'm unfamiliar with Schnorr's work, what we know of lattice problems would lead me to believe that this is not intended to lead to a polynomial-time algorithm directly. Rather, Schnorr spends some deal of time talking about actual implementations (e.g. running this program on such-and-such computer takes approximately so many weeks/months/years/eons).

P.S. As Suresh points out, it appears to be an effort to get "quick enough" or "quicker" run times for integer factorization, despite the complexity.

P.P.S. And if I can make a further conjecture: Given that Schnorr's paper pre-dates the work on hardness of approximating lattice problems, it's likely that there was some original hope that it might have led to a polynomial-time algorithm for integer factorization. In light of Arora et al and Dinur et al, however, it's clear that there's not a solution (or at least, a straightforward solution) along that route, however.


Distributed Turing Machine? I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing machine? That is, is it possible to extend (make a variant) the concept of a turing machine to take advantage of distributed computing?

One idea, is to make a shared tape (something similar to Tuple Space) between TM.

[Is there] a formal representation of
  a distributed system on top of a
  turing machine?

Regarding this, the discussion (see link posted by Jukka on comments) is the way to look. The way, I see it, how you would formally represent a distributed system largely depends on how you view them, and that depends on "your favourite system assumptions" (i.e., the assumptions on synchrony (i.e., relative timing of actions in the distributed system), on communication (message passing vs. shared memory), on faults (of processes and/or links, benign or Byzantine, etc). As the community does not agree on this point, there is also no agreement on the basic formalism.

  [Is] it
  possible to extend (make a variant)
  the concept of a turing machine to
  take advantage of distributed
  computing?

I guess it is entirely possible, but no-one (that I know of) has looked into it.
What I know of are these:

Timed IO Automata also used in Lynch's Distributed Computing book
Communicating Sequential Processes
Temporal logic of actions
Pi-Calculus (also already mentioned by Alex)
And more (have been and will be mentioned here)...


The number of integral points in a polytope Suppose we define a polytope with
$$
\mathbf{Ax} \leq  \mathbf{b}
$$
What is the best way to find/approximate the number of the integral points in the polytope?
Update: how hard is the complexity of this problem?

Update: dimension of the space is $n$ and is a variable in the problem.

Check out

https://www.math.ucdavis.edu/~latte/

and the corresponding paper

Effective lattice point counting in rational convex polytopes. Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, Ruriko Yoshida. Journal of Symbolic Computation 2004 38:4, 1273-1302.

The algorithm they implement was introduced in

A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Alexander I. Barvinok. Mathematics of Operations Research 1994 19:4, 769-779.


An algorithm for counting to Graham’s Number I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory.

I thougth of the way to organize counter suitable for calculating $a{\uparrow\uparrow}b$, but got stuck at even smaller problem of counting to $2^a$, where $a$ is a 64-bit integer ($2^{21}$Tb needed for storage of such number is above what I assume reasonable).

Is there some clever technique to count beyond $2{\uparrow\uparrow}6$? Or is there any conceptual limitations on the counters with a polynomial-bounded memory?

With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (exponential), Turing machine state (constant) and position of the head over the tape (polynomial)). Thus any machine that runs for more than exponential time would have to visit some state more than once and hence loop.

In general, to get a program to run for $T(n)$ time you need $\Omega(\log(T(n)))$ memory.


Can "$x(\lambda y.P\;)z$" be $\beta$-reduced? Consider the untyped $\lambda$-calculus expression

$$x(\lambda y.P\;)z$$

...where (FWIW) $z$ is not free in $P$, and $P$ does not contain a redex.  Can this expression be $\beta$-reduced?  I've consulted several textbooks, but they are all silent on this point (as far as I can tell).  Application is left-associative, so the fully-parenthesized rendition of the expression above would be

$$((x(\lambda y.P\;))z)$$

The formalism, as given in all the textbooks I've consulted, specifies a $\beta$-reduction for $((\lambda y.P\;)z)$, namely $((\lambda y.P\;)z)\; \triangleright_{\beta} \;([z/y]P\;)$, but not one for $((x(\lambda y.P\;))z)$.  Therefore, the answer to my question would appear to be "no", but a derivation I'm working my way through seems to require an invalid-looking $\beta$-reduction of the form

$$((x(\lambda y.P\;))z) \;\; \triangleright_{\beta} \;\;(x([z/y]P\;))\;.$$

Any help with this would be appreciated.  In particular, reference to a treatment of the $\lambda$-calculus that explicitly adjudicates this question would be very helpful.  Thanks!

The expression $x(\lambda y.P)z$ is not $\beta$-reducible (unless there is a redex inside $P$, that is, but no such reduction sequence can escape outside the $\lambda$). The reduction you mention is invalid even in $\lambda\eta$-calculus. The only explanation I can imagine is that the expression in your derivation was misbracketed, and should actually read $x((\lambda y.P)z)$.


Complexity of "destroying" the graph's minimum spanning tree weight Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\infty$ for graph $G'$ which is not connected.

Consider the following problem:

  Given an integer $k\in\mathbb N$, decide whether there exists an edge set $E'\subseteq E$ , such that $|E'|=k$ and $w((V,E\setminus E')) > w(G)$?

What is the complexity of the above problem?.

EDIT

As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited in my original answer. However, the asker poses instead the question of whether or not removing $k$ edges could increase the MST weight of $G$ by any amount. Let's call this problem "$k$ Any Vital Edges" or $k$-AVE. We will show that $k$-AVE is in P.

Let $G=(V,E)$ be an edge-weighted graph with weight function $w:E\rightarrow \mathbb{N}$. The goal of $k$-AVE is to find a subset of edges $S \subseteq E$ of size $k$ such that the MST weight of $G$ is strictly less than the MST weight of $G\setminus S \triangleq (V, E\setminus S)$. We'll call such an $S$ a valid $k$-AVE set. We will proceed by outlining necessary and sufficient conditions for $S$ to be a valid $k$-AVE set.

Let $T$ be a MST of $G$. For every edge $e \in T$, we may associate a partition of $V$ into two parts (i.e.: a cut) based on how $e$ splits $T$ (i.e.: each partition consists of the vertices reachable from either endpoint of $e$ using only edges in $T \setminus \{e\}$). In particular, we will denote by $C_e$ the cut-set of this associated partition (i.e.: set of edges in $G$ that straddle this partition, including $e$ itself).

Now, by the Cut Property of MSTs, we know that each $e$ has minimum weight among all edges in $C_e$; there may be more than one edge in $C_e$ with that same minimum weight. Let these sets be denoted $M_e \triangleq \{e' \in C_e | w(e') = w(e)\}$. Suppose that, for some $e$, $M_e\subseteq S$. Then, we conclude that $G\setminus S$ has larger MST weight than $G$. Otherwise, we would have some MST $T'$ in $G$ that did not use any of the minimum weight edges across the cut-set $C_e$, a contradiction of the Cut Property. This shows that a sufficient condition for $S$ to be a valid $k$-AVE set is for it to contain $M_e$ for some $e$.

Next, we will show that this is condition is also necessary. Suppose to the contrary that, for all $e\in T$, $S$ excludes some $e' \in M_e$ (of course allowing that $e'$ may equal $e$). In general, removing $S$ from $G$ splits $T$ into a forest. We will reconstruct a new minimum spanning tree $T'$ from $T\setminus S$ by using the edges spared by $S$, as follows:

  Let $T' = T\setminus S$
  For each $e$ in $T$ do
  $\qquad$If no edge in $T'$ spans $C_e$ then let $T' = T' \cup \{e'\}$
  Return $T'$

We leave as an exercise to the reader to prove that this procedure reconstructs a spanning tree $T'$ with the same weight as $T$. (Outline: each edge added in step 3 preserves acyclicity and no components of $T\setminus S$ can remain separated).

These necessary and sufficient criteria naturally suggest a poly-time algorithm for determining if $G$ has a valid $k$-AVE set. First, construct a MST $T$. For each $e\in T$, we compute the cut-set $C_e$ and the set of minimum weight edges in $C_e$, $M_e$. If for some $e$, $|M_e| \leq k$, then we can simply take any $S \supseteq M_e$ as our valid $k$-AVE set. Otherwise, if all $M_e$ sets are larger than size $k$, we conclude that $G$ has no $k$-AVE set.

Original Answer Below

Shen, Hong. "Finding the k most vital edges with respect to minimum spanning tree." Acta Informatica 36.5 (1999): 405-424.

  For a connected, undirected and weighted graph $G = (V,E)$, the problem of finding the $k$ most vital edges of $G$ with respect to minimum spanning tree is to find $k$ edges in $G$ whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary $k$.


Is there a way to solve or approximate the concave program with separable objective? I would like to solve the following problem:
"minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints."
Is there a polynomial time algorithm to solve or approximate it?
Thanks.

Jian.

I special cases of this problem are a convex optimization problem. If x_i>0, then the objective is a posynomial. If the polytope can be described using posynomials, then the problem becomes a convex optimization problem.

See the tutorial at http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf which discusses geometric programming and search for posynomial.

--clarification--

See page 73 of the above link.

If your polytope can be described by a posynomial, then you can solve the polytope as a convex programming problem, by converting the problem into an equivalent form.

    Given:
      Minimize f0(x)
      s.t.
      fi(x)<=0 for all i
      fj(x)=0 for all j

Where f0(x) is your original objective and fi(x) is your polytope.

Let x_k an element in x be equal to exp(y_k).
Now, an equivalent problem is cast as:

      Minimize log(f0(exp(y))
      s.t.
      log(fi(exp(y))<=0 for all i
      log(fj(exp(y))=0 for all j

The restriction here is that the only a subset of all polytopes will work in this formulation. However if you can find a reasonable approximation where the polytope is approximated by a set of posynomial constraints, then you will have a computationally fast solution.

--- additional comments ----

The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.

See http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.


Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$ Since every $3$-SAT instance with $n$ variables can be expressed as a  degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns,  the NP-hardness of $3$-SAT directly translates to NP-hardness of solving(finding roots) $3$-degree polynomials.

So my question is solving a single degree-$2$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, NP-hard?

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2:

Suppose our constraint is $p(x) = 1$, and assume, since we're only interested in $p$ as a function, that it is reduced mod $x_i^2 = x_i$ (ie that it's multilinear). We can plug in zero, and if it fails to satisfy the constraint, we can conclude that $p$ has no constant term. Next, we try all points of Hamming weight 1. If they all fail to satisfy the constraint, then, since $p$ has no constant term, this means $p$ has no terms of degree 1. [To see this, think of what a Hamming-weight-1 input does to each monomial.] Next we try all points of Hamming weight 2, and, again, if these fail, then, since $p$ has no terms of degree at most 1, this means $p$ has no terms of degree 2. Since $p$ has degree at most 2, the only way these can all fail is if $p$ is the zero polynomial, and of course no solution exists in that case.

This keeps going to higher degrees: (the multilinearization of) $p$ has no terms of degree at most $r$ iff it's zero on all points of Hamming weight at most $r$. So for any constant degree, you get an efficient algorithm.


what is a model of computation, mathematically? Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't treat it as a maths object, it states it in English. Contrast this to clear maths definition for formal language: subset of finite set of symbols together with Kleene star

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words over a finite alphabet), an early attempt of an overarching mathematical definition was the abstract family of acceptors, which encompasses Turing machines, finite automata,  stack automata,  pushdown automata and similar notions: Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139. Needless to say, that notion does not describe L-systems, nonuniform circuit families, quantum devices, probabilistic models, membrane computing etc.


Select circle with given radius that contains most points Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points.

I tried solving it by taking each pair of points and if it is possible, generate the two circles that pass trough those two points and have radius r.

Here I found 2 possible circles that have points a and b on their perimeter with radius 2. One circle contains most points so that would be the solution of this problem.

However, I am not sure that this works. One easy counter example is when we have only one point. No pairs can be generated so no circles can be generated. In my code, I just added a circle for every point in addition to my circle generating nonsense from before. But that also fails to give me the correct result.

How do I really go about solving this?

Your algorithm is correct.  If the best circle contains one point, your post-processing step will find it.  If the best circle contains two or more points, then there is a way to shift it around so it contains the same set of points and also two of them are on the perimeter; thus, in this case your algorithm will also find it.

There may be other algorithms that are even faster, but your algorithm shows that the problem can be solved in $O(n^2)$ time.


Balls and Bins analysis in the m >> n regime. It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from RANDOM 1998 by Raab and Steger explores this in some detail, showing that as $m$ increases, the probability of going even a little above the expected value of $m/n$ decreased rapidly. Roughly, setting $r = m/n$, they show that the probability of seeing more than $r + \sqrt{r\log n}$ is $o(1)$.

This paper appeared in 1998, and I haven't found anything more recent. Are there new and even more concentrated results along these lines, or are there heuristic/formal reasons to suspect that this is the best one can get ? I should add that a related paper on the multiple-choice variant co-authored by Angelika Steger in 2006 does not cite any more recent work either.

Update: In response to Peter's comment, let me clarify the things I'd like to know. I have two goals here.

Firstly, I need to know which reference to cite, and it does seem like this is the most recent work on this.
Secondly, it is true that the result is quite tight in the r = 1 range. I'm interested in the m >> n range, and specifically in the realm where r might be poly log n, or even n^c. I'm trying to slot this result into a lemma I'm proving, and the specific bound on r controls other parts of the overall algorithm. I think (but am not sure) that the range on r provided by this paper might suffice, but I just wanted to make sure there wasn't a tighter bound (that would yield a better result).

Not really a full answer (nor a useful reference), but just a rather an extended comment. For any given bin, the probability of having exactly $B$ balls in the bin will be given by $p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$. We can use an inequality due to Sondow, $\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$, to yield $p_B < \left(\frac{(r+1)^{r+1}}{r^r}\right)^B \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$, where $r=\frac{m}{B}-1$. Note that this bound is fairly tight, since a $\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$.

Thus we have $p_B < e^{B(r+1)\ln(r+1) - Br\ln r - m\ln n + (m-B)\ln (n-1)}$. Now, since you are interested in the probability of finding $B$ or more balls in a bin we can consider $p_{\geq B} = \sum_{b=B}^{m} p_b < \sum_{b=B}^{m} e^{b(r+1)\ln(r+1) - br\ln r - m\ln n + (m-b)\ln (n-1)}$. Rearranging the terms, we get $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \sum_{b=0}^{m-B} e^{b(r+1)\ln(r+1) - br\ln r - b\ln (n-1)}.$$

Note the summation above is merely a geometric series, so we can simplify this to give $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)^{m-B+1}}{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)}.$$ If we rewrite $\frac{(r+1)^{r+1}}{r^r (n-1)}$ terms using exponentials, we get
$$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right)^{m-B+1}}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}},$$ which then becomes $$p_{\geq B} < \frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}}.$$

Now, I take it you care about finding some $B$ such that $p_{\geq B} < \frac{C}{n}$ for some constant $C$, since this gives the total probability of any bin having $B$ or more balls as bounded from above by $C$. This criteria is satisfied by taking $$\frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}} = \frac{C}{n},$$ which can be rewritten as $$B = \frac{\ln\left(\frac{C}{n} e^{m\ln \frac{n}{n-1}} \left(1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right) + e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{(r+1)\ln(r+1) - r\ln r - \ln (n-1)}.$$

I'm not entirely sure how useful this comment will be to you (it's entirely possible I've made a mistake somewhere), but hopefully it can be of some use.


Low-depth arithmetic complexity of the product of $k$ matrices Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?

Trivial upper bounds (up to small factors) are:

if $k=2$, then there are $\Sigma\Pi\Sigma$ circuits of size
$n^{\omega}$ (where $\omega$ is the matrix multiplication exponent.)
if $k>2$, then  there are $\Sigma\Pi\Sigma$ circuits of size
$n^{k+1}$.
if $k>2$, then  there are $O(log(k))$-depth circuits of size
$n^{\omega}$.

Is it possible to construct circuits of size $n^{\omega}$ for every $k$, for some fixed depth? Is it even possible to beat the trivial construction?

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of exhaustivity):

Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication.
Suryajith Chillara, Partha Mukhopadhyay. Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach.
Suman K. Bera, Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication.


are there fixed context sensitive grammars which are PSPACE complete? wikipedia entry  says without reference that

"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

This is stronger than saying that CSG is PSPACE-complete.
But is this proved? where are the references?

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.


Reductions of hard problems to physical models 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.

Counting constraint-satisfaction problems (#CSP), evaluating partition functions of many physical models, as well as many topics in classically simulating quantum states/circuits, are all fundamentally contracting tensor networks, which is a #P-complete problem. For a good overview see the following papers:

Itai Arad, Zeph Landau, Quantum computation and the evaluation of tensor networks

Cai, Lu, Xia Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

See especially the introduction of the latter for the connection to physical models.


Is MALL + unrestricted recursive types Turing-complete? If you look at the recursive combinators in the untyped lambda-calculus, such as the Y combinator or the omega combinator:
$$
\begin{array}{lcl}
\omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\
Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\
\end{array}
$$
It's clear that all of these combinators end up duplicating a variable somewhere in their definition.

Furthermore, all of these combinators are typeable in the simply-typed lambda calculus, if you extend it with recursive types $\mu\alpha.\,A(\alpha)$, where $\alpha$ is allowed to occur negatively in the recursive type.

However, what happens if you add full (negative-occurence) recursive types to the exponential-free fragment of linear logic (i.e., MALL)?

Then you don't have an exponential $!A$ to give you contraction. You can encode the type of exponentials using something like
$$
!A \triangleq \mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)
$$
but I don't see how to define the introduction rule for it, since that seems to require a fixed point combinator to define. And I was trying to define exponentials, to get contraction, to get a fixed-point combinator!

Is it the case that MALL plus unrestricted recursive types is still normalizing‽

If additive commutations are omited in MALL, it's easy to show that the size of a proof decreases with every cut-elimination step. If additive commutations are allowed, the proof is not as easy, but it was provided in the original “Linear Logic” paper. It's called Small Normalization Theorem (Corollary 4.22, p71), which says that as long as the contraction–promotion rule is not involved (which is the case in MALL) normalization holds. The argument does not rely on formulas themselves, they could be infinite (e.g. recursively defined).

It means that it's not possible to encode a promotion for type $\mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$ in MALL, since it would allow for fix point combinators. Some additional recursion construct would be needed for that.

Note: I believe that it's possible to use MALL together with a coinduction principle (introduction of $\mu$'s dual) to keep the system normalizing and obtain a promotion for this encoding of $!A$. Allowing recursive types in MALL + coinduction would then make it Turing complete. But as long as MALL is considered alone, allowing recursive types is not a big deal.


Complexity of computing the union of H-polytopes in three dimensions Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target polytope $Q$, which we can assume is the box $[-1,1]^3$.

What is the complexity class of deciding whether $Q\subseteq \bigcup_{i=1}^k P_i$?

If I'm not mistaken, This paper by Aronov and Sharir shows that the problem can be solved in expected polynomial time.
Is it known whether the problem is in P?
If it simplifies things, in my setting the polytopes are each defined by 4 non-affine halfspaces, so they are infinite cones.

Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$):

Let $h_1,\ldots,h_n$ be an enumeration of all the bounding hyperplanes of the
polytopes $P_1,\ldots,P_k$ and $Q$.
Compute the arrangement of $h_1,\ldots,h_n$ (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial time; see for instance "Constructing Arrangements of Lines and Hyperplanes with Applications" by H. Edelsbrunner, J. O’Rourke, and R. Seidel, SIAM Journal on Computing 15 (1986), pp 341–363.
Now check whether there exists some cell $C$ in the arrangement that is contained in $Q$ but in none of $P_1,\ldots,P_k$.
(For checking containment, it is enough to check whether the vertices of
the cell satisfy the inequalities of the polytope.)
If such a cell $C$ exists, answer NO. Otherwise answer YES.

If the dimension $d$ is given as part of the input, then your problem
("Does the union of $P_1,\ldots,P_k$ cover all of $Q$") is coNP-hard.


Approximating the sign rank of a matrix The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in communication complexity and learning theory.

My question is: Are there any known (subexponential time) algorithms that approximate the sign-rank of a matrix to within a factor $o(n)$?

(I am aware of Forster's lower bound on the sign rank in terms of spectral norm, but this does not yield an approximation ratio better than $\Omega(n)$ in general.)

I believe this is an open question.

Lee and Schraibman in "An approximation algorithm for approximation rank" show that the approximation rank can be approximated to a constant factor by a polynomial time algorithm.  To do so, they relate a semidefinite programming quantity $\gamma_2^\alpha$ to the approximation rank, where the $\alpha$ is some finite parameter greater than 1.  Taking $\alpha$ to the limit of infinity yields the sign-rank but their result does not give anything in this setting.


Simple reduction to unbounded knapsack? Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited number of objects of each type)? I'm writing an introduction to a few of these problems, and noticed that I hadn't really heard of a standard reduction here. Shouldn't be that hard (it's a relatively expressive problem), but I can't think of anything right now… Thoughts/references?

There is a simple reduction from the subset sum problem. (We usually give it as an exercise.)

The idea is to encode in the weights that an element can only be included 0 or 1 times.

Assume the subset sum instance consists of numbers $w_1,\dots,w_n$ with target $W$. Assume that $w_i < B$ for all $i$.

We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $i$ we get two new weights $w^1_i = (2^{n+1} + 2^i)nB + w_i$ and $w^0_i = (2^{n+1} + 2^i)nB$. The new weight bound is defined as $W' = (n2^{n+1} + 2^n + \dots + 2^1)nB + W$. Values of elements are the same as their weights, and the target value is $W'$


Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure? Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its parent, left child or right child.

I am interested in what "tree-languages" can be accepted by what machines. More specifically, take the language where in every non-leaf we have the gate of a boolean circuit (ie. and or not), in the leaves either a constant or a variable (different for each leaf) and such a "tree-word" is in the language if and only if it has a satisfying assignment. Can this language be decided by a turing machine that has an o(log n) space worktape?

Note that it is accepted by a non-deterministic finite state machine and also by a deterministic turing machine with O(log n) space. Similarly, if all the variables are constant, then it can be decided by a deterministic finite state machine. (If there are no constants, then every formula is satisfiable.)

It seems to me that the problem can be solved in constant space.

We perform a recursive procedure, and store only the parity of the number of negation gates seen on the path from the root to the current node.

At a leaf, if we have a variable and have seen an even number of negation gates, we set the variable to be true. Otherwise, if we have seen an odd number of negation gates, we set the variable to be false.

As before, at an AND or OR gate we first call recusively to the left, and then to the right if the value has not been determined.

Now if there exists a satisfying assignment, then the assignment defined above will satisfy the formula.


Array slice reversing data-structure Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations:

You are allowed a one time $\mathcal{O}(n)$ preprocessing step:

$\text{Init}(A)$

And the operations

$\text{Reverse}(i,j)$: Reverse the slice $A[i \dots j]$ i.e. swap $A[i]$ with $A[j]$, $A[i+1]$ with $A[j-1]$ etc.
$\text{Retreive}(i)$: Returns the element at position $i$ in the array.

Now I have heard that there is a data-structure which supports both $\text{Reverse}$ and $\text{Retrieve}$ in guaranteed $\mathcal{O}(P(\log n))$ time, where $P(x)$ is a polynomial (Assume $\mathcal{O}(1)$ array accesses).

I am guessing this was published somewhere. Does anyone know any reference?

Apologies if this is actually at the level of undergraduate homework. Please feel free to close/delete it in that case (but please do provide a reference to the appropriate text/website in comments before deleting).

Splay trees can easily do this, with their nodes augmented to have two extra pieces of information: the total number of descendants of each node (so you can answer retrieve queries), and a reverse bit, such that the roles of the left and right pointers at node x are reversed if x and its ancestors have an odd number of reverse bits. The amortized time per operation would be O(log n).

Whenever the tree is rotated it is possible to update this extra information in constant time (and maintain consistency of the reverse bits so that each node has the same parity of ancestral reverse bits as it did before the rotation). To handle a retrieve, just do a binary search down through the tree using the number-of-descendants of the left subtree at each step to determine whether to go left or right (and then as with any splay tree operation, splay up the node found by the retrieve). To handle a reverse operation, split the splay tree at i and j to form three trees, flip the reverse bit of the root of the middle tree, and concatenate them back together again.

I'm not sure of a published reference but looking through the splay tree literature might work. The one I'd try first is Tarjan's Data Structures and Network Algorithms, but I don't have time right now to check it.


What are the compelling reasons for believing $L\neq P$? What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.

Suppose L=P for the moment. What would a log-space algorithm for a P-complete problem look like in its general outlines?

Mulmuley's result (from Mulmuley's webpage without paywall) that, in the PRAM model without bit operations, "$\mathsf{P} \neq \mathsf{NC}$". (In the usual boolean model where $\mathsf{L}$ lives, $\mathsf{L} \subseteq \mathsf{NC}$.) This model is strong enough that the result implies any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem would have to look quite different from most known algorithms for $\mathsf{P}$-complete problems.

The PRAM model without bit operations is a nonuniform, algebraic model over $\mathbb{Z}$ (similar to algebraic computation trees or the Blum--Shub--Smale algebraic RAM model) in which the nonuniform program can depend not just on the number of integer inputs, but also on their total bitlength. In this way it's not a "purely" algebraic model, but lives somewhere between algebraic and boolean. This model includes poly-time algorithms for linear programming, maxflow, mincut, weighted spanning tree, shortest paths, and other combinatorial optimization problems, the logspace algorithm for tree isomorphism (see comments below), and algorithms for approximating the complex roots of polynomials, which is why I say any $\mathsf{L}$ algorithm for a $\mathsf{P}$-complete problem (which, as your question indicates you know, most people think does not exist) would have to look quite different from any of these.


Quanitifier Free Presburger Arithmetic: Upper bound on solution size? DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question.

According to this paper, if there is a solution to a quantifier free Presburger formula, there is a solution whose size in bits is polynomial in the problem size. This allows the problem to be in $NP$, easier than arbitrary Presburger formulas.

However, the paper doesn't explicitly reference where this bound comes from, just mentioning a connection to Integer Linear Programming.

I was wondering if anyone knew, what was the exact bound on the solution size, or if they could provide a reference for such? I have another problem which I can phrase as a QF Presburger formula, and I'd like to find a definite bound on the solution size. But I'm also trying to work it into an actual software system, so simply knowing "there exists a polynomial" doesn't help me much.

You can find an answer in the following paper:

Joachim von zur Gathen, Malte Sieveking. A bound on solutions of integer linear equalities and inequalities.
Proc. AMS 72(1) (1978)
(pdf)

A simple corollary of their result follows.
Let's say we have two integer systems, $A x = b$ and $C x \ge d$,
where you want $x$ to be in $\mathbb Z^n$.
Consider determinants of all square submatrices of the matrix $E = \left(\matrix{A & b \\ C & d}\right)$
and denote by $M$ an upper bound on their absolute values.
(In other words, set $M$ to be larger than or equal to the absolute value of all minors of $E$.)
Now, if there exists an $x \in \mathbb Z^n$ satisfying both $A x = b$ and $C x \ge d$, then
there exists such an $x$ whose components are at most $(n + 1) M$ in absolute value.

It remains to note that a determinant of a $k \times k$-matrix $S$ is at most $k!\, \|S\|_{\mathsf{max}}^k$
where $\|S\|_{\mathsf{max}} = \max |s_{i j}|$. Combining these two bounds will give a specific polynomial
bound on the size of a smallest solution (and this is already an easy exercise).


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

References can be found in martinschwarz's answer, but here's a summary of a couple reductions.

The symmetric group $S_n$ acts on graphs of n vertices by permuting the vertices.  Determining whether two graphs are isomorphic is polynomial-time equivalent to computing a polynomial-size generating set for $Aut(G)$.

Reduction to the HSP over the symmetric group $S_n$ (where $n$ is the number of variables in the graph).  The function $f$ is $f(p)=p(G)$ where $p$ is a permutation in $S_n$, and $p(G)$ is the permuted version of $G$.  Then $f$ is constant on cosets of $Aut(G)$ and distinct on distinct cosets (note that the image of $f$ consists of all graphs isomorphic to $G$).  Since the hidden subgroup is exactly $Aut(G)$, if we could solve this HSP then we would have the generating set for $Aut(G)$, which is all we need to solve GI (see above).

Reduction to the HSP over $S_n \wr \mathbb{Z}/2\mathbb{Z}$.  If we want to know if two graphs $G$ and $H$ on $n$ vertices are isomorphic, consider the graph $K$ which is the disjoint union of $G$ and $H$ on $2n$ vertices.  Let $\mathbb{Z}/2\mathbb{Z}$ act on the vertices by swapping $i$ with $n+i$ for $i=1,...,n$.  Either $Aut(K) = Aut(G) \times Aut(H)$ or $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$.  As before, let $f(x)=x(K)$ where $x$ is now an element of $S_n \wr \mathbb{Z}/2\mathbb{Z}$ that acts on $K$ as described.  The hidden subgroup associated to $f$ is exactly $Aut(K)$, as in the previous reduction.  If we solve this HSP, we get a generating set for $Aut(K)$.  It is then easy to check whether the generating set contains any element that swaps the copy of $G$ with the copy of $H$ inside $K$ (has nontrivial $\mathbb{Z}/2\mathbb{Z}$ component).


Non-computable=>normal? If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite times as a subsequence at approriate rates etc?

No, the string need not be normal.  Take any uncomputable sequence and add two 0s between each term; now there are too many 0s for the sequence to be normal but it's still uncomputable.


Complexity Classes for Cases Other Than "Worst Case" Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide?

Another question considers the best case complexity, exemplified below:

Is there a class of (natural) problems whose decision requires at least exponential time?

To clarify, consider some EXP-complete language $L$. Obviously, not all instances of $L$ require exponential time: There are instances which can be decided even in polynomial time. So, the best case complexity of $L$ is not exponential time.

EDIT: Since several ambiguities arose, I want to try to clarify it even more. By "best case" complexity, I mean a complexity class whose problems' complexity is lower bounded by some function. For instance, define BestE as the class of languages which cannot be decided in time less than a some linear exponential. Symbolically, let $M$ denote an arbitrary Turing machine, and $c$, $n_0$, and $n$ be natural numbers:

$L \in \mathbf{BestE} \Leftrightarrow$
$\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

where $T(M(x))$ denotes the times it takes before $M$ halts on input $x$.

I accept that defining such class of problems is very odd, since we are requiring that, every Turing machine $M$, regardless of its power, cannot decide the language in time less than some linear exponential.

Yet notice that the polynomial-time counterpart (BestP) is natural, since every Turing machine requires time $|x|$ to at least read its input.

PS: Maybe, instead of quantifying as "for all Turing machine $M$," we have to limit it to some pre-specified class of Turing machines, such as polynomial-time Turing machines. That way, we can define classes like $\mathbf{Best(n^2)}$, which is the class of languages requiring at least quadratic time to be decided on polynomial-time Turing machines.

PS2: One can also consider the circuit-complexity counterpart, in which we consider the least circuit size/depth to decide a language.

Although I can't quite parse your definitions, you should know that much stronger time hierarchies are known, in particular "almost everywhere" time hierarchies.

Here is the formal statement: for every time bound $T(n)$, there is a language $L \in TIME[T(n)]$ with the property that every deterministic algorithm that correctly recognizes $L$ must run in time asymptotically greater than $t(n)$ on all but finitely many inputs, for sufficiently small time $t(n)$.

"Sufficiently small" means $t(n) \log t(n) \leq o(T(n))$.

Suppose we choose $T(n)=2^n$ for an example, and obtain a hard language $L$. Then, any algorithm that correctly recognizes $L$ must take at least $2^n/n^2$ time on all inputs past a certain length. This seems to be what you're looking for in your class BestE.

Reference:

  John G. Geske, Dung T. Huynh, Joel I. Seiferas: A Note on Almost-Everywhere-Complex Sets and Separating Deterministic-Time-Complexity Classes Inf. Comput. 92(1): 97-104 (1991)


Fast deletion / contraction in combinatorial embedding I wonder if there is a sublinear algorithm to make deletion or contraction of an edge in a combinatorial embedding of, lets say, planar graph?

Since in combinatorial embedding we have to maintain vertices of G and G* at the same time, taking in account that contraction in the primal is deletion in the dual, it's sufficient only to make deletions, updating primal permutation according to dual and vice-versa. But obvious way to do it is just recompute them, which takes linear time. Can we do any better?

Second question: is there any technique that helps to get rid of multiple edges between same vertices? (the only solution I see to the second problem is to postpone deletion of multiple edges until we will get graph with, for example, m=6n, where m - number of edges, n - number of vertices, this will make time amortized O(1)) Maybe there is some techniques, which can make this time not amortized? (I am also interested in just o(n) solutions, not necessarily O(1))

Thank you very much!

This question is incomplete without specifying what information about the graph as it changes you want your dynamic graph data structure to output or support queries for. But the following paper is likely relevant, even though it is described in a more general setting of combinatorial embeddings in arbitrary genus rather than just planar. It definitely supports both contractions and deletions, as well as their reverse operations, in logarithmic time per operation.

Dynamic generators of topologically embedded graphs.
D. Eppstein.
arXiv:cs.DS/0207082.
SODA 2003, pp. 599-608.

As for the second question: I don't see how to handle multiple adjacencies in general, but it's easy to get rid of bigons (multiple edges with nothing between them) as they can only come from the two faces that are on either side of a contracted edge or from the face that surrounds a deleted edge. That should be sufficient for many purposes since getting rid of the bigons ensures that the remaining graph has a number of edges proportional to its number of vertices.


What is the complexity of the set of closed boolean tautologies assuming well formed formulae? Let's define two CFGs:

S  ::= 0 | 1 | (S+S) | (S*S)
S' ::= 0 | 1 |  S+S  |  S*S  | (S)

And two languages:

M  = { w | S  generates w, and w evaluates to 1 }
M' = { w | S' generates w, and w evaluates to 1 }

In both cases, evaluating is done by interpreting + as logical or, * as logical and, and in the case of M' by being careful about * having higher precedence than +.

Suppose w is in S, and u is in S'. My questions are:

Is there a finite automaton (or a regex) that can decide wheter w is in M?
Is there a finite automaton (or a regex) that can decide wheter u is in M'?
Suppose S ::= 0 | 1 | +SS | *SS. (Prefix notation) Does this change the answer to question 1?

I'm aware that without knowing whether w is in S, deciding if w is in M isn't solvable by finite automata due to pumping lemma (we'd have an issue with parentheses), similarly for u, S' and M'. However, knowing that w is in S (and u is in S') might make the problem significantly easier.

Note: if the answer is yes, please write the grammar/regex/proof sketch/explanation in spoiler tags. :)

The answer to all three questions is negative. Consider e.g. the prefix version (3), and assume for contradiction that it is decidable by a (wlog deterministic) automaton $A$ with $m$ states. Consider the strings

$$\begin{align}
u_k&={+}^{m-k}{*}{+}^k,\\
v_l&=1^{l+1}0^{m-l+1}.
\end{align}$$

Notice that $u_kv_l$ is a well-formed Boolean sentence for every $0\le k\le m$, $0\le l\le m+1$, and it is easy to see that $u_kv_l$ evaluates to $1$ iff $k<l$. By the pigeonhole principle, there are $0\le k<l\le m$ such that $u_k$ and $u_l$ land in the same state of $A$, thus $u_kv_l$ and $u_lv_l$ are both accepted or both rejected. However, the former evaluates to $1$, and the latter to $0$.

For infix formulas (questions 1,2), one can use in a similar way formulas of the form

$$(0+((0+\cdots((0+((1+((0+\cdots((0+0)*1))*1))\dots*1))*0))*1))\dots*1)).$$

The argument in fact shows that any deterministic automaton evaluating well-formed Boolean sentences of length $n$ must have size $\Omega(n)$, or in other words, any online algorithm for evaluation of such sentences needs space at least $\Omega(\log n)$. This bound is tight: as shown by Buss, it is possible to evaluate Boolean sentences in infix notation in online space $O(\log d)$, where $d$ is the depth of the formula (i.e., maximum nesting of brackets). (The paper advertises it as an online $O(\log\log n)$-space algorithm for evaluation of balanced formulas, using the fact that these have depth $d=\log n$.)

On the other hand, as also shown by Buss, Boolean sentence evaluation (in either prefix or infix notation) can be done in ALOGTIME, aka uniform $\mathrm{NC}^1$, and it is in fact complete for this class under DLOGTIME many-one reductions. Since regular languages with unsolvable syntactic monoid (for example, $\bigl((a|b)^3(ab^*a|b)\bigr)^*$) are also $\mathrm{NC}^1$-complete, it follows that one can reduce Boolean sentence evaluation in DLOGTIME to a regular language.


Parametrized complexity of sparse optimization Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so if anyone has one handy, please say so in the comments!] The $\ell_0$ "norm" is the number of non-zero elements in the vector $x$. A common way to solve such problems is via a convex relaxation: relax $||x||_0\le k$ to $||x||_1\le k$ and solve the resulting linear program. With luck, one can quantify how close the relaxed solution is to the optimal.
My question is: What if we try a more gradual relaxation, via the $\ell_p$ norm for $0<p<1$? These result in non-convex programs, but the non-convexity degree can be tweaked. Surely the $p=0.999$ case, for reasonably set other parameters, cannot be much harder than the $p=1$ case?.. Has anybody tried this approach? The idea is to seek a better efficiency/optimality tradeoff via values of $p$ other than $1$.

This may be related to what you have in mind: arxiv.org/abs/0804.4666


Understanding the Beck-Chevalley Condition I've been reading through Bart Jacobs' "Categorical Logic and Type Theory", and lemma 1.8.9 has me stumped. The lemma is stated as follows:

Let $p : \mathbb E \to \mathbb B$ and $q : \mathbb D \to \mathbb B$ be fibrations and let $H : \mathbb E \to \mathbb D$ be a fibred functor. This functor $H$ has a fibred left adjoint if and only if both

(a) For each object $I \in \mathbb B$ the functor $H_I : \mathbb E_I \to \mathbb D_I$ restricted to the fibres over $I$ has a left adjoint $K(I)$

(b) The Beck-Chevalley Condition holds, i.e. for every map $u : I \to J$ in $\mathbb B$ and for every pair of reindexing functors $\mathbb E_J \overset{u^*}{\longrightarrow} \mathbb E_I$ and $\mathbb D_J \overset{u^\#}{\longrightarrow} \mathbb D_I$, the canonical natural transformation $K(I)u^\# \Rightarrow u^* K(J)$
is an isomorphism.

What does the canonical natural transformation $K(I)u^\# \Rightarrow u^* K(J)$ refer to? I was having a lot of fun reading this book. However, since the Beck-Chevalley condition is used throughout the rest of the book, this particular lemma has become a road block.

I'm not sure if this is considered a research level question, but I don't know where else to ask this.

So we need to construct a natural transformation $\phi : K(I)u^\# \Rightarrow u^*(K(J))$, which are functors from $D_J$ to $E_I$. So for every $d \in D_J$ we need a morphism $K(I)(u^\#(d)) \to u^*(K(J)(d))$ in $E_I$.

Since $K(I) \dashv H(I)$, this is equivalent to constructing a morphism $u^\#(d) \to H(I)(u^*(K(J)(d)))$ in $E_J$.
Now since $H$ is a fibred functor, $H(I)(u^*(e)) \cong u^\#(H(J)(e))$ for any $e$ so by composition with this isomorphism it is sufficient to construct a morphism $u^\#(d) \to u^\#(H(J)(K(J)(d)))$.
$u^\#$ is a functor so it is sufficient to construct a morphism $d \to H(J)(K(J)(d))$
So we can just use the unit of the adjunction $K(J) \dashv H(J)$.

The whole process is natural since every step is natural.


reference for a special modular decomposition For modular decomposition.

X is a module if all members of X have the same set of neighbors among vertices not in X.

I need a special modular decomposition.

X is my module if all members of X have the same set of neighbors among vertices not in X, and X is a clique.

I think this should have been studied already, I would like to avoid redefining it and use some non-standard name, can someone give me some reference?

Indeed this concept exists. Two vertices $u,v$ that have the same neighbors are often called twins. They are called true twins if they are also connected, and false twins otherwise. In your definition, all vertices of $X$ are true twins.

It looks like there are several other names in the literature for these concepts. See e.g. this MO question. In FPT algorithms we sometimes call the number of twin classes into which a graph can be partitioned the neighborhood diversity of the graph, see e.g. here (warning: self-citation!), and here for the related notion of twin-cover.


Complexity of solving linear equations What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse systems there are even better algorithms. However, I was wondering if there was some comlexity-theoretic characterization of this problem. For example, is the corresponding decision problem in $\mathbf{NC}$? Is it complete for any complexity class?

I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.


What is considered significant when applying for a TCS PhD with major changed I am a Master student on CS. Actually in theory.
I have a BE in polymer (Chemical Eng stuff), and I struggled somehow to get enrolled in this program.

I want to apply a TCS  PhD in US. So, what do you people think is important that I get to apply to a PhD ?

Perhaps you may value these following options:

published paper ( I am writing a paper on combinatorics )
strong recommend letter
a high score on GRE or GRE sub(math or CS ,U Chig  recommends a math sub as far as I know)
Meet some guys who doing recruiting.

Note that I have 2.0/5 GPA on my BE, so this  really upsets me much.

Hope that this problem could help others desiring to do a PhD in TCS.

If you're currently a masters student in CS, then a lot of your 'switched major' issues have already gone away. the main concern in applying for a Ph.D in TCS is if you have sufficient mathematical background, as well as background in algorithms. If your MS program experience can demonstrate this, and you also can demonstrate mathematical expertise via your paper in combinatorics, then that concern goes away.

But admissions decisions are multivariate and stochastic. Maybe the right question is whether you have the right background to succeed, and there are answers regarding what constitutes the right background (on mathematical background). Also see this on how to prepare for a TCS advanced degree.


Attribute efficiently learning the relevant attributes of juntas with membership queries Can the relevant attributes of k-juntas be learned attribute efficiently given a membership query oracle? What's the best known lower bound for this problem?

Juntas can be tested in an attribute efficient manner given a membership query oracle: http://www.cs.cmu.edu/~eblais/papers/TestingJuntas.pdf Testing is an easier problem than learning, and the attribute efficient result is relatively recent. This might be a good place to start poking around.

Incidentally, the hard part about learning juntas is just identifying the set of $k$ relevant variables. Once that is done, you can learn the junta through exhaustive querying with $2^k$ queries (which might be "attribute efficient" since it is independent of $n$. In any case, you can't hope to do much better since the function can be arbitrary on these $k$ bits...). The testing algorithm linked to seems to work by trying to identify relevant variables, so it might solve your problem if you go through the details.


Hard Problems for higher genus graphs Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :

Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?
More generally are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g ?

This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See http://arxiv.org/abs/1203.5944


Does the space hierarchy theorem generalize to non-uniform computation? General Question

  Does the space hierarchy theorem generalize to non-uniform
  computation?

Here are a few more specific questions:

Is $L/poly \subsetneq PSPACE/poly$?
For all space constructible functions $f(n)$, is $DSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly$?
For what functions $h(n)$ is it known that: for all space constructible $f(n)$, $DSPACE(o(f(n)))/h(n) \subsetneq DSPACE(f(n))/h(n)$?

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every value $b \leq \epsilon \cdot 2^n / n$, there is a function $f: \{0, 1\}^n \to \{0, 1\}$ such that $b - cn \leq B(f) \leq b$.

I think separating $\mathbf{PSPACE}/\text{poly}$ from $\mathbf{L}/\text{poly}$ would be difficult. It's equivalent to proving that some language in $\mathbf{PSPACE}$ has super-polynomial branching program complexity. A simple argument shows that $\mathbf{PSPACE}$ does not have fixed-polynomial-size branching programs:

Proposition. For every constant $k$, there is a language $L \in \mathbf{PSPACE}$ so that for all sufficiently large $n$, $B(L_n) > n^k$. (Here $L_n$ is the indicator function for $L \cap \{0, 1\}^n$.)

Proof. By the hierarchy we proved, there is a branching program $P$ of size $n^{k + 1}$ that computes a function $f$ with $B(f) > n^k$. In polynomial space, we can iterate over all branching programs of size $n^{k + 1}$, all branching programs of size $n^k$, and all inputs of length $n$ to find such a branching program $P$. Then we can simulate $P$ to compute $f$.


NP-hard problems on paths everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?

I've already found a related question about NP-hard problems on trees.

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be NP-hard for simple paths to the best of their knowledge.

See Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013), or the arXiv version.


Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ maps strings from $L_{1}$ to $L_{2}$, such that $x \in L_{1}$ iff $f(x) \in L_{2}$. The isomorphism holds for all $NP$-complete languages under polynomial time assumptions(p-isomorphisms). Special conditions are: p-isomorphisms, polynomial run time $f()$, and so also the inverse of $f()$ is computable in polynomial time. The conjecture if true, would imply no $NP$-complete language is sparse. What are the analogues to the conjecture in various types of reductions, for example under $AC^{0}$ reductions the conjecture is true: Under $AC^{0}$ many-one reductions, all $NP$ complete languages do show an $AC^{0}$ isomorphism.

This leads one to the creativity conjecture, which is: Are all NP-creative sets  languages the same as NP-complete sets under $\leq^{m}_{p}$ reductions. Formally, creativity for a set is defined as: A set $A$ is creative if its complement is "productive". By "productivity" of a set $A$, over a class of languages $C$, we mean there is a function(not necessarily polynomial), that witnesses $A \notin C$. So, it is natural to think of problems to be creative under different conditions, eg, a polynomial time function $f$, or even under log time, or oracular function restrictions. So, while $AC^{0}$ many-one reductions give a resolution to the Berman-Hartmanis conjecture, is there resolution to the creativity conjecture under $AC^{0}$ reductions(or any other reasonable assumptions)?

Creativity(k-creativity), like the Berman-Hartmanis conjecture(truth of which shows that there are no sparse $NP$-complete languages), shows us another fine grained level nature of $NP$ complete problems. Are there $NP$ complete problems that show creative(k-creativity, for one) properties, and some don't. Are there natural problems that
that one would consider creativity, such that the $NP$-complete language is known to be creative (any variants of SAT)?

First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely because of Berman-Hartmanis, but the theorem is independent of BH Isomorphism.)

The $\mathsf{AC}^0$ version of the isomorphism conjecture (with various restrictions on uniformity) is a theorem. See the following paper and references therein:

  Manindra Agrawal, The Isomorphism Conjecture for Constant Depth Reductions, JCSS 77 (special issue on Karp's Kyoto Prize): 3-13, 2011.

You may also be interested in other work of Agrawal, Allender, and others on related questions. Agrawal's and Allender's webpages have links to most of the relevant papers (I only say "most" in case I've missed a few that didn't involve either Agrawal or Allender, but I haven't done a thorough literature review recently).

On creativity, Joseph and Young's construction is still one of the main pieces of evidence against BH.


Why colon to denote that a value belongs to a type? Pierce (2002) introduces the typing relation on page 92 by writing:

  The typing relation for arithmetic expressions, written "t : T", is defined by
  a set of inference rules assigning types to terms

and the footnote says The symbol $\in$ is often used instead of :. My question is simply why type theorists prefer to use : over $\in$? If a type $T$ is a set of values then it makes perfect sense to write $t \in T$, no new notation needed.

Is this similar to how some cs writers prefer $3n^2 = O(n^2)$ even thought it is abuse of notation and should be written $3n^2 \in O(n^2)$?

The main reason to prefer the colon notation $t : T$ to the membership relation $t \in T$ is that the membership relation can be misleading because types are not (just) collections.

[Supplemental: I should note that historically type theory was written using $\in$. Martin-Löf's conception of type was meant to capture sets constructively, and already Russell and Whitehead used $\epsilon$ for the class memebrship. It would be interesting to track down the moment when $:$ became more prevalent than $\in$.]

A type describes a certain kind of construction, i.e., how to make objects with a certain structure, how to use them, and what equations holds about them.

For instance a product type $A \times B$ has introduction rules that explain how to make ordered pairs, and elimination rules explaining that we can project the first and the second components from any element of $A \times B$. The definition of $A \times B$ does not start with the words "the collection of all ..." and neither does it say anywhere anything like "all elements of $A \times B$ are pairs" (but it follows from the definition that every element of $A \times B$ is propositionally equal to a pair). In constrast, the set-theoretic definition of $X \times Y$ is stated as "the set of all ordered pairs ...".

The notation $t : T$ signifies the fact that $t$ has the structure described by $T$.

A type $T$ is not to be confused with its extension, which is the collection of all objects of type $T$.  A type is not determined by its extension, just like a group is not determined by its carrier set. Furthermore, it may happen that two types have the same extension, but are different, for instance:

The type of all even primes larger than two: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{iseven}(n) \times (n > 2)$.
The type of all odd primes smaller than two: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{isodd}(n) \times (n < 2)$.

The extension of both is empty, but they are not the same type.

There are further differences between the type-theoretic $:$ and the set-theoretic $\in$. An object $a$ in set theory exists independently of what sets it belongs to, and it may belong to several sets. In contrast, most type theories satisfy uniqueness of typing: if $t : T$ and $t : U$ then $T \equiv U$. Or to put it differently, a type-theoretic construction $t$ has precisely one type $T$, and in fact there is no way to have just an object $t$ without its (uniquely determined) type.

Another difference is that in set theory we can deny the fact that $a \in A$ by writing $\lnot (a \in A)$ or $a \not\in A$. This is not possible in type theory, because $t : T$ is a judgement which can be derived using the rules of type theory, but there is nothing in type theory that would allow us to state that something has not been derived. When a child makes something from LEGO blocks they proudly run to their parents to show them the construction, but they never run to their parents to show them what they didn't make.


Rewrite relations - proof of correctness Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := Id(\Sigma^* \setminus (\Sigma^* \cdot dom(T) \cdot \Sigma^*)) \cup \{ \langle \epsilon, \epsilon \rangle \}
$$
$N(T)$ is the identity relation of the set of all words that don't contain an infix in $dom(T)$ including the pair $\langle \epsilon, \epsilon \rangle$.
The idea is the following - we have an input string $t \in \Sigma^*$ and $R^{obl}(T)(t)$ will result in the translation of the substrings of $t$ which $\in dom(T)$ via $Т$, and the ones $\notin dom(T)$ via identity.
Example 1: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}$, the input text $t = babacbca$ is decomposed as $t = b \cdot ab \cdot ac \cdot bc \cdot a$ and the substrings $\{ b,ac,a \} \subseteq dom(N(T))$, whereas, $\{ab, bc\} \subseteq dom(T)$. So $R^{obl}(T)(t) = b \cdot d \cdot ac \cdot d \cdot a = bdacda$
Example 2: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}, t = abcc$. This time we have two possible decompositions due to overlapping. $t = ab \cdot cc = a \cdot bc \cdot c$, therefore, two possible translations $\langle abcc, dcc \rangle \in R^{obl}(T), \langle abcc, adc \rangle \in R^{obl}(T)$.
My questions is - how do we formulate a proof of correctness for such a construction? That it indeed translates the words as described
A bit of a context. I've studying rewrite systems based on regular relations (implemented as finite-state transducers) and more specifically the papers "Regular Models of Phonological Rule Systems" by Kaplan & Kay (1994) and "Directed Replacement" by Karttunnen (1996). They construct complex rewrite relations by using only the regular set and relation algebra, however, the papers do not provide formal proofs that their method is correct. If anyone has experience in this field and can provide some guidance, I'll greatly appreciate it.

To simplify, let $D$ be the domain of $T$ and let $R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition
$$
N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*.
$$
Here is a formal way to justify your idea.
Let $(u,v) \in \Sigma^* \times \Sigma^*$. By definition, $(u,v) \in R^{obl}(T)$ if and only if $(u,v)$ can be written as
$$
(u, v) = (r_0, r_0)(u_1, v_1)(r_1, r_1)(u_2,v_2) \dotsm  (r_{k-1}, r_{k-1})(u_k,v_k)(r_k, r_k)
$$
where $r_0, r_1, \ldots, r_k \in R$ and $(u_1, v_1), \ldots, (u_k,v_k) \in T$, which is exactly what you describe in your sentence starting by "The idea is the following".


Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string for this alphabet.

Usually, as long as $\Sigma$ contains more than 1 element, the exact number of elements in $\Sigma$ doesn't matter: at best we end up with a different constant somewhere. In other words, it doesn't really matter if we use the binary alphabet, the numbers, the Latin alphabet or Unicode.

  Are there examples of situations in which it matters how large the alphabet is?

The reason I'm interested in this is because I happened to stumble upon one such example:

For any alphabet $\Sigma$ we define the random oracle $O_{\Sigma}$ to be an oracle that returns random elements from $\Sigma$, such that every element has an equal chance of being returned (so the chance for every element is $\frac{1}{|\Sigma|}$).

For some alphabets $\Sigma_1$ and $\Sigma_2$ - possibly of different sizes - consider the class of oracle machines with access to $O_{\Sigma_1}$. We're interested in the oracle machines in this class that behave the same as $O_{\Sigma_2}$. In other words, we want to convert an oracle $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ using a Turing machine. We will call such a Turing machine a conversion program.

Let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2, 3 \}$. Converting $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ is easy: we query $O_{\Sigma_1}$ twice, converting the results as follows: $00 \rightarrow 0$, $01 \rightarrow 1$, $10 \rightarrow 2$, $11 \rightarrow 3$. Clearly, this program runs in $O(1)$ time.

Now let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2 \}$. For these two languages, all conversion programs run in $O(\infty)$ time, ie there are no conversion programs from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ that run in $O(1)$ time.

This can be proven by contradiction: suppose there exists a conversion program $C$ from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ running in $O(1)$ time. This means there is a $d \in \mathbb{N}$ such that $C$ makes at most $d$ queries to $\Sigma_1$.

$C$ may make less than $d$ queries in certain execution paths. We can easily construct a conversion program $C'$ that executes $C$, keeping track of how many times an oracle query was made. Let $k$ be the number of oracle queries. $C'$ then makes $d-k$ additional oracle queries, discarding the results, returning what $C$ would have returned.

This way, there are exactly $|\Sigma_1|^d = 2^d$ execution paths for $C'$. Exactly $\frac{1}{|\Sigma_2|} = \frac{1}{3}$ of these execution paths will result in $C'$ returning $0$. However, $\frac{2^d}{3}$ is not an integer number, so we have a contradiction. Hence, no such program exists.

More generally, if we have alphabets $\Sigma_1$ and $\Sigma_2$ with $|\Sigma_1|=n$ and $|\Sigma_2|=k$, then there exists a conversion program from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ if and only if all the primes appearing in the prime factorisation of $n$ also appear in the prime factorisation of $k$ (so the exponents of the primes in the factorisation doesn't matter).

A consequence of this is that if we have a random number generator generating a binary string of length $l$, we can't use that random number generator to generate a number in $\{0, 1, 2\}$ with exactly equal probability.

I thought up the above problem when standing in the supermarket, pondering what to have for dinner. I wondered if I could use coin tosses to decide between choice A, B and C. As it turns out, that is impossible.

Dinur's proof of the PCP theorem relies heavily on the manipulation of the alphabet size.

Specifically, the overall structure of the proof is an iterative application of a graph powering technique a logarithm in the graph size number of times. On each iteration, the graph is pre-processed into a regular expanding graph, amplified by a power (which blows up the alphabet size), and then a PCP composition is applied (turning each constraint over a large alphabet into a system of constraints over a small alphabet).

The implicit goal of the process is to find a way to re-use the amplification step until the UNSAT value becomes a constant fraction (proving the PCP theorem). The key point is that unless the alphabet size is pulled back each time, the resulting graph is not what is needed for the final reduction.


Dependent Sums and Products I'm trying to understand the connections between a few different concepts fundamental to dependent type theory.

Dependent functions ($\Pi$-types)

Including non-dependent functions ($A \rightarrow B$)

Dependent pairs ($\Sigma$-types)

Including non-dependent products ($A \times B$)

Coproducts ($A + B$)

Homotopy Type Theory says the following about $\Sigma$s and $\Pi$s:

[ $\Sigma$ ] is called a dependent pair type, or $\Sigma$-type, because in set theory it corresponds to an indexed sum (in the sense of a coproduct or disjoint union) over a given type.
The name "$\Pi$-type" is used because this type can also be regarded as the cartesian product over a given type

(I don't think I fully understand this point)
In a non-dependent setting I'm accustomed to calling coproducts "sums" because the number of inhabitants of a coproduct is the sum of its constituent types' inhabitants - $|A+B| = |A| + |B|$. Likewise I call dependent pairs "products" because $|(A,B)| = |A| \cdot |B|$. Also functions can be called exponentials - $|A \rightarrow B| = |B|^{|A|}$!
Now for the question.
Why does it make sense in Type Theory to use $\Sigma$ for products and $\Pi$ for exponentials? It seems like everything is shifted between non-dependent and dependent types.

sums approximately correspond to dependent coproducts
products approximately correspond to dependent sums
exponentials approximately correspond to dependent products
what about dependent exponentials?

What's the deeper connection?

I think what's confusing you is that $A \times B$ is both a product and a coproduct:

It is the product of two factors, namely $A$ and $B$.
It is the coproduct of $A$-many copies of $B$.

Once you realize this, you will see that we can obtain $A \times B$ as both a $\sum$ and a $\prod$:

Take $P : \mathtt{bool} \to \mathsf{Type}$ where $P(\mathtt{false}) = A$ and $P(\mathtt{true}) = B$. Then
$$\sum_{b : \mathtt{bool}} P(b) \simeq A + B$$
and
$$\prod_{b : \mathtt{bool}} P(b) \simeq A \times B$$
Take $Q : A \to \mathsf{Type}$ where $P(x) = B$ for all $x : A$. Then
$$\sum_{x : A} Q(x) \simeq A \times B$$
and
$$\prod_{x : A} Q(x) \simeq (A \to B)$$

We should therefore not pay attention to $A \times B$ when deciding on a good naming scheme for these two constructs.

The dependent exponential is exactly a dependent product.


Major conjectures used to prove complexity lower bounds? Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned in the above article? Did we achieve some progress towards proving one of these conjectures? Which conjecture do you think would require completely different techniques from the currently known ones?

The unique games conjecture has recently been one of the most fruitful assumptions for proving good lower bounds, although it is more controversial than most assumptions about complexity class separation.  See On the Unique Games Conjecture for a list of consequences.