Is this problem #P-hard and why? Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ are two nodes in $G$ and $k$ is a positive integer. What is the probability of the event that the shortest path from $s$ to $t$ has length at least $k$?

I feel this problem should be #P-hard, but I have no idea how to prove its #P-hardness.

I know I should choose a known #P-complete problem, and reduce it to the problem above. But I don't know which one to choose.

I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [http://www.vldb.org/conf/2004/RS22P1.PDF] for details and inspiration of my proof). This problem asks to count the number of valuations that satisfy a formula of the form $\Phi: \bigvee_{(i,j) \in E} X_i Y_j$ with $E \subseteq \mathbb{N}^2$, where the $X_i$ and $Y_j$ are pairwise distinct variables.

Represent the positive partitioned 2-DNF as one vertex $x_i$ per variable $X_i$ and one vertex $y_j$ per variable $X_j$ and an edge from $x_i$ to $y_j$ for each $(i, j) \in E$.

I add a source vertex $s$ and an edge from $s$ to each $x_i$ with parameter $p=1/2$, so with probability $1/2$ the distance is $1$ and with probability $1/2$ it is $>1$. Likewise I add an edge from each $y_j$ to the target vertex $t$ with the same distribution. Up to the exact value of edges with length $>1$, is a clear probability-preserving bijection between valuations of the $X_i$ and $Y_j$ and possible worlds of this graph: for a valuation $\nu$, the corresponding graph is the one where the probabilistic edge adjacent to $X_i$ has length $1$ iff $\nu(X_i) = 1$ and length $>1$ otherwise, and likewise for the $Y_j$.

I set $k=3$. I claim that the probability that there is a path from $s$ to $t$ is the number of valuations that satisfy $\Phi$ divided by $2^N$, where $N$ is the number of variables. Indeed this is clear as a valuation is true iff some adjacent pair of $X_i$ and $Y_j$ is true iff the incident edges to the corresponding $x_i$ and $y_j$ both have length $1$ in the corresponding world.
Note that the exact length of any edge of length $>1$ is irrelevant as the structure of the graph ensures it can never be part of a path of length $3$ from $s$ to $t$: there are only edegs from $s$ to the $x_i$, from the $x_i$ to the $y_j$, and from the $y_j$ to $t$.


Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes Assume you are given:

A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
A list of N memory access modes (read or write),

where the $i^{th}$ entry in the memory range list is accessed (either read from or written to) according to the $i^{th}$ entry in the data access modes list.

How do you efficiently generate a data dependency DAG representing the dependencies between subsequent accesses to possibly overlapping memory ranges?

The DAG should not have redundant dependencies. And ideally the algorithm should have running time quadratic in N (or better, if possible).

UPDATE: To clarify, a dependency between two memory accesses exists if

The two memory ranges being accessed overlap (i.e., have at least one byte in common), and
At least one of the access modes is a write (concurrent reads from the same memory range are ok).

Build an interval tree storing all of the ranges that have been written.  That data structure lets you efficiently determine, for any given memory address, the time when it was most recently written.

In particular, scan through the operations in chronological order.  When you see a write operation, update the interval tree.  Also, for each operation (read or write), check the interval tree to find all intervals that overlap it, and add them to the DAG.  This will build up a dependency DAG with no redundancies.

Each update to the tree can be done in $O(\log N)$ time.  Also, the overlap check can be done in $O(k + \log N)$ where $k$ is the number of intervals that overlap for that particular query.

The running time will depend on the size of the resulting dependency graph, but if that graph has $M$ edges, then the total running time will be $O(M + N \log N)$.  In particular, since this DAG can have at most $O(N^2)$ edges, the algorithm certainly runs in $O(N^2)$ time -- and possibly much faster, if the resulting dependency DAG is sparse.


Example of a $U^\omega$ that is not Deterministic Büchi recognizable Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.

Take an alphabet $A=\{0,1,2\}$, and $U=0^*+2A^*$. Then, $U^\omega$ is not deterministic Büchi recognizable.

To see this, imagine it is recognized by a deterministic Büchi automaton $\mathcal A$ with $n$ states. Then, look at the run of $\mathcal A$ on the word $w=2(0^{n+1}1)^\omega$.
Any inside loop of $0$ must contain a Büchi state, because otherwise pumping yields a contradiction (we get a word of the form $2A^*0^\omega$ that is in $U^\omega$ but not accepted by $\mathcal A$). But then, it means that $w$ is accepted, and therefore $\mathcal A$ does not recognize exactly $U^\omega$.


Is balanced Hamiltonian cycle NP complete on maximal plane graphs? I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.

If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane graphs, is the problem still NP complete?

My intuition is that this extra requirement shouldn't make the problem easier, but maybe this feeling is naive since after all it means that the reduction has to be more intricate.

Yes, it is still $NP$ complete. This is because of:

Claim: All Hamiltonian cycles on maximal planar graphs are balanced.

Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/wiki/Grinberg%27s_theorem


Theory of user control systems? TL;DR:

I am looking for theoretical sources about the different manners to implement user access control.

Long version

I have almost finished all the stand-alone tools needed in my CMS.

I am not at the moment where I need to bring all these pieces together.
Now what I would like to is to create a CMS (and an API) that is completely user-centric.
This means a very strong, yet easy to use, rights management framework at the base of everything. A bit like unix/linux filesystems work (not the actual implementation, but in the sense that they are at the very core of the system).

This framework would need to account for special cases ("user can access this data until date x"), and implement per-action, or per-item rights ("user can edit articles, but not article233"), be completely abstract (not tied to any particular database), and not tied to any authentication system. Also, since any request would go through it, it needs to be quite optimized. Lastly, I want to keep it open for modularity.

This is quite a large project, and before getting into it, I'd like to gather as much theory about used rights management. I know about ACL (and have already implemented a few custom systems myself), but I am looking for a more abstract, high-level document, ideally, not tied to a particular language. In the article/book I envision, code samples would be rare, a few lines only, and coded in pseudo-code just to illustrate a point.

I've been looking on the net but can only find tutorials about how to implement ACL, or discussions about role-based access control, but nothing about, say, research in the field, innovative/alternative solutions, etc.

Anyone can advise a good book/webpage/resource about that?

I can't help you with your CMS, but a very good place to read about the logic of access control is Deepak Garg's PhD thesis, Proof Theory for Authorization Logic and Its Application to a Practical File System.


Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of computation involving hidden variables or non-collapsing measurements, and prove that this model of computation is able to simulate Grover's algorithm in time $O(N^{1/3})$.

The proof — Theorem 10 of (1) or Theorem 4.1 of (2); both go the same way for my question — starts with applying $N^{1/3}$ Grover iterations.
After this we should have the state:

$$\alpha \lvert x\rangle+\beta \!\!\!\sum_{y \in \{0,1\}^n} \!\!\lvert y\rangle$$

where $\alpha = \dfrac{1}{\sqrt{2^{n/3} + 2^{-n/3 + 1} + 1}}$ and $\beta = 2^{-n/3}\alpha$.

My questions:

From where do we follow this? The original paper from Grover is referenced, but he provides only the recurrence (in later versions he added a reference to the explicit sin/cos solution).
In my opinion, the state should be something like $\alpha \lvert x\rangle+\beta \sum_{y \in \{0,1\}^n \:\! \setminus\{x\}} \lvert y\rangle$, otherwise we would have for $n=3$ a superposition of $1 + 2^3 = 9$ states. I guess this is only a lazy notation for convenience?
Is this state normalized? If I try e.g. $n=3$, then I will have:
$$\begin{aligned}[b]
      \alpha &= \frac{1}{\sqrt{2^{1} + 2^{-1 + 1} + 1}}
      = \frac{1}{2}
    \\[1ex]
       \beta &= 2^{-n/3}\alpha = 2^{-1} \cdot \frac{1}{2} = \frac{1}{4}
    \end{aligned}$$
If we assume a factor $k$ from the sum, we can try to check the normalization with:
$$\begin{aligned}[b]
   1 = \alpha^2 + (k\beta)^2
= \bigl(\frac{1}{2}\bigr)^2 + \bigl(\frac{k}{4}\bigr)^2
={}& \frac{4 + k^2}{16}
\\[1ex]\implies{}& k^2 = 12
\end{aligned}$$
which is not solvable in integer. (If I take the $n$ general, substitute by $2^{n/3} = s$, and solve for $\alpha^2 + (k\beta)^2 = 1$, I get a polynomial in 3. degree. The general case does not give any insight for me)

The statement from (1) that "one can check that this state is normalized" does not provide a good feeling for my question. Scott Aaronson published a "list" of some errata on his blog for this paper, but the list did not include this. What am I missing?

The short answer is that the state we wrote down is only an approximation in the large $n$ limit (which is all that is required to prove the upper bound). The state isn't normalized for finite $n$, but becomes normalized as $n \rightarrow \infty$. It looks like we either used a different approximation than what I will describe below, or made a typo - thanks for pointing this out! - but these details don't affect our proof.

The details:

After $t$ Grover iterations, the exact state of the system is
$\sin((2t+1)\theta) | x \rangle + \cos((2t+1)\theta) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$
Where $\theta$ is such that $\sin(\theta) = 2^{-n/2}$ (this exact solution is given in Nielsen & Chuang Section 6.1.3).

Working with the exact expression isn't very informative about how this state behaves asymptotically. So most of the time, to analyze asymptotics, people use the approximation that for small $\theta$, we have that $\sin\theta \approx \theta$ and $\cos\theta\approx 1-\theta^2/2$. Using this approximation, you can show that if you set $t=2^{n/3 -1}$, then your resulting state is $\approx \frac{2^{n/3}+1}{2^{n/2}} |x\rangle +\left(1-\frac{1}{2}\left(\frac{2^{n/3}+1}{2^{n/2}}\right)^2\right) \Sigma_{y\neq x} \frac{1}{\sqrt{2^n-1}} | y\rangle$. Note we've lost the normalization because of our approximation - so if you plug in any $n\in\mathbb{N}$ as you did, you'll get a non-normalized state. However as $n\rightarrow\infty$ the state becomes normalized, because the approximation $\sin\theta\approx \theta$ becomes increasingly accurate.

From this, you can easily see that if you measure this state, you see $x$ with probability $\Theta(2^{-n/3})$. Hence if you could perform $\tilde{O}(2^{n/3})$ non-collapsing measurements, you'd see the marked item once with constant probability. This is all we're using about the state to prove our upper bound.


Taxonomy of notable regular expression automata I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains.

I'm aware of several of the 'bigger' names, e.g.,

Thompson

"Regular Expression Search Algorithm", Thompson, 1968

Glushkov

"A New Quadratic Algorithm to Convert a Regular Expression into an Automaton", Ponty, et. al, 1996

Antimirov

"Partial Derivatives of Regular Expressions and Finite Automata Constructions", Antimirov, 1996

Follow

"Follow Automata", Ilie, et. al, 2003;

"Computing the follow automaton of an expression", Champarnaud, et. al, 2002

Hromkovic

"Translating Regular Expressions into Small e-Free Nondeterministic Finite Automata", Hromkovic, et. al, 2001

and their distinguishing properties (epsilon-free-ness, determinism, size, minimization, etc.) but I know this is not an exhaustive list.

I'm particularly interested in algorithms which present either significantly different time complexities to those listed above, and/or significantly different topologies.

If you know of others, a link to a paper which describes the construction algorithm in detail would be greatly appreciated (read necessary if I'm going to implement it!)

Edit: Added some references as per requested.

Watson (Tech. Rep. Univ. Eindhoven 1995) has written a taxonomy of finite automata construction algorithms; a few more recent developments are found below.

For NFAs with epsilon-transitions, the parsing theory book by Sippu/Soisalon-Soininen (Springer, 1998) contains a variant of Thompson's construction. Ilie and Yu (I&C 2003) and Gulan and Fernau (FSTTCS 2008) give refined versions of the classical construction. The minimum required size of epsilon-NFAs corresponding to regular expressions is further studied by Gruber and Gulan (LATA 2010). The structure of the underlying digraphs resulting from Thompson's construction is studied by Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) and by Gulan (Tech. Rep. Univ. Trier, 2010).

Regarding epsilon-free NFAs, I want to mention the earlier work by Berry & Sethi (TCS 1986) and by Brüggemann-Klein (TCS 1993), but that is probably covered by Watson's taxonomy.

Hagenah and Muscholl (RAIRO 2000) give a fast parallel version of Hromkovic, Seibert & Wilke's (HSW) algorithm. The initial lower bound on size (number of transitions) of epsilon-free NFAs by HSW is improved by Lifshits (IPL 2003). Geffert (JCSS 2003) improves the upper bound in the case of binary alphabets; Later Schnitger (STACS 2006) improves the lower bound on the size of epsilon-free NFAs (for largely growing alphabet sizes, the algorithm by HSW produces asymptotically optimal NFAs), and shows that size $n\cdot 2^{O(\log^*n)}$ suffices for binary alphabets.

Also note: Regarding fast algorithms for regular expression matching, I am aware of recent work by Bille and Thorup (ICALP 2009, SODA 2010). They use the classical Thompson construction (plus of course many tricks for getting speed).


If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b' I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including identity, or a constant function, or a random non deterministic function, or a function that encrypts a and b...) to an adversary $A$, that will give me back two bits $(a',b')$.

If by any chance, $A$ can guess correctly $(a,b)$ with a probability (taken over $a$, $b$, the randomness of $f$, and the randomness of the adversary) better than random, i.e:

$$\Pr[(a',b') = (a,b)] > 1/4$$
can I say that either:

he is good to guess $a$, i.e. $\Pr[a' = a] > 1/2$
or he is good to guess $b$, i.e. $\Pr[b' = b] > 1/2$
or he is good to guess the xor of $a$ and $b$, i.e. $\Pr[a' \oplus b' = a \oplus b] > 1/2$

?

NB: for sure the first two conditions are not enough, as if $f(a,b) = a \oplus b$, then the adversary that picks a random $a'$, and sets $b' := a' \oplus f(a,b)$ will guess $(a,b)$ with proba $1/2 > 1/4$, and still the proba for him to get $a' = a$ will be 1/2 (and same for $b'$). I have the feeling that adding the last line is enough, because it "makes sure" that $A$ cannot guess also the correlation between $a$ and $b$, but not sure how to prove it that it's enough.

Thanks!

There are 4 possibilities, name them e1-e4:

e1  neither match
e2  a only matches
e3  b only matches
e4  both match

Now I restate what you want to prove: Suppose:

\begin{align*}
  \Pr[e4] &\gt 0.25  & \text{prob of correct guess} \\
  \Pr[e2] + \Pr[e4] &\leq 0.5  & \text{prob guess a correctly} \\
  \Pr[e3] + \Pr[e4] &\leq 0.5  & \text{prob guess b correctly}
\end{align*}

This implies that
\begin{align*}
  \Pr[e2] < 0.25  \\
  \Pr[e3] < 0.25  \\
  \implies \Pr[e2] + \Pr[e3] < 0.5  \\
  \implies \Pr[e1] + \Pr[e4] > 0.5,
\end{align*}
and then we notice that this is the probability that the XOR matches.


Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements? Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition.

http://www.sciencedirect.com/science/article/pii/030439759190180A

Scott's algorithm on building parse trees doesn't take into account this enhancement.

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

Leo notes in his paper his algorithm builds an effective recognizer, but ultimately leaves out information that would be needed to construct the parse forest. Building the parse forest would require the transition items omitted by the enhancement and therefore undo the complexity gains.

So I would like to know if there is research or findings on creating a parse forest that retains the complexity gains from the Leo enhancement without pushing the complexity from the recognizer to the parse forest generation. Basically, is there a linear time algorithm on LR(k) grammars for building sparsely packed parse forests?

I ended up getting a hint on how to accomplish this by reading the leo semantics post from Jeffrey Kegler's deprecated Marpa algorithm page. https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy

Snippit that really helped:

  Leo Semantics: Indirect and Lazy

  Leo's hints about semantic processing, while brief, were insightful.
  The first decision to make with the Leo semantics was direct versus
  indirect. The direct approach does the semantic processing with the
  Leo items themselves, without converting them. This has the advantage
  that costs are incurred only for the Leo items that are actually used
  by the semantics. It has the very serious disadvantage of intertwining
  the Leo logic with the semantics. Dealing directly with Leo items
  would more than double the complexity of the logic for Marpa's
  semantics. Because of this, Marpa rejected the direct approach.

  Leo 1991 suggests an indirect approach. The indirect approach is to
  expand the Leo completions into the stacks of Earley items for which
  Leo completions are a shorthand. However, in a naive implementation,
  the indirect approach eliminates every advantage of using the Leo
  speedups -- it merely moves processing from the recognizer into the
  semantic phase.

  Marpa optimizes by using a lazy implementation of the indirect
  approach. Only those Leo completions useful for the semantics are
  expanded.

  For a lazy and indirect implementation, in all cases, time complexity
  is the same as with a direct implementation. But for some ambiguous
  grammars, the space required grows from linear to quadratic with any
  indirect approach. This does not change the worst case time-complexity
  -- that was already quadratic. Fortunately, this worst case -- highly ambiguous parses where all the parse results are demanded -- is of
  limited practical interest.

I ended up using the lazy approach as well and did just in time evaluation for only items needed to complete the parse tree. This avoids the intermediate items that the normal algorithm adds.


Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how many assignments (i.e., functions from the variables to $\{0, 1\}$) make $\Phi$ true. As this problem is #P-hard, I study it for restricted classes of DNF formulae.

The hypergraph of a DNF formula has as vertices the variables, and has one hyperedge per clause which contains precisely the variables of the clause. The requirement that I impose is that the hypergraph of the input DNF is a hypertree: in other words there is a tree $T$ on the variables such that each clause is a connected subtree of $T$.

Is anything known about the complexity of #SAT for monotone DNF formulae obeying this restriction? Is it still #P-hard, or does it become PTIME?

Depending on whether this is hard or not, I am also curious about other possible restrictions on the hypergraph, e.g., alpha-acyclicity, beta-acyclicity, or the strenghtening of the hypertree condition where each clause must be a connected path of the tree $T$ (I do not know a name for these hypergraphs).

Some remarks on the problem. I think it is the case that, if the size of the clauses is bounded by a constant, the problem can be solved in PTIME by writing an OBDD for the formula following $T$. However, if there is no bound on clause size, this approach doesn't seem to work, but on the other hand the constrained structure imposed by $T$ does not make it easy to encode arbitrary counting problems, so I don't know how to show hardness.

I am aware of works that study the complexity of #SAT under various constraints on the input formulae, such as this one for beta-acyclicity, but the definition here is for hypergraphs on an input CNF formula, and I didn't find anything relevant about DNF inputs.

Observe that the negation of a (monotone) CNF-formula F is a (monotone) DNF G which has the same hypergraph. Moreover #G = 2^n-#F where n is the number of variables of F. Thus, every known (structural) easyness and hardness result for the exact counting on CNF generalizes to DNF.

In other words, counting the number of model of beta-acyclic DNF is easy (from the paper you cite). And it is hard for alpha-acyclic DNF (just add a big clause containing every variables in a CNF).

It is also hard for hypertrees: take a DNF F and construct F' by adding a fresh vertex x in every clause. #F = #F' and H(F') is a hypertree: take T rooted in x and attached to it every other variables as leaves. Observe that this reduction also shows that the problem #(k+1)-DNF restricted to hypertree is harder than #k-DNF so I doubt that you can compile them into OBDD. Moreover, taking k = 2 (already hard for counting), the transformation leads to a hypertree 3-DNF where every edge is a path in the tree so even this restriction is unlikely to yield easy cases.

DNF however differ from CNF as approximating the number of model is possible in the first case (see On the hardness of approximate reasoning Dan Roth - Artificial Intelligence, 1996 for the hardness of approximating and Monte-Carlo Approximation Algorithms for Enumeration Problems
Richard Karp, Michael Luby, Neal Madras).


Measuring the randomness of CNF formulas It's widely known that CNF formulas can be roughly partitioned in 2 broad classes: random vs. structured. Structured CNF formulas, in opposition to random CNF formulas, exhibit some sort of order, showing patterns that are unlikely to happen by chance. However, one may find structured formulas showing some degree of randomness (i.e. certain specific groups of clauses seems much less structured than others), as well as random formulas with some weak form of structure (i.e. certain specific groups of clauses seems less randomic than others). Hence it seems that the randomness of a formula is not just a yes/no fact.

Let $r: \mathcal{F} \rightarrow [0,1]$ be a function that, given a CNF formula $F \in \mathcal{F}$, returns a real value between $0$ and $1$ inclusive: $0$ means a pure structured formula, while $1$ means a pure random formula.

I wonder if someone has ever tried to invent such a $r$. Of course the value returned by $r$ would be (at least this is my intent) just a practical measurement according to some reasonable criteria, rather than a solid theoretical truth.

I'm also interested to know if someone has ever defined and studied any statistical indicator that can be used in the definition of $r$, or in determining other useful overall properties of a formula. By statistical indicator I mean something like that:

HCV (Hit Count Variance)Let $h_F: \mathbb{N} \rightarrow \mathbb{N}$ be a function that, given a variable $v_j \in \mathbb{N}$, returns the number of times $v_j$ appears in $F$. Let $V$ be the set of variables used in $F$. Let $\bar{h}_F = \frac{1}{|V|} \sum_{v_j \in V}{h_F(v_j)}$ be the AHC (Average Hit Count). The HCV is defined as follows:

$HVC = \frac{1}{|V|} \sum_{v_j \in V}{(h_F(v_j) - \bar{h}_F)^2}$

In random instances, the HCV is very low (all variables are mentioned almost the same number of times), while in structured instances it is not (some variables are used very frequently and some others are not, i.e. there are "clusters of usage").
AID (Average Impurity Degree)Let $h_F^{+}(v_j)$ be the number of times $v_j$ occurs positive, and let $h_F^{-}(v_j)$ the number of times it occurs negative. Let $i: \mathbb{N} \rightarrow [0,1]$ be a function that, given a variable $v_j \in V$, returns its ID (Impurity Degree). The function $i(v_j)$ is defined as follows: $i(v_j) = 2 \cdot \frac{min(h_F^{+}(v_j), h_F^{-}(v_j))}{h_F(v_j)}$. Those variables occurring half of the times positive and half of the times negative have maximum Impurity Degree, while those variables occurring always positive or always negative (i.e. pure literals) have minimum Impurity Degree. The AID is simply defined as follows:

$AID = \frac{1}{|V|} \sum_{v_j \in V}{i(v_j)}$

In random instances (at least in those generated by negating variables with probability $0.5$), the AID is almost equal to $1$, while in structured instances it is usually far from $1$.
IDV (Impurity Degree Variance)The IDV is a more robust indicator than the AID alone, since it accounts for random instances generated by negating variables with probability different than $0.5$. It is defined as:

$IDV = \frac{1}{|V|} \sum_{v_j \in V}{(i(v_j) - AID)^2}$
In random instances the IDV is $0$ (because every variable is negated with the same probability), while in structured instances it is far from $0$.

  Motivations

  To better understand how CNF formulas work, how their randomness/structure could be measured, if other useful overall properties could be inferred by looking at their statistical indicators, if and how such indicators could be used to speed up search.
  Wonder if the satisfiability (or even the number of solutions) of a CNF formula could be inferred by just cleverly manipulating its statistical indicators.

  Questions

  Did anyone ever proposed a way to measure the randomness of a CNF formula?
  Did anyone ever proposed any statistical indicator that can be used to study or even to mechanically infer useful overall properties of a CNF formula?

I suggest to borrow physics intuition that "less random" structures are more symmetric. Symmetry for CNF is any transformation of the variables, that keeps the function invariant. By that criteria, functions of 3 variables such as

$\displaystyle x_{1} \vee x_{2} \vee x_{3} .$

or, say,

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}).$

are less random than, say

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee x_{3}) .$

In general, defining a concept of "random" on finite structures is challenging. Historically, it was tried on binary sequences, which arguably are the simplest finite structures. For example, intuitively, a sequence 01010101 is "less random" than, say, 01001110. However, it was quickly realized that there is no consistent formal definition of finite random sequence! Therefore, one have to be skeptical of any naive attempts to define a measure of randomness for any finite structure.


Initial population for a genetic algorithm from one individual I'm trying to use GA solve the quadratic assignment problem (QAP). We're planning on using it to be able to provide good solutions when using branch and bound becomes impossible, and as a requirement, I have to make it work as if it "improved" an existing solution.

The problem is of course in generating the initial population. I want to ensure diversity as well as good fitness, but the starting individuals, somehow, have to come from a single input individual (it's going to be a good one, in terms of fitness).

How should I go about this? I've thought about creating an initial population consisting on half (or some proportion) of individuals similar to the initial one, and then adding the other half of new randomly (using some heuristic) generated individuals, to combine my solution with other parts of the solution space. Is this a good approach? If so, anny recommendations on the random heuristic to search for the new random individuals?

One nice thing about QAP is that local search methods can take advantage of incremental evaluation of modified solutions, and GAs typically can't. So a pure GA needs O(n^2) time for every fitness evaluation, but a local search can do many fitness calculations in O(1) time, and the rest in O(n).

What I've often done for QAP is to employ something like a tabu search method to do much of the search. See Eric Taillard's paper on Robust Tabu Search for a good example of how to apply it to QAP in particular, including how to do the incremental fitness update.

You can generate multiple good initial points by running multiple tabu searches from random starting points, or you can integrate it directly into the GA as a hybrid method.


Follow the Perturbed Leader for nonlinear cost functions The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known?

Note that in the last paragraph of [1] it says "It would be great to generalize FPL to nonlinear problems".

In [2] (page 69, 70, 71) there is analysis of FTPL for general functions, but the resulting bound $O(T)$ does not attain the optimal bound (i.e. $\sqrt{T}$). Are you aware of better analysis for FTPL (with general nonlinear functions) that attain the optimal regret?

Update:  The algorithm in [2] is indeed $O(\sqrt{T})$ (by choosing $\eta = 1/\sqrt{T}$) but it is calling the linear optimiazation oracle many times (not just once as in [1]), which results in having a different bound.

[1] http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf

[2] http://ocobook.cs.princeton.edu/OCObook.pdf

Here is what you are looking for. It is quite new:

https://arxiv.org/pdf/1810.07362.pdf


NP-complete variants of undecidable problems? Examples of bounded $NP$-complete variants of undecidable sets:

Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps}

Bounded Tiling={ $(T, 1^t)$| there is a tiling of a square of area $t^2$ by tiles from $T$}

Bounded Post Correspondence Problem={ $(T, 1^t)$| there is a matching set of dominoes that uses at most $k$ dominoes from a set of dominoes $T$ (including repeated dominoes) }

  Is it always possible to get $NP$-complete variant of every Undecidable problem by imposing some bounds on the computation? Are there other natural examples of this kind?

As Jukka pointed out, the answer is trivially no for all undecidable problems.

A more reasonable question would be: Can every problem that is complete for the class of recursively enumerable languages be made NP-complete in a straightforward way? I am not sure this is true in general, but in the special cases you mention in your question (Bounded-Halting and Tiling) these problems are complete for RE even under "special" polynomial time reductions. (I leave "special" mostly undefined in this answer, but the properties needed can be worked out from it.)

So if we ask the even more reasonable question: Can every problem that is complete (under special polytime reductions) for the class of recursively enumerable languages be made NP-complete in a straightforward way?, here the answer is yes. Take any RE-complete problem $A$, defined with respect to a Turing machine $M_A$ that takes a pair of inputs $(x,y)$, such that $x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$. We are assuming that there is a polynomial time reduction from the Halting Problem to $A$. Define "Bounded-A" to be the set of pairs $(x,1^t)$ such that there is a $y$ of length at most $t$ such that $M_A(x,y)$ halts within $t$ steps.

Clearly "Bounded-A" is in $NP$. It's also $NP$-complete because we can reduce the $NP$-complete Bounded Halting Problem to Bounded-A in polynomial time (Note that here you need special properties on the polynomial time reduction $R$ to ensure that it carries over to Bounded-Halting as well: i.e., you need to be able to efficiently compute an upper bound $t'$ on how long $M_A(R(M,x),y)$ needs to run, assuming that $M(x)$ halts within $t$ steps.)

Now, is there a language which is RE-complete under (say) doubly-exponential-time reductions but not under exponential-time reductions? For such a problem, it is unlikely that you can trivially modify it to get an $NP$-complete version. I would guess that such a problem can be artificially constructed.


Problems that are NP-complete under randomized or P/poly reductions. In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which unproven assumptions in number theory are true). Are there any other such problems known? Are there any natural problems that are NP-complete under P/poly reductions, but not known to be under P reductions?

