Largest cell in an arrangement Q. What is the complexity of finding the largest volume bounded cell in an arrangment of
  $n$ hyperplanes in dimension $d$?

I feel I should know this... But I am not finding a definitive reference.

Is it $\Omega(n^d)$?
How about the $d{=}2$ specialization:
The largest area bounded cell in an arrangement of lines?

Somehow doing better than $O(n^d)$ looks hard. If the cell is significantly larger than its average expected size, one can use sampling, to find it. Formally, assume the bounded cells (in the plane) form a polygon of area $1$ (this polygon $Q$ can be computed in near linear time in the plane). Assume the largest bounded cell $C$ in the arrangement of lines has area $\alpha \gg 1/n^2$. Sample, $m = (\log n)/\alpha$ points from $Q$ - and let $P$ be the resulting point set. With high probability one of the points falls inside $C$, and computing all the faces in the arrangement containing points of $P$ takes $O(( n^{2/3} m^{2/3} + n + m)*\mathrm{polylog})$ time using standard magic (i.e., algorithms for computing many faces in the arrangement of lines).

It is now straightforward to apply binary search on $\alpha$, to get an algorithm that computes the largest cell, in time $O\Bigl( \bigl(n + 1/\alpha + n^{2/3}/\alpha^{2/3}\bigr) \mathrm{polylog n}\Bigr)$, where $\alpha$ is the fraction of area of the largest cell out of the total area of the bounded cells (i.e., the area of $Q$).


Intuitive explanation behind Goemans-Williamson randomized rounding A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more sophisticated: first, they do a semi-definite relaxation to obtain $n$ unit vectors $X_i$ (rather than the $n$ bits $x_i$ that the original integer program MAXCUT is supposed to solve for), and then each vector  $X_i$ is converted to a random bit by seeing what side of a random hyperplane
$g\sim N(0,I_n)$
 it falls on.

Intuitively, the new random variables $\mathrm{sign}(X_i\cdot g)$ are no longer independent -- unlike the naive randomized cut, where each vertex was chosen independently. I can see why creating dependencies might be beneficial: if a given vertex $i$ is chosen to be in the cut and has a large degree, then perhaps we might not want its neighbors to be in the cut. Is there an intuitive explanation behind the kind of dependencies that Goemans-Williamson rounding is creating between the vertices and why these are beneficial for obtaining larger cuts? [I understand the formal proof, which is relatively simple and very slick. Looking for intuition!]

Great intuitive explanations above by Sasho Nikolov and Neal Young. Here's another one Eden Chlamtáč emailed in:

Well, the intuition is that the SDP solution assigns greater weight in
the objective function to edges whose endpoints that are placed
farther apart in the vector solution, so it makes sense to cluster the
set of vertices geometrically into two contiguous sets. A random
hyperplane is the simplest way of doing that, and it happens to work
well.


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

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

There are several connections between parameterized complexity and approximation algorithms.

First, consider the so-called standard parameterization of a problem. Here, the parameter is what you would optimize in the optimization version of the problem (the size of the vertex cover for the Vertex Cover problem, the width of the tree decomposition for the Treewidth problem, etc.). Let us concretely look at Vertex Cover. Any kernel with a linear number of vertices for Vertex Cover implies a constant factor polynomial-time approximation algorithm: into the approximate solution, put all the vertices that have been forced into the solution by the kernelization algorithm, and all the vertices of the kernelized instance. On the other hand, lower bounds on the approximation factor imply lower bounds on the size of a kernel. For example, under the Unique Games Conjecture, Khot and Regev (JCSS 2008) rule out approximation algorithms for Vertex Cover with a ratio of any $c<2$, which rules out a kernel for Vertex Cover with at most $ck$ vertices, $c<2$, as well.

EDIT: The argumentation for the kernel lower bound in the previous paragraph is very informal, and to the best of my knowledge it is open whether such lower bounds on the kernel size can be proven, even for Vertex Cover. As @Falk points out in the comments, the argument holds for most (all?) known kernels. However, I don't see how one could exclude the existence of kernelization algorithms where a feasible solution of the kernelized instance has a different approximation ratio than the corresponding solution in the initial instance.

Then, there is the issue of PTAS versus FPTAS. If we want to find a solution within $(1+\epsilon)$ from optimal, we can parameterize by $1/\epsilon$. Then, a PTAS corresponds to an XP-algorithm in the parameterized setting, whereas an FPTAS corresponds to an FPT-algorithm. For an approximation lower bound, we may not expect an EPTAS for any problem whose standard parameterization is W[1]-hard: running the EPTAS with $\epsilon=1/(k+1)$ would solve the problem exactly in FPT time.

Finally, an FPT approximation algorithm is an algorithm with FPT running time and an approximation ratio which may depend on the parameter. For example, the standard parameterization of the Cliquewidth problem has an FPT approximation algorithm with approximation ratio $(2^{3k+2}-1)/k$ (Oum, WG 2005), whereas the standard parameterization of Independent Dominating Set has no FPT approximation algorithm with performance ratio $g(k)$ for any computable function $g$, unless FPT=W[2] (Downey et al., IWPEC 2006). See (Marx, The Computer Journal 2008) for a survey on FPT approximation.


Golden ratio or Pi in the running time There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.

It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in

"An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization", Vida Dujmovic, Sue Whitesides, Algorithmica 40:15–31, 2004.

Also, it's a lower bound rather than an upper bound, but:

"An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape", Paul M.B. Vitányi, Inf. Proc. Lett. 21:147–152, 1985.

Finally, the one I was trying to find when I ran across those other two: the ham sandwich tree, a now-obsolete data structure in computational geometry for triangular range queries, has query time $O(n^{\log_2\varphi})\approx O(n^{0.695})$. So the golden ratio is properly in the exponent, but with a log rather than as itself. The data structure is a hierarchical partition of the plane into convex cells, with the overall structure of a binary tree, where each cell and its sibling in the tree are partitioned with a ham sandwich cut. The query time is determined by the recurrence $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$, which has the above solution. It's described (with a more boring name) by

"Halfplanar range search in linear space and $O(n^{0.695})$ query time", Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289–293, 1986.


Dependent corrections in measurement-based Universal Blind Quantum Computation In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing almost anything about the content of the computation.

In the protocol description, the authors mention "dependency sets" associated to each qubit, which are supposed to be calculated by some method described in Determinism in the one-way model

However, it's not clear to me from reading the paper how these set are computed.

Can somebody help to clarify this issue?

Sure. The dependency sets arise from 'flow', which is indeed described in the paper you link to. This is, however, perhaps overkill for what we need.

The idea behind the corrections is to insure that the same effective operator is applied independent of which branch you find yourself in after making a measurement. To do this in principle is fairly simple. Since all the measurements we make are in the XY plane, obtaining a 1 as the measurement outcome for a particular qubit $q$ of state $| \psi \rangle$ yields the same final state as as obtaining a 0 for the same measurement of the same qubit on a state $Z_q | \psi \rangle$. Thus to correct for obtaining a 1 rather than a 0 it is sufficient to find an operator $C$ on the output state such that $Z_q \otimes C | \psi \rangle = | \psi \rangle$.

Now, this implies that $Z_q \otimes C$ is a stabilizer of the initial state. A stabilizer for a state is simply an operator which has that state as an eigenvector with corresponding eigenvalue $+1$.

As it turns out, it is extremely easy to enumerate the generators of the stabilizer group for any graph: For every vertex $v$ in graph $G$ the operator $X_v \prod_{i\in\mbox{nbgh{v}}} Z_i$ is a stabilizer of the graph state, where $\mbox{nbgh{v}}$ denotes neighbours of $v$ in $G$. Thus in order to find the correction for the measured qubit it we can simply pick the stabilizer corresponding to a qubit neighbouring $q$ and multiply it by $Z_q$. This gives a set of $X$ and $Z$ corrections which, when applied to the output state, yield a state equal to the output of the process had the measurement result been inverted.

We need one further requirement, which is that the correction set be in the future of $q$ (i.e. have not yet been measured). This obviously places restrictions on which neighbour of $q$ we choose. In the case of the brickwork state we introduce, this is satisfied uniquely by choosing $v$ to be neighbour of $q$ which is in the same row as $q$ but the next column on. This may sound arbitrary,but as it turns out, this is the unique choice satisfying the conditions I mentioned.

Hopefully this answers your question.

EDITED TO NOTE: You can propagate forward $Z$ corrections by applying the above procedure recursively, so that corrections on any qubit which is to be measured will be $X$ corrections. Whether or not an $X$ correction needs to be made to a particular qubit will then depend on the parity of the measurements for all qubits for which the correcting operator contains an $X$ at this location. To work out this set it is easiest to work the other way around: Simply calculate the correction operators for each vertex propagating all the $Z$ operators to the output qubits, and then once you have these operators work out which measurements alter the measurement at a given site.


NP-hardness of minimizing sum of weighted product Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into the bins such that:

(1) no bin is empty;

(2) $\sum_{B_i}(|Bi|\prod_{I_j \in B_i}w_j)$ is minimized.

where $|B_i|$ is the number of items in $B_i$. Is this an NP-hard problem? If yes, how to prove it?

The problem is indeed NP-complete - reduce from the 3-partition problem where you are given $3n$ positive integers and asked to group them into $n$ groups such that for all the groups the sum of the elements is the same.

Note (1) that partition is strongly NP-complete - i.e remains NP-complete when the input numbers are polynomial in $n$. Note (2) that if the sum of all the groups is the same then this sum must be equal to $X$, where $X$ is the sum of all the numbers in input, divided by $n$. (3) The problem remains NP-complete even when all numbers are strictly between $X/4$ and $X/2$. In this case, each group forced to be a triple.

