Bouziane’s transformation of the Petri net reachability problem and incorrectness This paper seems to point out that Bouziane’s solution is incorrect.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.143.9009&rep=rep1&type=pdf

In the conclusion:

  This false claim served for deriving a bound on the number of states
  of the constructed automaton – which in reality can have infinitely
  many states.

I think I understand this point as it relates to the general reachibility problem, However The Petri-Net used as an illustration contains 'loops' at transitions: t3 and t1 - transitions that have both incoming and outgoing arcs.

If Petri-Net being examined were composed of only elementary paths, the resulting witness sequence / state machine language would not be susceptible to the pumping lemma.

Does this seem accurate? why or why not?

Found another article that helped me understand:

COMPEXITY OF SOME PROBLEMS IN PETRI NETS*

http://www.sciencedirect.com/science/article/pii/0304397577900147

This paper does a good job of explaining the difference between a k-bounded Petri-Net and an unbounded one.

A Petri net is bounded if and only if it has a finite reachability set.

Bouziane’s solution applies only to bounded Petri-Nets.


Decomposing complete graphs into clique-free graphs of certain size Modified in accordance with Tsuyoshi's comment which seems to generalize.

Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no cliques of size $k$ for some $k \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

How about the case when $K_{n}$ is replaced by a bipartite $K_{m,n}$ where one seeks a partition such that there is no $K_{k,l}$ for some $k,l \in \mathbb{Z}_{+}$? What is the minimum number of partitions would I need to make?

This question is about Ramsey theory.  In the case of the complete graphs, you can take a=1 by considering partitioning into only two sets.

The Ramsey number R(k,k) is the minimum integer m such that however you partition the edges of the complete graph Km into two sets, at least one of the sets contains Kk as a subgraph.  This immediately implies that if m < R(k,k), then the edges of the complete graph Km can be partitioned into two sets so that neither set contains Kk as a subgraph.

Erdős proved that R(k,k) grows exponentially: R(k,k) > k⋅2k/2/(e√2).  This means that if m is sufficiently large, then m < R(k,k) for k = ⌈2 log2m⌉ = O(log m).  In other words, you can take a=1 with two sets.


Limits on lock-free collections? David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way.

This statement isn't very precise, but let me try to rephrase it in a slightly more formal way: For every collection type C, there exists a lock-free collection type CLF that offers the same set of operations, and where each operation on CLF has the same big-O complexity as the corresponding operation on C.

I don't expect a transformation, by the way.

Since I was myself somewhat confused, I begin by clarifying a few concepts in the question.

Collection. I see no reason to spend time rigorously defining what "collection" means when we can simply ask what happens for data structures in general. A data structure occupies a piece of memory and has some operations that may access that memory and that may be invoked by users. These users may be distinct processors or just different threads, it does not concern us. All that matters is that they may execute operations in parallel.

Lock-free. Herlihy and Boss say that a data structure is lock-free when a crashing user does not prevent further uses of the data structure. For example, imagine one pours water on a processor that is in the midst of inserting a node in a sorted set. Well, if other processors try later to insert into that sorted set, they should succeed. (Edit: According to this definition, it is the case that if a data structure uses locks then it is not lock-free, but it is not the case that if a data structure does not use locks then it is lock-free.)

With these definition, I think Herlihy and Boss basically say that the answer is to turn critical regions into transactions.

But, you may ask, does this have the same complexity? I'm not sure the question makes sense. Consider push(x) { lock(); stack[size++] = x; unlock(); }. Is this a constant time operation? If you ignore the locking operation and hence other users then you can answer YES. If you do not wish to ignore other users, then there really is no way to say whether push will run in constant time. If you go one level up and see how the stack is used by some particular algorithm, then you might be able to say that push will always take constant time (measured now in terms of whatever happens to be the input of your parallel algorithm). But that really is a property of your algorithm, so it doesn't make sense to say that push is a constant time operation.

In summary, if you ignore how much a user executing an operation waits for other users, then using transactions instead of critical regions answers your question affirmatively. If you don't ignore the waiting time, then you need to look at how the data structure is used.


Separating Logspace from Polynomial time It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$, $LogCFL$, $NC^i$, $SAC^i$, $AC^i$, $SC^i$. It is widely believed that $L \neq P$.

In one of my blog posts I mentioned two approaches (along with the corresponding conjectures) towards proving $L \neq P$. Both these approaches are based on branching programs and are 20 years apart !! Are there other approaches and/or conjectures towards separating $L$ from $P$ (or) separating any intermediate classes between $L$ and $P$.

Circuit depth lower bounds (equivalently, formula size lower bounds) are probably the most natural approach:  A Super-$\log^2(n)$ depth lower bound for a problem in $\mathsf P$ would separate $\mathsf P$ from $\mathsf L$, and the Karchmer-Wigderson communication complexity technique may be the natural one for that.


Practical approaches to solving whether programs will halt What kinds of systems are available that accept a certain program $P$ and attempts to figure out "the program does terminate" or "the program does not terminate" and output a proof of one or the other?

Yes, an example of a system that performs this task is T2. It does not solve the halting problem but instead it only attempts to solve certain special cases. A overview is at https://en.wikipedia.org/wiki/Microsoft_Terminator . The newest version of this system is at https://mmjb.github.io/T2/ .


Upperbound on the degree of a boolean function in terms of its sensitivity A very interesting open problem in the study of complexity measures of Boolean function is the so called sensitivity vs block sensitivity conjecture. For background on sensitivity versus block sensitivity you can look at the following blogpost of S. Aaronson at http://www.scottaaronson.com/blog/?p=453.

To best of my knowledge, the best upper bound known on $bs(f)$ in terms of $s(f)$ is $bs(f)=O(e^{s(f)}\sqrt{s(f)})$. [Kenyon, Kutin paper] But of course maybe it is more convenient to relate $s(f)$ to some other complexity measure of $f$ say $\deg(f)$, the degree of $f$ as polynomial over $\mathbb{R}$, i.e. the size of its highest Fourier coefficient.

The question is what's the best upper bound known on $\deg(f)$ in terms of $s(f)$?

This paper came up on the arXiv today and it improves on the upper bound on $bs(f)$ in terms of $s(f)$. They prove the following bound:

$$
bs(f) \leq 2^{s(f)-1}s(f).
$$

This along with the connection that Marcos mentioned in his comment should give better bounds than previously known.


Questions about computing matrix rigidity Matrix rigidity was introduced by Valiant in 1977:

The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the
smallest number of entries of $M$ that must be changed in order to
reduce its rank over GF(2) down to $r$.

$Rig_M(r)$ has a deep connection to boolean function complexity & circuit lower bounds by a result of Razborov 1989 see eg [1]. It also has a connection to finding locally correctable codes eg see [2]
It appears to me there is little to no published empirical analysis of $Rig_M(r)$ & that it could give some useful insight into its properties (thinking for example of the transition point research with SAT).
As a start I was interested in analyzing $Rig_M(r)$ using a simple greedy algorithm. The idea is as follows.

generate random matrixes $M$.

Compute Delta_row(i,j) where i,j are row (vectors) of $M$ and Delta_row(i,j) is the Hamming distance between the two rows

likewise calculate the Delta_col(i,j) where i,j are column vectors of $M$ (equivalent to calculating Delta_row(i,j) of the transpose of M).

next sort Delta_row(i,j) and Delta_col(i,j) and remove the column or row from $M$ with the "lowest value". (the lowest value is associated with a row or column pair, remove either row or column of the pair).

This greedy algorithm can be used to estimate $Rig_M(r)$ by giving a (fairly tight?) upper bound. One repeatedly reapplies the greedy algorithm until the matrix $M$ has been reduced to size $r$ and counts the sum of the Delta_row/col values of removed rows. and note that upon removing rows or columns, the new Delta_row and Delta_col arrays can be computed efficiently without recalculating the whole arrays.

how far off can the greedy algorithm be from the optimal value $Rig_M(r)$?

what kind of matrices maximize the difference between the greedy algorithm and the optimal rigidity measure?

can a modified local greedy algorithm find the optimal value $Rig_M(r)$

[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"
[2] On matrix rigidity and locally self-correctable codes by Zeev Dvir
[3] ECCC reports tagged matrix rigidity
[4] Matrix rigidity talk/overview by Mahdi Cheraghchi
[5] The geometry of matrix rigidity by Landsberg et al
[6] Blog note on Midrijanis paper on Matrix rigidity by Lance Fortnow
[7] Empirical results in CS papers

The following additional references on Matrix Rigidity may be helpful:

Complexity Lower Bounds using Linear Algebra, S. V. Lokam,
in Foundations and Trends in Theoretical Computer Science, Volume 4, 1-2, 2009.
http://dx.doi.org/10.1561/0400000011
Using Elimination Theory to construct Rigid Matrices, A. Kumar, S.V. Lokam,. V. Patankar, J. Sarma,
ECCC TR09-106, http://eccc.hpi-web.de/report/2009/106/


Does the first order theory of a finite structure have bounded quantifier rank? Let $\mathfrak{A} $ be any finite structure.
Does its first order theory $ \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) $ have bounded quantifier rank, in the sense that there is a $ q\in\mathbb{N} $ such that for all $ \varphi\in\mathfrak{T} $ with $ qr(\varphi) > q $ there is a $ \varphi'\in\mathfrak{T} $ with $ qr(\varphi')\leq q $ and $ \varphi'\equiv\varphi $ ?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after which all quantifiers of the original formula can be simulated by conjunctions and disjunctions. In particular, the number of quantifiers (hence quantifier rank) is bounded by the size of the structure.


For which algorithms is there a large gap between the theoretical analysis and reality? Two ways of analyzing the efficiency of an algorithm are

to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.