As suggested by Peter, I converted my comment into an answer.

Valiant-Vazirani Theorem states that if Unique SAT $\in P$ then $NP=RP$. To prove their theorem they showed that the promise problem Unique SAT is $NP$-hard under randomized reductions.

[1] Valiant, Leslie; Vazirani, Vijay. "NP is as easy as detecting unique solutions", Theoretical Computer Science, 47: 85–93


Type-based memory safety without manual memory manage or runtime garbage collection? Let's say we wanted a typeful, pure functional programming language, like Haskell or Idris, that is aimed at systems programming without garbage collection and has no runtime (or at least not more than the C and Rust "runtimes"). Something that can run, more or less, on bare metal.

What are some of the options for static memory safety that don't require manual memory management or runtime garbage collection, and how might the problem be solved using the type system of a pure functional similar to Haskell or Idris?

Roughly speaking, there are two main strategies for safe manual memory management.

The first approach is to use some substructural logic like linear logic to control resource usage. This idea has floated around basically since linear logic's inception, and basically works on the observation that by banning the structural rule of contraction, every variable is used at most once, and so there is no aliasing. As a result, the difference between in-place update and re-allocation is invisible to the program, and so you can implement your language with manual memory management.

This is what Rust does (it uses an affine type system). If you are interested in the theory of Rust-style languages, one of the best papers to read is Ahmed et al's L3: A Linear Language with Locations. As an aside, the LFPL calculus Damiano Mazza mentioned is also linear,  has a full language derived from it in the RAML language.