For each integer $a$ in the input to $3$-partition, replace it by $n^{10a}$ in the input to your problem. Use $n$ bins. Ask whether you can obtain a value of the objective function at most $3n^{10X+2}$.

For the forward direction, if there is a $3$-partition then putting each group into a bin gives value at most $n \cdot 3n \cdot n^{10X}$ for your objective function.

For the reverse direction, suppose that there is a distribution into bins such that the objective function value is at most $n \cdot 3n \cdot n^{10X}$. Make bins into groups. Note that no group adds to more than $X$, since otherwise the product in that bin would be at least $n^{10X+10}$ which is already more than objective function value. Since the input numbers all have value $X/4 < a < X/2$ it follows that all groups have size exactly $3$.

Note that this proves NP-completeness of your problem, but not strong NP-completeness. I suspect that this problem is also strongly NP-complete.


Does there exist a data structure for quick list manipulation and order queries? We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$.  Each element from $N$ appears in a single list in $L$.  I am looking for a data structure which can perform the following updates:

$concat(x, y)$ : concatenates the list containing $y$ onto the end of the list containing $x$
$split(x)$ : splits the list containing $x$ directly after $x$

It also needs to perform the following queries:

$follows(x, y)$ : returns $true$ if $x$ and $y$ are in the same list and $y$ comes after $x$ (but is not necessarily adjacent to $x$)
$first(x)$ : returns the first element of the list containing $x$
$next(x)$ : returns the the next element after $x$ in the list containing $x$

I have already come up with a data structure which performs these updates in $O(lg^2 (n))$ and queries in $O(lg (n))$ time.  I'm mostly interested in whether or not there is already a data structure which can do this (hopefully faster?).

Motivation: rooted directed forests can be represented with two of these list sets and they allow quick calculation of reachability in such forests.  I want to see what else they can be used for and if all of this is already known.

Keep your integers in skip lists. Normal skip lists are ordered by key, but we will just use them as a representation of sequences. Additionally, maintain an array of pointers of size $n$. Each element of the array should point to a node in a skip list. I believe this supports $next$ in $O(1)$ and all other operations in $O(\lg n)$.

Specifically:

$concat$ing or $split$ting two skip lists takes $O(\lg n)$ time and therefore invalidates at most $O(\lg n)$ pointers.
$next$ just follows the forward pointer at the leaf level, taking $O(1)$ time.
$first$ takes $O(\lg n)$ time: follow up pointers until you get stuck, then follow a left pointer. When you can't follow any more left pointers, you're at the head pointer of your skip list. Follow down pointers to the leaf, then one forward pointer. This is the first element in the list.
$follows$ is somewhat trickier. Proceed as in $first$ for $y$, but record a list of the values where you get stuck (that is, where you can't follow up pointers any more). We'll call this list you record a "trace". Do the same for $x$, but follow right pointers when you get stuck, not left. If $x$ precedes $y$, their traces will intersect. The traces are of size $O(\lg n)$. If each element in the trace is annotated with the stuck level, we can check for an intersection in time $O(\lg n)$.

$next$ is worst-case $O(1)$, all others are $O(\lg n)$ with high probability. They can be made worst-case by using deterministic skip lists.

I think $concat$ can be made $O(\lg \lg n)$ by using leaf-level-linked (2,5) trees and boostrapping the spines. For the bootstrapping trick, see "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.


Busy beaver candidate elimination: Minimum space requirements I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state 2-symbol BB listed in Wikipedia).

To more quickly eliminate bad candidates, I'm searching for conditions that imply indefinite runtime. I found a couple of filters already, but the number of indefinite runs is still rather high (indefinite, as in, either seemingly running forever or sometimes checked manually).

In this questions in particular I would like to inquire what space requirements a BB must have after a certain number of shifts. If it accessed less of the tape than this number, it can be dismissed directly. For this purpose, consider the tape length to extend exactly as far as the head went at most in either direction.

As simple upper bound I guess something like $N_{shifts} \leq {N_{TapeLength}}^{|Q|}$ could work, though I am not sure this is even correct. Also, it should certainly be possible to improve this boundary considerably.

Edit: I currently employ the following eliminations:

Static

Fixed first/last transition (A0-B1R,xx-H1R)
State enumeration ordering
All states in transitive closure of A
H in transitive closure of all states
Trap states
Equivalent states
Inability to change the tape

Dynamic

At either end of the tape, current state's transitive closure (using only 0-transitions) always directs further away

There are many methods for detecting that specific TMs will run infinitely. As Marzio mentioned, Heiner Marzen's page and papers provide almost all of the currently used methods.

The method you describe is a great simple requirement. Specifically, if we know that the TM has only moved around on a small tape of size $N_{tape}$, then the exact configuration at every step so far can be described by (1) the symbols at each of these $N_{tape}$ cells, (2) the position of the reading head and (3) the TM state. Thus there are $|Q| \cdot N_{tape} \cdot |S|^{N_{tape}}$ possible configurations (Where $|Q|$ is the number of states and $|S|$ is the number of symbols). So, if the TM has taken more than that many steps of computation, you know that it must have been in one configuration at least twice and thus that it will infinitely repeat.

However, I don't think this method works very often in practice because it is more common for TMs to run off infinitely in one direction than to stay on a small section of tape.


Using the extra power of the negative adversary method The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:

The property testing barrier: if all 0-instances are $\epsilon$-far from all 1-instances then the adversary method cannot prove a lower bound better than $\Omega(1/\epsilon)$.
The certificate complexity barrier: if $C_b(f)$ is the certificate complexity of $b$-instances then the adversary method cannot prove a lower bound better than $\sqrt{C_0(f)C_1(f)}$ where

In the original $ADV^\pm$ paper the authors construct an example function for which their method overcomes both barriers. However, I have not see examples of any natural problems where this has yielded new lower bounds.

  Can you provide any references where the negative adversary method was used to achieve a lower bound that the original method could not attain?

The biggest interest for me, is in property testing. Currently there are very few lower bounds on property testing, in fact I only know two (CFMdW2010, ACL2011), that both use the polynomial method (the first by reduction from the collision problem which was originally lower bounded by polynomial method). We know that there are properties that require $\Theta(f(n))$ quantum queries to check, for any computable $f(n) \in O(n)$ (by combining the results in BNFR2002 and GKNR2009). Why is so hard to use the negative adversary method to prove $\Omega(f(n))$ lower bounds on them?

Apparently, I cannot comment so this will be an answer, even if it only a partial answer.

Element-distinctness has a lower bound of $\Omega(N^{2/3})$ and its certificate complexity is $\sqrt{N}$, so if one tries to prove it using the adversary method, he would need to use the adversary method with negative weights (which is optimal), or why not the Multiplicative adversary method.

Otherwise, the polynomial method is sometimes easier to use that the adversary methods since it suffices to prove the existence of polynomial whereas for the adversary method, you need to explicitly have a good adversary matrix, and compute its operator norm.


Is Hartmanis-Stearns conjecture settled by this article? The paper

  "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
  by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
  https://arxiv.org/abs/1601.02771

claims in Theorem 2.3: "
An algebraic irrational real number cannot be generated by a one-stack machine, or equivalently, by a determistic push down automaton."

I have read and checked the article, have not found any gap in it, and thus the Hartmanis-Stearns conjecture is closed by the theorem? Since the conjecture is hard to prove, I suspect that I misunderstood the article or some fault in it.

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn".

Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time.

Third, the result of Adamczewski et al. is only about finite automata and deterministic pushdown automata, both of which are weaker models than real-time Turing machines.


in SAT resolution proofs, are all DAGs possible? these are some probably very hard but possibly significant and deep questions related to an unusual but intriguing possible "recursive" construction/formulation in SAT, with some important "structure" or "dynamics" not previously considered. do not expect definitive answers in the short term but am sharing in a preliminary/sketchy form & maybe somebody in cyberspace/TCS will find it interesting also.

consider a resolution based proof for a set of SAT clauses. that resolution proof is in the form of a 2-indegree DAG (or in special cases, a tree) where the leaf nodes are clauses, and every node has 2 "ancestors". (this is potentially very interesting though because circuits are usually/often represented as DAGs and can be and are also converted to 2-indegree.)

  can arbitrary/all 2-indegree DAGs be represented by SAT resolution proofs based on selecting particular/specially constructed/contrived SAT instances? in other words, given an arbitrary 2-indegree DAG, are there clauses that "generate" it in the corresponding resolution (refutation?) proof, and if so, what are they? and also what are the minimal clauses that do so?

(of course a resolution DAG could be either for a proof or a refutation proof. am not specifying/fixing that for this above question. also minimal is not yet/further defined. it could be either "length" (number) or "width" (number of variables) of the SAT instance, or some combination or maybe some other meaningful/natural measure.)

it feels like it could be used in a (important?) proof, eg possibly for complexity class separation via diagonalization, somehow, someday. am working on a further/related possibly remarkable construction that requires a "yes" answer ie that all 2-indegree DAGs are possible. (hope to post further on that later.)

these do seem to be fundamental yet novel, not-previously considered questions based on the literature. "nearby" refs could be useful. my intention will be to upvote and/or accept any partial but intelligent answers & encourage others to follow.

Let's assume that you do not allow Tautologies in the leafs, and consider a structure where exactly 3 leafs have edges to a node $A$. Denote the leaf clauses by $(a\vee L_1),(\neg a\vee b\vee L_2),(\neg b\vee L_3)$, where $L_1,L_2,L_3$ are discunctions of literals.
Since they all have edges to $A$, we have the following:
Leaves 1,2 resolve to $(b\vee L_1\vee L_2)$.
Leaves 2,3 resolve to $(\neg a\vee L_2\vee L_3)$