I wonder if there are known cases where there is a significant gap between (1) and (2). By this I mean that either (a) the experimental data suggests a tighter asymptotic or (b) there are algorithms X and Y such that the theoretical analysis suggests that X is much better than Y and the experimental data suggests that Y is much better than X.

Since experiments usually reveal average-case behavior, I expect most interesting answers to refer to average-case upper bounds. However, I don't want to rule out possibly interesting answers that talk about different bounds, such as Noam's answer about Simplex.

Include data structures. Please put one algo/ds per answer.

The most glaring example is of course the Simplex method that runs quickly in practice, suggesting poly-timeness, but takes exponential time in theory.  Dan Spielman just got the Nevanlinna award to a large extent for explaining this mystery.

More generally, many instances of Integer-programming can be solved quite well using standard IP-solvers, e.g. combinatorial auctions for most distributions attempted on significant sized inputs could be solved -- http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf


Covering a binary relation as a union of rectangles Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\subset Y$, and I don't care whether the $X_i$ are disjoint, whether the $Y_i$ are disjoint, or whether the $X_i\times Y_i$ are disjoint. (I'm calling each $X_i\times Y_i$ a "rectangle" but there's no geometry here, just sets.)
If I think of this as a generic set cover problem, then it looks like it might be NP-hard. (With respect to what variable though, $|R|$ maybe?)
But I'm really hoping that this version of the problem, using these really "nice" rectangular covering sets that intersect in predictable ways, might be easier. What is known about this problem? Does it have a standard name and a nice theory behind it? Maybe if we think of $R$ as a matrix or a bipartite graph...?
For what it's worth, in practice I'm interested in what I suspect are fairly easy problem instances, where $|X|\leq 15$, $|Y|\leq 15$, typically $|R|\leq 70$, and the optimal $n$ is probably $\leq 4$. I haven't tried greedy search yet, because I'm hoping for an even simpler solution.

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions.
Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p


The meaning of: a program P posseses a property R I am reading an article called The temporal semantics of concurrent programs
.

A construction is then given for assigning to a program P a temporal
formula W(P) which is true on all proper execution sequences of P.
In order to prove that a program P posseses a property R, one has only
to prove the implication $$W(P)\supset R$$
My question is this: Didn't they get the containment the other way
around ?

If I understand correctly, a property,R, is a set of traces, for P
to hold the property each trace of P needs to be in R, hence $$W(P)\subset R$$
Do I understand something wrong here, or is there a mistake in the

I cannot see the article and have to guess. The text makes clear that they are using the symbol $\supset$ as notation for implication. So you could read it as

  In order to prove that a program $P$ possesses a property $R$, one has only to prove the implication
  $W(P) \implies R$.

See the Wikipedia page on material implication for other notation for implication.


Theoretical results for random forests? Random forests have a reputation among practitioners of being among the most effective classification techniques. Yet we don't encounter them much in the learning-theoretic literature, from which I surmise an absence of deep theoretical results. If one wanted to delve into this theory, where would one start?

I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references:

Empirical comparisons of different RF simplifications that allow proving theorems:  Narrowing the Gap: Random Forests In Theory and In Practice

This is the newest reference I can provide. In this paper you can also find some citations of Biau's papers about initial work on theoretical results for RF.

If you are interested in theoretical results about variable importance in RF: Understanding variable importances in forests of randomized trees

Actually I just found out that last paper's author (Gilles Louppe) just posted on arxiv his PhD thesis (v2): Understanding Random Forests: From Theory to Practice


Which model of computation to simulate to prove universality? I am starting out in theoretical computer science.

I have a model of computation based on observations of auto-associative memory in the brain.  I believe (with little evidence) that I can do anything in this simple model.  I understand the primary way of proving universality is to show that your model can simulate another universal model, especially a turing machine.

I would like to request the following information:

References to clear and easy to follow proofs of universality of a computational model, graspable by an able beginner such as myself.
Guidance as to what model would be easiest model to attempt to simulate.  I imagine the answer to this may be 'it depends'.  Currently it appears my model bears some semblance to lambda calculus.

There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, Computability and Unsolvability. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.


Is Degrees Of Separation NP Complete? I'm doing a bit of research on doing social analysis between so called "hub" people.  Basically what I want to try to do is determine the shortest paths between two individuals.  The problem is that while there are relatively few individuals (a few hundred at most), there are a LOT more connections between the nodes (and several categories of connections).  So while a graph may have 100 nodes, there may be tens of thousands of connections (Some of which are redundant).

Now, what we want to try to do is show the relationships from each individual to each other.  So for example, if you pick person A, show all of their first degree relationships.  Then show all second degree relationships, etc until all the relationships are shown.

There may be as many as 1000 nodes and 100,000 connections, but I don't think too much more than that.  Are there any simple algorithms available for this, or would pre-computing unique permutations (via a Map-Reduce style system) be my best bet?

Am I right by thinking this problem is a NP problem (I don't think it's NP-Complete, but it might by NP-Hard)?

Thanks

You can create a table with the degrees-of-separation between every two users by doing a BFS or DFS from each node and recording the length of the shortest path to each node you reach as you get there (sometimes replacing a larger value with a shorter one through a different path you explored later). That's definitely polynomial time (O(|V|^2 + |V|*|E|)), but that's not to say it's cheap to do.


Expander Graph from Hypergraph I came up with this problem while thinking about an optimizing compiler.

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

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

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

This is not an answer but is too long for a comment:

The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions of expansion you can choose for hypergraphs/simplicial complexes. For one of these notions (based on the spectrum of an adjacency matrix of the hypergraph), this is mentioned as an open problem in the conclusion of this thesis.


Minimize in polynomial time a super-additive increasing function under linear constraints? I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):

Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$),
$$
\min \sum_{i=1}^n f(y_i)
$$
under the constraints
$$
Ay \geq b
$$

To answer to Peter Shor's comment, we are trying to find the vector $y=(y_1,\cdots,y_n)$, $A$ is a $n\times n$ matrix. We suppose that $k$ is a constant.

I am particularly interested in the case where $f$ is a piecewise linear function, not continuous ($\exists (a_1,\cdots,a_k),0<\alpha_1<\cdots<\alpha_k) $, such that $\forall x\in ]a_i,a_{i+1}], f(x) = \alpha_{i+1}x$).

It seems to me that the ellipsoid algorithm could work for those special functions, but I have not been able to find any references, maybe because either this is a sub problem of a known problem? Note that I am trying to solve this for any rational values.

(Note that this is a sub-question of What classes of mathematical programs can be solved exactly or approximately, in polynomial time?)

The problem as presented is NP-hard.

Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y > 1$. Now if we have the constraints $y_1 + y_2 \geq 2.01$ and $y_i \geq 0$, and we want to minimize $\sum_i f(y_i)$, clearly we should choose one of these $y_i$ to be $1$ and one to be $1.01$.