If you are interested in Idris-style verification, you should look at Xi et al's ATS language, which is a Rust/L3 style language with support for verification based on Haskell-style indexed types, only made proof-irrelevant and linear to give more control over performance.

An even more aggressively dependent approach is the F-star language developed at Microsoft Research, which is a full dependent type theory. This language has a monadic interface with pre- and post-conditions in the spirit of Nanevski et al's Hoare Type Theory (or even my own  Integrating Linear and Dependent Types), and has a defined subset which can be compiled to low-level C code -- in fact, they are shipping verified crypto code as part of Firefox already!

To be clear, neither  F-star nor HTT are linearly-typed languages, but the index language for their monads are usually based on Reynold and O'Hearn's separation logic, which is a substructural logic related to linear logic that has seen great success as the assertion language for Hoare logics for pointer programs.
The second approach is to simply specify what assembly (or whatever low level IR you want) does, and then use some form of linear or separation logic to reason about its behaviour in a proof assistant directly. Essentially, you can use the proof assistant or dependently-typed language as a very fancy macro assembler that only generates correct programs.

Jensen et al's High-level separation logic for low-level code is a particularly pure example of this -- it builds separation logic for x86 assembly! However, there are many projects in this vein, like the Verified Software Toolchain at Princeton and the CertiKOS project at Yale.