Since $A$ is a single node, then these expressions are equal.
Since there is no initial tautology, then $b\notin L_3$, but this implies that $b\in L_2$, which isn't the case (assume we have no duplicates).

So the only possibility is $b=\neg a$, but this means that $L_1=L_2\vee L_3$ and $L_3=L_2\vee L_3$, so the leaves aren't distinct.

If I am not mistaken, then this means that this structure is not possible, so not every DAG is possible (under the assumptions).


Palindrome language and Finite Automata Machines I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring.

1) A complete treatment of palindrome language with reference to finite automata, particularly interested in how a probabilistic finite automate would recognize palindrome language.

2) A thorough treatment of context-sensitive languages. Introductory books don't discuss it in details as it is perhaps not a topic to be studied in a first course.

it appears that introductory books have rather sketchy discussions of the topics, mostly end of chapter problems. Any suggestion is greatly appreciated.

Regarding probabilistic (and quantum) automata, you may start by digging this survey: https://arxiv.org/abs/1507.01988

For very recent results on quantum automata, you may check two recent works by Zachary Remscrim: https://eccc.weizmann.ac.il/author/659/

Palindrome is an (exclusive) stochastic language, but a probabilistic machine requires log-space to recognize it with bounded error. Two-way quantum automata recognizes palindrome language with bounded-error in super-polynomial time.


For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles I have asked the question at Math SE and at SO, but I can't seem to get the answer I want. So I paraphrase the question and it here.

In a planar graph $G$, one can easily find all the cycle basis by first finding the spanning tree ( any spanning tree would do), and then use the remaining edges to complete cycles. Given Vertex $V$, edge $E$, there are $C=E−V+1$ number of cycles ( Euler formula), and there are $C$ number of edges that are inside the graph, but not inside the spanning tree.

Now, there always exists a set of cycle basis such that each and every edge inside the $G$ is shared by at most 2 cycles. My question is, is there any algorithm that allows me to find such a set of cycle basis? The above procedure I outlined only guarantees to find a set of cycle basis, but doesn't guarantee that all the edges in the cycle basis is shared by at most two cycles.

One of the suggestion I got from Math SE is to use planar embedding algorithm to "guess" the most natural coordinates for each vertex ( so that the graph looks "nice" visually), and then construct the polygonal faces. But this is exceptionally long-winded. I believe that this problem can be tackled more simply without involving coordinates.

Construct a planar embedding and use all but one of the faces of the embedding as cycles in the cycle basis. (It doesn't matter which one you leave out.)

Note that there are actually two different subproblems in planar embedding: determining the cyclic ordering of the edges around each vertex, and computing explicit coordinates. But for the cycle basis, you only need the cyclic ordering, since that's what determines the structure of the faces; you don't need any kind of "nice" coordinates.

Finding planar embeddings is linear time but complicated; there are several standard algorithms.


Best resources for string searching or pattern matching exercises I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.

Are you already familiar with the main algorithms in the area? Are you familiar with this site a huge and well-maintained list of references in pattern matching?

I don't see how one could come up with a list of exercised for string matching, except "implement all main approaches and test them on a lot of data". And data is really easy to come by: you can grab any text file and it will do (you can create a positive example by seeking to a random location in the text file and getting n characters, and for a negative example any random string will do).

I'd read up on KMP, Boyer-Moore, automata methods, and the naive algorithm and implement them, and then think about the problem trying to make your algorithms faster.

There is a huge literature in the area, of course, and the first link I posted can steer you in that direction.


How to choose a correct prior Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-p)$.  Now repeat this experiment $n$ times, and let the total number of positive outcomes (heads) be $k$.

Now, given $n$ and $k$ but not $p$ what is the probability that the Bernoulli experiment (flipping the coin) again will result in a positive outcome (head)?

If $n$ and $k$ were 0 this would be an easy task: as there is no further information and the outcomes could be defined the other way around, it is symmetric and thus $p=0.5$.

Otherwise it's a little more complicated (the dependency on n ($|n$) is omitted for clarity).
The expected probability is:
$\langle p |k\rangle = \int _0 ^1 p\cdot f(p|k) \,\mathrm{d} p$.

Using Bayes' theorem gives
$f(p|k) = p(k|p) \frac{f(p)}{p(k)}  $
and marginalization gives $p(k)=\int_0^1 p(k|p) \cdot f(p) \,\mathrm{d} p$. The Binomial distribution further tells us that $p(k|p)=\binom{n}{k}\cdot p^k \cdot (1-p)^{n-k}$. But what is the correct term for the prior of $p$, $f(p)$?

Jaynes & co. tell me to use a maximum Entropy prior.
To maximize entropy of $p$  ($H(p)=-\int_0^1 f(p) \cdot ln(f(p)) \,\mathrm{d} p$), set $f(p)=1$. But this would not maximize the entropy of $k$; the entropy of $k$ would be maximal if $p$ was $0.5$ thus if $f(p)=0$ but infinity at 0.5 (integrating to 1).

So, what is the correct prior to choose for $f(p)$? Does it depend on $n$?

The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?"

Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to describe what the sequence tells you about the bias of the coin. (Or if you know $n$, either number alone.) This follows because, for each possible parameter $p$, all sequences resulting in a particular count $(h,t)$ are equally likely. So revealing the individual bits adds no information about the bias of the coin once $h$ and $t$ are known. On the other hand, presumably you don't mind releasing $h$ and $t$ as they do not give too much information about any one bit flip.

As a sidenote, one way to approach this general sort of problem is differential privacy. I'm not sure that it's a good fit for your setting, but it formalizes the notion of how much one learns about data from computing some function on the data. The idea is that, if I have two sequences $x$ and $x'$ that differ only on a single bit (say the $i$th bit), then my function, which is randomized, should produce approximately the same distribution over outputs:

\begin{equation}
\Pr[f(x) = a] \leq e^{\varepsilon} \Pr[f(x') = a]
\end{equation}
for all $a$.


Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows:
$$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$
and, for $n\geq 2$,
$$A_{n} = \begin{pmatrix} A_{n-1}&I_{n-1}\\I_{n-1}&-A_{n-1}\end{pmatrix}$$
In particular, it is easy to see that $A_n^2 = n I_n$ for all $n\geq 1$.

Now, maybe I am reading too much into this, but this looks at least syntactically related to another famous family of matrices, the Hadamard matrices, which is also such that $H_n^2 \propto I_n$ and has 'similar' spectrum:
$$H_1 = \begin{pmatrix} 1&1\\1&-1\end{pmatrix}$$
and, for $n\geq 2$,
$$H_{n} = \begin{pmatrix} H_{n-1}&H_{n-1}\\H_{n-1}&-H_{n-1}\end{pmatrix}$$

  Is there any formal connection, possibly useful, between the two, except that "they look vaguely similar"?

For instance, $A_n$ seen as the signed adjacency matrix of the hypercube $\{0,1\}^n$ has a nice interpretation (the sign of an edge $(x,b,x')\in\{0,1\}^n$ is the parity of the prefix $x$). Is there an analogue for $H_n$? (this may be obvious?)

$^*$ I am also wondering if a non-explicit construction, e.g., a uniformly random $\pm1$ matrix, would have the desired spectral properties, but that'd probably have to wait for another question.

Here's just a couple of observations I couldn't fit in a comment:

0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity.

1) In general, the spectrum of block matrices can be very complicated and not obviously related to the spectra of the individual blocks, as the characteristic polynomial will look awful. But for a symmetric block matrix $M=\begin{pmatrix} A & B\\ B^T & C\end{pmatrix}$ that might arise via a recursive construction like the $A_n$ and $H_n$ above, where each matrix is square, one of the only simplifications occurs when $B^T$ and $C$ commute, in which case one has $\det(M)=\det(AC-BB^T)$. Then the characteristic polynomial of $M$ will be $$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$
For this to lead to nice recursive formulas for the eigenvalues, one basically needs $C=-A$ to kill the linear $\lambda$ term. If further $A$ and $B$ are symmetric and commute, we get
$$
\det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)),
$$
from which one easily reads off the eigenvalues using the fact symmetric commuting matrices admit a common eigenbasis. This might be obvious, but all of this is to say that as far as getting good, recursive formulas for the eigenvalues, it is basically essential to require the lower right block to be $-A$ and hope that lower left and upper right blocks are symmetric and commute with $A$, which is the case for the $A_n$ (with $B=I$) and $H_n$ matrices (with $B=H_{n-1}=A$).

2) On the random sign question: the signing of the adjacency matrix given in the paper is optimal in the sense of maximizing $\lambda_{2^{n-1}}$, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing $M_n$ of the adjacency matrix of the $n$-dimensional hypercube, one immediately gets
$$
\text{Tr}(M_n)=\sum_{i=1}^{2^n} \lambda_i(M_n)=0,\quad \text{Tr}(M_n^2)=\sum_{i=1}^{2^n} \lambda_i(M_n)^2=\|M_n\|_F^2=n2^n,
$$
where $\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$. If for some signing $M_n$ one has $\lambda_{2^{n-1}}(M_n)>\sqrt{n}$, then
$$
\sum_{i=1}^{2^{n-1}} \lambda_i(M_n)>\sqrt{n}2^{n-1},\quad \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)^2>n2^{n-1}.
$$
One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than $\sqrt{n}2^{n-1}$ (in absolute value), and their squares must sum to strictly less than $n2^{n-1}$. Minimizing the sum of squares while keeping the sum constant happens when they are all equal, but in this case will make the sum of squares too large anyway. So for any signing, one can see via elementary means that $\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$ without knowing the magic signing in the paper, where equality holds iff the values are $\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are $-n, -n+2,\ldots,n-2,n$, where the $i$th eigenvalue has multiplicity ${n\choose i }$, so it's very interesting (to me, anyway) how the all-$+1$ signing maximizes $\lambda_1$, while this signing maximizes $\lambda_{2^{n-1}}$.