Now, suppose we have a graph $G$, and we put a constraint like this for every edge. Replace $2.01$ by $2 + \epsilon$ for a sufficiently small $\epsilon$. (You don't even need to do this, because vertex cover has an inapproximability result.) To minimize the objective function, we want to find the minimum number of vertices that hit every edge. This is the minimum vertex cover problem, and it is NP-complete.

The only reason that this isn't exactly your problem is that the matrix $A$ is not square, because the number of variables is the number of vertices in $G$, and the number of equations is the number of edges in $G$. But you can always add dummy vertices that don't participate in the equations to make $A$ square.

Possibly your real problem has more structure so that this NP-completeness proof doesn't apply. Maybe if you told us more about the real problem, it might be solvable in polynomial time.

For convex $f$, this should be solvable in polynomial time ... see Chandra's comment.


High-level overview of Razborov's method of approximations What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind it?

Let $f$ be a Boolean function on $n$-bits. Let $Z = f^{-1}(0) \subseteq 2^n$. Let $C$ be circuit on n bits and of size $m$ and gates $g_1, \ldots, g_m$. $g_i$ also denotes the function on $n$-bits computed by subcircuit with $g_i$ as the last gate. The first $n$ gates are for the input $x_1, \ldots, x_n$. The goal is to show that $C$ of size $m$ cannot compute $f$. Consider all computations of $C$ on inputs from $Z$. A computation assigns values to outputs of gates. Let $B$ be the Boolean algebra of $P(Z)$.

The idea is to consider for any function  $g$ on $n$-bits how well it approximates $f$ on $Z$. Let $||g|| = \{w \in Z \mid g(w) \neq 0 \}$.

For an ultrafilter $F \subseteq B$ we can define a new computation by ultraproduct from it: $c(g_i) = 0$ iff $||g_i|| \not\in F$. Because an ultrafilter is essentially a set of consistent computations for 0 values the resulting $c$ is a valid computation. It would follow that $f(c_1, \ldots, c_n) = 0$. We created a new computation from existing ones. Since all ultrafilters on finite sets are principal $c_1,\ldots,c_n \in Z$. This works for any circuit, we have not exploited the fact that the circuit is of size $m$.

The next idea is now to exploit the finiteness of the circuit to construct a new input that is outside $Z$ and $f(w) \neq 0$ but the circuit does not notice because of its limited size and therefore still outputs 0. So it does not compute $f$.

We need to relax the definition of ultrafilter so that we can get an input outside $Z$. In place of ultrafilters we use upward-closed subsets of $B$ ($a \in F$ and $a \subseteq b$ implies $b \in F$) that preserve meets($a,b \in F$ implies $a \cap b \in F$).

Let $W_F = \{w \in 2^n \mid w_i = 0 \to ||\lnot x_i|| \in F, w_i \neq 0 \to ||x_i|| \in F\}$. $W_F$ is the set of inputs consistent with $F$. If $F$ is prime ($a \cup b \in F$ implies $a \in F$ or $b \in F$) and nonfull ($\emptyset \not\in F$) then for each $i$, $F$ contains either  $||x_i||$ or $||\lnot x_i||$ and $W_F$ contains only a single input.

We are going to relax preservation of meets. In place of all meets in the Boolean algebra we will preserve a small number of them. Let $|f|$ be the smallest number $k$ of meets $M = (a_1 \cap b_1, \ldots, a_k \cap b_k)$ such that for all upward-closed, nonfull, $M$-preserving $F$, $W_F \subseteq Z$.

Let $m$ be the circuit complexity of $f$. Razborov proved that $\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$.

Note that this inequality holds for all functions. To prove a circuit size lower bound $m$ show that for all $m$-meets $M$, there is a $F$ that satisfies the conditions but its $W_F$ is not contained in $Z$. Moreover any strong circuit lower bound can be proven by this method because of the second inequality.

The actual part of a circuit lower bound proof is to show that for given $m$, for any $m$-meets there is such an $F$. In the case of monotone circuits the condition about $W_F$ simplifies to $w_i \neq 0 \to ||x_i|| \in F$ so coming up with $F$ is easier.

Alexander Razborov, On the Method of Approximation, 1989.
pdf

Mauricio Karchmer, On Proving Lower Bounds for Circuit Size, 1995.

Tim Gowers, Razborov's method of approximation, 2009. pdf


Generalized Secretary Optimization Problem In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates.  I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar game:

The goal is to maximize the net score.  Each candidate has a value that (if hired) would be added to the score.  And each day that goes by without hiring a candidate costs the company 1 point of score.  Starting score is 0.

Each day, the company either interviews a new candidate or attempts to hire a previously interviewed candidate.  The value of the candidate is discovered during the interview and is uniformly distributed between $0$ and (known) $v$.  There is an unlimited number of possible candidates to interview.

If the job is offered to a candidate, then the candidate will accept with a probability of $d^k$ for (known) constant $d$ and $k$ being the number of days since the candidate was interviewed.  You may only attempt to hire a candidate once.

So the question is: what is the best strategy for this game given $v$ and $d$?  Other natural questions: what is the best strategy if $v$ and/or $d$ are unknown?

Any insights, answers, or references to similar games would be appreciated.

Let's assume the first strategy is the best until someone comes up with a better one, ok?

So we set a threshold for value (between 0 and v). If the value of the candidate is higher than the threshold, try to hire that candidate. Otherwise, interview the next candidate. If we interview several candidates in a row whose value is below the threshold, decrease the threshold until future candidates are likely to have a higher value. If d is low and the candidates decline offers, lower the threshold further.

A few points to determine: the first threshold for value. It's probably ok to wait a few days and just interview candidates so we can see what kind of values they have. Then set a threshold so that 50% (or 20% or 80% or whatever%) of the candidates have higher values.

Another point to determine: when we fail to hire a secretary, how frequently and how much should we lower the threshold.

If v is unknown, we obviously have to observe a few values before making good guesses for a good threshold.

If d is unknown, we'll have to try to hire a few candidates before tuning the algorithm.

What was not mentioned in the question:

How long does it take for the candidate to accept or decline the job offer?
Is the game over when the first candidate accepts the offer?
Can you play the game n times?

If you can't choose the candidates for the interview it seems like winning this game is a matter of coincidence but I might be wrong.


Programming languages for efficient computation It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard complexity class. In particular, we can define a language in which we can express all efficient computations and only efficient computations.

For instance, for something like $P$: take your favorite programming language, and after you write your program (corresponding to Turing Machine $M'$), add three values to the header: an integer $c$, and integer $k$, and a default output $d$. When the program is compiled, output a Turing machine $M$ that given input $x$ of size $n$ runs $M'$ on $x$ for $c n^k$ steps. If $M'$ does not halt before the $c n^k$ steps are up, output the default output $d$. Unless I am mistaken, this programming languages will allow us to express all computations in $P$ and nothing more. However, this proposed language is inherently non-interesting.

My question: are there programming languages that capture subsets of computable functions (such as all efficiently computable function) in a non-trivial way? If there are not, is there a reason for this?

One language attempting to express only polynomial time computations is the soft lambda calculus. It's type system is rooted in linear logic. A recent thesis addresses polynomial time calculi, and provides a good summary of recent developments based on this approach. Martin Hofmann has been working on the topic for quite some time. An older list of relevant papers can be found here; Many of his papers's continue in this direction.

Other work takes the approach of verifying that the program uses a certain amount of resources, using Dependent Types or Typed Assembly Language.

Yet other approaches are based on resource bounded formal calculi, such as variants of the ambient calculus.

These approaches have the property that well-typed programs satisfy some pre-specified resource bounds. The resource bound could be time or space, and generally can depend upon the size of the inputs.

Early work in this area is on strongly normalising calculi, meaning that all well-typed programs halt. System F, aka the polymorphic lambda calculus, is strongly normalising.  It has no fixed point operator, but is nonetheless quite expressive, though I don't think it is known what complexity class it corresponds to. By definition, any strongly normalising calculus expresses some class of terminating computations.

The programming language Charity is a quite expressive functional language that halts on all inputs. I don't know what complexity class it can expression, but the Ackermann function can be written in Charity.


An equation relating Time complexity, Space complexity, and entropy of output Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship between the three, something like $E=f(T+S)$ where $E$ is shannon entropy of the output, $T$ is time, $S$ is space, and f is a linear function or something like that. The main argument being that any function can be written as a hash map that takes its input to its output. This hashmap could be compressed based on its entropy.

I have a hunch that the only way to decrease the space an algorithm uses more than that is to increase the time complexity, as if the hashmap is moved onto a time axis instead of a space one. Is this crazy? Has there been any research done on this subject?

Edit for clarification: What I mean by "entropy of the output of a function" is this. Assume a function $g$ takes as input a bit string $x$ and outputs a message $y$. Now $g$ can thought of a source who's $x$th output is $y$. By "entropy of the output" I mean the shannon entropy of $g$ when thought of as a source.

Again, the argument is that $g$ can be implemented using a hash map in exponential space but in $O(1)$ time. However, I have a hunch that it seems reasonable that this space complexity can be reduced based on the entropy of $g$ (i.e. the entropy of the hashmap) and still maintain $O(1)$ time, essentially by compressing the hash map.

Beyond this reduction I also have a hunch that that you can decrease the space further, but in doing so you have to increase time proportionally. The idea being that you can't actually compress the information in the hash map any more than you already have (even when you compress using other measures of entropy like kolmogorov complexity), you can just "move" it along the time axis.

(Too long for a comment.)

There are two aspects to your question. There is the idea of a time-"space" tradeoff, and the idea of entropy as a measure or bound for how hard this tradeoff must be for a problem. Both aspects have some issues relating to how theorists usually study these problems. Here is why and some suggestions.

Regarding entropy: This is an interesting idea but either wrong or hard to formalize for several reasons. Notice that a program that just spits out a long sequence of independent bits (whether it produces them or reads them from an input) has very high entropy but is also very simple. Its running time and space requirements are minimal. And in general there are deterministic algorithms with 0 entropy that solve very difficult problems on both time and space axis. Finally, many problems of theoretical interest are decision problems where the output is just one bit.

So entropy seems unrelated at least from usual perspectives, and you have to think it through more or else switch to a notion like Kolmogorov complexity (e.g. compressibility of the truth-table of a decision problem or something).

Regarding time-space tradeoffs: It's hard to reconcile your ideas with what we traditionally call space-time tradeoffs, which refer to time and memory usage of an algorithm starting from scratch (unlike your hashtables etc). It is studied but very, very hard. You are asking to go even farther and relate this tradeoff to some other notion of complexity of the problem, so we are probably even farther from those results (maybe not in some specific domain?).

However, I do think your intuition can be captured by complexity classes involving "advice". For instance, P/poly are problems solved by polynomial time algorithms with access to polynomial-length advice strings. You seem to be observing that all problems are in O(n)/EXP: trivial linear-time algorithm, or constant time in word RAM model, that has access to a lookup table for all answers. Whereas the problem might not be in P/poly or might not be in Exp/O(1) or so on. We trade off advice space for running time. I don't know of work on this -- I'm not an expert so maybe it exists, but it sounds hard. A general theorem relating this tradeoff to a measure of complexity of the problem would be very cool, but even harder.


why are the constraints in the following paper tight? My question is about the following paper:

http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf

In section 2 they show Equation 3 (which is just an optimization problem), which they transform into the optimization problem right before section 3. Everything is very easy to read and self-contained. However, I do not understand how they can tell so easily that the constraints in the convex program are tight (which allows them to transform the program to the one before section 3). Are they relying on some result that they are not saying, or is this a very simple argument coming from optimization?

An edit, following a request to rewrite the question in a self-contained way.
Let $w \in R^d$ and $y_i \in R^d$ and $A_i$ be a finite set of vectors in $R^d$.
Consider the following optimization problem:

$\min_{w,\xi} ||w||_2^2 + \sum_i \xi_i$

under the constraints that $\forall i$ we have $w^T y_i + \xi_i \ge \max_{y \in A_i} \left( w^T y \right)$

why in any solution of this optimization problem, the constraints are tight, so that we can reformulate the optimization problem by replacing $\xi_i$ with $\max_{y \in A_i} \left(w^T y \right) - w^T y_i$ and get rid of the constraints?

Well, if any constraint is loose you can just decrease the corresponding $\xi_i$ until the constraint becomes tight, in which case you are only decreasing the objective value and get a better solution.


Relation between computational complexity and information I work in a computational neuroscience lab that quantifies the mutual information between pairs or groups of neurons. Recently, the boss his shifted focus to measuring the "complexity of neural dynamics". In pursuing that line of research, some people in my group appear to equate "complex" with "has a high entropy".

Can anybody guide me on what the relationship is between computational complexity (in a CS sense) and entropy in the information theory sense?

To explain a bit further, measures like Lempel-Ziv complexity, don't seem, to me, valid measures of complexity because they conflate informative (to the user) with carrying a lot of bits. Other measures, like [Causal State Splitting Reconstruction][1] are much less known but have the appealing property that random processes have zero complexity, because zero hidden states are needed to represent a stationary random process.

There are enough connections between information theory and computational complexity to merit a graduate course, e.g. this one: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/


Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other? Let the variables be $x_1 , x_2 , x_3 ... x_n$.  The distance between two variables is defined as $d(x_a , x_b) = |a-b|$.  The distance between two literals is the distance between the corresponding two variables.

Suppose I have a 3-SAT instance such that for every clause $(x_a , x_b, x_c)$ we have $d(x_a , x_b) \leq N \wedge d(x_a , x_c) \leq N \wedge d(x_b , x_c) \leq N$ for some fixed value $N$.

Conceptually you can picture this as all the literals being physically on a line and all the clauses are incapable of reaching beyond a certain length for physical reasons.

Given this constraint are there any hard instances of 3-SAT? How small can I make the neighborhood and still find hard instances? What if I allow a few clauses to violate the constraint?

By hard I mean a heuristic solver would fall back on the worst case.

No.  If the 3-SAT instance has $m$ clauses, then you can test satisfiability in $O(m 2^N)$ time.  Since $N$ is a fixed constant, this is a polynomial-time algorithm that solves all instances of your problem.

The algorithm works in $m$ stages.  Let $\varphi_i$ denote the formula consisting of the clauses that use only variables from $x_1,\dots,x_i$.  Let $S_i \subseteq \{0,1\}^n$ denote the set of assignments to $x_{i-N},x_{i-N+1},\dots,x_i$ that can be extended to a satisfying assignment for $\varphi_i$.  Note that given $S_{i-1}$, we can compute $S_i$ in $O(2^N)$ time: for each $(x_{i-N-1},\dots,x_{i-1}) \in S_{i-1}$, we try both possibilities for $x_i$ and check whether it satisfies all clauses from $\varphi_i$ that contain the variable $x_i$; if so, we add $(x_{i-N},\dots,x_{i})$ to $S_i$.  In the $i$th stage, we compute $S_i$.  Once we have finished all $m$ stages, the 3-SAT instance is satisfiable if and only if $S_m \ne \emptyset$.  Each stage takes $O(2^N)$ time, and there are $m$ stages, so the total running time is $O(m 2^N)$.  This is polynomial in the size of the input, and thus constitutes a polynomial-time algorithm.

Even if you allow a fixed number of clauses to violate the constraint, the problem can still be solved in polynomial time.  In particular, if $t$ counts the number of clauses that violate the constraint, you can solve the problem in $O(m 2^{(t+1)N})$ time, by first enumerating all possible values for the variables in those clauses, then continuing with the algorithm above.  When $t$ is a fixed constant, this is polynomial time.  There may be more efficient algorithms.


What are the must-read search trees paper? I would like to ask a help from researchers who conduct a research in an area of search trees. Could you please write the list of the must-read papers and most recent papers which are important to read
if I want to write papers about search trees.

I personally has the following list of papers (It's nonuniform, quite old and affects different topics. There is also a huge amount of papers about finger search tree but I didn't write references to them).
Thank you for help.

Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (July 1985), 652-686. DOI=http://dx.doi.org/10.1145/3828.3835
Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (June 1983), 362-391. DOI=http://dx.doi.org/10.1016/0022-0000(83)90006-5
Scott Huddleston and Kurt Mehlhorn. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 2 (June 1982), 157-184. DOI=http://dx.doi.org/10.1007/BF00288968
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu. 2009. The geometry of binary search trees. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 496-505.
Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased Search Trees. SIAM Journal on Computing 1985 14:3, 545-568
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak:
Self-Adjusting Binary Search Trees: What Makes Them Tick? ESA 2015: 300-312

Since I conducted research in area of fast concatenation of search trees:

Haim Kaplan and Robert E. Tarjan. 1996. Purely functional representations of catenable sorted lists. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96). ACM, New York, NY, USA, 202-211. DOI=http://dx.doi.org/10.1145/237814.237865
Purely Functional Worst Case Constant Time Catenable Sorted Lists. Lecture Notes in Computer Science.  Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas.  Algorithms – ESA 2006, Chapter 18, 172-183. Berlin, Heidelberg.  http://link.springer.com/10.1007/11841036_18

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list.
There is a lot of other recent work related to splay trees and dynamic optimality, for instance:

Applications of forbidden 0-1 matrices to search tree and path compression-based data structures, Seth Pettie, SODA 2010
An O (log log n)-competitive binary search tree with optimal worst-case access times, Bose et al, SWAT 2010
Upper bounds for maximally greedy binary search trees, Kyle Fox, WADS 2011.
De-amortizing binary search trees, Bose et al, ICALP 2012
Pattern-avoiding access in binary search trees, Chalermsook et al, FOCS 2015
Weighted dynamic finger in binary search trees, Iacono and Langerman, SODA 2016

On more classical lines, I think

Rank-balanced trees, Haeupler, Sen, and Tarjan, ACM TALG 2015

is worth including as an elegant unification of AVL and red-black trees.


A metric space on Turing machines Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \Sigma^*$. Define a metric on the set of equivalence classes as folows:
Let $R>0$ be some big number. $d(A,B) = \sup_{w\in \Sigma^*} | t_A(w) -t_B(w)|$ If this number is bigger than $R$, set $d(A,B) = R$. This defines a complete metric space on the set of equivalence classes of $X^L$.  Let $f:X^L \rightarrow X^L$ be the function which to each equivalence class of dTM maps it to its "linear speedup-theorem"-Machine. Suppose that for each machine $M$ we have: $t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$. Then this map $f$ is a contraction. By the banach fix-point theorem there must exist an equivalence class $M$ such that $f(M) = M$ . But then $t_M(w) = t_{f(M)}(w) = 1/2 t_M(w) + |w| + 2$ and we get $t_M(w) = 2 |w| + 4$. However this seems very absurd. Does it contradict something known? The only assumption which I made is that we have equality instead of $\le$ in the linear speedup theorem.

The map $f$ is not a contraction.  To see why, let's take for concreteness $R = 100$.  Suppose $w$ is a word and $A,B$ are two machines such that $t_A(w) = 200$ and $t_B(w) = 400$.  Then $d(A,B) = 100$.  Now $t_{f(A)}(w) = 100 + |w| + 2$ and $t_{f(B)}(w) = 200 + |w| + 2$, so $|t_{f(A)}(w) - t_{f(B)}(w)| = 100$ and $d(f(A),f(B)) = 100$ also.  But to have a contraction in the sense of the Banach fixed point theorem (also called a strict contraction) you need to have a constant $c < 1$ such that $d(f(A), f(B)) \le c d(A,B)$, so this can't be achieved.


Does Karp reducibility yield a total order? Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?

Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (K. Ambos-Spies, Sublattices of the polynomial time degrees, Inform. & Control 65(1):63-84, 1985).


Proof refutation: Amateur reviews of ambitious CoRR papers I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I just need to improve my plausibility checks. Here is a recent sample of such papers:

Uniqueness Trees: A Possible Polynomial Approach to the Graph Isomorphism Problem
On the Group and Color Isomorphism Problems
Multiplicative weights, equalizers, and P=PPAD
NP vs PSPACE

After detailed reading, I often end up with the conclusion that the approach is interesting and might have some merit, but that it is insufficient to reach to huge ambitious goal announced or hinted at in the abstract. I sometimes write the authors of such papers my thoughts, but the typical reaction is to totally ignore my email such that I don't even know whether a spam filter eliminated it before reaching the author, the best reaction is an "thanks for your kind words, I'm used to much more insulting feedback". Being totally ignored feels bad, but maybe it is an appropriate reaction to "proof refutation"?

Are there good ways or places to post general feedback on "arbitrary ambitious CoRR papers"? What else can I do after I invested the effort to read such a paper? (And the hypothetical question: What could I do if I came to the conclusion that the result announced in the abstract is indeed correct?)

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks.

You even get a mild form of peer review for your posts, since they write:

  Because of widespread Trackback spam we have a semi-automated editorial process that approves trackbacks for display.

As for where to post your review, Recent trackbacks currently returns a mix of blogs, magazines, and news sites.


How many distinct colors are needed to lower-bound the choosability of a graph? A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\in f(v)$, and such that, for all edges $vw$, $c(v)\ne c(w)$.

Now suppose that a graph $G$ is not $k$-choosable. That is, there exists a function $f$ from vertices to $k$-tuples of colors that does not have a valid color assignment $c$. What I want to know is, how few colors in total are needed? How small can $\cup_{v\in G}f(v)$ be? Is there a number $N(k)$ (independent of $G$) such that we can be guaranteed to find an uncolorable $f$ that only uses $N(k)$ distinct colors?

The relevance to CS is that, if $N(k)$ exists, we can test $k$-choosability for constant $k$ in singly-exponential time (just try all $\binom{N(k)}{k}^n$ choices of $f$, and for each one check that it can be colored in time $k^n n^{O(1)}$) whereas otherwise something more quickly growing like $n^{kn}$ might be required.

Daniel Král and Jiří Sgall answered your question to the negative. From the abstract of their paper:

  A graph $G$ is said to be $(k,\ell)$-choosable if its vertices can be colored from any lists $L(v)$ with $|L(v)| \ge k$, for all $v\in V(G)$, and with $|\bigcup_{v\in V(G)} L(v)| \le \ell$. For each $3 \le k \le \ell$,
  we construct a graph $G$ that is $(k,\ell)$-choosable but not $(k,\ell+1)$-choosable.

So, $N(k)$ does not exist if $k\ge 3$. Král and Sgall also show that $N(2)=4$. Of course, $N(1)=1$.

Daniel Král, Jiří Sgall: Coloring graphs from lists with bounded size of their union. Journal of Graph Theory 49(3): 177-186 (2005)


Counting the number of thick regions which overlap a square Let $S$ be a unit square.
As a function of $\beta$, what is the maximum number of $\beta$-fat pairwise-disjoint regions with diameter at least 1 which can intersect $S$?

Below, we give a figure showing that for $\beta=1$, the maximum number is 7. What about for $\beta = 2, 3, \ldots, n$?

Recall the definition of fat for regions in the plane. Given a region $R$, let circle $C_1$ of radius $r_1$ be the largest circle contained in $R$, and let circle $C_2$ of radius $r_2$ be the smallest circle that contains $R$. The fatness of $R$ is given by $\frac{r_2}{r_1}$, and we say that $R$ is $\beta$-fat, for $\beta = \frac{r_2}{r_1}$.

For example, if $r_2 = r_1=\frac{1}{2}$, then the regions are unit circles, and there are at 7 circles with diameter at least 1 which can overlap $S$ without overlapping each other.
In the figure below, we have depicted a unit square and 7 unit circles which overlap the square.

I think that the maximum number of pairwise disjoint fat regions which overlap the square should be strongly related to circle packing.

The worst-case shape for a region is something like a "ball & chain". Below I have depicted such a region for $\beta=2$ with diameter 1

.

and these can pack within distance 1 of the unit square obviously much more tightly than I've depicted them.

Note that the actual ball & chain region is defined by the green area, and the outer circle is just a guide to depict the fact that these regions have fatness 2. In fact, the chain part of the region, can "bend" to allow more regions to be packed.


Complexity of finding a second solution given a correct solution to an NP-complete problem I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem.  More precisely, I'm interested in any problems of the following form:

Given a solution $S$ to an instance $I$ of an NP-complete problem, is there a solution $S' \neq S$ to $I$?

Any examples of problems of this sort, both NP-complete and not, or general work, or even a what this sort of problem is called (so I can properly do my own searching) would be appreciated.

Another question addresses this issue specifically as pertaining to SAT.

I hope I'm not asking something really basic; there don't seem to be any examples in Garey and Johnson of this kind of thing.

Thanks
Mark C.

The question seems to be solved while I was writing this answer, but let me post my answer anyway.

Yato and Seta [YS03] (both are my colleagues when I was a student) propose a general framework to prove the NP-completeness of this kind of problems, where they are called Another Solution Problems or ASPs, and prove the NP-completeness of the ASPs of many puzzles.  They consider a restricted notion of reductions between relation problems called ASP reductions, and show that the NP-hardness of ASPs is preserved under ASP reductions and show that many known reductions can be in fact viewed as or modified to ASP reductions between natural relation problems.

[YS03] Takayuki Yato and Takahiro Seta.  Complexity and completeness of finding another solution and its application to puzzles.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.


Computing any information about Max-3SAT For a 3CNF formula $C$ let $M(C)$ be the maximal number of satisfied clauses in any assignment to $C$. It is known that Max-3SAT is hard to approximate (subject to P≠NP), i.e. there is no polytime algorithm whose input is a 3CNF formula $C$, and whose output is the number $M'$ such that $M(C)$ is within a multiplicative factor $1+c$ from $M'$, where $c>0$ is an absolute positive constant.

I believe that it is also NP-hard to compute $M(C) \bmod p$ for any constant modulus $p$. I wonder if the following common generalization of these two facts is true: There is no polytime algorithm whose input is a 3CNF formula $C$ with $N$ clauses, and a string of $\log_2 N-B$ advice bits, and whose output is $M(C)$. Here $B$ is an absolute constant. In plain words, there is no algorithm that computes $B$ bits of information of $M(C)$.

I apologize if the question has a well-known answer, for I am not a complexity theorist by the way of background.

Here is an argument that if you could solve Max 3SAT on an m-clause instance given a constant number of bits of advice, then the polynomial hierarchy would collapse.

Fix an NP-complete problem L. From Cook's theorem, we know a transformation f() of inputs x for L into 3SAT formulas f(x), so that

1) if $x\in L$ then $M(f(x)) = m$