All of these approaches will "feel" like a bit like Rust, since tracking ownership by restricting the usage of variables is key to them all.


Problems to reduce from to prove an $\Omega(n\log n)$ lower bound What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?

Of course, state problems other than sorting and element distinctness.

Ben-Or directly proved  $\Omega(n\log n)$ lower bounds for several fundamental problems in the algebraic computation tree model:

Element distinctness: Given an array of $n$ real numbers, are its elements distinct?
Set disjointness: Given two sets of $n$ real numbers, do they have an element in common?
Set equality: Given two sets of $n$ real numbers, is one array a permutation of the other?
Measure problem: Given $n$ real intervals, what is the total length of their union?
Set inclusion: Given two sets of real numbers, is one a subset of the other?
Permutation Parity: Given an permutation of the set $[n]$, is the permutation even or odd?

The first three are the ones most often used in computational geometry.


What greedy algorithm satisfies greedy choice property but does not have optimal substructure? Based on the textbook Introduction to Algorithms, the correctness of a greedy algorithm requires a problem to have two properties:

greedy choice property
optimal substructure

It is easy to come up with counter examples for which a greedy solution fails due to the lack of the greedy choice property, e.g. the 0/1 knapsack problem. But I find the other possibility pretty hard to imagine. Can anybody give me a problem and a corresponding greedy algorithm which satisfies the first property but not the second?

One of the standard estimators in robust statistics is a type of trimmed mean where you choose a majority subset of a set of input numbers in such a way as to minimize the maximum difference between any two selected numbers, and then take the mean of the selected subset. There's an easy greedy-choice first step: choose the median as part of your subset. But once you've made that choice, the remaining problem is not of the same type (i.e. we don't have optimal substructures), so there's no obvious method of continuing this algorithm greedily. In particular it doesn't work to keep choosing medians of the remaining points. (The repeated greedy median strategy, done with a little care, gives the interquartile mean which is also robust but does not solve the same problem and has a lower breakdown point.)


Integer priority queue with distribution-sensitive deleteMin Is there in an integer priority queue that uses $O(n)$ words of space with the following operations, all in worst-case time and without access to randomness:

createEmptyQueue in $O(lg^c U)$ for some constant $c$.
insert in $O(1)$.
deleteMin in $O(\delta_{\min})$, where $\delta_{\min}$ is the difference between the smallest and the second-smallest key.

Furthermore, once a key $k$ has been subject to a deleteMin, all further inserts are $> k$.

Related work:

Bose et al.'s "Fast Local Searches and Updates in Bounded Universes", which is faster than I need for deleteMin but slower than I need for insert.

Brodnik et al.'s "Worst case constant time priority queue", which uses the exotic "Yggdrasil memory". For the purposes of this question, I'm interested in more standard integer RAM models.

Brodnik and Karlsson's "Multiprocess Time Queue", which limits insert to elements with keys in $(k_{\min}, k_{\min} + \delta_{\min}]$, where $k_{\min}$ is the value of the minimum key.

Note that this is pretty simple with a hash table, but that uses amortization and randomness:

Queues are pairs of a hash table of keys and a copy of the minimum key.
insert adds the key to the hash table and updates the minimum key copy if appropriate.
deleteMin looks up the minimum key in the hash table, then searches for the next minimum key by searching for $k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$ in order.

This paper[1] additionally introduced the "time-finger" property, a unified property encapsulating both the working-set and the queueish properties:

  We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element $x$ in worst-case $O(lg(min\{w_x,q_x\}+2))$ time, where $w_x$ (respectively, $q_x$) is the number of elements that were accessed after (respectively, before) the last access of $x$ and are still in the priority queue at the time when the corresponding operation is performed.

[1] A. Elmasry, A. Farzan, and J. Iacono, ‘A Unifying Property for Distribution-Sensitive Priority Queues’, in Combinatorial Algorithms, vol. 7056, C. Iliopoulos and W. Smyth, Eds. Springer Berlin Heidelberg, 2011, pp. 209–222.


How to design concurrent data structures? I previously asked this question on Programmers.SE, without success.

I'm looking for written learning resources on how to design concurrent data structures. I'm more interested in the design process (e.g., identifying the right invariants) than in the final product (a full code listing).

For a concrete example: I really enjoyed Chris Okasaki's book “Purely Functional Data Structures”, because it's more than just a reference - it guides the reader through the design of its data structures and algorithms. Often, the book motivates a tricky or non-obvious design by first giving a more naïve version, and only then refining it until the desired time complexity (either worst-case or amortized) is achieved. This is the kind of thing I'm looking for.

So:

What techniques or heuristics exist for designing concurrent data structures?
Are there any books, papers, blog posts, tutorials, etc. explaining these techniques and heuristics?

While I have not read deeply in this area, I found The Art of Multiprocessor Programming by Maurice Herlihy and Nir Shavit to be a helpful introduction and survey of techniques.  It explores different algorithms, reasons about how they work and examines the trade-offs, features and limitations of the different approaches.  While it has some formalism I expect it is a fairly introductory and accessible text.

For a flavor of the text, here is the introduction to the section on Atomic Registers from the 2008 edition:

  The obvious place to begin is to ask whether we can solve consensus
  using atomic registers.  Surprisingly, perhaps, the answer is no.  We
  will show that there is no binary consensus protocol for two threads.
  We leave it as an exercise to show that if two threads cannot reach
  consensus on two values, then n threads cannot reach consensus on
  k values, where n > 2 and k > 2.


Complexity of finding large grid minors What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version asking whether there exists such a minor for given $k$) but I don't know of a published proof.

There are some papers on constant factor approximations to this problem, e.g.:

Demaine, E.D.; Hajiaghayi, M.; Kawarabayashi, K. (2005). Algorithmic graph minor theory: Decomposition, approximation, and coloring. FOCS, 637–646.
Gua, Q.-P.; Tamaki, H. (2011). Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time. Theoretical Computer Science 412 (32): 4100–4109.

Is it hard to $(1+\epsilon)$-approximate, for some $\epsilon>0$?

If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$;  you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$.

Then connect each of the $n-2$ remaining nodes of the last row to each of the nodes in $|V| \setminus \{s,t\}$ adding $(n-2)^2$ edges.

The resulting graph $G'$ has a graph minor of size $n \times n$ if and only if there is an Hamiltonian path from $s$ to $t$ in the source graph $G$.

In the following picture a no instance (left) and a yes instance (right) with the corresponding $n \times n$ grid graph minor.


Colouring achieving simple discrepancy bound? Given a hypergraph $H$ with $n$ vertices and $m$ edges,
one of the simplest inequalities on the discrepancy of $H$ is
$\text{disc}(H) \le \sqrt{2n \ln (2m)}$.