As far as would a random signing work, it's harder to say because I think most non-asymptotic bounds on eigenvalues focus on spectral norm. One expects random signings to smooth out the extreme usual eigenvalues, and indeed, using the noncommutative Khintchine inequality and/or recent tighter bounds like in here, a uniformly random signing has $\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{n})$. It's hard for me to imagine the middle eigenvalues would be on a similar polynomial order as the leading one in expectation (and asymptotic results like the semi-circular law for different matrix ensembles suggest similarly, I think), but maybe it's possible.


Cancellation and determinant Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation essential for attaining a circuit of polynomial size with logarithmic or linear depth to calculate determinant (and any possible best circuit for permanent)? Are there fully exponential (not just superpolynomial or sub exponential) lower bounds for these problems using circuits without cancellation?

Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible.  See discussion in Monotone arithmetic circuits.  A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf


Generalizations of linear programming Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.

Is there a survey/lecture notes describing generalizations of LP that can be solved in poly time?

This is related to this question, but the questions in that post are quite different and most of the questions have not been answered.

Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).


Kraft Macmillan inequality explanation I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me.

We would like to encode a sequence of symbols that come from an alphabet with d+3 symbols. We want to encode symbols  a_1,a_2,and a_3 using code words that are three bits long and symbols a_4,a_5,…,a_(d+1) with code words that are eight bits long. What is the maximum value of d for which this will be possible, if the code must be uniquely decidable?

and the answer is:

The codeword lengths are possible if and only if they satisfy the Kraft-MacMillan inequality,which in this case is
1/2^3 +1/2^3 +1/2^3 +d/2^8 <= 1
This is equivalent to
d/256<=5/8
which is equivalent to d<=160. The maximum value possible value of d is therefore 160.
what is the function d+3 , and where we used it . How 5/8 appears in equation.

What is the effect of d+3 symbols on all this scenario. If I change it to d+1, what is the effect of it

I think it's just in the first inequality (the Kraft inequality): you sum over all the symbols $1/2^{\text{length of encoding}}$. There are 3 symbols of length $3$ bits and $d$ symbols of length $8$ bits, so that's how you get the first inequality. (Also, does your question have a typo? $a_4,a_5,\dots,a_{d+3}$ rather than $\dots,a_{d+1}$.) The $5/8$ comes from simplifying the inequality: you get $3/8 + d/256 \leq 1$, which is equivalent to $d/256 \leq 5/8$.


Does Memcomputing really solve an NP-complete problem? I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims.

  Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size.

(Italics mine).

I would dismiss this off the bat as non-serious, given the strong nature of the claims, if it weren't for the fact that this was published in Science, and that related material by some of the authors was published in Nature Physics, in an IEEE journal and in Physics Review E, all of which are reputable peer-reviewed publications that wouldn't let such claims get published without them being serious.

So is it true? Can these people solve NP-complete problems in P-time using their model?

I feel this has been answered sufficiently in the comments, so to just sum everything up:

The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines.
The authors propose a model of computation that they claim to show is equivalent in power to nondeterministic Turing machines.
The authors construct physical machines that implement this model of computation for small input sizes.
The authors argue that building larger versions is physically realizable/possible with polynomial-sized resources.
This last claim, which is of course not proven and not really a formal statement, would imply a that it is generally physically possible to solve NP-complete problems with polynomial-sized resources.
Scott Aaronson in a blog post explains why this last claim is problematic and why the scalability of their approach has problems: http://www.scottaaronson.com/blog/?p=2212


${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$ We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$.
We also know that ${\bf E} \subset {\bf EXP}$, where
${\bf E} = \cup_c DTIME[2^{cn}]$ and
${\bf EXP} = \cup_c DTIME[2^{n^c}]$.

It has been shown by Book in [1972] that ${\bf E} \not = {\bf NP}$ and in 1974 [1974] that ${\bf E} \not = {\bf PSPACE}$.

${\bf Question}$: Why is it believed that there could be an exponential time algorithm for any problem in ${\bf PSPACE}$?

Edit:  How is it still possible to argue that an NP-complete problem or a PSPACE-complete problem could possibly have a polynomial time algorithm or an exponential time algorithm when it is known that ${\bf P} \subset {\bf E} \subset {\bf EXP}$ and that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$. The fact that ${\bf E} \not = {\bf NP}$ and ${\bf E} \not = {\bf PSPACE}$ should be able to disqualify one of these two possibilities. [The possibility that 1) A NP-Complete problem or a PSPACE-Complete problem having a Polynomial time algorithm. OR 2) A NP-Complete problem or a PSPACE-Complete problem having an Exponential time algorithm.]

[1972]: R. Book. On languages accepted in polynomial time. SIAM ournal on Computing, 1(4):281-287, 1972.
[1974]: R. Book. Comparing complexity classes. Journal of Computer and System Sciences, 3(9):213-229, 1974.

${\bf E} \not = {\bf NP}$ does not imply ${\bf E} \subset {\bf NP}$ nor ${\bf NP} \subset {\bf E}$. Similarly, ${\bf E} \not = {\bf PSPACE}$ does not imply ${\bf E} \subset {\bf PSPACE}$ nor ${\bf PSPACE} \subset {\bf E}$. You would need to show one of these containment's to be able to get a proper separation result out of those inequalities.


Is $AC^0/poly \cap NP$ contained in $P$? I thought I would share this question as it might be interesting for other users here.

Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/poly$, i.e. nonuniform $AC^0$), does this imply that the function is contained in a smaller uniform class (like $P$)? If the answer to this question is positive, what is the smallest uniform complexity class that contains $NP \cap AC^0/poly$? If negative, can we find an interesting natural counterexample?

  Is $AC^0/poly \cap NP$ contained in $P$?

Note: A friend has already partially answered my question offline, I will add his answer if he doesn't add it himself.

The question is my second attempt to formalize the following informal question:

  Can non-uniformity help us in computing natural uniform problems?

Related:

Is there a candidate for a natural problem in $P/poly−P$?

Answer to your first question: Seems unlikely.

Theorem: If $NP \cap AC^0/poly \subseteq P$ then $NEXP = EXP$.

Given a circuit $C$ that outputs a bit, define the decompression of C to be the bit string obtained by evaluating $C$ on all possible inputs. That is, the decompression is $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$.

Define the Succinct 3SAT problem as: given a circuit $C$ of size $n$, does its decompression encode a satisfiable Boolean formula? Succinct 3SAT is well-known to be $NEXP$ complete.

Now consider the language

$L = ${$1^n | $the integer $n$ written in binary is a yes-instance of Succinct 3SAT}.

$L$ is clearly in $AC^0/poly$, since you can just hardcode whether $1^n$ is in $L$, for each $n$.

$L$ is also in $NP$: the integer $n$ written in binary has length about $\log n$, so the decompression of this circuit has length no more than $O(n)$. Hence the satisfying assignment has length at most $O(n)$.

But by the same observations, if $L \in P$, then $NEXP=EXP$, because it means that you
have an $O(n^c)$ time algorithm for deciding every instance of Succinct 3SAT of length $\log n$.

Your second question is wide open (and open-ended).


k-testable languages with non-constant k? Let $p_t(w)$ and $s_t(w)$ denote the prefix and suffix of length $t$ of the word $w$, respectively. If $|w| < t$, then $p_t(w) = s_t(w) = w$. Furthermore, let $i_t(w)$ be the set of infixes of length $t$ of $w$. (If $|w| < t$, then $i_t(w)$ is empty.)

For $k \in \mathbb{N}_0$, a language $L \subseteq \Sigma^\ast$ is said to be strictly $k$-testable if there is are sets $P, S \subseteq \Sigma^{\le k}$ and $I \subseteq \Sigma^k$ such that, for every word $w$, $w \in L$ if and only if $p_k(w) \in P$, $s_k(w) \in S$, and $I_k(w) \subseteq I$.

A language is strictly locally testable if it is strictly $k$-testable for some $k$. A language is locally testable if it can be expressed by the union, intersection, or complement of finitely many strictly locally testable languages. It is known that the locally testable languages are a strict subset of the regular languages.

(The above definitions are slightly adapted from here and  here.)

Are there any papers which analyse the case in which $k$ is no longer a constant? That is, when $k$ is allowed to scale with the length $|w|$ (but we still have $k \in o(|w|)$; e.g., $k = \log |w|$)? Clearly, the resulting languages will not necessarily be still regular, but they seem to be strongly related to parallel computing models such as cellular automata.

(My Google Scholar searches have been fruitless so far...)

Locally testable languages form a subset of the first-order definable languages, where the only allowed numerical predicate is the successor  (see Straubing, page 46 [1]).

By allowing the "local" part to grow, you somehow change the predicate from successor to a length dependent predicate. In particular, the predicate is still "numerical" and thus the languages you are defining are still in $\textrm{AC}^0$ (which is equivalent to FO with the set of all predicates). It is even much lower than that, probably depth-4 wire-linear size circuits, but I didn't check this carefully. I doubt it has a good "cellular automata" variant  since it contains a mixture of local (local patterns) and global (alphabet) information. I would be interested to have some insight on the parallel complexity of cellular automata.

My bet is that your class is indeed much more expressive than regular languages, but fails to recognize more regular languages than locally testable ones. To be a bit more formal:

For a sublinear function $f\colon\mathbb{N}\to\mathbb{N}$, let $\textrm{LocTest}_f$ be the class of languages $L$ such that $L\cap A^n$ is a $k$-locally testable language for $k=\mathcal{O}(f(n))$. Then, my guess is that you should have $\textrm{LocTest}_f \cap \textrm{Reg}$ is exactly the class of (classical) locally testable language. This kind of statement can be found for logical framework at the end of Straubing Book (I like to call these properties of classes of languages "Straubing Properties" when it is known and "Straubing Conjecture" when it is open).

For this specific case, I doubt it has been studied as such but it can be seen as a restricted case of the first level of alternation hierarchy of first-order logic with any predicates (which has a known "Straubing Property"). I would bet it should not be too hard to adapt the proof but it requires some heavy semigroups theory results.

[1] Straubing, Howard. Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1994.


Can we efficiently enumerate the words accepted by a DFA by order of increasing weight? Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $n \in \mathbb{N}$ (written in unary) as input, I want to enumerate all words of the language of $A$ of length $n$, by increasing weight (i.e., first all words of the smallest possible weight, enumerated in some arbitrary order; then all words of the second smallest possible weight, in some arbitrary order; etc., until all words of length $n$ in the language of $A$ have been produced). I'm interested in this in the context of enumeration algorithms, so let's say I want polynomial delay, i.e., the time to produce the next word is always bounded by some polynomial function of $n$. Of course, finding some word achieving the smallest possible weight is easy (make $n$ copies of the automaton and do a shortest path algorithm); the difficulty is in finding the next words, keeping in mind that you are not allowed to enumerate the same word multiple times. And of course, enumerating all words with polynomial delay is not complicated if you do not care about ordering them by weight: make $n$ copies, prune the useless states, and simply enumerate all paths exhaustively with a DFS.

Is anything known about the complexity of this problem? Can the enumeration be performed in PTIME (maybe only for some DFAs?), or can it be shown to be intractable?

I'm also interested in:

A weighted variant, where instead of $n \in \mathbb{N}$ written in unary, I get as input an $n$-tuple of integers $w_1, \ldots, w_n$, and the weight of a word $u_1, \ldots, u_n$ is then $\sum_i u_i w_i$, i.e., I want to enumerate all words by increasing weight of their dot product with the input vector $w$. (The unweighted version above is the case where all values of the $n$-tuple are 1.) In this problem variant, if the numbers in the vector components are written in binary, it becomes NP-hard to decide if a certain weight can be achieved (this is the subset sum problem, already for the trivial automaton $A$ accepting $\Sigma^*$). But this does not imply that enumerating is hard.
A combined complexity variant where the automaton is also given as input and not fixed. In this case, you might as well do directly the product of the automaton with $n$, so you can simply assume that the input is an acyclic DFA, or equivalently an OBDD. But I'm not aware either of algorithms to enumerate OBDD valuations in order of increasing weight.

EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1.  Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof.  Here's the algorithm.  Fix an input DFA $M$ and integer $n$.
For each $k\in\{0,1,\ldots, n\}$ in increasing order, do the following:

Construct a new DFA $M_k$ with a state $(s, i, j)$ for each state $s$ in $M$ and $i, j \ge 0$ with $i+j\le n$.  The new DFA $M_k$ simulates $M$, but uses the indices $i$ and $j$ to count, respectively, the number of 0's and 1's seen so far.  Make $(s, 0, 0)$ the start state, where $s$ is the start state of $M$. Make each state $(s, i, j)$ an accepting state of $M_k$ if $s$ is an accepting state of $M$ and $i+j=n$ and $j=k$. So $$L(M_k) = \{w \in L(M) : w \text{ has length $n$ and $k$ ones}\}.$$  Note that $M_k$ is a directed acyclic graph whose size is polynomial in $n$ and the size of $M$.

Enumerate the words accepted by $M_k$ as follows.  First delete all dead states (states not reachable from the start state, or from which no accept state can be reached).  Find the lexicographically first path in the language of $M_k$ by starting at the start state, then traversing from each node to the next, taking a 0-edge if possible and otherwise a 1-edge.  Stop upon reaching a start state, and output the path found.  Next, repeat the following: let $p$ be the path just enumerated.  Find the path $p'$ following $p$ in lexicographic order as follows.  Take the last 0-edge $(u, w)$ on $p$ such that there is a 1-edge out of $u$, and replace that 0-edge edge and the remaining suffix of $p$ by the 1-edge (say, $(u, w')$) out of $u$ and the lexicographically first path from $w'$ to an accept state (computed as described above, taking 0-edges when possible).  If there is no such edge $(u, w)$, stop.

Note that there are no dead states, so the algorithm can always find $p'$ as described above.
By inspection the time for Step 1 is polynomial in $n$ and the size of $M$, and each path enumerated in Step 2 is enumerated in time polynomial in $n$ and the size of $M$.  The words in $L(M)$ of length $n$ are enumerated in order of increasing number of 1's (i.e., increasing value of $k$.)  $~~\Box$
Lemma 2.  Given an instance of the "weighted" variant in the post, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing weight, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof. By a construction similar to Step 1 of the algorithm in the proof of Lemma 1, the problem reduces to the following problem.  Given an edge-weighted DAG $G=(V,E)$ and two nodes $s$ and $t$, enumerate all paths from $s$ to $t$, in order of increasing path weight, taking time polynomial in the size of the DAG between enumerated paths.
Here is an algorithm for that problem.  (Note: the data maintained by the algorithm will be become exponentially large, but this will be okay each additional path will still be enumerated in polynomial time.)
Observation 1.
Let $P_v$ denote the paths from $s$ to $v$.  For $v\ne s$,
$$P_v = \bigcup_{u:(u,v)\in E}\{ p \circ (u, v) : p \in P_u \},$$
where $\circ$ denotes concatenation.  Consider $P_v$ ordered by increasing path weight.  In this order, consider only the paths that end in a given edge $(u, v)\in E$.  Let these paths be
$$p_1 \circ (u, v),~p_2 \circ (u, v), ~\ldots, ~p_\ell \circ (u, v).$$
Then $p_1, p_2, \ldots, p_\ell$ are the paths in $P_u$, ordered by increasing path weight.
For each vertex $v$ and index $i$, let $P_v(i)$ denote the $i$th in $P_v$, ordered by path weight. We will build an enumerator of $P_v$ that enumerates the $s$-$v$ paths in order $P_v(1), P_v(2), \ldots$, that is, by increasing path weight.  At any given time, each enumerator $P_v$ will have so far enumerated $P_v(1), P_v(2), \ldots, P_v(i_v)$ for some $i_v$. It will support two operations:

Increment. Enumerate the next path $P_v(i_v+1)$ in the sequence and increase $i_v$ by one.

Query. Given an index $i\le i_v$, return the cost of the $i$th path in the sequence, i.e., the cost of $P_v(i)$.