2) if $x\in L$ then $M(f(x)) = m-1$

where $m$ is the number of clauses in $f(x)$.

We also have a theorem of Kadin, that says that, if given $k$ inputs $x_1,\ldots,x_k$ of an NP-complete problem, you have a polynomial time algorithm that makes $\leq k-1$ queries to an NP oracle and determines the correct answer to the $k$ NP problems $x_i \in ? L$, then the polynomial hierarchy collapses.

Suppose we have an algorithm that solves Max SAT on m-clause inputs given k bits of advice. We will use Hastad's result to construct an algorithm as in the premise of Kadin's theorem.

Start from the $K=2^k+1$ inputs $x_1,\ldots,x_K$ to problem $L$. Apply Cook's theorem to each of them. After some normalization (which can be done by assigning weights to the clauses, or duplicating them if we do not want to use weights), we construct $K$ formulas $F_1,\ldots,F_K$ where, for a certain $m$:

1) $M(F_1)= m-1$ if $x_1 \in L$ and $M(F_1) = m-2$ otherwise

2) $M(F_2) = m\cdot (m-1)$ if $x_2 \in L$ and $M(F_2) = m\cdot (m-2)$ otherwise

...

k) $M(F_K) = m^{K-1} \cdot (m-1)$ if $x_K\in L$ and $M(F_K) = m^{K-1} \cdot (m-2)$ otherwise