This is usually proved by mixing together one type of Chernoff bound using the probabilistic method (for instance, see the outline proof at the Wikipedia article on discrepancy).

Is there a known colouring $\chi \colon V(H) \to \{-1,1\}$ of the vertices of a hypergraph $H$ with $-1$ and $1$ that witnesses this bound?  In other words, such that for every edge $e \in E(H)$,
$$\left|\sum_{v \in e} \chi(v)\right| \le \sqrt{2n \ln (2m)}.$$

Of course, the probabilistic method guarantees the existence of such a $\chi$, but is there an algorithm better than exhaustively checking all possible colourings?

For completeness, the discrepancy of a hypergraph $H$ is the minimum over all possible colourings $\chi \colon V(H) \to \{-1,1\}$ of
the largest value of the local discrepancy $\left|\sum_{v \in e} \chi(v)\right|$ over all edges $e$ of $H$.

I assume you mean a deterministic algorithm. The best discrepancy bound is in fact $O(\sqrt{n\log (m/n)})$ which is $O(\sqrt{n})$ when $m = O(n)$. This the famous Six Standard Deviations Suffice bound of Spencer (1985 TAMS). A coloring achieving this bound can be found in deterministic polynomial time, using a recent result by Bansal and Spencer.

Achieving the random coloring bound of $\sqrt{2n \ln (2m)}$ can be done with simple classic derandomization methods. You can use the method of conditional expectations or variants of the multiplicative weights method. You can even achieve the stronger $\sqrt{2|e|\ln(2m)}$ bound for each edge $e$. See Section 1.1. of Chazelle's book.

For completeness, let me reproduce the multiplicative weights argument, because it's nice and simple. Identify the vertices of $H$ with $[n]$. We will pick $\chi(i)$ for $i = 1, \ldots, n$ greedily. Define $D(e, k) = \sum_{i \in e, i \leq k}{\chi(i)}$ to be the discrepancy of $e$ up to $k$. Let $p(e, k) = \frac{1}{2}e^{\alpha D(e, k)} +\frac{1}{2}e^{-\alpha D(e, k)}$ for $\alpha = \sqrt{2\ln (2m)/n}$, and the potential function $P(k) = \sum_e{p(e, k)}$. Define also $p(e, 0) = 1$ and $P(0) = m$. You can verify that for a random choice of $\chi(k+1)$, $\mathbb{E}P(k+1) \leq P(k)e^{\alpha^2/2}$. So you can just pick each $\chi(k)$ to minimize $P(k)$, and after the final step you have
$$
\frac{1}{2} e^{\alpha |D(e, n)|} \leq \max_e p(e, n) \leq P(n) \leq me^{n\alpha^2/2}.
$$

Simple algebra gives the bound.


Approximation algorithms for Maximum Independent Set on special classes of graphs We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?

What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?

There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.


On $NP=coNP$ problem in average case $1)$Can a $NP$-hard problem can have short certificates that can be verified in deterministic polynomial time for ALL but $\frac{1}{n}$ of the NO instances$?

$2)$ Can one concoct versions of NP complete problems $\Pi_1$ and $\Pi_2$ where probability $p=P(\Pi_2=NO|\Pi_1=YES)=P(\Pi_1=NO|\Pi_2=YES)$ is between $\frac{1}{2}+\epsilon$ and $1-\epsilon$? Then almost all the time short certificates are possible as in $1)$ if $p$ is closer to $1-\epsilon$.

You can construct artificial examples by padding. For example, take an NP-hard language $L$ and pad it by zeroes to $L'=\{x0^{|x|^2}|x\in L\}$. Then the original instances form only a $2^{-n^2}$ fraction, and the answer to the fraction $1-2^{-n^2}$ of the instances is trivially "no" (no certificate is needed at all), yet the language remains NP-hard.

If you look specifically at SAT and the uniform distribution, you need to specify a particular encoding of formulas into bit strings (it will change the effective distribution on formulas). See, for example, the paper by Frieze, Goerdt, and Krivelevich on easy random SAT instances and short proofs of unsatisfiability.


Does this notation have a special meaning? I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot.

http://moxn.brainex.de/pub/dfg.png

Do the pointy angle brackets have a special meaning or did the author choose them just to confuse me?

I googled it and apparently they are commonly used in group theory, which does not make much sense to me here.

Thanks for your input.

btw: The paper is called "A Formal Definition of Data Flow Graph Models" by Kavi, Buckles and Bhat, and is available here.

No special meaning here. The angle brackets simply denote a tuple or pair. The author chose the angle brackets to look prettier than the usual round parentheses. Thus a graph $G$ is a set of vertices $A \cup L$ and a set of edges $E$.


Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?" I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ...correlates precisely with the set of techniques that can be used to prove that the halting problem is undecidable.  (I believe the same holds for Godel's first incompleteness theorem, but that might be off-topic.)

A post on another thread (relating to the halting problem), coupled with my interest in recent days in this notion, led me to post this.  I am curious as to whether or not the answer to either of the following two meta-mathematical questions is 'yes':

1)  Is there a technique that can be used to prove the halting problem that has nothing to do with any paradox?

2)  Is there any paradox that cannot be used to prove the halting problem?

For the record, I recently came up with a (slightly garbled, but probably correct) proof that HP is undecidable based on the Unexpected Hanging paradox.  I believe that the answer to both of the above questions is 'no,' but I'm not sure how to establish this.

If anyone can offer a counterexample to my claim (on either question), I'd love to hear it.  I realize that I've left the term paradox undefined.  Ideally, I'd like to think that a reasonable definition of paradox might be crafted in terms of the halting problem.