The overall algorithm will simply repeatedly increment the enumerator for $P_t$ to enumerate all its paths in order.  It remains to describe how to implement the enumerator $P_v$ for any given $v\ne s$ to support the two operations above.
$P_v$ will record (in an array), for each path $P_v(i)$ that it has already enumerated (i.e., $i\le i_v$), the cost of that path.  This will let it perform the query operation in constant time.
To support the increment operation, following Observation 1, $P_v$ will maintain, for each edge $(u, v)$ into $v$, the index $j_{uv}$ such that the most recent path that ends in edge $(u, v)$ that it has enumerated is $P_u(j_{uv})\circ (u, v)$.  (Hence, $\sum_u j_{uv}$ equals $i_v$, the number of paths that $P_v$ has enumerated so far.)
By Observation 1, the next path $P_v(i_v+1)$ in the sequence is the cheapest of the following paths:
$$P_u(j_{uv}+1) \circ (u, v) \text{ such that } (u,v) \in E.$$
The enumerator will find this path by calling each enumerator $P_u$ for $(u, v)\in E$, to find the cost of $P_u(j_{uv}+1)$.  Having found the best path, say $P_{u'}\circ (u', v)$, it will increment $j_{u'v}$, and in the case that $j_{u'v} = i_{u'}$ (the best path uses the most recent path enumerated by $P_{u'}$), it will increment $P_{u'}$ (have it enumerate its next path), ensuring that $i_{u'}$ is at least $j_{u'v}+1$.  This way, each cost query to $P_v$ can be done in constant time.
Note that any given call to $P_t$ results in each enumerator $P_u$ being incremented at most once total, even though increments can propagate and  several enumerators $P_v$ could in principle ask $P_u$ to increment.  This is because, during any given call to $P_t$, for a given enumerator $P_u$, we can assume by induction (on distance to $t$) that each of its "parents" $P_v$ (with $(u,v)\in E$) is incremented at most once during the call to $P_t$.  So, once $P_u$ is incremented once during the call, its $i_u$ has increased by one, which is the most that any parent could need.
(Alternatively, we could proceed in rounds $r=1,2,\ldots$, and in round $r$ have every enumerator $P_u$ increment by one, producing $P_u(r)$.  Because $P_v(i) = P_u(i') \circ (u, v)$ where $(u,v)\in E$ and $i' \le i$, this would suffice.  It would still be polynomial time, but not as efficient.)  $~~\Box$
EDIT 2: Code for the algorithm (on DAGs) in the proof is here.


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

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

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

If all edge weights are non-negative, then the minimum weight set of edges that covers all the nodes automatically has the property that it has no three-edge paths, because the middle edge of any such path would be redundant. If we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w_e$ be the weight of $e$, then the cost of a solution is $\sum_{v\in G} c_v + \sum_{(u,v)\in M} (w_{(u,v)}-c_u-c_v)$. The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c_u+c_v-w_{(u,v)}$. If you really want this to be a minimum weight perfect matching problem, then instead use weights $w_{(u,v)}-c_u-c_v$ and add enough dummy edges with weight zero to guarantee that any matching with the real edges can be extended to a perfect matching by adding dummy edges.

If the input graph can have negative edge weights, then the three-edge-path constraint becomes meaningful. In this case it's not obvious to me that there is a polynomial time solution.


Von Neumann architectures and quantum computing Can you do quantum computing in a von neuman architecture? If not, why? What is the constraint? If you control a qbit, can a quantum computer use the von neuman architecture?

Thanks.

What do you mean by von Neumann architecture?

I'll use the Wikipedia definition, and say that it's a computer which keeps its program and its data in the same random-access memory. This works well as a theoretical model of a quantum computer, but there are severe drawbacks to implementing such a device. In particular, for a quantum computer, the data has to be quantum. If the data and program are stored in the same memory device, this would imply that the program has to be quantum, as well. So the computer would then have to be able to implement a superposition of instructions in its instruction set. This is orders of magnitude more difficult experimentally than just having the memory in superposition.

In fact, even indirect memory retrieval, including RAM, pointers, and so forth, appears to be quite difficult to implement experimentally.

This has resulted in the default model of a quantum computer being the uniform quantum circuit model, which is both easier to imagine implementing experimentally and tractable to deal with theoretically from a TCS perspective. The circuit model is able to simulate the von Neumann architecture with only a polynomial slowdown, so quantum complexity classes are not changed by this change of model.


What are the practical issues with intersection and union types? I'm designing a simple statically typed functional programming language as a learning experience.

It appears that the type system I have implemented so far could (with a little extra work) incorporate intersection and union types, e.g. you could have:

<Union String Integer>
<Union Integer Foo>
The intersection of the two types above would be a plain Integer
The union of the two types would be <Union String Integer Foo>

The fact that this is possible, of course, doesn't necessary mean it is a good design idea. In particular, I'm a somewhat concerned about the implementation difficulties of keeping the types disjoint and/or handling overlaps.

What are the pros/cons of incorporating such features in the type system?

Here are a few things to keep in mind:

Although we generally think we know what we mean by set-theoretic intersection and union, there have been several different takes on what exactly intersection and union types are.  So, it's worth pinning this down before you embark on an implementation.
One element which I think is awfully important for understanding intersections and unions is the concept of type refinement, essentially the idea that a program has a certain intrinsic "archetype" (e.g., "foo is a function from integers to integers"), which can then be refined to express more precise properties (e.g., "foo takes even integers to even integers and odd integers to odd integers"). With the concept of refinement in hand, the key property which distinguishes intersections and unions from products and sums is that the intersection/union of two types can be formed only if they refine the same archetype.  In other words, the type formation rules for intersections and unions may be expressed like so (read "$S \sqsubset A$" as "$S$ refines $A$")
$$\frac{S\sqsubset A \quad T \sqsubset A}{S\cap T\sqsubset A}\qquad
\frac{S\sqsubset A \quad T \sqsubset A}{S\cup T\sqsubset A}$$
whereas the formation rules for ordinary products and sums are
$$\frac{S\sqsubset A \quad T \sqsubset B}{S* T\sqsubset A*B}\qquad
\frac{S\sqsubset A \quad T \sqsubset B}{S+T\sqsubset A+B}$$
Since intersections and unions can be used to make more precise assertions about the run-time behavior of a program, it is natural that typing becomes sensitive to evaluation order. For example, papers (2) and (4) below explained why  the "obvious" (and fairly standard) typing and subtyping rules for intersections and unions are actually unsound for ML-like languages (due to the presence of side effects and non-termination). You have been warned!
For similar reasons, global type inference generally becomes impractical or undecidable. Indeed, the whole concept of "principal type" is arguably a red-herring, since a function may satisfy many different properties which are irrelevant to its intended use (e.g., "foo takes prime integers to integers greater than 7"). Instead, practical approaches to intersections and unions (see (3), (4)) are generally based on a combination of inference and checking.

I suppose some of the above points might sound negative, though I wouldn't call them "cons" but merely "realities" of intersection and union types. On the other hand, from a language design perspective, one reason for making the effort of supporting intersections and unions (and for getting them right!) is that they allow more precise properties of programs to be expressed in a fairly incremental way, requiring a much less drastic transformation than, say, dependent type theory.

A brief reading list:

Design of the Programming Language Forsythe by John C. Reynolds
Intersection Types and Computational Effects by Rowan Davies and Frank Pfenning
Practical Refinement-Type Checking by Rowan Davies (dissertation)
Tridirectional Typechecking by Joshua Dunfield and Frank Pfenning


Are there pre-doc positions in TCS? Are there positions for recently graduated bachelor or masters students with a record of research to work as a researcher before committing to their PhD?

TCS has a culture of post-doc positions for recent PhD graduates to do research before attempting to apply for a faculty position. Is there a similar mechanism in place for Bachelor or Masters students to do research before applying for a Ph.D? In particular, if they have a research record already (say a few published papers). I have heard of such positions, but usually they are through your current or future supervisor. Are there other options in industry or at universities/research-centers that are more formal than these personal connections?
The goal of such a position is to work within your field or at an institute you are considering for PhD before committing to it for a longer term.
Related questions:
What are some career options for someone with a computer scientist master degree?
Deciding between different PhD programs
Edit:
After a number of answers, I'd like to emphasize the interest is in having an analogue to a post-doc in that it is purely (or almost completely) a research position. Programs where you take courses to ready for a PhD application are not interesting, since the goal is not to prepare yourself for a PhD application as much as it is to do research to make sure research is what you want to do for the long term.

My answer only applies to Japan, I don't know about other countries. There is a special position termed "Research Student". I did that for 6 months before my masters .

I know that in general any student (foreigner or japanese) can do this. However, it is very common for foreigners to do this before starting the masters or phd program. It gives you adaptation time, and you also start studying the basics of your future research. Most student also start preparing for admissions.

During my time as a research student, I worked as a research assistant for my current advisor in different projects. I also took the time to really study quantum computing, which at that time I had 0 intuition for quantum mechanics. That was perfect for me, before doing any serious stuff.

EDIT:

Q: Are research student positions elusively research positions (i.e. no mandatory coursework)?

A: There is no mandatory coursework for research students. However, there are a lot of things you can do. In my case, I started directly doing research (mostly learning the basics), prepared myself for admissions, and colaborated in some projects. I also attended group seminars, school seminars, etc. You gain access to all activities in the university. You can also attend classes if you want, but that doesn't count for coursework in the graduate course. Another example is when you come from another university (from anywhere in the world) and you want to learn the tools of the trade in some field. So you talk with a professor, and if he agrees you can spend some time in his group as a research student.

Q: Also, are you expected to then stay for a Masters/PhD at the institute where you held the research student position?

A: No, you can change universities if you want. I have a friend that did exactly that. This is a position that doesn't give you a degree nor a diploma or anything, besides the experience.

It is very important also to note Okamoto-sensei's comment below. Specially, note that you don't get paid for doing this, unless 1) you have a good scholarship, like MEXT's scholarship; or 2) you get some funds from a company or a professor looking for phd students.

To give you and idea, I post a couple of links explaining the requirements to be a research student. The first link is from my own university, and the second is from the university of Tokyo:

1) http://www.naist.jp/en/international_students/prospective_students/admission_information/research_student_applications/index.html

2) http://www.s.u-tokyo.ac.jp/en/admission/research-students.html

You can also find more information here

http://www.studyjapan.go.jp/en/index.html


Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game There are pursuers and evaders in the vertices of a directed graph G with one component.  Each vertex must have atleast one outgoing edge (can be a loop).

At each time t:

The evaders must move along an edge to another vertex (may use loop)
Each pursuer must check one vertex (it can be any vertex in G).

A vertex is considered contaminated at time t if an evader can be there without having been caught by the pursuers. A vertex v is decontaminated at time t if:

A pursuer is checking v.
All edges to v originate from vertices which were decontaminated at time t-1.

At time t=0 all vertices are contaminated. The goal is that all vertices are decontaminated. This translates to the evaders being guaranteed to be caught.
A search strategy for k pursuers is a sequence of k-tuples referencing k vertices i.e. "check these k vertices at time t=0, then these k vertices at time t=1" and so on.

What is the minimum amount of pursuers needed to decontaminate all vertices in G?

What is the optimal (shortest sequence) search strategy given a graph G and k pursuers?

So, where can I find this problem definition or an equal one? Is this problem NP-complete and if it is, how can that be shown?

My friend Bastian and I devoted our bachelor's thesis to researching this problem. So I guess the problem has been researched (at least a little bit) now which answers my original question. Here is a link to the final result: The Monk Problem.

Results include:

New kind of recursive system (EL-systems) which is used as a verifier
Connection between search number and strongly connected components
Greedy heuristics based on graph decomposition

The complexity class still remains unknown.


May Boolean circuits be exponentially more concise than Boolean formulae? Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest Boolean circuit $C_n$ describing $f_n$. Say we have $|F_n| = \Omega(g(|C_n|))$ for a certain function $g$.