Now take the union of the formulas, which were constructed over disjoint variables sets, and call it $F$. So we have $M(F) = M(F_1) + \cdots + M(F_k)$, and we can "read off" the answer to the $K$ problems $x_i \in? L$ by looking at the base-$m$ representation of $M(F)$. If we can compute $M(F)$ given $k$ bits of advice, it means that we can find $2^k$ values such that one of them is $M(F)$. We can then ask non-adaptively an NP oracle whether $M(F) \geq n_i$ for each of the candidate values $n_1,\ldots,n_{2^k}$ we generated. So we have been able to solve $2^k+1$ instances of NP-complete problems by making $2^k$ non-adaptive queries to an NP oracle, which implies that the polynomial hierarchy collapses.

Using Hastad's theorem instead of Cook's theorem, it's possible to push  the size of $F$ to $O(1)^k \cdot m$ instead of $m^k$, so it's possible to push $k$ to $\log m$, and the number of advice bits to $\log\log m$. Understanding what happens when you are given  $\log m  - O(1)$ advice bits seems really difficult.

Edited to add: Krentel (The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509 (1988)) proved that computing the value of the optimum of the maximum clique problem is complete for $FP^{NP[O(log n)]}$, the class of functions computable in polynomial time with $O(log n)$ queries to an NP oracle. The completeness is under "one query reductions," in which function f is reducible to function g if one can write $f(x) = r_1(g(r_2(x))$ for polynomial time computable $r_1$ and $r_2$. Presumably the same is true for Max Clique. Now, if Max Clique had a polynomial time algorithm that produces a list of $m^{o(1)}$ possible values, it would be in $FP^{NP[o(logn)]}$, because you could use binary search to find the optimum with a number of queries that is log of the list size.

Now, if we have $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ we would definitely have $P^{NP[O(log n)]} = P^{NP[o(log n)]}$, which is the special case for decision problems, and that is known, by results of Wagner (improving a result of Kadin that applies to a constant number of queries), to collapse the polynomial hierarchy. But I think that it might be known that $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$  would actually imply P=NP. But in any case the results of Krentel and Kadin-Wagner should be enough to give another proof of Andy Drucker's result. Now I wonder if it is actually the same proof, that is, if the Fortnow-Van Melkebeek result works, explicitly or implicitly, via a "simulating NP queries with fewer NP queries" argument.

A good survey paper that explains what is going on with optimization problems and bounded query classes:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf


Longest path in Complete Directed Graphs I searched in Google and checked similar questions on this site, but couldn't find an answer for my problem. I hope this place is appropriate for my problem.
The problem is formulated as follows:

We are given a weighted digraph with the following properties:

The weights are real numbers

Each vertex has a directed edge into every vertex, but without self-loops (i.e. the graph is complete, each vertex has |V|-1 in and out degree)

The weight for some edge $X \rightarrow Y$ is not necessarily the same as for $Y \rightarrow X$ (therefore we can't treat the graph as an undirected graph)

We are also given a source s and a sink t.
The problem is to find the longest path from s to t.
(Obviously the path should not contain any loops, and can contain at most |V|-1 edges)

Even though the problem is NP-hard and even finding a constant factor approximation is NP-hard for the general case, I wonder if for that kind of graphs we can do better.
The questions are:

Is the problem NP-hard?

If yes, how good can the problem be approximated? I would prefer fast running time over good results.

Do you know any good heuristics for the problem? (that work well in practice)

Any comment/answer/reference is appreciated. Thanks in advance!

Sage's implementation of it for instance :-)

http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path

Nathann


Automata learning without counterexamples In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher:

Word queries: given $w\in \Sigma^*$, is $w\in L$?

Equivalence queries: given a language $K\subseteq \Sigma^*$, is $K=L$? If not, the teacher gives a counterexample, i.e. a word $w\in K\setminus L \cup L\setminus K$.

Using Angluin's algorithm, the student learns $L$ with polynomially many queries in the number of states of the minimal DFA of $L$ and the size of the counterexamples.

Now, consider a restricted scenario where the teacher no longer gives counterexamples. Is it still possible to learn L with a polynomial number of queries? I conjecture that this is not the case because for every polynomial-length sequence of queries and answers, one can find several regular languages consistent with the answers.

Does anyone see how to prove this?

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need exponentially many of these to find the "needle in the haystack". (This is even if the learner knows in advance that the target automaton is of this form.) For a formal proof, a teacher could simply respond to the first $2^{n}-1$ membership/equivalence queries with NO, adaptively choosing the target automaton as the unique remaining possibility.

Update. I neglected to mention that the password automaton has $n+1$ states and is learnable using a single standard Angluin equivalence query (namely, with candidate $M$ as the empty automaton).


Is there a Quantum equivalent of the Time hierarchy theorem ? My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965.

I wanted to know then if there was anything similar for Quantum Computing.

Also, if not what are the people / groups working in this direction!

The answer is no. We don't even have a time hierarchy theorem for bounded-error probabilistic polynomial time (i.e., BPTIME).  The deterministic and non-deterministic time hierarchy theorems have a diagonalization argument, which does not seem to work for semantic classes. This is why we don't have strong hierarchy theorems for semantic classes.

The best result I'm aware of is a hierarchy theorem for BPTIME with 1 bit of advice: Fortnow, L.; Santhanam, R. (2004). Hierarchy Theorems for Probabilistic Polynomial Time.

I don't know of any groups working on a quantum time hierarchy theorem. I would guess that this is because it seems like the BPTIME hierarchy problem is easier, so researchers would attack that problem instead.

(Somewhat related questions: Is there a syntactic characterization for BPP, BQP, or QMA? on MathOverflow and Semantic vs. Syntactic Complexity Classes on cstheory.)


Pseudorandom generators indistinguishable by uniform deterministic adversaries I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries.  (For example, a monograph Pseudorandomness by Vadhan (here's its draft does that.)

I believe that it's natural to think about pseudorandom generators indistinguishable by uniform deterministic efficient adversaries.  Has that notion studied before?  Does it have any significance to some degree?

EDIT: I was mistaken in that Vadhan defined pseudorandomness against uniform probabilistic adversaries: he did define indistinguishability by uniform probabilistic algorithms, but he neither defined, nor stated facts about, the corresponding notion of pseudorandomness.  My interest mostly concerned with uniform adversaries and my original question was about deterministic vs. probabilistic.

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm sure there are more.

O. Goldreich and A. Wigderson. On pseudorandomness with respect to deterministic observers

O. Goldreich. In a world of P=BPP

R. Williams. Towards NEXP versus BPP?


A comparison of extractors in terms of tradeoffs between time, randomness and space ? Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?

The default reference is Ronen Shaltiel's survey.  This predates the important results of [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc.  I believe Anup Rao's Ph.D. thesis is a good recent reference that describes these developments.


Time/Space Requirements of Verifying or Falsifying a First-Order Statement Though L.Berman proved that the problem of verifying or falsifying any first-order statement about real numbers that uses addition and comparison but not multiplication is in EXPSPACE.  Has it been shown how much time or space you would nee to verify or falsify any first-order statement about real numbers that uses addition comparison AND multiplication?

The theory of real closed fields (RCF) is complete for the first order theory of real numbers in the language you described. Therefore it is equivalent to checking if RCF proves the formula.

By Tarski's quantifier elimination for RCF this can be computed. Tarski's algorithms complexity is non-elementary and there is a doubly exponential lowerbound for the problem.

A more efficient algorithm than Tarski's algorithm is given by Saugata Basu "An Improved Algorithm for Quantifier Elimination Over Real Closed Fields", FOCS 1997 (which seems to be almost optimal, see Theorem 1) (a draft of the paper is available here).

Also check Saugata Basu, "New Results on Quantifier Elimination Over Real Closed Fields and Applications to Constraint Databases", Journal of the ACM, 1999.


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

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

In general, what we usually call the logical relations argument isn't really linked to impredicativity: the main idea is simply to interpret terms in some abstract algebra $\cal A$, and to represent types as a ($n$-ary) relation $R \subseteq \cal A^n$.

This works perfectly fine for all kinds of type theories, including dependently typed theories, see e.g. Shürmann and Sarnat: Structural Logical Relations where a predicative logic (that of Twelf) is used to prove a certain property (decidability of equality) for a predicative calculus (simply typed $\lambda$-calculus) using logical relations.

As you may have suspected, however, it is not possible to prove normalization of system F in Agda (if Agda isn't secretly stronger than expected, i.e. about the strength of Martin-Löf type theory with a bunch of universes). This is because normalization of system F implies consistency of 2nd order arithmetic ($\mathrm{PA}_2$) which is stronger than M-L type theory with any number of (predicative) universes.

It's instructive to work out exactly where the proof goes wrong in Agda, though. It indeed occurs when you try to define the logical relations interpretation of the impredicative quantification. The interpretation of the non-impredicative connectives though (including "dependent" quantification) is kosher in a theory like Agda.


Is there any book on the philosophical implications of Theoretical Computer Science? I find some books about computers, but all of them are about technology. I want something more linked to theory.

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" https://arxiv.org/abs/1108.1791


Computational Complexity of the Divisor summatory function The divisor function $d(n)$, is the number of $(a,b)\in\mathbb {N^+}^2$ such that $a\times b =n$.
For example, $d(2)=2$ because $2=1\times 2=2\times 1$ and d(6)=4 because $6=1\times 6=2\times 3=3\times 2=6\times 1$.

The divisor summatory function is defined by :
$$D(n)=\sum_{i=1}^n d(i)$$

This is sequence A006218 in OEIS.

Does anyone know the best time complexity algorithm to compute this function ? Are they any results published on the computational complexity of this function ?

Based on a "folkore intuition" for a related problem, one might expect this to be at least as hard as factoring:

The folkore intuition suggests that computing the number of prime factors, or even computing essentially any useful information about the prime factorization, is as hard as factoring itself (see Tao's answer to this related question). $d(n)$ gives you exactly such information, and is essentially equivalent (from the computational perspective) to computing $D(n)$, since $d(n) = D(n) - D(n-1)$.

For example, if $n$ is squarefree, then $d(n)$ is equal to $2^{f}$ where $f$ is the number of prime factors. For general $n$, $d(n)$ is $\prod_{p} (m_p + 1)$ where $m_p$ is the number of times the prime $p$ divides $n$ (that is, $n = \prod_{p} p^{m_p}$ is the prime factorization of $n$).


Using error-correcting codes in theory What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of extractor and amplification of hardness of boolean function (by Sudan-Trevisan-Vadhan).

What are other 'serious' or 'recreational' applications of error-correcting codes?

UPD: one amusing application of list decoding of Reed-Solomon codes is a solution to particular variation of 20 questions game (and another, more straightforward, variation).

Here's a straightforward application in communication complexity (which I see now is also described in a comment by Andy Drucker on his blog) outside the context of derandomization:

Suppose Alice and Bob are given strings $x$ and $y$ respectively, and they want to find out if the Hamming distance between $x$ and $y$ is at most $\epsilon n$ (where $\epsilon$ is some fixed constant).  We want to prove a communication complexity lower bound for this problem.  The observation is that any deterministic protocol for this problem yields a deterministic protocol with the same number of rounds for checking equality of two strings $a$ and $b$ of length $cn$ where $c<1$ is some constant depending on $\epsilon$.  Why?  To check equality of $a$ and $b$, Alice and Bob can run the protocol for the first problem on $C(a)$ and $C(b)$ where $C$ is an error correcting code with distance at least $\epsilon$.  Since there is an easy linear lower bound for the equality problem, this also yields a deterministic linear lower bound for the first problem.


Name for "uniformly polynomial" subclass of XP? Suppose $L$ is a parameterized language with respect to some alphabet $\Sigma$.
The $k$-slice of $L$ is $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$, the set of instances in $L$ which have parameter $k$.
The complexity class $\mathsf{XP}$ contains the parameterized languages $L$ such that $L_k \in P$ for each $k$, possibly with a different algorithm and polynomial running time bound for each $k$.
Each fixed-parameter tractable language is in $\mathsf{XP}$, and there are languages in $\mathsf{XP}$ that are not in $\mathsf{FPT}$; this is Proposition 27.1.1 in the Downey & Fellows 2013 textbook.

However, $\mathsf{XP}$ seems to have nontrivial structure beyond this, since one can stratify this class based on how fast the degree of the bounding polynomial grows with $k$: for $\mathsf{FPT}$ the degree is constant, whereas for $\mathsf{XP}$ it can grow arbitrarily.
Downey & Fellows does not mention anything about the structure of $\mathsf{XP}$ beyond Proposition 27.1.1, and the discussion in the Flum & Grohe 2006 textbook isn't much more detailed.

Following on from my earlier question Limits of variants of Independent Set? is there a name for the subclass $\mathsf{Q}$ of $\mathsf{XP}$ where $L \in \mathsf{Q}$ if there is a polynomial $g_L$ such that every instance $(x,k)$ in $L$ can be decided in at most $|x|^{g_L(k)}$ steps?

In other words, this class $\mathsf{Q}$ allows only up to $|x|^{\text{poly}(k)}$ time instead of $|x|^{g(k)}$ time for some arbitrary function $g$ as for $\mathsf{XP}$.

I don't think this subclass of $\textsf{XP}$ has been studied in the literature (and given a name).

One reason why researchers might shy away from studying this subclass, is that it is not closed under fpt-reductions (and so one would have to deal with an 'annoying' new type of reductions). This is because fpt-reductions allow the parameter value to blow up superpolynomially (as long as it is bounded by some computable function of the old parameter value). To get a restricted notion of fpt-reductions under which your subclass of $\textsf{XP}$ is closed, you would need to add the restriction that fpt-reductions require the new parameter value to be bounded by some polynomial of the old parameter value.


Maximum stable matching/allocation I checked some papers on two-side stable allocation/matching (marriage, worker/company, doctor/hospital), but has not found any literature on the following problem. Can someone point out if I missed some paper or help analyze the problem?

Consider two sets of nodes, $U$ and $V$. $f_u(v)$ is the non-negative (integer) preference function of $u\in U$ towards $v\in V$. Similarly, $f_v(u)$ is for $v\in V$ towards $u\in U$. Let $E\subseteq U\times V$ be a set of pairs. Each pair $(u,v)\in E$ indicates that we can never allocate  one to the other.

$\pi$ is an allocation where $\pi(u)\in V$ is the node allocated to $u$ and $\pi(v)\in U$ is the node allocated to $v$. $\pi$ is weak-stable if there does not exist a pair ($u,v$) such that $f_u(v)>f_u(\pi(u))$ and $f_v(u)>f_v(\pi(v))$, which means that $u$ prefers $v$ to $\pi(u)$ and $v$ prefers $u$ to $\pi(v)$ simultaneously.

I want to compute a stable matching with maximum size, i.e. $maximize_{\pi}|\pi|$. Notice that, ties are allowed in any preference function.

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists).  You can find the current best approximation algorithm for MAX SMTI in the following paper:
Z. Kiraly, Linear Time Local Approximation Algorithm for Maximum
Stable Marriage, Algorithms 2013, 6, 471-484.

There are many papers on MAX SMTI, but unfortunately I am not aware of any paper that handles the weighted version of MAX SMTI.


What's the point of $\eta$-conversion in lambda calculus? I think I'm not understanding it, but $\eta$-conversion looks to me as a $\beta$-conversion that does nothing, a special case of $\beta$-conversion where the result is just the term in the lambda abstraction because there is nothing to do, kind of a pointless $\beta$-conversion.

So maybe $\eta$-conversion is something really deep and different from this, but, if it is, I don't get it, and I hope you can help me with it.

(Thank you and sorry, I know this is part of the very basics in lambda calculus)

Update [2011-09-20]: I expanded the paragraph about $\eta$-expansion and extensionality. Thanks to Anton Salikhmetov for pointing out a good reference.

$\eta$-conversion $(\lambda x . f x) = f$ is a special case of $\beta$- conversion only in the special case when $f$ is itself an abstraction, e.g., if $f = \lambda y . y y$ then $$(\lambda x . f x) = (\lambda x . (\lambda y . y y) x) =_\beta (\lambda x . x x) =_\alpha f.$$ But what if $f$ is a variable, or an application which does not reduce to an abstraction?

In a way $\eta$-rule is like a special kind of extensionality, but we have to be a bit careful about how that is stated. We can state extensionality as:

for all $\lambda$-terms $M$ and $N$, if $M x = N x$ then $M = N$, or
for all $f, g$ if $\forall x . f x = g x$ then $f = g$.

The first one is a meta-statement about the terms of the $\lambda$-calculus. In it $x$ appears as a formal variable, i.e., it is part of the $\lambda$-calculus. It can be proved from $\beta\eta$-rules, see for example Theorem 2.1.29 in "Lambda Calculus: its Syntax and Semantics" by Barendregt (1985). It can be understood as a statement about all the definable functions, i.e., those which are denotations of $\lambda$-terms.

The second statement is how mathematicians usually understand mathematical statements. The theory of $\lambda$-calculus describes a certain kind of structures, let us call them "$\lambda$-models". A $\lambda$-model might be uncountable, so there is no guarantee that every element of it corresponds to a $\lambda$-term (just like there are more real numbers than there are expressions describing reals). Extensionality then says: if we take any two things $f$ and $g$ in a $\lambda$-model, if $f x = g x$ for all $x$ in the model, then $f = g$. Now even if the model satisfies the $\eta$-rule, it need not satisfy extensionality in this sense. (Reference needed here, and I think we need to be careful how equality is interpreted.)

There are several ways in which we can motivate $\beta$- and $\eta$-conversions. I will randomly pick the category-theoretic one, disguised as $\lambda$-calculus, and someone else can explain other reasons.

Let us consider the typed $\lambda$-calculus (because it is less confusing, but more or less the same reasoning works for the untyped $\lambda$-calculus). One of the basic laws that should holds is the exponential law $$C^{A \times B} \cong (C^B)^A.$$ (I am using notations $A \to B$ and $B^A$ interchangably, picking whichever seems to look better.) What do the isomorphisms $i : C^{A \times B} \to (C^B)^A$ and $j : (C^B)^A \to C^{A \times B}$ look like, written in $\lambda$-calculus? Presumably they would be $$i = \lambda f : C^{A \times B} . \lambda a : A . \lambda b : B . f \langle a, b \rangle$$ and $$j = \lambda g : (C^B)^A . \lambda p : A \times B . g (\pi_1 p) (\pi_2 p).$$
A short calculation with a couple of $\beta$-reductions (including the $\beta$-reductions $\pi_1 \langle a, b \rangle = a$ and $\pi_2 \langle a, b \rangle = b$ for products) tells us that, for every $g : (C^B)^A$ we have $$i (j g) = \lambda a : A . \lambda b : B . g a b.$$
Since $i$ and $j$ are inverses of each other, we expect $i (j g) = g$, but to actually prove this we need to use $\eta$-reduction twice: $$i(j g) = (\lambda a : A . \lambda b : B . g a b) =_\eta (\lambda a : A . g a) =_\eta g.$$
So this is one reason for having $\eta$-reductions. Exercise: which $\eta$-rule is needed to show that $j (i f) = f$?


Isomorphic graph embeddings in the Euclidean Space Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path length between $i$ and $j$ in $G$?
I have been testing a few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cycle), but in this case they work.

This is not possible in general.
The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $1$ and those between the non-adjacent pairs must be $\sqrt{2}$).
Now consider the complete bipartite graph $K_{2,3}$. Let us call its vertices $a_1,a_2,b_1,b_2,b_3$. In any embedding $f$ satisfying your condition, the 4-cycles $(a_1,b_1,a_2,b_2)$, $(a_1,b_1,a_2,b_3)$ and $(a_1,b_2,a_2,b_3)$ would all have to be mapped to squares as above, but the first two of these conditions imply $f(b_2) = f(b_3)$, contradiction.


Computational complexity of modular power towers (tetration) The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod N$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod N$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod N$)

Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm.

Consider first the problem of computing a modular exponentiation $ a^r \mod m $.

You say above that you can compute this by repeated squaring modulo $ m $, and that this needs $ O(\log r) $ multiplications.  This is true, and it's certainly a practical algorithm for some range of inputs.  But for other inputs, it's not the best you can do. The important case I want to talk about comes up when $ r $ is very large.

First, let $ c = gcd(a, m) $ and $ b = a/c $ and we'll compute the result as the product of the $ c^r \mod m $ and $ b^r \mod m $ values.  If $ \log_2 m < r $ then $ c^r \equiv 0 $, otherwise computer $ c^r $ by the simple algorithm with $ \log r $ multiplications.  Now we need a number $ s $ such that $ b^s \equiv 1 $, from which we can compute $ b^r $ as $ b^{r \mod s} $.  The Euler phi function $ s = \varphi(m) $ is such a number.  To compute $ s $, you need the integer factorization of $ m $, which takes $ O(m^\epsilon) $ time.

If the exponent $ r $ is so large that even $ \log r $ is significantly greater than $ m $, then reducing the exponent this way gives a faster method for the modular exponentiation.  Alternately, if you have a problem where the inputs are constrained so you always know the factorization of $ m $, such as if you take only prime or power of two exponents, then this method is worth already when $ r $ is significantly greater than $ m $.

This case of the faster method comes up when you want to evaluate an exponential tower $ a^{r^t} \mod m $, supposing $ t $ is significantly larger than $ m $.  For this, first compute $ s = \varphi(m) $ like above, then compute $ r^t \mod s $ by some modular exponentiation algorithm, then compute $ a^{r^t} $ as above.  As $ r^t $ is large, this is faster than the simple method of first computing $ r^t $ and then doing $ O(\log(r^t)) $ modular multiplications.  You can apply this to any exponential tower, thus recursively computing the exponential tower modulo $ m $.  If you have an exponential tower of at least four levels and the final exponent is of comparable size to $ m $, such as in a tetration, then it is very likely that the logarithm of final exponent will be much greater than $ m $, so again this method is worth to compute a tetration.


Complexity of checking if two words have an interleaving in a language For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING:

Input: two words $u, v \in A^*$
Output: whether there exists an interleaving of $u$ and $v$ which is in $L$.

Here, an interleaving of two words $u$ and $v$ is a word $w$ that can be obtained intuitively by taking the letters of $u$ and $v$ while keeping their relative order. Formally, $w$ is an interleaving of $u$ and $v$ if we can partition it into two disjoint subsequences, one which is equal to $u$ and the other which is equal to $v$. For instance, "bheleloll" is an interleaving of "hello" and "bell".

What is the complexity of the $L$-INTERLEAVING problem, depending on the language $L$? In particular:

If $L$ is regular, then we can solve the problem with a dynamic algorithm on the two strings which shows it to be in the class NL. Is it NL-hard for some regular languages? However, for some regular languages, the problem is clearly in L (deterministic logspace). Is there some characterization of the languages for which the problem is in L?
If $L$ is not regular, the problem is still in NL when $L$ has polynomial online deterministic space complexity (see here for this notion, or my earlier question). However, this does not cover, e.g., all context-free languages; yet, some others (e.g., palindromes) can be also shown to be NL (e.g., by doing a dynamic algorithm simultaneously from the beginning and from the end). Is there a context-free language whose $L$-interleaving problem is NP-hard?

For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$.
Furthermore we let $w(0,0)$ denote the empty word.

Let $u=u_1\ldots u_m$ and $v=v_1\ldots v_n$ be the two words under consideration.
Assume that the context-free language $L$ is specified by a context-free grammar in Chomsky normal form.

Construct a dynamic program, where a state $[i,j,r,s,A]$ is specified by

two integers $i,j$ with $1\le i\le j\le m$ or $i=j=0$
two integers $r,s$ with $1\le r\le s\le n$ or $r=s=0$
a non-terminal symbol $A$ in the context-free grammar

For every state, decide whether in the context-free grammar there exists some derivation that starts with the non-terminal $A$ and that ends with some interleaving of the two words $u(i,j)$ and $w(r,s)$.
This decision can easily be made, if the states are handled in the right order (short subwords before longer subwords).

All in all, this yields a polynomial time algorithm for the $L$-interleaving problem of any context-free language $L$.


Lower bound on number of oracle calls for solving $n$ instances of the halting problem I encountered the following question, which is an easy exercise (spoiler below).

We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of them halt on $\epsilon$. That is, we need to output $\{i: M_i\text{ halts on }\epsilon\}$. We are given an oracle for the halting problem, but we have to use it a minimal number of times.

It is not hard to show that it can be done with $\log (n+1)$ calls.

  My question is: can we prove a lower bound? Is there reason to suspect that such a bound will be very hard to find?

The answer to the question itself (spoiler, hover mouse):

   Consider the case of $3$ TMs. We can construct a TM $H_2$ that runs $M_1,M_2,M_3$ in
 parallel, and halts if at least two of them halt (otherwise it gets stuck).
 Similarly, we can construct a TM $H_1$ that halts if at least one of them halts.
 We can then call the oracle on $H_2$. If it halts, then we can run the machines in
 parallel, and wait for one to halt. We can then call the oracle on the last one. If the
 oracle says "no", then we run the oracle on $H_1$. If it halts, then we run the machines
 until one halts, and it's the only one that halts. If $H_1$ does not halt, then none of
 them halt. Extending this to $n$ machines is easy.

The first observation about this question is that it seems impossible to solve using information-theoretic tools, since we crucially rely on our ability to obtain information by running the machines without the oracle.

The result can be found in

Beigel, R., Gasarch, W. I., Gill, J., and Owings, J.  Terse, superterse, and verbose sets.  Inform. and Comput. 103 (1993), no. 1, 68–85.

Their proof in fact shows that your problem cannot be solved with fewer than $\log_2 n$ queries to any set $X$, let alone to the halting problem itself. For some notation, your problem is sometimes denoted $C_n^K$ or $C_n^{HALT}$ (depending on your favorite notation for the halting problem).

For this and many related results, see also:

This survey by Gasarch
The book Bounded Queries in Recursion Theory by Gasarch and Martin.


Find a largest cube contained in the union of cuboids I have a lot of cuboids in 3D space, each has a starting point at (x,y,z) and has size of (Lx,Ly,Lz). I wonder how to find a largest cube in this 3D space that is contained in the union of the cuboids. Is there an efficient algorithm for this?

For instance,
If I have the following cuboids:

a cuboid starting at (0,0,0) with size (10,10,10),
a cuboid at (10,0,0) with size (12,13,15),
a cuboid at (0,10,0) with size (10,10,10),
a cuboid at (0,0,10) with size (10,10,10), and
a cuboid at (10,10,10) with size (9,9,9).

Then, the largest cube contained in the union of these cuboids will be a cube starting at (0,0,0) with size (19,19,19).

A more general version of this question:

  Given a collection of $n$ boxes in
  $\mathbb{R}^d$, find the largest hypercube
  contained within the union of the boxes.

Well, here is an first try silly answer... Take a plane through each face of of the rectangular boxes. This form a grid of size $O(n^3)$. It is not hard to compute for each such grid cell whether its inside the union or outside. Now, from each grid vertex, grow a cube (having this vertex as a vertex) trying to make it as large as possible. Doing it in the most naive way, this takes $O(n^3 \log n)$ time per vertex, but probably using orthogonal range searching magic, one should be able to do it in $\log^{O(1)} n$ per vertex. So $O(n^3 \log^{O(1)} n )$ should be possible...

A second try: Compute the union. In this specific case, this can be done in $O( n \log n)$ time (by sweeping planes). Now, observe that you just need to compute the $L_\infty$ voronoi diagram of the boundary of the union. Using the result: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf, this can be done in $O(n^{2+\varepsilon})$ time, for an arbitrary small constant $\varepsilon > 0$.

Breaking the $O(n^2)$ running time bound here would be interesting, IMHO.


What's the status of Babai's Graph isomorphism result? It's been over a year since his January 2017 retraction and correction.
Is there news?
If not is this normal for validation to take this long? I would expect it would get plenty of attention.
Has anyone of note spoken up to support/doubt the quasi-polynomial result?

Aggregating comments by  Thomas Klimpel, Sasho Nikolov and  Mohammad Al-Turkistany into a community answer:

The correction (and hence the quasi-polynomial result) was immediately supported by Harald Andrés Helfgott. His expository paper (https://arxiv.org/abs/1701.04372) and its translation (https://arxiv.org/abs/1710.04574) are all the support that is needed for the quasi-polynomial results. Helfgott’s exposition appeared as Exposé 1125 in Astérisque 407 (2019), Séminaire Bourbaki 2016/2017, pp. 135–182.

There are no current known issues with Babai’s proof, and it has gone through extensive peer review. That said, even published peer-reviewed papers have later been withdrawn as incorrect.

The support by Harald Andrés Helfgott along with the lack of other issues should be sufficient for us to accept that graph isomorphism is indeed solvable in quasi-polynomial time.


Is there any notion of sensitivity for probabilistic Boolean functions? Sensitivity is defined here. Denoting the neighbors of $x$ in the Boolean cube as $N(x)$, we define the sensitivity to be $s(f, x) = \sum_{y \in N(x)} I(f(x) \neq f(y))$, where $I$ is $1$ if the statement inside is true, $0$ otherwise. I'd imagine that you could do the same thing but instead of the indicator function use the probability and a lot of the results from that paper could still go through but in a probabilistic way.

I'm mostly just curious if anyone has looked at this before, as I think the notion I stated works just fine, but if anybody has an alternative notion or a problem with my candidate I'd be interested in that.

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity:
$$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \Pr(f(x) \neq f(y)).$$


What is complexity of this max-edge subgraph problem? While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below:

  Given a connected undirected graph, finding a maximum-size subset of
  the edges such that every vertex has degree at most two.

I have found some paper on complexity of relative problems. Most of them added more constraint on the original one. FOS03 added "with no odd cycles" and proved that it is NP-hard. CTW07 implied that the variant added "with no 3-cycle" is P referring to another paper (which I failed to find). But I have been unable to judge complexity of the original problem. So how to judge it? Thanks.

The generalized problem (such that each vertex $v$ has degree at most $b_v$) is called the $b$-matching problem. Chapter 31 of Schrijver's book is devoted to the subject. It can be solved in strongly polynomial time.

The case that $b_v=2$ for every vertex $v$ has been studied, particularly for providing lower bounds for the traveling salesman problem.


Finding all possible simple cyclic paths in a digraph I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is there any efficient algorithm to perform this operation?

Efficient Algorithms are already known in the literature.

See e.g.,

Tarjan, R E and Read, R C (1975) Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3):237-252
Johnson, D. B. (1975) Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing 4(1):77-84.


Number of Automorphisms of a graph for graph isomorphism Let $G$ and $H$ be two $r$-regular connected graphs of size $n$.
Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$.
If $G=H$ then $A$ is the set of automorphisms of $G$.

  What is the best known upper-bound on the size of of $A$?
  Are there any results for particular graph classes (not containing complete/cycle graphs)?

Note:
Constructing the automorphism group is at least as difficult
(in terms of its computational complexity) as solving the graph isomorphism problem.
In fact, just counting the automorphisms is polynomial-time equivalent to
graph isomorphism, c.f. R. Mathon, "A note on the graph isomorphism counting problem".

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs.

For a lower bound, consider formula $F$ with $n$ inputs whose gates are addition $\mod k$ gates of fan-in 2.  Then using a resut of Toran one can construct a $k$-regular graph $G(F)$ with $O(k^2\cdot n)$ vertices whose automorphism group encodes all possible evaluations of $F$. This implies that the number of automorphisms of
$G(F)$ is at least $k^n$. This shows that the there is an exponential lower bound for the number of automorphisms of $k$-regular graphs in function of its number of vertices.


Is there a constructive parallel repetition theorem for nice MIP protocols? Theorem 1.1 of Ran Raz's paper is a non-constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness.

As far as I can see, despite the second sentence of that paper's abstract suggesting otherwise, that paper does not give a constructive upper bound on the relevant quantities.

  Is there a known constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness?

In his simplified proof of the parallel repetition theorem, Holenstein gives the following explicit bound on the value of the $n$-fold parallel repetition of a game with value $v$:

$$
\left(1-\frac{(1-v)^3}{6000}\right)^{n/\log(|\Sigma_1|\cdot |\Sigma_2|)},
$$
where $\Sigma_1, \Sigma_2$ are the alphabets of the two players.

It's not clear to me that Raz's bound is not constructive in your sense; I am wondering what step in his proof you think is not computable. He does not make his bound fully explicit, but I thought this was done more for exposition.


What is the known complexity of this game? (similar to PushPush-1) I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to know if it has a name, and whether it's computational complexity has been studied:

A block sits on a starting position in a room containing a bunch of blocks, and an exterior agent can slide the block in any one of four directions (N, S, E, W). When it's moved, it slides in that direction until it is stopped by hitting a wall or a block.

For an illustration (not the sharpest, but the first I could find on Google), a student designed this game in the Scratch programming language: http://scratch.mit.edu/projects/StrykerV/1466085.

Specifically, I want to know if this game is NP-hard or PSPACE-complete. It seems that it should be, since it is similar to PushPush-1, but perhaps having only one moving piece makes it easier.

There are no sliding blocks, so the game is in $P$

Informally: from the starting position just mark the cells reachable by the cursor. The level has a solution iif the final position becomes reachable.

The algorithm is similar to the Dijkstra's algorithm for shortest path applied to the graph derived from the level.

For example:

For an $n \times n$ level the complexity is $O(n^4)$.

Let me know if you need further details.