(Also, I've always been curious as to whether or not there's a way to express paradoxes mathematically...that's another part of the motivation for asking this.  I've always wondered if there is any way to figure out precisely how many "basically distinct" paradoxes there are, and if there's a way to prove how many there are.)

Thanks,

Philip

EDIT:  I'm trying to clarify, because some posters think that my question is off-topic.  What I am referring to is the notion that a paradox, such as the liar's paradox, the Berry paradox, unexpected hanging paradox, etc., could be used intuitively as a guide for proving the Halting problem.  As an example, Turing used logic similar to Godel's in proving that the halting problem is undecidable; in that sense, I think one could argue that this halting problem proof is "based on" the liar's paradox.  The question, again, is:  is there any paradox that cannot be used to prove THP, or any proof that doesn't use a paradox?

If you believe that this is somehow less on-topic to TCS than, say, the Baker-Gill-Solovay result, please let me know why you think so.

EDIT #2:  I am now trying to more clearly define what I mean by a "paradox."  By a paradox, I mean a natural language situation, idea, or sentence that is intuitively and inherently contradictory.  In a Wikipedia article, they refer to this type of paradox as an "antimony."

I'm not referring to paradoxes that do not lead to an inherently absurd seeming result; i.e., I have no interest in the Obama paradox, or even less blatant paradoxes such as the chicken-and-the-egg paradox.  I am also not interested in paradoxes that seem philosophical but not logical, e.g., Zeno's paradox.

It's difficult to really nail down what I mean by "paradox," so here's a partial list of paradoxes that are relevant:

liar's

Russell's/barber

Berry

Quine

Curry's

Most, but not all of the paradoxes listed in this Wikipedia article under the heading of "Logic" other than vagueness are relevant.  Another question I am wondering about is Newcomb's paradox, or the psychic paradox.

Thanks to anyone who has any ideas on this.  In particular, one way to answer the question that I would appreciate is:  Can you come up with a reasonable way to define/capture the notion of paradox that I'm referring to?

I apologize if this question, as originally asked, was vague or unclear.

It sounds like you are looking for a characterisation of the features required to capture diagonalization arguments.  Lawvere's Diagonal Arguments and Cartesian Closed Categories unified each of the main diagonal arguments back in 1969, including Cantor's and Rice's Theorems, the halting problem, and Gödel's first incompleteness theorem.

Yanofsky's 2003 tutorial discussion A Universal Approach to Self-referential Paradoxes, Incompleteness and Fixed Points provides a nice overview of Lawvere's ideas  (arXiv:0305282).

More recently, Samson Abramsky and Jonathan Zvesper have been taking this further (arXiv:1006.0992).


Problems that are decidable but cannot be verified in polynomial time While working on a somewhat unrelated project for Suresh I recently came across some work done by Page and Opper about User-Composable systems and a portion of their work briefly discussed problems that cannot be verified in polynomial time.  I have been unable to find much information about other problems that cannot be verified in polynomial time or an analysis of a such a problem.  I was wondering if any of you knew of any such problems and/or how to analyze them.

As stated in the comments a better way to phrase this question is:
What problems are decidable but outside of NP?

The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages. That said, many of the interesting problems in computer science lie within NP so they get a lot of attention.

It's conjectured that $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$.

The classes PH, PSPACE, and EXP contain many of the "interesting" problems in $R \setminus NP$, which is what I assume you're asking about in this question. So far NEXP has gotten all of the attention because $NP \subsetneq NEXP$ is the only proper containment that we can prove (by the nondeterministic time hierarchy theorem, as I mentioned above).

Here are some interesting concrete examples of problems in some of these other classes:

Determining if a player has a winning strategy in chess or Go (adapted to n x n boards) is EXP-complete.
MAJ-SAT, the problem of determining whether over half of the assignments to the variables in a boolean formula satisfy that formula, is in PSPACE. It is also complete for the smaller class PP.
EXACT-CLIQUE, the problem of determining whether the largest clique in a graph is of size exactly k, is in $\Sigma_2^P$, part of the second level of the polynomial hierarchy.


List of papers on Runtime and Statistical Tradeoffs on Machine Learning I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having more data actually help the algorithms run faster? Or maybe not run faster but yield better results.

Let me give you two papers with such examples:

“SVM Optimization: Inverse Dependence on Training Set Size”, Shalev-Shwartz,
Srebro.

This first example discusses how the runtime of SVM optimization should decrease as the training data increases in a theoretical (and empirical) framework.

A second example:

“More Data Speeds up Training Time in Learning Halfspaces over Sparse Vectors”,
Daniely, Linial, Shalev-Shwartz.

On how we get computational speed ups as data increases when learning halfspaces over sparse vectors.

I was wondering if there were other interesting papers on the same or similar spirit as the two above.

We explored the Runtime-Accuracy tradeoff in the context of nearest neighbors in a 2010 COLT paper [journal version]:
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374

Roughly speaking, your dataset has margin $\gamma$ if every pair of opposite-labaled points is at least $\gamma$ apart in distance. You can also impose a desired margin by counting the violating pairs as sample error (this is analogous to the SVM setting where it may be advantageous to impose a margin that's bigger than the data margin, at the expense of some violations). Unlike SVM, the metric margin very much affects the algorithmic runtimes. We also have margin-based generalization bounds. Thus, one can answer questions such as: if my runtime is on a certain budget, what sort of accuracy can I expect?

We continued this line of research in last year's NIPS paper:
http://papers.nips.cc/paper/5528-near-optimal-sample-compression-for-nearest-neighbors.pdf

where we showed that the margin also allows for the sample to be compressed (in fact, nearly optimally).


Can one return to a TCS research job after an excursion to a non-research industry job? I have heard from some senior researchers in theoretical computer science that working in a non-research industry job, even just for a few years, will kill your career as a TCS researcher.
However I am suspicious of the claim that the road from being a TCS researcher to a non-research job in the industry is a one-way street. I want to know if this claim is plausible and any implications of making an excursion into a non-research job in the industry in case one later decides to return to a research job in academia.

Do you know examples of people who went to non-research industry jobs after their completing their PhD, worked there for a few years, and successfully made it back into academia as researchers (e.g. got research faculty positions)?
If yes, what fraction of senior researchers (tenured) do they constitute in your department or departments you are familiar with?
What fraction of such candidates who apply for academic research positions fail to obtain one?
Does the number of years in non-research jobs before returning make a difference?
More generally, what role would such excursions play in decisions made by hiring committees?

Since the answer may vary from a region to another one (e.g. North America, Europe, etc.) please mention the region you are talking about in your answer.
For the purposes of this question, let's consider all jobs in which the main task is conducting (publishable) research as "academia" and all jobs in which the main task is not conducting (publishable) research and it is difficult to do research and publish papers as "industry".

Let me disagree with the other responses.

While there are clearly notable examples of people who can transition to industry and back (see other answers), going to a non-research industrial position, even for a couple years, will make it very hard to return to academia, unless you're already very famous.

The reason is not because academics look down on industry or will think you "impure," but rather that it's very hard to stay active publishing when your job requires all your work time be spent on something else.  And if you haven't published anything for a couple years, it will be nearly impossible to convince a hiring committee to choose you over people who have. (Again, this doesn't apply if you already have a Turing award, etc.)

But if you can find the time to stay active in research and publish while working in your industry position, then you can still be competitive.  It's just likely to be a losing battle, and your other job responsibilities will realistically probably end up taking priority over research on-the-side.


Physics results in TCS? It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are

Quantum computation
Statistical mechanics results used in complexity analysis/heuristic algorithms.

So my question is are there any major areas I am missing?

My motivation is very simple: I'm a theoretical physicist who has come to TCS via quantum information and I am curious as to other areas where the two areas overlap.

This is a relatively soft question, but I don't mean this to be a big-list type question. I'm looking for areas where the overlap is significant.

The search technique simulated annealing is inspired by the physical process of annealing in metallurgy.

Annealing is a heat treatment where the strength and hardness of the substance being treated can change dramatically. Often this involves heating the substance to an extreme temperature and then allowing it to cool slowly.

Simulated annealing avoids local minima/maxima in search spaces by incorporating a degree of randomness (the temperature) in the search process. As the search process proceeds, the temperature gradually cools, which means that the amount of randomness in the search decreases. Apparently it is quite an effective search technique.


Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas The k-FLIP SAT parametrized problem is defined as:

Input: a 3-CNF formula $\varphi$ with $n$ variables and a truth assignment $\sigma : [n] \to \{0,1\}$
Parameter: $k$
Question: can we transform the assignment $\sigma$ into a satifying assignment $\sigma'$ for $\varphi$ flipping the truth value of at most $k$ variables?

The problem is clearly in FPT (Stefan Szeider: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT. Discrete Optimization 8(1): 139-145 (2011))

  Does it admit a polynomial kernel ? (under reasonable complexity assumptions)

The recent cross-composition techniques (see Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch, "Kernelization Lower Bounds By Cross-Composition") seem unuseful for this problem. And they also seem unuseful for similar problems that ask if a given solution to an NP-hard problem can be found from a given instance by local search (limiting the search to the neighbours of the given instance, under some natural distance measure).

The problem does not have a polynomial kernel unless NP is in coNP/poly. The cross-composition technique from our paper applies in a nontrivial way.

Let me show how the classic Vertex Cover problem OR-cross-composes into the k-FLIP-SAT problem; by the results in the cited paper, this is sufficient. Concretely, we build a polynomial-time algorithm whose input is a sequence of Vertex Cover instances $(G_1,k), (G_2, k), \ldots, (G_t, k)$ that all share the same value of $k$ and all have exactly $n$ vertices. The output is an instance of $k$-FLIP SAT with a parameter value of $O(k + \log t)$, which is sufficiently small for a cross-composition, such that the $k$-FLIP SAT instance has answer yes iff one of the input graphs has a vertex cover of size $k$. By duplicating one input (which does not change the value of the OR) we can ensure that the number of inputs $t$ is a power of two.

The composition proceeds as follows. Number the vertices in graph each input graph $G_i$ as $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$. Make a corresponding variable in the FLIP-SAT instance for each vertex of each input graph. Additionally, make a selector variable $u_i$ for each input instance number $i \in [t]$. For each input graph $G_i$, we add some clauses to the formula. For each edge $\{v_{i,x}, v_{i,y}\}$ of graph $G_i$, add the clause $(v_{i,x} \vee v_{i,y} \vee \neg u_i)$ to the formula, which will encode "either one of the endpoints of this edge is set to true, or the instance $i$ is not active". In the initial assignment, all vertex-variables are set to false and all selector variables $u_i$ are set to false, so that these clauses are all satisfied. To build the OR-behavior into the composition we will augment the formula to ensure that a satisfying assignment sets at least one selector to true, and must then also form a vertex cover of the selected graph.

To make sure we can do this selection while keeping the flip distance small compared to the number of inputs $t$, we use the structure of a complete binary tree with $t$ leaves, which has height $\log t$. Number the leaves from $1$ to $t$ and associate the $i$-th leaf with the variable $u_i$ that controls if input $i$ is active or not. Create a new variable for each internal node of the binary tree. For each internal node, let its corresponding variable be $x$ and the variables of its two children be $y$ and $z$. Add the clause $(\neg x \vee y \vee z)$ to the formula which captures the implication $(x \rightarrow (y \vee z))$, enforcing that $x$ can only be true if one of its children is true. To complete the formula, add a singleton clause saying that the variable of the root node of the binary tree must be true. In the initial truth assignment, the values of all variables for internal nodes is set to false, which satisfies all clauses of the formula except for the singleton clause requiring the root node of the tree to have its variable true.

This completes the description of the formula and truth assignment. Set the parameter $k'$ of the FLIP DISTANCE problem to be equal to $(k + \log t + 1)$, which is suitably bounded for a cross-composition. It remains to show that we can flip $k'$ variables to make the formula true iff some input graph $G_i$ has a vertex cover of size $k$.

In the reverse direction, suppose that $G_i$ has a size-$k$ vertex cover. Set the $k$ variables corresponding to the $k$ vertices in the cover to true by flipping them. Set the selector variable $u_i$ to true to encode that input $i$ is activated, and flip the variables of the $\log t$ internal binary tree nodes on the path of leaf $i$ to the root to true. It is easy to verify that this is a satisfying assignment: the implications in the binary tree are all satisfied, the root node's value is set to true, the clauses that check edges of $G_{i'}$ for $i' \neq i$ remain satisfied because $u_{i'}$ remains false, while the clauses for graph $G_i$ are satisfied because for every edge we set at least one endpoint to true.

For the forward direction, suppose that the formula can be satisfied by flipping at most $k + \log t + 1$ variables. Then we must flip the variable of the root node to true. The implications in the binary tree enforce that at least one selector variable of a leaf is set to true, say $u_i$. To satisfy the implications encoded in the binary tree, all internal nodes on the path from $u_i$ to the root were set to true, accounting for $1 + \log t$ flips. Since $u_i$ is set to true, the clauses made for graph $G_i$ are not satisfied on the literal $\neg u_i$, so they are satisfied because one of the endpoints of each edge of $G_i$ is set to true. Since at least $1 + \log t$ variables of the binary tree were flipped, at most $k$ vertex-variables are flipped to true in this solution. This encodes a vertex cover of size $k$ in $G_i$ and proves that one of the inputs is a YES-instance. This completes the proof.


Implementation that solves minimum set cover Does anyone know of any tools that solve the approximate minimum set cover problem?

I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about more sophisticated algorithms/heuristic that do better on many problems in practice.  (e.g., Algorithms for the Set Covering Problem by Caprara et al.)  Are there any implementations generally available?  Any tools that others can use to find approximately optimal solutions, for large problem instances?  I'd prefer to use an existing tool, rather than try to understand and implement these sophisticated algorithms myself.

sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider Espresso, a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering is chosen with a command line switch.

ie it implements the Quine-McCluskey method where set cover is part of the final optimization. there is some research on an improved exact set cover (also called the "minimum canonical cover") by McGeer et al called Espresso Signature which was implemented but may be more difficult to obtain source code.

note the set cover algorithms are apparently decoupled in the code but possibly not decoupled in the interface. ie it might require a little bit of "wrapper" coding to provide a direct interface to the set cover subroutines. another possibility is using monotone formula inputs in which there are no "derived" prime implicants other than those supplied as input in which the entire logic minimization reduces to set cover only.


Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT? Getting Started

Consider a parameterized problem $F$.  We use $n$ to denote the input size and $k$ to denote the parameter.  Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{N}}$.