What is the fastest-growing $g$ for which this is known to be possible, and the slowest-growing $g$ for which it is known to be impossible? (From the comments, it seems like there is still a gap here, but I'm trying to understand which one.)

This is the "simple" version of my question. What I am interested in is a multi-output, probabilistic (=weighted), variant of the problem, defined as follows. It is clear how to extend circuits to be multi-output, and I define a $k$-output formula to be just a $k$-tuple of formulas on the same inputs. I say that the input variables have a certain probability of being true (written in binary and accounted for in the circuit or formula size), each independently from the others, and I look at the probability distribution on the tuple of outputs (forgetting which input is yielding which output, just looking at the distribution on values), given this product distribution on the inputs, in the circuit and formula context. Here again the circuits are certainly more concise than formulae, but how much? Are there some distributions that can be exponentially more concise to represent with circuits, intuitively because of sub-expression reuse?

To give an example for this more elaborate version, consider the following distribution on $n$ outputs:

$000 \cdots 00$ with probability $1/2$,
$100 \cdots 00$ with probability $1/4$,
$110 \cdots 00$ with probability $1/8$,
...
$111 \cdots 10$ with probability $1/2^n$,
$111 \cdots 11$ with probability $1/2^n$.

There is a multi-output probabilistic circuit of size $O(n)$ which generates this (and reuses the draw of the $i$-th bit to draw the $(i+1)$-th). By contrast, the straightforward Boolean function encoding of this is quadratic, and I can't see how you could make it shorter but yet cannot prove it...

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ for the formula complexity of any $n$-variable boolean function. See for example these lecture notes for a detailed presentation. Of course this does not rule out a separation of $2^{\Omega(n)}$.

To the best of my knowledge the biggest separation known currently is $n^{3-o(1)}$ (over the de Morgan basis). It was proved by Håstad for a function with linear circuit complexity. This was an improvement on the method of Andreev, who showed a formula size lower bound of $\Omega(n^{2.5})$ for the same function using the method of random restrictions. You can check these notes for Andreev's proof. Håstad's bound is essentially tight for Andreev's method.

The class of functions computable by polynomial size formulas coincides with (nonuniform) NC1 and the class of functions computable by polysize circuits is P/poly. Separating these two classes is a well-known open problem in complexity theory, and is almost certainly well out of reach.


Monochromatic Rectangle Tiling This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M_{n \times n}$. A rectangle is defined as a submatrix $A \times B$ where $A \subseteq \{0,1\}^n$ and $B \subseteq \{0,1\}^n$. A rectangle is said to be monochromatic if all its elements are 0 (or all are 1). Define the minimum number of monochromatic rectangles needed to tile the whole matrix $M$ as $\chi$.

But the tiling defined as above might be difficult to visualize. For example, consider

$\begin{bmatrix}
1 0 1 0 \\
0 0 0 0 \\
1 0 1 0 \\
0 0 0 0
\end{bmatrix}$

At first glance it might be that $\chi$ is very large. But after permuting the second and third row/column, we have

$\begin{bmatrix}
1 1 0 0 \\
1 1 0 0 \\
0 0 0 0 \\
0 0 0 0
\end{bmatrix}$

then $\chi$ is easily seen to be 3 (since permutation doesn't change $\chi$).

To ease visulization, we define a contiguous rectangle as a rectangle with additional requirement that both $A$ and $B$ are contiguous. (For ex. $\{1,2,3\}$ is contiguous but $\{1,3,4\}$ isn't.) Assume $M'$ is formed from $M$ by a row/column permutation (which means you can permute any rows and any columns of $M$). Define $\chi'(M')$ as the mininum number of contiguous rectangles needed to tile $M'$. Define $\chi' = \min\{\chi'(M')$ | for any $M'\}$. The question is:

Is $\chi$ = $\chi'$?

As can be seen in the comments, Jukka provides a $2 \times 4$ counter example, which is further generalized by Peter to $4 \times 4$ to meet the requirements. Both analysis and program verification (use dynamic programming to calculate $\chi'$) can be performed to make sure $\chi \neq \chi'$ is possible when $n = 4$.

Actually Peter's generalization can be used to show there is an $n \times n$ matrix s.t. $\chi \neq \chi'$ for any $n$. The counter example is shown below:

$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
0 0 0 0 0 \cdots 0 \\
\vdots \\
0 0 0 0 0 \cdots 0
\end{bmatrix}$

There's a unique column with two 1's. At least one continuous rectangle is needed to cover the 0's in this column. And this continuous rectangle doesn't cover any elements in the two rows corresponding to the two 1's. Remove this continuous rectangle and the rest will be a $2 \times n$ matrix:

$\begin{bmatrix}
1 1 0 0 0 \cdots 0 \\
0 1 1 0 0 \cdots 0
\end{bmatrix}$

which needs at least 5 continuous rectangles to cover. So $\chi' \geq 6$. However, it is easy to see $\chi \leq 5$. So $\chi \neq \chi'$.


Heterogeneous Hoeffding/McDiarmid Hoeffding's inequality for independent random variables $a_i\le X_i\le b_i$ states that their sum has sub-Gaussian tails, decaying as $\exp(-2t^2/\sum_i (b_i-a_i)^2)$. Question: Are there any interesting applications exploiting the heterogeneous ranges? In all of the applications I'm aware of, either the $X_i$ all have the same range, or else Hoeffding/McDiarmid (and for that matter, Bernstein/Bennett) are simply too crude, and a sharper tool such as Kearns-Saul is called for (see, e.g., Theorem 1(i) in http://jmlr.org/papers/v16/berend15a.html, or Theorem 2.1 in https://projecteuclid.org/euclid.ecp/1465315542; Talagrand's inequality also comes to mind of course). So again: is heterogenous Hoeffding actually ever used?

Yes. See for example the stronger concentration for the occupancy problem in the following note:

http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf

Theorems 10.3.1 and 10.3.2.
(This is also covered in the Randomized Algorithm book by Motwani and Raghavan).

The version stated here is the martingale version, but it is the same thing...


Upperbound the order of P3-free partition of P4-free graphs A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free graphs are exactly cographs.

Question. In the worst case, how many $P_3$-free graphs are necessarily needed to partition a $P_4$-free graph of $n$ vertices?

A trivial upperbound is $\frac{n}{2}$. Because graphs of 2 vertices are trivially $P_3$-free, so we can simply partition any graph of $n$ vertices into $\frac{n}{2}$ components with each component having 2 vertices.

A clique-cover number is also an upperbound because clique is also $P_3$-free.

I update my reply in light of Aravind's comment. The claim in my previous answer was clearly incorrect but, in my defence, I never had a good intuition about graphs.

By adapting Aravind's argument you can show an upper bound of $O(\sqrt{n})$, as every $n$-vertex perfect graph has an independent set or a clique of size $\sqrt{n}$. It should be possible to show the tightness of the bound by reasoning on the tree-representation of the cograph. Consider for instance a complete binary tree $T$ with $N = 2^n$ vertices, and label its nodes as series/parallel in an alternating fashion. It represents a cograph $G$, and any $P_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path; it should imply that this graph may have at most $O(\sqrt{N})$ vertices, but I leave the details to you.

A related question would be to look for a partition in bicluster graphs, as they are exactly the bipartite $P_4$-free graphs. Observe that this problem can be solved in polynomial time by computing the chromatic number of the graph: an arbitrary pairing between color classes then gives the optimal partition.


Extended Church-Turing Thesis One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis.  This is partly because Dershowitz and Gurevich published a proof of the Church-Turing Thesis is the Bulletin of Symbolic Logic in 2008.  (I won't discuss that here, but for a link and extensive comments, please see the original question, or -- shameless self-promotion -- a blog entry I wrote.)

This question is about the Extended Church-Turing Thesis, which, as formulated by Ian Parberry, is:

  Time on all "reasonable" machine models is related by a polynomial.

Thanks to Giorgio Marinelli, I learned that one of the co-authors of the previous paper, Dershowitz, and a PhD student of his, Falkovich, have published a proof of the Extended Church-Turing Thesis, which just appeared at the workshop Developments of Computational Models 2011.

I just printed out the paper this morning, and I have skimmed it, nothing more.  The authors claim that Turing machines can simulate any sequential computational device with at most polynomial overhead.  Quantum computation and large-scale parallel computation are explicitly not covered.  My question relates to the following statement in the paper.

  We have shown -- as has been conjectured and is widely believed -- that every effective implementation, regardless of what data structures it uses, can be simulated by a Turing machine, with at most polynomial overhead in time complexity.

So, my question: is this really "widely believed," even in the case of "truly" sequential computation with no randomization?  What if things are random?  Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?

Preparatory Rant

I've gotta tell you, I don't see how talking about "proofs" of the CT or ECT adds any light to this discussion.  Such "proofs" tend to be exactly as good as the assumptions they rest on---in other words, as what they take words like "computation" or "efficient computation" to mean.  So then why not proceed right away to a discussion of the assumptions, and dispense with the word "proof"?

That much was clear already with the original CT, but it's even clearer with ECT---since not only is the ECT "philosophically unprovable," but today it's widely believed to be false!  To me, quantum computing is the huge, glaring counterexample that ought to be the starting point for any modern discussion about the ECT, not something shunted off to the side.  Yet the paper by Dershowitz and Falkovich doesn't even touch on QC until the last paragraph:

The above result does not cover large-scale parallel computation, such as quantum computation, as it posits that there is a fixed bound on the degree of parallelism, with the number of critical terms fixed by the algorithm.  The question of relatively [sic] complexity of parallel models will be pursued in the near future.

I found the above highly misleading: QC is not a "parallel model" in any conventional sense.  In quantum mechanics, there's no direct communication between the "parallel processes"---only interference of amplitudes---but it's also easy to generate an exponential number of "parallel processes."  (Indeed, one could think of every physical system in the universe as doing so as we speak!)  In any case, whatever you think about the interpretation of quantum mechanics (or even its truth or falsehood), it's clear that it requires a separate discussion!

Now, on to your (interesting) questions!

No, I don't know of any convincing counterexample to the ECT other than quantum computing.  In other words, if quantum mechanics had been false (in a way that still kept the universe more "digital" than "analog" at the Planck scale---see below), then the ECT as I understand it still wouldn't be "provable" (since it would still depend on empirical facts about what's efficiently computable in the physical world), but it would be a good working hypothesis.

Randomization probably doesn't challenge the ECT as it's conventionally understood, because of the strong evidence today that P=BPP.  (Though note that, if you're interested in settings other than language decision problems---for example, relational problems, decision trees, or communication complexity---then randomization provably can make a huge difference.  And those settings are perfectly reasonable ones to talk about; they're just not the ones people typically have in mind when they discuss the ECT.)

The other class of "counterexamples" to the ECT that's often brought up involves analog or "hyper" computing.  My own view is that, on our best current understanding of physics, analog computing and hypercomputing cannot scale, and the reason why they can't, ironically, is quantum mechanics!  In particular, while we don't yet have a quantum theory of gravity, what's known today suggests that there are fundamental obstacles to running more than about 1043 computation steps per second, or resolving distances smaller than about 10-33 cm.

Finally, if you want to assume out of discussion anything that might be a plausible or interesting challenge to the ECT, and only allow serial, discrete, deterministic computation, then I agree with Dershowitz and Falkovich that the ECT holds! :-)  But even there, it's hard to imagine a "formal proof" increasing my confidence in that statement -- the real issue, again, is just what we take words like "serial", "discrete", and "deterministic" to mean.

As for your last question:

Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?

Today, there are lots of interesting examples of physical systems that seem able to implement some of quantum computing, but not all of it (yielding complexity classes that might be intermediate between BPP and BQP).  Furthermore, many of these systems might be easier to realize than a full universal QC.  See for example this paper by Bremner, Jozsa, and Shepherd, or this one by Arkhipov and myself.


Extensions of beta-theory of lambda calculus The beta-eta-theory of the lambda-calculus is Post-complete.  Can additional rules be added to extend the beta-theory of the lambda-calculus to get confluent theories other than the beta-eta theory?

Postscript

This question violated my own rule that questions should explain why the questioner cares.

It struck me one night, not long before this site went into private beta, that because extensionality and the principle of the excluded middle are related, the eta rule is some sort of extensionality rule, and there are intermediate logics between intuitionistic and classical logic, then it would be interesting if there was such a thing as "intermediate eta" theories.

If I has done so, it would have been obvious that Evgenij's answer raises an obvious problem in the way I'd formulated the question, rather than being what I was after.

Yes. There is for example beta + the rule {s = t | s and t are closed unsolvable terms}. This is as far as I remember not equal to beta-eta, and is consistent. See mathgate for a short description and reference to Barendregt.


How to define the _regret_ in multiagent systems? Any good definition please? I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent received up until time $t$ and the average per-period reward the agent would have received up until time $t$ had he played pure strategy $s$ instead, i.e., $\mathrm{Regret}=\alpha^t-\alpha^t(s)$.

I do not get this definition of regret. For me it looks the other way around, i.e., $\mathrm{Regret}=\alpha^t(s)-\alpha^t$. I also looked for definitions in the internet and I am really lost now.

Can you please explain to me what I am missing here? Could the authors be wrong in the definition (since it is uncorrected manuscript)?

It does appear to be a mistake in this pdf version of the book, where the authors are dealing with rewards: The regret should be the reward that would have been gained for playing s minus the actual gain.

Note that often this is set up with losses (rather than rewards) so that the regret would be the incurred loss minus the loss that would have been incurred under some pure strategy.

For a given pure strategy s, the regret for not having played s should be 0 if one's choice gave the same payoff as s, positive if it was worse (i.e., lower in a rewards setting, higher in a losses setting) than s, and negative if it was better than s.

Commonly one defines the regret as the regret for not having played the best pure strategy (given the choices of others). This will be non-negative, and 0 if and only if the current choice is optimal.


Eta expansion in the pattern lambda calculus Klop, van Oostrom, and de Vrijer have a paper on the lambda calculus with patterns.

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

In some sense, a pattern is a tree of variables -- though I am just thinking of it as a nested tuple of variables, for example, ((x,y),z),(t,s)).

In the paper they showed that if the patterns are linear, in the sense that no variable in a pattern is repeated, then the rule

(\p . m) n = m [n/p]

where p is a variable pattern and n is a tuple of terms with the exact same shape as p, is confluent.

I am curious if there are similar developments in the literature for the lambda calculus with patterns and the additional eta rule (expansion, reduction, or just equality).

In particular, by eta, I mean

m = \lambda p . m p

More directly, I am curious what properties such a lambda calculus would have.  For example, is it confluent?

It forces the classifying category to be closed because it forces the property that

m p = n p implies m = n

By using the \xi-rule in between.  But perhaps something could go wrong?

This is not a complete answer; it is a comment that got too large.

If you extend typed lambda calculus with products with projective eliminators (ie, product eliminators fst(e) and snd(e)), there are no basically issues whatsoever. The reason it took so long to figure out is because it turns out to be more natural to do eta expansions rather than eta reductions.  See Barry Jay's The Virtues of Eta Expansion.

If you want products to have a pattern-style eliminator

let (a,b) = e in t

Then matters are more complex. The primary difficulty with pattern matching are the commuting conversions. That is, these calculi have the equation

C[let (a,b) = e in t] === let (a,b) = e in C[t]

and figuring out (a)  which context C[-] to use and (b) how to orient this equation gets tricky. IMO, the state of the art for rewriting-style approaches are Sam Lindley's  Extensional Rewriting with Sums and Gabriel Scherer's Deciding Equivalence with Sums and the Empty Type, both of which consider the typed lambda calculus with both products and sums.


To which complexity class does this language belong? I was thinking about which class this language belongs:
$L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$

I thought of $L$ as (1) " there is no coloring of k-1 colors" and (2) "there is coloring of $k$ colors". Now, (1) is coNP and (2) is NP-complete so I assume that this language is neither in NP nor in coNP, but I didn't find to which class it belongs.
Any help will be welcomed.

Thanks

(as pointed out by Robin the problem is in DP...)

...and it is also DP-complete.

In fact, Jörg Rothe has shown that this even holds for fixed k=4: Jörg Rothe: Exact complexity of Exact-Four-Colorability. Inf. Process. Lett. (IPL) 87(1):7-12 (2003)


Existing technique to detect the clique and biclique cover the edges in a graph? I wonder if there is any existing method to find the clique and biclique structures in a graph that can cover all the edges in it, and every edge belongs to exactly one of the cliques or bicliques found? I try to illustrate the idea in the figure above where the red edges belong to a biclique and the blue edges belong to a clique. All the edges in the graph are covered by the structures found.

The bicliques and cliques may have overlapping nodes.

The motivation of doing this is that in social networks, the biclique structure often corresponds to an influential group of persons that reach a common group of audiences, and such structural feature cannot be described by clique ...

As noted by Tom van der Zanden, a trivial solution would be to return all the edges of the graph.  I am trying to look for non trivial solutions such as those with minimum numbers of cliques and bicliques.

I wonder if anybody could point to some research in this area?

In case the input graph is bipartite, all cliques in the cover must be bicliques. Thus for bipartite graphs the problem that you are describing is the biclique partition problem. The biclique partition problem (and hence the more general problem that you describe) is NP-complete, and is NP-hard to approximate within $n^{1-\epsilon}$ for every $\epsilon>0$.

See here for more details:
P. Chalermsook, S. Heydrich, E. Holm, A. Karrenbauer:
Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. In:
Proceedings of 22th Annual European Symposium on Algorithms (ESA), LNCS 8737, 2014, pp. 235-246

EDIT: Some easy combinatorial bounds: Let $opt(G)$ denote the minimum number of cliques/bicliques in an edge partition. Then $opt(G)$ is at most the chromatic number of the complement graph $\overline G$. Also, if $bp(G)$ denotes the number of bicliques in a minimum biclique edge partition of $G$, then $opt(G)\le bp(G)$.

If you are interested in implementing a solution... Whereas you cannot resort to approximations, then you can still use some preprocessing and a greedy heuristic. In a preprocessing step, you can put all twin vertices, i.e. pairs of vertices that have the same set of neighbors, into equivalence classes. For the heuristic, call a heuristic for maximum clique, and one for maximum biclique. If the number of edges in the biclique we found is larger than that of the found clique, add the biclique to the edge cover, remove all edges in the biclique, and continue with the remaining graph. Otherwise, we add the clique to the edge cover and proceed in a similar manner.


Incremental drawing of large graphs I have the following problem:
I'm developing a software for data visualization where I get a graph structure and represent it in 3D space. So far, I've been using force-based algorithms to draw graphs and it worked well, until I got requirement that my software should represent very big number of vertices and edges (few millions). It would be very impractical to hold all those in memory, so I'm looking for an algorithm that will enable me to stream small portions of graph as I "walk" through the space.

However, the main problem is in showing and dynamically repositioning of vertices, since I don't have already predefined positions, and I must get them from graph.

Can you point me to some algorithms for incremental drawing and streaming of graph? (and yes, I Googled a lot :))

Thanks in advance!

I would suggest using some Graph database like neo4j and have a look into the paper running large graph algorithms


Complexity of factorial exponent over composite moduli I know that computing factorial modulo a composite number has no fast algorithm and showing non-polylogarithmic lower bound in BSS model for factorial would separate P from NP in that model.

Given $a\in\Bbb Z/n\Bbb Z$, where $n$ is composite, what is the complexity of calculating $a^{m!}$ in $\Bbb Z/n\Bbb Z$ for any given integer $n>m>0$?

Borwein's method to compute the exponent and the doubling method for multiplying out the $a$'s wouldn't be too terrible, but as @SashoNikolov pointed out it is exponential with regards to the input size. You can store all intermediate results in $O(log(n))$ bits when multiplying out $a$.

I don't see what this has to do with P vs NP.