Definitions

We say that $F$ is in non-uniform $FPT$ if there exists a constant $c$, a function $f(k)$, and a family of algorithms $\{A_k\}_{k\in\mathbb{N}}$ such that for every $k$, $A_k$ solves $F_k$ in $O(f(k) * n^c)$ time.

We say that $F$ is in uniform $FPT$ if there exists a constant $c$ and a function $f(k)$ such that there exists a parameterized algorithm that solves $F$ in $O(f(k) * n^c)$ time.

Remark: One could construct unnatural examples of paramterized problems that are in non-uniform $FPT$, but are not in uniform $FPT$.  For example, take an undecidable language and define the parameter $k$ to be the input length.

Question

Does there exist a natural parameterized problem $F$ that is proven to be non-uniform $FPT$ and suspected (yet not proven) to be uniform $FPT$?

A More High-level Question

Does uniform vs non-uniform parameterized complexity have any relationship to uniform vs non-uniform circuit complexity?

In Downey and Fellows' 2013 book (Fundamentals of Parameterized Complexity; Section 2.2), they mention an example of a problem in non-uniform FPT (Graph Linking Number) and briefly discuss that it's open whether this problem is in uniform FPT. This problem seems fairly natural.

When considering non-uniform parameterized complexity, one can look at many different variants, and many of them do have some relations to (non-uniform) circuit complexity. As far as I know, this hasn't been explored much.

For an overview of some basic connections, you could have a look at a report that I wrote: An Overview of Non-Uniform Parameterized Complexity.


What would be the consequences of factoring being NP-complete? Are there any references covering this?

As well as implying NP=co-NP, it would also imply that BQP contained NP.

It would also seem to imply that hard instances of NP-complete problems were easy to generate.


What are the limits of total functional programming? What are the limitations of total functional programming? It is not Turing-complete, but still supports a large subset of the possible programs. Are there important constructs that you could write in a Turing-complete language, but not in a total functional language?

And is it correct to say that programs written in total functional languages can be completely statically analysed, while static analysis in Turing-complete languages is limited by things like the halting problem? With that I do not mean that in total functional languages everything can be staticaly determined, because some things are only known at runtime, but I mean that in theory, programs written in an ideal total functional programming language, can be analysed so that everything that could in theory be determined statically can be determined statically. Or are there still undecidable problems inherit in total functional languages that make static analysis incomplete? Some problems will always be undecidable, no matter in which language they are written, but I am interested in such problems that are inherit to the language, like the halting problem in Turing-complete languages.

It depends on the total functional language.

This answer sounds like a cop-out, but nothing more specific can be said. After all, consider whatever important decidable program that you're interested in. Write a program in your favorite Turing-complete language to solve it. Since the problem is decidable, your program will halt on all inputs.

(Arguably, a non-decidable problem could have interesting programs, but not such that people can use, because they'll never be able to wait long enough to know the answer.)

Now, define a new language such that it has only one valid input program: the program that you just wrote, with the same semantics as it had before. It's certainly total, since all inputs to all programs written in it (of which there's only one) always terminate.

This cheap trick is actually useful: the language Coq, for example, is a total functional language in that no program typechecks unless there is a proof that it terminates. (If you were to waive that requirement, it would be Turing-complete, so the only obstacle is finding a proof of termination.)

I'm not sure what you mean by "everything that could in theory be determined statically can be determined statically"; it sounds tautologically true. Nonetheless, total languages aren't inherently easy to analyze; you know that nothing diverges, which is a useful fact, but the relationship between input and output is still complex. (In particular, there are still infinitely many possible inputs, so you can't exhaustively try them all, even in theory.)


Avoiding Cycles with Unification and Subtyping Context

I realize that subtyping often doesn't admit principle types, and that inference in the presence of subtypes is undecidable. I'm working in a context where typechecking should simply fail there is not a single most general solution, and where annotations can be added to aid inference.

Suppose that we have a type system where, during typechecking, some types need to be inferred using unification, and may be type variables $\alpha, \beta$ etc.

If, at some point, the constraint $\alpha <: T_1 \to T_2$, where $\to$ is the usual function type constructor, then we can decompose this into $\alpha = \alpha_1 \to \alpha_2$, with $T_1 <: \alpha_1$ and $\alpha_2 <: T_2$.

The Problem

The problem arises if you have constraints  $\alpha_2 <: \beta_1 \to \beta_2$, $\beta_2 <: \alpha_1 \to \alpha_2$.

In such a case, we get:
$\alpha_2 = \alpha_{21} \to \alpha_{22}, \beta_1 <: \alpha_{21}, \alpha_{22} <: \beta_2 $ from the first constraint,
and $\beta_2 = \beta_{21} \to \beta_{22}, \alpha_2 <: \beta_{21}, \beta_{22} <: \alpha_2$ from our second problem.

If we substitute from our equalities, we then get (among other constraints), $\alpha_{22} <: \beta_{21} \to \beta_{22}$ and $\beta_{22} <: \alpha_{21} \to \alpha_{22}$, which is  identical to the form of our original problem. Clearly if we continue solving this way, we will never terminate.

When going to write a proof of termination, the problem is that substitution decreases the number of unsolved variables but increases the structural-size of the problems, and solving subtyping decreases the structural size of the problems, but increases the number of unsolved variables, so they don't work in a well-founded ordering.

My Solution Attempt

With my definition of subtyping, if $\alpha_2 <: \beta_1 \to \beta_2$, $\beta_2 <: \alpha_1 \to \alpha_2$ has no solution. The problem seems to be the "cycle", so if we do a sort of occurs check and fail when cycles are detected (or turn them into equality cycles, which will fail except for $\alpha <: \beta \wedge \beta <: \alpha$).

I'm not exactly certain how to formalize a cycle like this, and how such a check would give me something that I can use in a proof of termination.

My Question

My work is about the specifics of a particular subtyping system, but the problem here seems very general, so I'm wondering if this is a known problem, if there are known solutions to it, and if there is research that either formalizes or disproves my intuition about cycles.

What kind of cycles in subtyping constraints do I need to eliminate to avoid this infinite looping? Or is this a deeper problem with no solution?

From what I understand, it is likely that your subtyping constraints will always be of the form $\alpha \subseteq A$ or $A \subseteq \alpha$, where $\alpha$ is a unification variable. If that is the case, then one idea would be to follow a kind of occurs-check discipline. One thing that you can do to eliminate cycles is to maintain the invariant that there is a solution to your system. The solution that is the easiest to built (but the least general in some sense) is to set $\alpha := A$ for all constraints of the form $\alpha \subseteq A$, and to set $\alpha := \top$ for all constraints of the form $A \subseteq \alpha$ (and there is probably some work to do if $\alpha$ appears to the left/right of several constraints). For this solution to be valid, the simultaneous instantiation of all the unification variables should not induce a cycle in their definition. To do that, you can construct a form of dependency graph on unification variables, in which $\alpha$ depends on the unification variables of $A$ for each constraint $\alpha \subseteq A$. You then need to ensure that the obtained graph does not contain cycles.


Counting the number of distinct s-t cuts in a oriented graph I am trying to find the number of distinct s-t cuts in a oriented unweighed graph. In an article Enumeration in Graphs p. 45 I found good way how to enumerate those cuts (section 7.3). Is there a faster or simpler algorithm I can use if I am interested only in the number of such cuts and I do not actually need to enumerate it?

The definition of a s-t cut I am using is following. We have a directed graph where two vertices are labelled S and T. Cut is a minimal set of edges of a graph such that by removing those edges there will no longer exist a path from vertex S to vertex T.

I tried to ask this at Stack Overflow and I have been pointed here.

Counting the number of s,t-cuts is #P-complete.  This is a result by Provan and Ball.

J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

Therefore, unless some complexity-theoretic collapse happens, you cannot get essentially faster algorithm than listing all of them.


Maximizing difference of a submodular and a modular function I'm considering a network planning problem which is stated as follows:
From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that
\begin{equation}
f(\mathcal{A}) - \sum_{v_i \in \mathcal{A}} c_i
\end{equation}
is maximized where $f$ is a monotone submodular function and $c_i \ge 0$ is the cost of selecting $v_i$. The problem is an instance of nonomonotone submodular maximization for which a local search heuristic with approximation bound of $\frac{2}{5} - \frac{\epsilon}{n}$ is presented in

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: "Maximizing Non-Monotone Submodular Functions ", FOCS 2007.

I'm wondering if anyone is aware of a better approximation algorithm for my specific problem?

To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there exists $\gamma \in [0, 1]$ such that $f$ is weakly $\gamma$-submodular, i.e such that

$$
\sum_{i \in B\setminus A}f(A \cup \{i\}) - f(A)  \ge \gamma (f(A \cup B) - f(A)),\;\forall A,B \subseteq [n].
$$

Then, greedy maximization produces a subset $A^G$  with $k$ elements such that

$$
f(A^G)-h(A^G) \ge (1-e^{-\gamma})f(A^*)-h(A^*),
$$

where $A^*$ is the $k$-element subset of $[n]$ which maximizes $f(A)-h(A)$.
This is a direct consequence of Theorem 3 of this ICML paper.


How "hard" is it to maximize a polynomial function subject to linear constraints? General Problem

Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following optimization problem?

\begin{align*}
 \text{Maximize} & \;\; f(\mathbf{x}) \\
  \text{Subject to: } & \;\, \ell_i(\mathbf{x}) \le 0\text{ for all } i
\end{align*}

We can assume that the region determined by the constraints is bounded.

Related, but More Specific, Problem

Suppose we have a bounded polytope (represented as the intersection of a set of linear inequalities).
I want to compute the maximum volume of an (axis parallel) hyperrectangle completely contained in the polytope. What is the complexity of solving this problem?

Help on either of these problems is greatly appreciated.

Your problem is NP-hard, even for polynomials of degree 2.
The crucial reference is

  Theodore Motzkin and Ernst Strauss  (1965)
  "Maxima for graphs and a new proof of a theorem of Turan"
  Canadian Journal of Mathematics 17, pp 533-540

Motzkin and Strauss consider an undirected graph $G=(V,E)$
with vertex set $V=\{1,2,\ldots,n\}$.
They show that the optimal objective value of the following optimization problem equals $1-1/\omega$, where $\omega$ is the clique number of $G$:

\begin{eqnarray*}
\max &&\sum_{ij\in E} x_ix_j \\[2ex]
s.t. &&\sum_{i\in V} x_i=1 \\[1ex]
&& 0\le x_i\le 1~~~ \text{ for all $i\in V$}
\end{eqnarray*}

Since computing the clique number is NP-hard, this implies the NP-hardness of maximizing a multivariate polynomial function subject to linear constraints.


Does the order of declarations in an inductive type matter? I was wondering if the order of declarations of an inductive type can matter.

For example in Coq you can define Nat either by:

Inductive Nat :=
  | O : Nat
  | S : Nat -> Nat.

or

Inductive Nat :=
  | S : Nat -> Nat
  | O : Nat.

This will perhaps change the order of the parameters in the automatically generated eliminator, but that’s not a big deal.

What I’m wondering is if it is possible to write a declaration like

Inductive typewhereordermatters :=
  | cons1 : type1
  | cons2 : type2.

where type2 is a dependent type, depending on cons1? (and in this case, write the declarations in the other order would not have any meaning, because type2 would be referring to cons1 which does not exists yet).

The order does not matter. I cannot think of a case where it would. As Andrej Bauer points out in a comment, if you change the order the result is canonically isomorphic to the original.
One case cannot depend on another case. The elements of the sum represent a choice, so it doesn't make sense that the choice taken depends upon a choice that is not taken.


Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$ In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his factorization algorithm. The standard algorithm outputs $r'$, a divisor of the order $r$ of $x$ modulo $N$. Instead of checking if $r'=r$ by checking if $x^{r'}\equiv 1 \mod N$, the improvement is the following :

  [F]or a candidate $r$ one should consider not
  only $r ′$ but also its small multiples $2r ′ , 3r ′ , \dots$ , to see if these are the actual order of $x$. [... This] technique will reduce the expected number of
  trials for the hardest $n$ from $O(\log \log n)$ to $O(1)$ if the first ($\log n)^{1+\epsilon}$ multiples of $r ′$ are
  considered [Odylzko 1995].

The reference to [Odylzko 1995] is a “personal communication”, but I was not present when Peter Shor and Andrew Odlyzko discussed this... I perfectly understand why it is an improvement, but I don't know how to show the number of trials is reduced to $O(1)$. Do you know any proof of this?


How do 'tactics' work in proof assistants? Question: How do 'tactics' work in proof assistants? They seem to be ways of specifying how to rewrite a term into an equivalent term (for some definition of 'equivalent'). Presumably there are formal rules for this, how can I learn what they are and how they work? Do they involve more than choice of order for Beta-reduction?

Background about my interest: Several months ago, I decided I wanted to learn formal math. I decided to go with type theory because from preliminary research it seems like The Right Way To Do Things (tm) and because it seems to unify programming and mathematics which is fascinating. I think my eventual goal is to be able to use and understand a proof assistant like Coq (I think especially being able to use dependent types as I am curious about things like representing the types of matrixes). I started off knowing very little, not even rudimentary functional programming, but I'm making slow progress. I've read and understood large chunks of Types and Programming Languages (Pierce) and learned some Haskell and ML.

The basic tactics either run an inference rule forwards or backwards (for example, convert hypotheses $A$ and $B$ into $A\wedge B$ or convert goal $A\wedge B$ into two goals $A$ and $B$ with same hypotheses), apply a lemma (~ function application), split up a lemma about some inductive type into a case for each constructor, and so on. Basic tactics may succeed or fail depending upon the context in which they are applied. More advanced tactics are like little functional programs that run the basic tactics, perform pattern matching over the terms in the goal and/or assumptions, make choices based on the success or failure of tactics, and so forth. More advanced tactics deal with arithmetic and other specific kinds of theories. The key paper on Coq's tactic language is the following:

D. Delahaye. A Tactic Language for the System Coq. In Proceedings of Logic for Programming and Automated Reasoning (LPAR), Reunion Island, volume 1955 of Lecture Notes in Computer Science, pages 85–95. Springer-Verlag, November 2000.

The formal rules which form the essence of the basic tactics are defined in the Coq users guide here or in Chapter 4 of the pdf.

A quite instructive paper on implementing tactics and tacticals (essentially tactics that take other tactics as arguments) is:

Amy Felty. Implementing Tactics and Tacticals in a Higher-order Programming Language Journal of Automated Reasoning, 11(1):43-81, August 1993.

Coq's tactic language has the limitation that the proofs written using it hardly resemble proofs one does by hand. Several attempts have been made to enable clearer proofs. These include Isar (for Isabelle/HOL) and Mizar's proof language.

Aside:
Did you also know that the programming language ML was originally designed to implement tactics for the LCF theorem prover? Many ideas developed for ML, such as type inference, have influenced modern programming languages.


Exact planar electrical flow Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor.  How quickly can we compute the exact effective resistance between two vertices in G?  Equivalently, how quickly can we compute the exact current flowing along each edge if we attach a 1V battery to two vertices in G?

Kirchhoff's well-known voltage and current laws reduce this problem to solving a system of linear equations with one variable per edge.  More recent results — described explicitly by Klein and Randić (1993) but implicit in earlier work of Doyle and Snell (1984) — reduce the problem to solving a linear system with one variable per vertex, representing that node's potential; the matrix for this linear system is the Laplacian matrix of the graph.

Either linear system can be solved exactly in $O(n^{3/2})$ time using nested dissection and planar separators [Lipton Rose Tarjan 1979].  Is this the fastest algorithm known?

Recent seminal results of Spielman, Teng, and others imply that the Laplacian system in arbitrary graphs can be solved approximately in near-linear time.  See [Koutis Miller Peng 2010] for the current best running time, and this amazing article by Erica Klarreich at the Simons Foundation for a high-level overview.  But I'm specifically interested in exact algorithms for planar graphs.

Assume a model of computation that supports exact real arithmetic in constant time.

Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a paper  I have with Günter Rote and Ares Ribó and in this paper by Alon and Yuster.

The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^\omega})$. This paper by Kenyon might also contain helpful ideas.


For which families of graphs is Generalized Geography in $P$? As @Marzio mentioned, the following game is known as Generalized Geography.

Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:

At each turn (two players alternating), a player chooses $u\in N(v)$, and then the following happens:

$v$, as well as all of its edges, is removed from $G$.
$u\to v$ (i.e. $v$ is updated to be the vertex $u$).

The player who is forced to select a "dead end" (i.e. a vertex with no outgoing edges) loses.

In which graph families is the optimal strategy computable in polynomial time?

For example, it's easy to see that if $G$ is a DAG, then we can easily compute the optimal strategy for the players.

Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:

Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245

GG (and some other PSPACE-complete variants) are linear-time-solvable in graphs of bounded treewidth.

SIDE NOTE: one of the Generalized Geography variants that has recently been proved to be PSPACE-complete is Tron (Light Cycles game): given an undirected graph, two players pick two different starting vertices, and then take turns, by moving to an adjacent vertex from their respective previous one in each step. The game ends when both players cannot move anymore. The player who traversed more vertices wins (it was conjectured to be PSPACE-complete in 1990 by Bodlaender and Kloks).
Tillmann Miltzow, Tron, a combinatorial Game on abstract Graphs (2011)

Edit: I made a small program to test the game on small $n \times m$ rectangular solid grid graphs (undirected), and the result suggests that it is polynomial time solvable also for this class of graphs (assuming that the first node picked by player A is the top-left node):

               Width n
           1 2 3 4 5 6 7 8
         1 A B A B A B A B    Winning matrix up to 8x8
         2   B B B B B B B
         3     A B A B A B
Height m 4       B B B B B
         5         A B A B
         6           B B B
         7             A B
         8               B

Curiously, the same matrix is obtained if player A can choose an arbitrary starting node.

As said in the comments, I think that the complexity of deciding if there is a winning strategy when GG is played on solid grid graphs (with arbitrary shapes, but without holes) is not known and probably it is not so easy to prove something about it (indeed the - somewhat related - problem of deciding if a solid grid graph has an Hamiltonian path is still open, though deciding if a solid grid graph has an Hamiltonian cycle is polynomial time solvable).

A final trivial note: GG is polynomial time solvable also in complete graphs.