Splitting line segments with a line Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
 Here splitting means that if $l$ intersects a line segment $xy$ in a point $z$ then $xy$ gets replaced by two new line segments $xz$ and $zy$.

The goal is to chose $l$ such that it minimizes the length of the longest line segment in $S'$.

I would be interested to know if this problem has been studied before.
What confuses me is that the problem does seem to be continuous and not discrete.

I don't know about whether this specific problem has been studied before but I can point you to a general class of problems that include it and that have been studied: This looks like an LP-type problem (or perhaps even a low-dimensional linear program although I am not quite seeing how to coordinatize it so that works). If so it can be solved by a linear-time combinatorial algorithm.

To set this up as an LP-type problem, we need an objective function mapping sets of line segments to some totally ordered set of solution values. The obvious objective function to use here is the numerical value $l$ that you're trying to optimize (the length of the longest split segment), but I think that's not quite good enough. Instead you should use a lexicographic combination of $l$ with the coordinate vector of a line achieving value $l$. With this lexicographic combination, the problem automatically satisfies the monotonicity and locality properties of LP-type problems: adding another segment to an instance only makes its solution worse, and if a given line is the solution to two sets $A\subset B$ of segments, and adding a new segment $x$ to $A$ doesn't change the solution (because the line cuts $x$ in pieces shorter than $l$) then adding $x$ to $B$ also doesn't change the solution (because the same line cuts $x$ in the same way).

So the main remaining question is whether this problem has bounded dimension, where the dimension of an LP-type problem is defined as the largest size of a minimal instance with a given solution value. So, in any problem of this type, is there a subset of a constant number of the line segments that has the same solution as the whole problem? I think the answer must be yes, because the optimal line must cross some three segments at points that are at distance $l$ from the ends of their segments (else it could be moved continuously to a better solution) and those three segments should determine the solution value.


What are the main sub-areas of theoretical computer science? I often want to give students a broad view of theoretical computer science, in the beginning of algorithms class or when advising a new student. It is hard for me to decide which sub-areas to talk about and how much emphasis to put on each of them.

Therefore, my question is: What are the main sub-areas of theoretical computer science and what is their relative "size"? Let's say the size is the number of researchers who work mostly in that area.

Of course the division into sub-areas is a clustering problem with no unique answer. I also don't expect people to have precise statistics for the size of each area, but some feeling of the relative sizes is already helpful.

Also I wonder if 'size' is the right metric. that tends to vary as subfields come in and out of fashion. For example, a visitor from the 1980s would be very puzzled as to where all the parallel algorithms disappeared to. Someone attending SoCG in the last five years would think that we should call it the Symposium on Computational Topology :).

Maybe the best thing to do is to let the student browse proceedings from theory conferences to get a sense of what's in vogue RIGHT NOW, and emphasize that this answer will change over time.


Where is the counting hierarchy if polynomial hierarchy collapses? Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses.

Does the counting hierarchy collapse as well?
Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of counting hierarchy that imply collapse results of polynomial hierarchy and vice versa?

Yes, the counting hierarchy collapses in this case: Suppose that $P^{\#P}\subseteq BPP$. We know that $P^{\#P}=P^{PP}$, so $P^{PP}\subseteq BPP$. Consider the second level of the counting hierarchy, $C_2^P=PP^{PP}$. By hypothesis, we have

$$C_2^P=PP^{PP}\subseteq PP^{P^{PP}}\subseteq PP^{BPP}\subseteq PP\subseteq P^{PP}\subseteq BPP $$

So the counting hierarchy collapses to $BPP$.

As for your second question, I don't know any implications that would follow from a weaker collapse of the counting hierarchy, i.e. $CH=PP$ or something weaker. That question has been asked before, here, without answers. This question asks whether $PH\subseteq PP$; but nothing more would necessarily follow if $CH$ collapses, even under that hypothesis. According to this answer, it is an open problem whether $PH^{\#P}$ collapses (note that $PH^{\#P}$ does not trivially collapse as a result of Toda's theorem).

There are at present, according to the Zoology active inclusion diagram, no oracles relative to which the counting hierarchy collapses to any level other than $CH=P^{\#P}$; that is, it is an open problem to find an oracle relative to which $P^{\#P}\subsetneq CH$ or indeed $P^{\#P}\subsetneq PSPACE$. Hence there are no oracles, therefore, supporting any argument relating non-trivial collapses of the counting hierarchy to the polynomial hierarchy.


Why SHA-224 and SHA-256 use different initial values? Wikipedia - SHA-2 says

  SHA-224 is identical to SHA-256, except that:

  the initial variable values h0 through h7 are different, and
  the output is constructed by omitting h7.

RFC3874 - A 224-bit One-way Hash Function: SHA-224 says

  The use of a different initial value ensures that a truncated SHA-256
  message digest value cannot be mistaken for a SHA-224 message
  digest value computed on the same data.

My questions:

Is the above quoted reason the only reason why SHA-224 and SHA-256 use different initial values?
Why is it important to make sure that a SHA-256 message digest value cannot be mistaken for a SHA-224 message digest value?
If we use the same initial values for both hash functions, will the security of either hash function worsen? If yes, how?

This We called Domain Separation, when we use same algorithm for different output size.
Separation is necessary because if i found two messages which have hash value (SH256), differs only in last octet and then i can publish the hash value as first 7 octet showing i used SHA224. since i already have two messages colliding on SHA224 which i can use later for forgery attack.
Using domain separation we can avoid such situation


logic in the presence of doubt, uncertainty, lies I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity.

This is not a gratuitous exercise.  This may have applications to computer science, since we are always piping data-sets into each other.  Some of these data sources may be specious, the piping process can break down, or the conclusions we draw from them can be wrong as well.

One way of approaching Frankfurt's theory may be to express in terms of logical circuits, where the integrity of the gates or the inputs may be in question.

On pencil and paper, we mostly use boolean logic with values $T,F$ and gates $\mathbf{not},\vee,\wedge$.  Maybe it is possible to perturb boolean logic slightly to model how circuits are robus or break down with respect to noise.

Do logical theories exist accounting for doubt and uncertainty? Can we measure how much a lie hurts the integrity of a conclusion?

I'm sure that even with a collection of verifiably true or false statements, it's possible to write arguments (and conclusions) whose values are in the middle.  Or even to decide if one argument is "more" valid than another.

I apologize ahead of time, if there's no single question here.

COMMENTS

Logic is a very broad subject, but I'm not a logician so I'm not sure how to be more specific.  Ease of use is a priority, which is why I consider just bootstrapping Boolean logic.

I think that when we "call out" a proposition... the conclusion may be true, but the thought process may be wrong, as VijayD suggests in the comments.

It's not clear if bulls**t is the same as uncertainty -- we may be quite sure the proof is wrong.

I think it would be nice to see an extension of boolean logic, which assigns a value to proofs rather than statements.  A proof where all the steps are valid gets assigned a value of T, if steps are faulty, we'd like to measure to what extent the conclusion doesn't follow from the premises.

This idea must have been tried before.  A Google search comes up with the notions like heyting algebra, topos, multi-valued logic and even more sources in the comments and answer.

There isn't really a single formalization of the kind of thing you are asking. There are many, many aspects to truth, trust, lies, and fallible reasoning, and this leads to an enormous variety of logical formalisms, each handling different aspects of this problem.

If you want to account for uncertainty about your hypotheses, the traditional route is via Bayesian probability theory. See E.T. Jaynes' (sadly incomplete) Probability Theory: the Logic of Science for a good exposition of this point of view.
One difficulty with probabilistic methods is that it is difficult to interpret quantifiers, essentially because limits do not necessarily exist. That is, a proposition may hold for all finite approximations, but fail to hold in the infinite limit.

Taking this into account leads you to view propositions topologically, which (a) leads you the Beth semantics of intuitionistic logic, and (b) also leads you to geometric logic. See Steve Vickers' Topology via Logic for an introductory exposition, and Peter Johnstone's Stone Spaces to jump into the deep end of the pool.

(However, to my knowledge there is not yet any satisfactory constructive account of probability theory.)
If you are interested in the difference between truth and belief, then you need to look at epistemic logic. The idea is to extend traditional logic with a modality $B_X(A)$, which is intended to read "$X$ believes $A$". See the SEP entry on epistemic logic for an introduction, and follow the bibliographic links in the article for more details.
However, when you have multiple agents, you also have to think about the difference between truth and assertion. This is particularly important in applications like authorization (e.g., I can look at a file, because the owner of the file has the right to delegate the right to look at it, and says that I can look at it). There is a huge amount of work on this; a good entry point into this literature is in Deepak Garg's PhD thesis, Proof Theory for Authorization Logic and its Application to a Practical File System.
Next, one of the traditional principles of logic is ex falso quodlibet: that is, $\bot \to A$ holds for all propositions $A$ — if you assume false, everything follows. If you are thinking about the possibility of believing false things (for example, someone has lied to you, or you have a database with errors in it), this is potentially disastrous. In practical reasoning, you don't want to derive a contradiction and then happily believe everything — you want to find a contradiction, and deduce that you have made an error.

The study of what happens to logic when you drop ex falso is called relevance logic, so named because the idea is that you should only make inferences from hypotheses that are relevant to the conclusion. Again, see the SEP article on relevance logic for more. Also, you might wish to tolerate contradictions in your logic system. In this case, the thing to look at is paraconsistent logic.
Next, you mentioned a worry that individual inferential steps might not be completely reliable. In traditional logic we accept the unrestricted use of modus ponens. That is, inside a proof, if we know $A \to B$ and $A$ hold, we can conclude $B$ holds, any number of times. If you start to consider the idea that individual inferential steps might not be completely reliable, then you might think that proofs depending on long chains of inferential steps are "less reliable" than short ones.

It's a bit tricky to formalize this, but it is one of the (several) motivations for ultrafinitism. See Mannucci and Cherubin's draft Model Theory of Ultrafinitism I: Fuzzy Initial Segments of Arithmetic, for an exploration of this idea (and some explanation of its connection to fuzzy logic).

Finally, note that that none of these approaches actually talk about Frankfurt's idea of bullshit as an assertion which is made with an indifference to its truth value. You probably want to look at J.L. Austin's theory of speech acts (e.g., his book How to Do Things With Words) to help organize your thinking on this, and if you try to formalize it, you will probably find Per Martin-Löf's judgemental methodology (see for example his Siena lectures) helpful.


What is the complexity of the equivalence problem for read-once decision trees? A read-once decision tree is defined as follows:

$True$ and $False$ are read-once decision trees.
If $A$ and $B$ are read-once decision trees and
$x$ is a variable not occurring in $A$ and $B$,
then $(x \land A) \lor (\bar x \land B)$ is also a read-once decision tree.

What is the complexity of the equivalence problem for read-once decision trees?

Input: Two read-once decision trees $A$ and $B$.
Output: Is $A \equiv B$?

Motivation:
This problem came up while I was looking at
the proof equivalence problem (permutation of rules) of
a fragment of Linear Logic.

I found a partial solution. The problem is in L.

The negation of $A \leftrightarrow B$ is equivalent to $(\bar A \land B) \lor (A \land \bar{B})$ which is equivalent to $False$ iff both $(\bar A \land B)$ and $(A \land \bar{B})$ are.

The read-once decision tree for $\bar{A}$ can be obtained from the read-once decision tree for $A$ by switching $True$ and $False$ in $A$.
This can be done in log space.

To check if $\bar A \land B$ is equivlent to $False$
(and similarly for ${A} \land \bar{B}$)
we run through all the pairs of $True$ leaves, one from each tree,
and check if they are compatible (that is there is no $x$ on one of the paths and $\bar x$ on the other). It is equivalent to $False$ iff we find no compatible pair.
This can be done in log space.

So the problem is at least in L.

EDIT: I have some ideas to prove this to be L-complete, under $AC_0$ reduction probably. But I'd need to check the details and it won't fit in here. I'll post a link to the article I am writing if it all works out!

EDIT2: there it is, http://iml.univ-mrs.fr/~bagnol/drafts/mall_bdd.pdf

So the problem is indeed Logspace-complete.


Best parameterized algorithm for maximum clique I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "parameterized algorithm maximum clique" all failed.

What is the best known algorithm for maximum clique problem parameterized by the maximum degree. Or at least, how would you look for something like that?

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the neighborhood of the vertex.

Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most $d$ is the same as time complexity of maximum clique in graphs with $d$ vertices. I think currently the best known (and peer reviewed) algorithm works in $O(1.1996^n)$ time [1]. Confusingly, there also seems to be an older claimed result with $O(1.1892^n)$ time [2].

[1] M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set.
Information and Computation, 255:126–146, 2017.

[2] J.M Robson. Finding a maximum independent set in time $O(2^{n/4})$. LaBRI, Université de Bordeaux I, Technical report, 2001.


Graph planarity testing via adjacency matrix I have looked at several efficient graph planarity algorithms which
rely on computing and traversing DFS trees
(that add one vertex/edge/path at a time).

I am looking for graph planarity algorithms based on
the adjacency matrix and operations on it, e.g.
taking the square of the matrix,
computing the eigenvalues of the matrix, etc.

Ignoring trivial responses like, recreate the graph from the matrix and apply any standard planarity algorithm, the closest I know of to a matrix-based planarity test is Whitney's planarity criterion. But it uses the incidence matrix, not the adjacency matrix, and is a mathematical criterion rather than a polynomial time algorithm.

It states that a graph is planar if and only if its matroid (the independence matroid of the columns of the signed incidence matrix) has a dual (the matroid for the dual space of the column space) which is also a graphic matroid.


Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs For a project I'm working on, it would seem useful to have a normal form for
deterministic (sub)sequential transducers in which the set of states, $Q$, is
partitioned into states, $r \in Q_R$, that read a letter from the input tape (but do
not write any output) and states, $w \in Q_W$, that write a letter to the output
tape (but do not read any input).  The goal is to have (inputs and) outputs occur one letter at a time.

In some proofs that I've seen, a similar kind of normal form is used for
deterministic pushdown automata.  What I'm looking for is papers that use this kind
of normal form in the context of (sub)sequential transducers.  Does anyone know of
any references?

Specifically, in the normal form that I'm thinking about, there would be two transition functions, one for each part of the partition $Q = Q_R \cup Q_W$:
$$\begin{eqnarray}
\delta_R &:& Q_R \times \Sigma \to Q \\
\delta_W &:& Q_W \to \Gamma \times Q \\
\end{eqnarray}$$
To enforce finite output, each cycle in the state-transition graph must contain at least one state from $Q_R$.  (For subsequential transducers, I think that one needs another class of "terminal write states" that can be entered from a "read state" only when the input has been completely read.)

I'm not sure what your question is. Tell me if I am mistaken.
From what I understand:
Given a subsequential transducer, you can easily transform it into your canonical form by replacing every transition $(q,a)\to (p,v)$ into a transition reading $a$ and producing nothing followed by a sequence of transitions reading nothing and producing $v$ one letter at a time.

On the other hand, given such a transducer with $\epsilon$ transitions where all loop read some letter, you can compress the finite $\epsilon$-paths to get to a classical sequential transducer.


Shortest cycle with a specific number of vertices Given an undirected graph with n nodes, I need to find the shortest cycle of involving exactly n/2 vertices (i.e. keeping the distance traveled by the cycle to a minimum). Some nodes cannot directly connect; they're in specific areas and I can only travel from one area to another, not within one area.

I'm just asking in general here, what kind of techniques can I use to get the best (shortest) possible cycle of n/2 nodes?  So far I've written a basic substitution optimizer and just a greedy Depth First Search.  I'm wondering what would be the best approach for me to start on now?

The problem of finding the shortest tour that covers a given number k of nodes is usually referred to as k-TSP. Searching Google scholar for that term will find some relevant literature. It is NP-hard but can be approximated within a constant factor. So finding an exact solution may be out of reach, unless you're prepared to use sophisticated branch and bound methods extending what Concorde does for the usual TSP.


Diving straight into "research" versus studying broadly as an undergrad (soft question) I'm nearing the end of my first year as an undergraduate and am very confident that I want to pursue a PhD in TCS. Fortunately because I quickly realized what I'm interested in and have a solid background in math, I've been able to take multiple TCS classes early on so as to get exposure in the field. I've also been doing lot of study on my own as time allows (though of course it is difficult when taking classes).

It also so happens that I live very close to my university, and at my request one of my professors was nice enough to say that I could come in and work in the theory space every day during the summer. It is still really up in the air as to what I will actually focus on, but I'm just excited to have a space to study TCS all summer.

Since as I said I'm only a first-year, one thing my professor emphasized is I have a choice many undergrads don't have: I could spend the summer doing "research" or studying far more broadly. I put research in quotation marks because I don't think I have enough experience to actually collaborate with a graduate student, but I could devise my own project. I.e., try to find some very recent results in a topic that doesn't require too much advanced math and just go at it.

On the other hand, I found a lot online advising undergrads to (if possible) study broadly instead of narrowly since obviously you aren't going to be working on the same problem in 10 years. To me, studying broadly would look like spending the summer going through as many textbooks as possible and doing lots and lots of exercises. (I would still find this a lot of fun!) And also reading papers in different areas. That said, there is the ever-looming pressure of graduate admissions and the need for some kind of publication.

So my question is basically what would you recommend to do in my situation? (But more widely, should an early undergrad go for depth or breadth?) Some other thoughts I've had:

I could obviously come up with some kind of compromise. Instead of doing a "research" project I could read and present lots of papers. Since going through a paper is a mini project in itself for me at this point, this would give me some depth but obviously not at the level of a project.
Some comments I've read online suggest that one reason to emphasize breadth if possible is it will lead to a far smoother initial research experience down the road. However, one thing I've been told is that you will never be fully "ready" to dive into research. Meaning that everything is so specialized at this point that even grad students only understand 90% of their specialization, 70% of their subfield, and 30% of everything else. Someone told me that because this will always be the case, it is better that I dive in right away. (But of course it is hard to know what to dive into!)

[This is really a comment, but too long to fit in a comment field.]

You seem to be exceptionally well prepared compared to most students at the end of your freshman year.  And I'm not sure what you mean by "research" or "publication".  But, by the common meaning of the words in theoretical CS, I would say that the goal of a PhD is to learn to do independent research leading to publication, and that, as a rule, achieving that goal requires a lot of hard work, time, and usually help from an advisor, spread over more than four years of graduate study.  This is why a typical REU (research experience for undergrads) does not have this goal, but instead will allow you to work as a team member in a larger group, or perhaps with an advisor on a smaller project, with the more limited goal of gaining some initial exposure to the process.  (Even MS students rarely do original, published research.)  Can you find any summer REU opportunities to apply for?  They could be at another school.

I'm not sure what to say about "depth" vs "breadth".  I would guess that, at your stage, your fastest way to develop is to complete your undergraduate TCS courses, and take some graduate-level TCS courses if you can.  You may be able to work through some of the undergraduate material on your own in the summer (maybe that's your "studying broadly").  Meanwhile, if there is some degree of TCS community in your school, or nearby, you could try to connect with it.  Find students (including grad students) and a few faculty to cultivate relationships with, and find out what kind of research projects are going on nearby.  A big part of learning to do research is becoming part of the TCS community, learning its norms, and what is currently of interest.  Over the years I've known a small number of students who had an idea they wanted to pursue, and tried to start research on their own, and while I'm sure some have enjoyed the experience, the usual outcome (by an academic / professional standard) is to fall short, for all kinds of reasons.


What are the limitations of dependent typing? It seems dependent types can provide lots of desirable guarantees about program behavior. What kinds of program properties can they NOT guarantee (besides what's computationally infeasible)? Is there an even more powerful or general type system that can model any computable property of a program?

One obvious missing feature from most dependent type theories is the ability for substructural reasoning.

The guarantees given by systems like Agda and Coq tend to be very extensional, that is they enforce properties about the values of the computations, rather than their operation. Some obvious things we might want to track about the operation of an algorithm:

Runtime
Space usage
Which resources they "own", e.g. which files they are allowed to access without risk of a race condition

All these things (and more!) become possible with various flavors of substructural types. This seems to be an important active research subject in the PL community.

A possible reference is Wadler, Linear Types can Change the World!

Note that using "deep embeddings", it is possible to enforce some of these properties in a standard dependent types system, see e.g. Brady & Hammond Resource-safe Systems Programming with
Embedded Domain Specific Languages.


Methods for proving deterministic communication complexity lower bounds I am familiar with the classic techniques for proving deterministic communication complexity lower bounds for boolean functions in the 2-party model: To the best of my knowledge, these are

fooling sets,
the rank method, and
the "tiling method", which refers to determining the minimal number of monochromatic rectangles needed to cover all possible outputs.

It is known that (3) gives almost tight bounds but is difficult to apply. On the other hand, fooling sets are easier to find in general, but the obtained bounds can be exponentially smaller than the actual deterministic communication complexity, whereas the rank method yields lower bounds that can be polynomially smaller.

These are the only techniques that I am aware of and they were invented in the early 90s.

Are there any newer techniques for finding deterministic lower bounds?

Related question:
Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

One approach that's quite different from the ones you mention is proving communication complexity lower bounds by reductions to query complexity problems. This approach can give lower bounds which are nearly quadratically stronger than the partition-based bounds, i.e. is able to actually exploit the structure of a deterministic communication protocol.

The basic idea is to compose a boolean function $f:\{0,1\}^k \to \{0,1\}$ with $k$ copies of a two party "gadget" function $g:\{0,1\}^{b} \times \{0,1\}^b \to \{0,1\}$, where $b = n/k$. It turns out that, by a simulation theorem of Raz and McKenzie, for a well-chosen $g$ and every $f$, the deterministic communication complexity of the composed function $F =f \circ g^k$ is equivalent up to lower-order factors to the deterministic decision tree complexity of $f$. The upshot is that to prove communication lower bounds it suffices to prove query lower bounds, which can be much easier.

See this paper by Göös, Pitassi, and Watson for references, and an application of this approach to giving nearly optimal separation between the partition number and deterministic communication complexity.


Which models of computation can be expressed through grammars? This is a reformulation of Are grammars programs? previous asked by Vag and with many suggestions from the commenters.

In what way can a grammar be seen as specifying a model of computation?
If, for example, we take a simple context-free grammar such as

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Assuming that the parser does not differentiate between terminal and nonterminal symbols as I've demonstrated here, then it is possible to perform simple arithmetic for numbers up to 3.

For example, take the string

"2 + 0 + 1"

Running a LR(1) parser on this string should give us the following concrete syntax tree where the result of the computation is stored at the root of the tree:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0'

Thus, if we take a grammar to be a program and a parser generator to be a compiler, could we see the grammar specification language as a programming language?

Furthermore, could we build Turing-complete programs by specifying grammars similar to how you could build turing complete programs with celullar automata or the lambda calculus?

In other words, it is known that in the sense of recognizing a language, regular languages correspond to finite state automata, context-free languages correspond to push down automata, and context-sensitive languages correspond to linear bounded automata. However, if we look at grammars as computational devices (i.e. programs in the sense of the example above), then how do we classify the computational strength of each class of grammars in the Chomsky hierarchy?

Regular grammars
Context-free grammars
Context-sensitive grammars
Unrestricted grammars (for recursively enumerable languages)

Also, how about the lesser known subclasses of grammars such as

Deterministic context-free grammars (also LR(k)/LL(k)/SLR/LALR etc)
Nested word grammars
Tree adjoining grammars
Indexed grammars

EDIT: By the way, this is a nitpick on my own question but I didn't mention that I gave no starting symbol for the example grammar and hand-waved at the need to distinguish between terminals and nonterminals. Technically or traditionally I think the grammar would probably have to be written in a more complicated form like this one (where S is the starting symbol and the \$ represents the end-of-stream terminal):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

...not that it really changes anything, but I thought I should mention it.

EDIT: Something else that came to mind when I read gasche's answer is that each branch in the tree in my example represents a sub-computation. If you look at each production rule as a function where the LHS represents the result and the RHS represents its arguments, then the structure of the grammar determines how functions are composed.

In other words the context of the parser together with its lookahead mechanism helps to determine not only which functions to apply ('kinda' like parametric polymorphism) but how they should be composed together to form new functions.

At least, I guess you could look at it this way for unambiguous CFG's, for other grammars the mental gymnastics is a little bit too much for me right now.

There is a one-to-one correspondence between Chomsky Type-0 grammars and Turing machines.

This is exploied in the Thue programing language which allows you to write Turing-complete programs specified by an initial string and a set of string-rewriting rules (a semi-Thue grammar, which is equivalent to a type-0 grammar).

UPDATE:

Other than esoteric "Turing tar-pit" languages like Thue, various general purpose languages that allow the programmer to extend their own syntax can be used to perform Turing-complete computation during the parsing-compilation stage.

Languages in the Lisp family, in particular Common Lisp, are probably the most obvious examples, but also, broadly speaking, languages with static type checking that doesn't always need to halt, such as C++ with templates, Scala and Qi.


What is the name of this type of directed graph problem? Take a directed graph $G$ where the edges are decorated with a a natural  number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is decorated with a natural number that is greater than the natural number decorating the previous edge.

An application for this would be bus or train schedules. If you're trying to determine the different routes between two cities based on transfers between stations. (You can't take a second train scheduled to leave for before the first one arrives.)

I've informally been calling this a "scheduled graph". But I don't know what the name for this in the literature is.

Any references to algorithms related to this are of interest as well.

As far as I know, the problem is sometimes called "nondecreasing paths", and was studied since the 50s.
See for instance this paper: G. J. Minty. A Variant on the Shortest-Route Problem, Operations Research, 6(6):882–883, 1958.

The version of the problem which asks for the nondecreasing path from $s$ to $t$ with minimum last edge weight is typically referred to as "earliest arrivals" (since the last edge weight is the arrival time in the itinerary application). There's a lot of work in the literature focusing on this version.


Can factorial be encoded in the Kappa-calculus with fixed point operator? Suppose we have a $\kappa$-calculus with operator $fix$, that could be used to transform function with type $(1 \rightarrow a) \rightarrow a$ to a value of type $1 \rightarrow a$. We use a normal reduction strategy.
We'd like to represent factorial function in such a system. The problem is that whatever function we're trying to find a fixed point of, when we apply the function to its fixpoint, there's no way to determine whether we need to use the value of argument $x$ or not. There's no "counter" to base our solution on.
$fix (\kappa{}x. \cdots) = (\kappa{}x. \cdots) (fix (\kappa{}x. \cdots))$
In $\lambda$-calculus we could run $fix (\lambda f. \lambda x.\cdots)$ and terminate depending on the value of $x$.

How to prove that $\kappa$-calculus with fixed point operator cannot really represent a factorial function?
How could we extend $\kappa$-calculus to make it Turing-complete, leaving space for its translation into generalized arrows?

The bare $\kappa$-calculus does not permit defining factorial, even when extended with a fixed point operator. However, this answer deserves some unpacking.

The fixed point operator you give is not well-formed according to the grammar of types in the $\kappa$-calculus. Note that the grammar of types does not contain the function space $\tau \Rightarrow \tau'$ -- this is because the $\kappa$-calculus is a language of first-order functions. An expression has a type $\tau_1 \to \tau_2$, to indicate that it is an expression of type $\tau_2$, whose free variables are typed by $\tau_1$.

The proper typing for a fixed point operator would be roughly something like:
$$
\frac{\Gamma, x:1 \to \tau \vdash e : 1 \to \tau}
     {\Gamma \vdash \mu x:1 \to \tau. e : 1 \to \tau}
$$
Once you've fixed this, you still can't define a factorial.

The plain $\kappa$-calculus does not have sums or natural numbers as a base type. As a result, you can't write branching programs, and so you cannot define interesting recursive functions. If you added natural numbers and their iterator, you could define a factorial function. Hasegawa actually gives factorial as an example in his paper on the $\kappa$-calculus, in a calculus augmented with a basic natural number type.

However, you might wonder why you are able to define factorial in the pure lambda calculus, even though it has no apparent control structures. The reason is that the interaction of fixed points and recursion gives you a "universal type" (i.e., a type $V$ such that $V$ is isomorphic to $V \to V$), and this lets you encode any datatype as a subset (more accurately, a retract) of it.

In more syntactic terms, you can write the Y combinator (i.e., Curry's paradox) in any language with (a) higher-order functions, (b) recursion, and (c) the ability to use each variable more than once in a program. Since the basic $\kappa$-calculus lacks (a), adding even an unrestricted fixed point operator does not make it Turing-complete!


Complexity of 3SAT where each pair of 3-clauses share at most one variable Consider the variant of the 3SAT problem with the following restrictions:

Each clause has 2 or 3 literals.
Each pair of 3-literal clauses have at most one common variable.

What is the complexity of this SAT problem?

The central insight is that you can use two $2$-variable clauses to make sure two variables have the same value. Let me abbreviate $(x \vee \neg y) \wedge (y \vee \neg x)$ with $x=y$.
This allows the following reduction from 3SAT.

Given a 3SAT formula, copy the clauses to your reduction one by one. If you encounter a clause with a variable $x$ you've already seen twice, write the clause with a new variable $y$ instead of $x$ and add two $2$-variable clauses for $x=y$. Call the resulting formula $\phi$.

Formula $\phi$ satisfies requirements 1) and 2). Next, employ the same technique
to ensure requirement 3). Walk through each pair of $3$-variable clauses of $\phi$ and for each pair which shares two variables $x$ and $y$, keep $x$ in one clause and in the other clause, change $x$ to $z$, and add $x=z$. An example:

$(x\vee y\vee h) \wedge (\neg x \vee \neg y \vee h) \mapsto (x\vee y\vee h) \wedge (\neg x \vee \neg z \vee h) \wedge (y=z)$

The resulting formula has as many $3$-variable clauses as the original and two $2$-variable clauses for each third or later repetition of a variable and then some more to satisfy requirement 3). Because the $2$-variable clauses ensure that $x=y$ so that your substitutions work, the resulting formula is satisfiable exactly when the original 3SAT formula was satisfiable. Its length is at most quadratic in the number of clauses of the original formula, so your problem is NP-Complete.

EDIT: I notice I interpreted your question to mean, a variable cannot appear in more than two $3$-variable clauses. The way it is formulated now, requirements 2) and 3) are equivalent. I hope you're not mad.


Have imperative programs been defined like this? Possibly improper definition $\;$ An imperative program is a labeled directed graph, with every vertices labeled by a command and every edge labeled by a predicate.

Denote an edge labeled by predicate $p$ from $x$ to $y$ by $(x, p, y)$,

Two consecutive steps are expressed as $(x, \top, y)$. "Goto" is also expressed in this way.
A binary branch is expressed as $\{(x, p, y), (x, \neg p, z)\}$.

As can be easily noticed, "command" is not defined. I do not know what that should be, but it should be as weak as possible.

Have imperative programs been defined like that?

I also think a mathematical definition could help me go further understanding the space of imperative programs.

Short answer: yes.

Longer answer -- there probably isn't a unique reference but control flow graphs (essentially what you describe) and their precursors, flowcharts are Old. Here are three random references from antiquity to something very recent that use minor modifications of the model. The latter two define the model fairly precisely. You'll find a lot of lattices in the second paper.

Assigning Meaning to Programs, Robert Floyd, 1967.
Systematic Design of Program Transformation Frameworks by Abstract Interpretation, Patrick Cousot and Radhia Cousot, POPL 2002.
Assertion Checking Unified, Sumit Gulwani and Ashish Tiwari, VMCAI 2007.


Why is the state of a FSM traditionally denoted $q$? While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is typically denoted $q$ (and the state space $Q$). I first asked on EE.sx, but then while researching a bit this topic, I found that even Turing's original 1936 paper uses $q_1..q_n$ to denote the states of the Turing machine.

So I wonder: When does this convention go back to, and why would a "state" be denoted $q$ ?

In his 1936 paper "ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM", Alan Turing wrote :

  "We may compare a man in the process of computing a real number to
  machine which is only capable of a finite number of conditions q1, q2,
  .... qR which will be called " m-configurations"

So he stressed the fact that the machine has a finite, discrete (not continuous) number of states or quantities. For me, it is a reference to the term Quanta used in physics to denote phenomena variating not continuously but by "leaps" or "quanta". In his 1950 article "Computing Machinery and Intelligence" Alan Turing is more explicit about "leaps" speaking of "sudden jumps":

  "The digital computers considered in the last section may be
  classified amongst the "discrete-state machines." These are the
  machines which move by sudden jumps or clicks from one quite definite
  state to another."

So I think that Alan Turing used q instead of s to denote a machine state to stress the fact that the state machine can be only in a set of discrete and finite values like the quanta in physics. And since then, the same notation is generally used.


The entropy of a noisy distribution Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that
$$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$
and $f$ is a distribution, i.e., $\sum_{x\in \mathbb{Z}_2^n} f(x) = 1$.

The Shannon entropy of $f$ is defined as follows:
$$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) .$$

Let $\epsilon$ be some constant.
Say we get an $\epsilon$-noisy version of $f(x)$, i.e., we get a function  $\tilde{f}:\mathbb{Z}_2^n \to \mathbb{R}$ such that $|\tilde{f}(x)- f(x) | < \epsilon$ for every $x\in \mathbb{Z}_2^n$. What is the effect of the noise on the entropy? That is, can we bound $H(\tilde{f})$ by a "reasonable" function of $\epsilon$ and $H(f)$, such as:
$$(1-\epsilon)H(f) < H(\tilde{f}) < (1+\epsilon)H(f),$$
or even,
$$(1-\epsilon^c n)^d H(f) < H(\tilde{f}) < (1+\epsilon^c n)^d H(f),$$
for some constants $c,d$.

Edit: Trying to get a feeling for the effect of noise on Shannon's entropy, any
 "reasonable" additive bound on $H(\tilde{f})$ would also be very interesting.

Such a bound is not possible. Consider the case where $f$ is the distribution that is uniform over some set $S$ of size $2^{\delta \cdot n}$, and let $\tilde{f}$ be the distribution that with probability $\delta$ outputs a uniformly distributed element of $S$, and otherwise outputs a uniformly distributed string.

It is not hard to see that you can get from $f$ to $\tilde{f}$ you only need noise of at most $(1-\delta) \cdot 2^{-\delta \cdot n}$.  However, $H(f)= \delta \cdot n$ while $H(\tilde{f}) \approx (1 - \delta + \delta^2) \cdot n$. Thus, you get a difference of $(1 - \delta)^2 \cdot n$ for arbitrarily small $\delta$ for an extremely low noise.

In particular, you can set $\delta = \frac{\log(1/\varepsilon)}{n}$, and obtain noise $\varepsilon$ and entropy difference $\approx n - 2\log(1/\varepsilon)$.


On the class of the FNP version of the Hamiltonian Cycle problem This post is linked to: FNP complexity class

Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in polynomial time.

Suppose I ask someone "Does a Hamiltonian Cycle exist?" and she answers "YES", then how can I (in polynomial time) verify that she is not lying? (I am assuming here that the solution I got "YES" is the only thing I have with me)

Alternate interpretation: Is "Any given solution to L can be verified quickly (in polynomial time)" to be interpreted as "Given some solution to the Hamiltonian Cycle problem for this graph, it can be verified quickly"?

If it is the latter, then things fall into place.

Quoting from http://en.wikipedia.org/wiki/FNP_(complexity):
"This means that the FNP version of every NP-complete problem is NP-hard."

Is this necessarily true?

And comparing with the Hamiltonian Cycle problem, if she (the solver) says "YES and here it is ..." then I can take that and verify if it is actually a Hamiltonian Cycle. Hence, shouldn't this (FNP) version actually be NP-Complete not be NP-hard? What am I missing here?

The FNP version of an NP-complete language $L$ asks to solve the following problem on every input $x$:

1) If $x \not\in L$, output "NO".

2) If $x \in L$, output some witness "w" such that a polynomial-time entity, given $(x,w)$, can verify that $x \in L$.

Consider the transformation $T$ of the above scheme: If the FNP machine answered "NO", $T$ answers "NO". Otherwise, $T$ answers "YES".

Obviously $T$ is a Karp-reduction of any NP-complete problem to the corresponding FNP-complete instance.


Detecting circuit that's similar in functionality and implementation Let $x=(x_1,\dots,x_n)$ be a vector of boolean variables.  Let $C,D$ be two boolean circuits on $x$.  Say that $C$ is similar to $D$ if:

$\Pr[C(x) \ne D(x)]$ is exponentially small, when $x$ is drawn uniformly at random from $\{0,1\}^n$ (in other words, they have almost-identical functionality); and,
$C,D$ differ in graph edit distance by a tiny amount (their edit distance is much smaller than the size of the circuit, say, $O(1)$ or some small constant), meaning that almost all of the gates and wires of $C$ match a corresponding gate and wire in $D$, with only a few gates added/deleted/changed.

My problem: I am given a circuit $C$, and I want to know whether there exists a circuit $D$ that is similar to $C$ but not identical to $C$ (i.e., where there exists $x$ such that $C(x)\ne D(x)$).

Can anyone suggest an algorithm to solve this problem?

If it helps, we can restrict attention to circuits $D$ that are smaller than the given circuit $C$ (i.e., we want to know whether there exists a circuit $D$ such that $D$ is smaller than $C$, $D$ is similar to $C$, and there exists $x$ such that $C(x)\ne D(x)$).

If it helps, you can additionally assume we are given known-good test cases $x^1,\dots,x^m,y^1,\dots,y^m$ such that $C(x^i)=y^i$ for all $i$, and we can further restrict attention to only circuits $D$ such that $D(x^i)=y^i$ for all $i$.

This arises from a practical application, so if you can't solve this problem, feel free to solve any variant or interesting special case.  For instance, feel free to instantiate any of the parameters or thresholds in any way that's convenient for you.  You can assume the circuits are not too large (polynomial sized, or something).  Feel free to replace graph edit distance by some other measure of near-match of implementation.  Also, in practice SAT solvers are often surprisingly effective on the structured circuits that arise in practice, so it's probably fine to invoke a SAT solver as a subroutine/oracle (at least, if you're invoking it on something like a SAT instance derived from a circuit like $C$).

Alternatively, lacking any algorithms, I would also be interested in the existence question: for an "average" circuit $C$, what's the probability that there exists some $D$ that meets all the criteria?  (I'm hoping this probability is very low, but I have no clue if that is the case.)

The practical application is to test whether a circuit $C$ might contain a malicious backdoor / hidden Easter egg.  The hypothesis of how such a thing might get inserted goes like this.  We start with a "golden" circuit $D$, that computes the desired functionality and has no hidden backdoor.  Then, the adversary makes a small change to $D$ to introduce the hidden backdoor, obtaining a modified circuit $C$.  The purpose of the backdoor is to change the function computed by $D$ in some way.  If $\Pr[C(x) \ne D(x)]$ is not too small, the change can plausibly be detected by random testing, so an adversary will probably try to keep $\Pr[C(x) \ne D(x)]$ very small.  Similarly, if $C$ differs from $D$ in too many places, this might be noticed by random inspection of the circuit, so an adversary will probably try to minimize the number of changes.  (And, there may be a test suite of $x^i,y^i$ pairs that represent instances of the desired functionality, so we know that whatever the "golden" circuit $D$ is, it satisfies $D(x^i)=y^i$ for all $i$.)  Ultimately, we are given the circuit $C$ (but not the "golden" circuit $D$), and we want to know whether $C$ might be a modified version of some $D$, where the modification was made to introduce a hidden backdoor of this sort.

This is only an extended comment that came to my mind immediately after reading the question:

suppose you have a 3SAT formula $\phi$ with $n$ variables $x_1,...,x_n$ and let $C$ be the corresponding circuit;
build a new circuit $C'$, adding $m = n^k$ variables $y_1, y_2, ...,y_{n^k}$, and enough gates to AND the $m$ new variables with the output of the original $C$ ($C' = \phi \land y_1 \land ... \land y_m$);
build a new circuit $D'$ from $C'$ that simply forces its output to 0 using an AND and NOT gate ($D' = C' \land \neg C'$)

If $\phi$ is not satisfiable then $D'$ and $C'$ are equivalent, otherwise they differ when the $x_i$ satisfy the formula AND all $y_i = 1$, but you can choose $m$ large enough to make the probability that $\bigwedge y_i =  1$ very small.

So if you have an efficient algorithm for your problem, you can afficiently solve the 3SAT instance.


What is the best-known inapproximability result for MIN-3CNF-DELETION? I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF
SAT formula with at most 3 literals per clause. The objective function is the number of unsatisfied clauses. The strongest hardness result I have been able to find is that of MIN-HORN-DELETION, which is a restricted variant of MIN-3CNF-DELETION. As far as I know the best-known inapproximability result for MIN-HORN-DELETION is that which is given in The Approximability of Constraint Satisfaction Problems by Khanna et al (2000).

However, I have not yet been able to find explicit references to MIN-3CNF-DELETION. Is it even harder than MIN-HORN-DELETION? In which case, what is the best known inapproximability threshhold? Any feedback would be most welcome. Thanks!

There is no approximation algorithm for MIN-3CNF-DELETION at all since it is not even possible to determine in polynomial time whether a 3 CNF SAT instance is satisfiable or not (if P≠NP). That is, it is not possible to determine if the objective function is equal to 0 or strictly positive. Specifically, if we had an $f(n)$ approximation algorithm for the problem, given a satisfiable instance the algorithm would find a solution of cost $0 \cdot f(n) = 0$ ; that is, a solution that satisfies the instance.

In contrast, if an instance of Min-Horn-Deletion or Min-2CNF-Deletion is (completely) satisfiable, we can efficiently find a solution that satisfies all clauses. Thus it makes sense to talk about approximation algorithms for Min-Horn-Deletion and Min-2CNF-Deletion.


Do "outer-bounded-genus" graphs have constant treewidth? Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of outerplanar graphs. Can the treewidth of graphs in $G_k$ be upper bounded by some function of $k$?

The other direction obviously does not hold, since constant treewidth does not even imply constant genus: Let $H_n$ be the union of $n$ disjoint copies of $K_{3,3}$. The treewidth of $H_n$ is constant, its genus however is $n$.

Yes.

Add a vertex in the middle of the outer face, connected to all the vertices in the outer face; this does not change the genus, and does not decrease the treewidth. Now the graph has a very shallow breadth-first search tree rooted at the new vertex (everything is adjacent to it).

Form a spanning tree of the dual graph whose dual edges are disjoint from the edges of the breadth first search tree. Then there is a set of O(genus) edges that do not belong to either tree. Each of these edges induces a short cycle (a triangle) together with a path in the breadth first search tree, and cutting the surface along these cycles produces a planar surface (see my paper "Dynamic generators of topologically embedded graphs"). That is, if G' is the subgraph of the input graph induced by the vertices that are not endpoints of the O(genus) cut edges, then G' is planar, and its vertices can be covered by O(genus) faces of its planar embedding (the faces that the cut cycles cut the original outer face into).

But in a planar graph in which all vertices belong to k faces, one can remove another O(k) edges (a spanning tree of the faces) to get an outerplanar graph. So the treewidth of G' is O(genus). If one forms a tree-decomposition of G' with this width, and then adds to each bag the vertices that are endpoints of the cut cycle edges, the result is a tree-decomposition of the original input graph with treewidth O(genus).

It seems likely that this must be in the literature already somewhere, but I don't know where and some quick searches haven't succeeded in finding an explicit statement of this precise result. However, a more general statement is in a different paper of mine: in "Diameter and treewidth in minor-closed graph families" I prove among other things that bounded genus graphs of bounded diameter have bounded treewidth. In this case (by adding that extra vertex within the outer face) the diameter can be taken to be at most two.


Complexity of a parametrized min-cost flow problem Consider the following  min-cost flow variant:

Input:

a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$
edges from $s$ to $S$ and from $T$ to $t$.
lower and upper capacity bounds $l_i, u_i$ on each edge $(s, s_i)$
flow values $g_i$ for each edge $(t_i, t)$ with the constraint that $\sum_i g_i = 1$

For any flow assignment $f$ on the edges $(s, s_i)$ (note that by flow conservation $\sum_i f_i = 1$), let $\text{cost}(f)$ be the cost of a min-cost flow satisfying the upper and lower bounds.

Problem:

  Find an $f$ satisfying all capacity constraints such that
  $\text{cost}(f)$ is maximized.

this is too long for a comment, but it's not an answer

One reformulation of your problem might prove to be useful in terms of finding related work.

Note that $f$ and $g$ essentially define probability distributions over the $s_i$ and $t_i$. If we treat the $c(e)$ as a "length", then the mincost flow is basically the earthmover distance between the two distributions $f$ and $g$.

Now your maximization over $f$ is really saying: find the farthest neighbor to $g$ lying in a box defined over the simplex.

Formulating the problem this way suggests that you want some kind of projection from $g$ to the box.


Characterizing the exponential savings in active learning Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target (separable case).

Active learning potential lies in its exponential saving in terms of the number of queries required compared to the supervised learning. This big saving in known for some structures ( for example learning threshold functions requires $O(\frac{1}{\epsilon})$ examples while we can achieve the same goal with $log \frac{1}{\epsilon}$ in active learning ).

What characterizes this exponential reduction in general? Are there certain properties such that if $H$ satisfies them then active learning would help?

See Hanneke's disagreement coefficient,
http://projecteuclid.org/euclid.aos/1291388378


How to prove that Supremum preorder coincides with Hoare preorder? Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$.

I mean:

Hoare preorder $(2^{B_L}, \sqsubseteq_H)$, where for $X, Y \in 2^{B_L}$,

$X \sqsubseteq_H Y \iff \forall x \in X$, $\exists y \in Y$ such that $x \sqsubseteq y$
Supremum preorder $(2^{B_L}, \sqsubseteq_{\sqcup})$, where for $X, Y \in 2^{B_L}$,

$X \sqsubseteq_{\sqcup} Y \iff \sqcup X \sqsubseteq \sqcup Y$

Where $l \in L$ is completely $\sqcup$-irreducibles $\iff \forall X' \subseteq L$ such that $l = \sqcup X' \implies l \in X'$ (note that $\bot$ isn't completely $\sqcup$-irreducible since $\bot = \sqcup \emptyset$ but $\bot \not\in \emptyset$).

I'm pretty sure that "Hoare" is the right name for the intended preorder, a little less about "Supremum" (maybe "Smyth" could be better).

My question is, given a distributive lattice $L$, how to prove that Hoare preorder and Supremum preorder coincide?
It is easy to see that in general (without distributivity) $X \sqsubseteq_H Y \implies X \sqsubseteq_{\sqcup} Y$. But I'm stuck in the converse implication $X \sqsubseteq_{\sqcup} Y \implies X \sqsubseteq_H Y$, that probably uses distributivity of $L$.

Where $L$ is distributive $\iff \forall a, b, c \in L$ it holds that $a \sqcap (b \sqcup c) = (a \sqcap b) \sqcup (a \sqcap c)$. By the way, I'm still not sure if I need to require $L$ to be only distributive or completely distributive.

Thanks in advance for any hint.

I’m going to use normal notation, as the square symbols are a pain to typeset.

Proposition: Let $L$ be a complete lattice, and $B$ its set of completely join-irreducible elements. If every element of $L$ is a join of a subset of $B$, then the following are equivalent:

$\bigvee X\le\bigvee Y\implies \forall x\in X\,\exists y\in Y\,x\le y$ for all $X,Y\subseteq B$.

All $x\in B$ are completely join-prime, i.e., $x\le\bigvee Y\implies\exists y\in Y\,x\le y$ for all $Y\subseteq L$.

$L$ satisfies the infinitary distributive law $x\land\bigvee_{i\in I}y_i=\bigvee_{i\in I}(x\land y_i)$.

Note that condition 3 is not equivalent to its dual, and it is weaker than full complete distributivity.
Proof:
1 → 2: By the assumption on $L$, $\bigvee Y=\bigvee\{u\in B:\exists y\in Y\,u\le y\}$. Thus, if $x\le\bigvee Y$, then $\bigvee\{x\}\le\bigvee\{u\in B:\exists y\in Y\,u\le y\}$, hence by 1, there exists $u\in B$ and $y\in Y$ such that $x\le u\le y$.
2 → 1: For any $x\in X$, $x\le\bigvee X\le\bigvee Y$, hence $x\le y$ for some $y\in Y$ as $x$ is completely join-prime.
3 → 2: If $x$ is completely join-irreducible and $x\le\bigvee Y$, then $x=\bigvee\{x\land y:y\in Y\}$ by 3, hence $x=x\land y$ (i.e., $x\le y$) for some $y\in Y$ by complete irreducibility.
2 → 3: $x\land\bigvee_{i\in I}y_i\ge\bigvee_{i\in I}(x\land y_i)$ always holds. For the other inequality, since the left-hand side is a join of a subset of $B$ by assumption, it suffices to show that
$$u\le x\land\bigvee_{i\in I}y_i\implies u\le\bigvee_{i\in I}(x\land y_i)$$
for all $u\in B$. The premise implies $u\le x$, and since $u$ is completely join-prime by 2, there exists $i\in I$ such that $u\le y_i$. Then $u\le x\land y_i\le\bigvee_{i\in I}(x\land y_i)$.


Continuous Clustering So I have an issue I'm facing in regards to clustering with live, continuously streaming data.  Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective clustering.  I've come up with a few possible solutions including:

Setting a limit on how many data points to allow, thus whenever the limit is reached as another data point comes in the oldest point is removed.  Essentially, this would suggest that older data isn't relevant enough to us anymore to care what we're losing by throwing it out.
Once there is enough data to make a good clustering, consider this "the setup" and as new points come, rather than re-clustering all the data just figure out which cluster center the new point is closest to and add it to that.  The benefit here is you could avoid having to re-cluster on every new point and you wouldn't have to store all the other points, just the cluster centers, considering this clustering "good enough".  The downside is that re-running the algorithm with all data points from the beginning may be more accurate.

While those are some potential solutions I brain-stormed, I'd like to know if there are any better known techniques to face this problem.  I figure sites like Google had to deal with it somehow (and I'm hoping that "add more ram, servers and processors" or "continually expand your data centers" aren't the only answers available).

There's a fair amount of work on stream clustering (which is slightly different to online methods, but is essentially what you want). The above reference by Guha et al is a very good one, and for a more general perspective on what kinds of techniques work, and what methods have been used in the past (both heuristic and precise), you might want to look at my survey on clustering on streams.


Will quantum computing pave the way for native, true RNGs? Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user input (or any other external variables)?

Actually, today's computers can generate truly random data on their own, and many in fact do. The random data is produced as a byproduct of the physics of the components, not as the product of a given algorithm, so it necessarily has to be implemented in hardware. But the hardware is readily available.

The popular TPM chip, for example, typically has an embedded TRNG, as do many security-oriented peripherals, such as some authentication tokens.

The actual mechanism used to harvest sources of entropy varies by component, but a simple-to-understand mechanism is the analysis of noise generated at the avalanche breakdown of a P-N junction of a diode or transistor. The noise from such a cascade is actually the amplification of the random movement of electrons at the junction - essentially amplifying the randomness of quantum mechanics to the level where it can be read by traditional electronics.

Obviously this isn't the only mechanism you can use to harvest randomness in today's computers, but it's an easy one to understand. In fact it's worth pointing out that the Intel's recent Ivy Bridge architecture introduced a new instruction: RDRAND, which yields the output of an on-chip TRNG. IEEE Spectrum has a detailed write-up of how it works.


Complexity of selective network improvement problem We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ through it. The min-cost flow to minimize $\sum_{(i,j) \in E}{c_{ij}f_{ij}}$ is well known to be solved in polynomial time. But now we are given opportunities to improve the cost on the arcs. Suppose we know in advance that after improvement on an arc, its cost will be reduced by $\Delta_{ij}$. My problem is given an integer $K$ ($K<|E|$), how to select the $K$ arcs to improve so that the resulting min-cost objective function is minimized?

Currently, I can formulate the problem as:

$\min{\sum_{(i,j) \in E}{(c_{ij}-x_{ij}\Delta_{ij})f_{ij}}}$

subject to

$\sum{f_{ij}} - \sum{f_{ji}}=b_i, \quad i \in V$
$l_{ij} \leq f_{ij} \leq u_{ij}, \quad (i,j) \in E$
$\sum{x_{ij}}=K, \quad (i,j) \in E$
$x_{ij} \in \{0,1\}, \quad (i,j) \in E$

Constraints 1. and 2. are just normal flow constraints while 3. and 4. are like packing constraints. With the introduce of 0/1 variable $x_{ij}$, this problem seems to be hard to solve. So I'm wondering what is the complexity of this problem? Thanks.

Reduction from Set Cover. Suppose the Set Cover instance has sets $S_1,\ldots,S_m$ which are subsets of a universe $U$ of $n$ elements, and an integer $k$. The problem is to decide if the elements of $U$ can be covered by using at most $k$ sets from $\{S_1,\ldots,S_m\}$. Create a directed graph with a node for each set $S_i$ and a node for each element in $U$ and a set is connected by an arc to an element iff that element is in that set (these arcs have a capacity of $1$ each). Add a source node $s$ and connect it to each set $S_i$ with an arc of capacity $|S_i|$. Add a sink node $t$ and arcs connecting each element to $t$ (the capacity if $1$ and cost is $0$). The arc $(s,S_i)$ has cost $1$ and if we improve it the cost becomes $0$. The other arcs have cost $0$ so there is no point improving them. The claim is that there is a feasible cover of size $k$ in the Set Cover instance iff one can select $k$ arcs to improve so that the resulting graph has an $s$-$t$ flow of $n$ with cost $0$. This is not hard to see. One can use lower bounds on a $(t,s)$ arc to enforce a flow of $n$ between $s$ and $t$.


Is the set of Multiplicative Proof Nets a proper subset of set of well formed single-agent Interaction Nets? There are various criteria for the correctness of multiplicative proof nets.
In Correctness of Multiplicative Proof Nets is Linear, Stefano Guerrini nicely describes few of them with an efficient algorithm.

We can erase the difference between par and tensor connectives and treat it as an interaction net with a single node (agent) type.
In such a net we still can perform cut elimination faithfully as the procedure does not depend on the node labeling (by par and tensor). Is that right?

Assuming that's right let's consider the converse problem.
Let's have an interaction net with single agent type that normalizes. Further assume that the normalized net has no vicious cycles.

Is it always possible to assign par-tensor labeling to the un-normalized net so that we obtain a correct proof net? Is there an efficient 'labeling' inference algorithm?

Your observation about cut-elimination being faithfully represented in the unlabelled interaction nets is correct.  However, the answer to your question is no.

Let us call $\delta$ the unique agent of the system. Such an agent is binary; we distinguish its two auxiliary ports by referring to as left and right. We call cell an occurrence of the agent in a net. The interaction rule between two $\delta$ cells $c$ and $d$ is as follows: the two cells disappear and two wires are created, each connecting that which was the left (resp. right) port of $c$ to the left (resp. right) port of $d$.

Consider now the net $\mu$ composed of two $\delta$ cells, call them $c$ and $d$, such that:

their principal ports are connected by a wire (there is a cut);
the right auxiliary port of $c$ is connected by a wire with the left auxiliary port of $d$ (there is an axiom between them);
the other two auxiliary ports (the left of $c$ and the right of $d$) are free (in proof net syntax, this means they are connected with two axioms with one free conclusion each).

Observe that $\mu$ reduces in one step to a wire (in proof nets syntax, the net reduces in two steps to an axiom).  So the result certainly has no vicious circle.  However, the only sensible way to label $\mu$ (by "sensible" I mean avoiding ill-typed things like a cut between two tensors or between two pars) is to label one delta cell with a tensor and the other with a par, obtaining a net which is not correct: there is a "bad" cycle going through the cut and the axiom connecting the auxilary ports of $c$ and $d$.


How are PCPs and ZKPs related? I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge Proofs?

PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the proof is relatively efficient.

The main problem tends to be the computational complexity: generating a PCP for an arbitrary NP language is efficient only in theory, and thus people look for more efficient solution.

A recent related paper, that does something in between is by Bitansky and others (TCC 2013) where they study "linear PCPs" and their relation to ZK. Since linear PCPs (see their paper) are less stringent than general PCPs, they can be constructed more efficiently.


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

In Agda this is done by tagging types as "irrelevant". It's a kind of quotenting. A function from an irrelevant to a (relevant) type must be constant (and Agda enforces this). You can read more about it on the Agda wiki Irrelevance page.


How do you organize your papers? Possible Duplicate:
  Do you use any article organizers?

[[ This is intended as a wiki question ]]

I have tons of papers on the subject I'm studying.  When you get them from ACM or someone's website, they're usually called something like kautz-a1.pdf or, my favorite, paper.pdf.  What I've done is organize them by:

year - first author's last name - paper title.pdf

So for example, in /papers:

2007 - Wang - PRT for RT indirect lighting using spectral mesh basis.pdf

This seems to work, and I can usually find what I'm looking for.  I mirrored this folder on DropBox, so I can pull down the collection if I happen to be working on another computer than my main.

How do other people store them?

I use Mendeley, which allows you to tag your papers, find them by topic, author, export bibtex files, and so on.


Abstract high-level framwork for #SAT In Abstract DPLL and some other sources there is a high-level framework/ model explained using states and transitions. I need (to build) such a model for a #SAT algorithm. I do know that #SAT algorithms can be build on top of DPLL or other solvers but i could not find a high-level framework/ model for #SAT.

Question: Is there any such or similar model for a #SAT solving algorithm, or else which rules will have to be added to abstract DPLL to get a #SAT solver?

DPLL can be modified to count model, i.e. to solve #SAT. So yes, you can modify the Abstract DPLL for #SAT.

However, AFAIK DPLL is not state-of-the-art for #SAT, so a DPLL-based framework is neither important nor useful. The Abstract DPLL is useful because it covers most state-of-the-art DPLL-based SAT solvers.

You can take a look at these following papers:

1) Counting Model using Connected Components. It is implemented in the tool RelSAT.

2) On Compiling CNF into Decision-DNNF. CNF is compited into DNF to count model. The authors have a tool, c2d, implementing this approach.


Functions that are Not Efficiently Computable but Learnable We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable") can be expressed by polynomial neural networks with reasonable sizes, and thus can be learned with polynomial sample complexity ("learnable") under any input distributions.

Here "learnable" only concerns the sample complexity, regardless of the computational complexity.

I am wondering about a very closely related problem: does there exist a function that can not be efficiently computed by Turing machine in polynomial time ("not efficiently computable"), but meanwhile, can be learned with polynomial sample complexity ("learnable") under any input distributions?

[1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, "On the Computational Efficiency of Training Neural Networks", 2014

I will formalize a variant of this question where "efficiency" is replaced by "computability".

Let $C_n$ be the concept class of all languages $L\subseteq\Sigma^*$
recognizable by Turing machines on $n$ states or fewer.
In general, for $x\in\Sigma^*$ and $f\in C_n$, the problem of evaluating
$f(x)$ is undecidable.

However, suppose we have access to a (proper, realizable)
PAC-learning oracle $A$
for $C_n$. That is, for any $\epsilon,\delta>0$,
the oracle requests
a labeled sample of size
$m_0(n,\epsilon,\delta)$
such that, assuming such a sample was drawn iid from
an unknown distribution $D$,
the oracle $A$ outputs a hypothesis $\hat f\in C_n$
which, with probability at least $1-\delta$, has $D$-generalization error
not more than $\epsilon$.
We will show that this oracle is not Turing-computable.

Actually, we will show that a simpler problem is undecidable:
One of determining,
given a labeled sample $S$,
whether there exists an $f\in C_n$ consistent with $S$.
Suppose (to get a contradiction) that $K$ is a Turing machine
that decides the consistency problem.

We make the following notational conventions.
Identify $\Sigma^*$ with $\mathbb{N}=\{0,1,2,\ldots\}$ via the usual
lexicographic ordering.
For $x\in\{0,1\}^*$, we say that a TM $M$ "S-prints"
$x$ if it accepts all of the strings in $\Sigma^*$
corresponding to the indices $i$ s.t. $x_i=1$
and does not accept (possibly by not halting)
any of the strings
corresponding to the indices $x_i=0$.
Since (by assumption) $K$ is
decidable,
it follows that the function $\tilde K:x\mapsto k$,
defined to be the smallest $k$ such that some TM in $C_k$
S-prints $x$, is Turing-computable.
It further follows that
the function
$g:k\mapsto x$, which maps a $k\in\mathbb{N}$
to the least (lexicographically) string $x\in\{0,1\}^*$
such that $\tilde K(x)>k$, is also computable.

Now define the TM $M$ as follows: $M$ S-prints $g(|\langle M\rangle|)$,
where
$\langle M\rangle$ is the encoding of $M$,
$|x|$ denotes string length, and the recursion theorem
is being invoked to assert the existence of such an $M$.
Then $M$ has some encoding length, $\ell=|\langle M\rangle|$,
and it S-prints some string, $x_M\in\{0,1\}^*$.
By construction, $\tilde K(x_M)>\ell$, and so $x_M$ cannot be S-printed
by any TM with description length $\ell$ or shorter. And yet it is defined
as the S-print output of a TM with description length $\ell$ --- a contradiction.


Motivation for randomness extractors I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must admit I am getting somewhat out of my depth.

From what I have read, a randomness extractor is a function:

$E:\{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$

such that for every distribution $X$ on $\{0,1\}^n$ with minimum entropy $k$ and $Y$ (a "truly random seed") uniformly distributed on $\{0,1\}^d$, we have $E(X,Y)$ is $\epsilon$-close to a uniform distribution on $\{0,1\}^m$.

I understand the motivation to produce truly random bits, but do not understand how the concept of an extractor is useful if it already requires a truly random seed. Surely if we can already produce a truly random seed we have already solved the problem of producing truly random bits?

Also, are there any examples of an explicit use of extractors in areas such as cryptography or coding theory?

Here we have $d \ll m$, i.e., we start with a little bit of good randomness, and we end up with a lot.  That's why it's called a "seed": you need something small to get you started, but you end up with a giant beautiful oak tree of randomness.

The other thing to know is that uniformly distributed bits are high-quality randomness, whereas bits with min-entropy $k$ are low-quality randomness.  So an extractor says: if you start with a little bit of high-quality stuff, and a lot of low-quality stuff, you can generate a lot of high-quality stuff.  That sounds potentially useful, at least in theory.

Do cryptographers use them in practice?  Well, they could, but honestly, practitioners usually don't.  Instead, they often use hash functions (and implicitly apply some kind of random oracle assumption).  That's not as principled -- using an extractor would lead to stronger, provable guarantees -- but it's somehow similar.  You could view extractors as providing solid theoretical foundations for this sort of thing.  They also have important implications for a variety of complexity-theoretic results, which I won't try to summarize here, so extractors are certainly interesting to study.


Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm In the quantum adiabatic algorithm, one prepares the ground state of a Hamiltonian $H_{i}$, and then evolves the Hamiltonian slowly over time to a target Hamiltonian $H_{f}$ via the interpolation $H(s)=(1-s)H_{i}+sH_{f}$.

Let $\Delta(s)$ denote the gap between the two smallest eigenvalues of $H(s)$. The Adiabatic Theorem states that if $s$ changes at a rate proportional to $\frac{1}{\Delta(s)^2}$, then the system will remain in the ground state of $H(s)$ at all times with high probability. Thus proving a lower bound on $\Delta(s)$ implies an upper bound on the runtime of the adiabatic algorithm.

My question is:

  What proof techniques are know to place lower bounds on the size of the spectral gap $\Delta(s)$?

I'm aware of two results in this area:

In some cases the gap can be found analytically, as is the case for adiabatic Grover search. Reference: http://arxiv.org/abs/quant-ph/0206003
In some cases the gap can be be bounded using results from the mixing times of Markov chains, as is the case when preparing the Kitaev clock state for a poly-size quantum circuit. Reference: http://arxiv.org/abs/quant-ph/0405098

I'd appreciate pointers to any other results in this area.

You might find the techniques here useful too:
http://arxiv.org/abs/1203.5801

A generalization of the above is on its way.

There are various references that give bounds for mixing times of Markov chains. Sometimes the gap of the quantum systems can be related to a the gap (largest to second largest) of a Markov chain, in which case the techniques such as rapidly mixing, high conductivity, gap upper bounds of Markov chains become relevant . Eg.
Persi Diaconis and Laurent Saloff-Coste, 'comparison theorems for reversible markov chains'

RM


Boolean Circuit in a Black Box? Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.

Let's equip a normal Turing machine with a "black box oracle" that contains a boolean circuit of unknown size, and call this Turing machine a "black box machine". The black box oracle pretty much works the same way as an ordinary oracle machine, whose input and output (which are just the input/output of the circuit) are both polynomially bounded by the input size of our black box machine. As in the usual oracle machine's case, the evaluation of the black box circuit takes $O(1)$ time.

Now we define the boolean black box (BBB) problem:

(BBB) Given a circuit $C$ which size is polynomially bounded by $n$ and a black box $B$ which input and output are both polynomially bounded by $n$, determine whether $C$ will always behave identically as $B$ (in other words, for any possible input, whether $C$ and $B$ always produce the same result).

And the corresponding function problem:

(BBB-F) Given a black box $B$ which input and output are both polynomially bounded by $n$, compute a circuit $C$ that always behaves identically as $B$.

It seems to me that BBB is unlikely to be in $P$, or even $NP$, because generally one needs to check all $2^n$ possible input/output pairs, which would take more than polynomial time. However, what happens if we restrict the size of the black-box circuit to be polynomially bounded by $n$? (Notice that this does change something: if we restrict the size to be some constant $c$, then the problem can be solved in linear time. But what happens when the bound is polynomial?) Of course, we would also like to know if BBB-F will fall into $FP/FNP$ with this restriction.

A variant of this problem is that we only require the machine to be correct with a probability that is significantly higher than $1/2$. In other words, does $BBB \in PP$?

Third question: $PSPACE$. Can this possibly be solved in polynomial space?

Also, I can see some vague connections between this problem and some craptographic problems. For instance, I would guess that a CCA2-secure cryptosystem exists if and only if BBB-F is not in FP. To see the left-to-right part, simply put the decrypting procedure along with the secret key into a black box. An attacker with access to this black box has essentially the power to perform CCA2 attack. Now if BBB-F is indeed in FP, then we can construct a valid circuit $C$ within polynomial time that behaves the same as the black box circuit, which is the decryptor, and that would break the security of the system.
As for the other way around, I don't have a good idea yet.

I googled quite a bit but couldn't find useful info about work done along this direction, so I would really appreciate it if someone can point me to some relevant literature. Any further thoughts on this problem would also be much appreciated. Thanks for your time!

Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of the initial input is "hidden" from you.

As suggested by M. Alaggan, the problems BBB and BBB-F are probably closest to the "learning with membership queries" framework, where one can only access a target function by querying it at various points and tries to infer the function. Nevertheless, both problems require superpolynomially many queries to the black box in the worst case, so they are both "intractable" in that sense. For BBB and BBB-F, your intuition is correct: it requires $\Omega(2^n)$ queries just to check that $B$ is not the "all-zeroes" function.

Even if you assume that the black box in these problems can be indeed modeled by some polynomial size circuit, it is highly unlikely that this helps. For example, if pseudorandom functions exist (a common cryptographic assumption) then for all $n$ there are polynomial size circuits $C_n$ with $n$ bits of input that cannot be distinguished from a completely random $n$-bit function, by any probabilistic subexponential time algorithm with black-box access to $C_n$. It follows that no subexponential time algorithm can efficiently reconstruct $C_n$ just from queries to $C_n$.


If $P=BPP$, then Is it correct that $IP=NP$? This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, this is not a repeated question, my question is the following:

I'm now studying Interactive Proof System in Goldreich's textbook and here. I have the following question:

Suppose P=BPP, then this show that randomness doesn't give us power over deterministic model (moreover, this would show that we can derandomize every randomness algorithm into deterministic model). Now, In interactive proof system, we know that if Verifier is deterministic, then Prover can guess all questions that Verifier would ask. So, interactive proof system is useless without randomness (see Claim 1 in the above lecture note). Moreover, interactive proof system such that Verifier is not using randomness would be equivalent to class NP. Now, does this mean if P=BPP, then IP=NP? Why I say something like that? Well, since Prover has unbounded computation power, then Prover can simulate randomness by derandomness.

Thank you!

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the latter is even weaker than $\mathsf{IP} = \mathsf{NP}$). To give you a little intuition, the point is this: $\mathsf{P} = \mathsf{BPP}$ says that when deciding a deterministic thing, randomness doesn't help (up to poly factors). But in interactive proofs, the randomness isn't used to decide a deterministic thing, the randomness is used to "fool" the prover.

As a related (but admittedly different) example note that even if $\mathsf{P} = \mathsf{BPP}$, that doesn't obviate the need for randomness in distributed computing. For example, selecting unique IDs for processors in a distributed system can be done using randomness with high probability (everyone just picks a random ID from a large enough range), and even if $\mathsf{P} = \mathsf{BPP}$ there seems to be essentially no way to remove this use of randomness. (Same goes for one-time pads in crypto.)

I suppose some more formal evidence would be an oracle relative to which $\mathsf{P} = \mathsf{BPP}$ and yet $\mathsf{IP} \neq \mathsf{NP}$ - shouldn't be too hard to construct...


What are the complexities of the following SAT subsets ? Assume $P \neq NP$

Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$).

|x| is the size of the instance x.

Let L be a language, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ |  } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

What is the complexity of the following languages :

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$
$L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

As $L_1 \sqcup L_2 = SAT$, they can't be both in P under the assumption that $P \neq NP$.
As there both have exponential holes, I don't think SAT can be reduced to one.

Hence the intuition would be that they are both in NPI, but I can't find a proof or disproof.

Two others languages are
$L_3 = SAT|_{|x|={}^{2i+1}2}$
$L_4 = SAT|_{|x|={}^{2i}2}$

If one of both is in NPC, the other is in P because for each instance of one, it can't be transformed into an greater instance of the other because it is of exponential size, and smallers instances have a logarithmic size. Still by intuition, there is no reason why they would have a different complexity. What would their complexity be ?

Ladner's proof of NPI problems under $P \neq NP$ assumption use languages like $L_1$ or $L_2$, but $L_1$ and $L_2$ aren't built by diagonalization.

I think both are NPI under the stronger assumption (but obviously true) that NP is not in "infinitely often P" - i.e., every polynomial time algorithm A and every sufficiently large n, A fails to solve SAT on inputs of length n.

In this case, such languages are not in P, but they also cannot be NP complete, since otherwise a reduction from SAT to a language L with large holes will give an algorithm for SAT that succeeds on these holes.

Such an assumption is also necessary, since otherwise the languages can be in P, or NP-complete, depending on where the "easy input lengths" are located.


Bloom filter for predecessor queries? Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form,  given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$?  Like a Bloom filter it would allow rare false positives and would only report yes or no.

To clarify a little, I am looking for a data structure that uses much less space than a binary search tree would but with comparable or better performance. Also, what is theoretical minimum space for a randomized data structure for this problem with a given false positive rate?

Another related problem is (1d) emptiness queries in computational geometry but in our case the range is fixed in advance.

Here's one possible approach.

For a fixed value $b$, it's easy to build a Bloom filter that stores a set $S$ of values and lets us answer queries of the form "is there any $s \in S$ such that $s \in [x,x+2^b-1]$?", where $x$ is a parameter of the query and is constrained be a multiple of $2^b$ (in other words, the ranges are $2^b$-aligned and are of length $2^b$).  (How do you do that?  Store $\{\lfloor s/2^b \rfloor : s \in S\}$ in a regular Bloom filter.)

Now, for a value $x$, you can decompose the range $[x-k,x+k]$ into a union of $O(\lg k)$ ranges of the above form.

So, our succinct data structure will be composed of multiple Bloom filters: one Bloom filter for each non-negative integer $b$.  We store a copy of $S$ in each of those Bloom filters.  To answer the query "is there any $s \in S$ such that $s \in [x-k,x+k]$?", we decompose $[x-k,x+k]$ into $O(\lg k)$ ranges that are $2^b$-aligned, and then we make the appropriate queries to the component Bloom filters.  Since we increase the number of queries by a factor of $O(\lg k)$, the false positive rate doesn't increase too much.  In fact, I think you can show that you will only need to make at most 2 queries to each component Bloom filter (i.e., the constant hidden by the big-O notation is at most 2), so I expect this should work pretty well in practice.

Note that this data structure actually allows you to generalize even further: $k$ does not need to be fixed in advance; it can instead be specified as part of the query.

I would expect this data structure to be a little bit more compact than a binary search tree, but not a lot.

A binary search tree uses $\Theta(|S| \lg \max(u,|S|))$ space, where $u$ is an upper bound on the largest value that can be stored in $S$.
In contrast, for a fixed $k$, my data structure uses $O(|S| \lg k)$ space.  This is a little bit smaller, if $k \ll u$ or $k \ll |S|$.
Also, if $u \approx |S|$, then my data structure is more compact still: it uses $O(|S|)$ space (due to collisions, the Bloom filter for $b$ only needs to able to hold up to $u/2^b$ items and thus can be stored in $O(u/2^b)$ space; note that $u + u/2 + u/4 + \dots \le 2u$).

At this point the constants are likely to matter, so you might need to try out some implementations to see if my approach is truly better than a binary search tree in practice.  You might also want to compare to storing the elements of $S$ in sorted order and answering queries using binary search over that list.


Shortest paths when randomly scrambling a Rubik's cube I saw a previous question about local maxima for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a Rubik's cube.

  If I were to pick a (solvable) configuration at random, how far is it
  to the solved state?
  How many random moves does it take to sufficiently scramble the cube?

For the second question, I'm thinking of it as the mixing time, like for the Diaconis 7 shuffle result for a deck of cards. (Perhaps this is the wrong terminology?)

This is related to another question of mine about adversarially scrambling a Rubik's cube.

Edit: I accepted Marzio's answer, though I still wonder about the mixing time. Google revealed some results for particular finite groups, but I didn't see anything about Rubik's cube. Maybe one of these is applicable / can be ported over?

At God's number is 20 site you can find a nice distance/count table:

"... Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher ...."

According to the table if you pick a random configuration it will be with high probability at distance 17-18 from the solution.

See also D. Joyner's notes Mathematics of the Rubik's cube (and D. Joyner's book "Adventures in Group Theory: Rubik’s Cube, Merlin’s Machine, and Other Mathematical Toys")


Natural NP-complete problems with high density? (This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.)

Let us say that a language $L\subseteq \{0,1\}^*$ has high density, if it contains a positive constant fraction of all $n$-bit strings. That is, there is a constant $c>0$, such that $$|L\cap \{0,1\}^n|\geq c2^n$$ holds for all $n$.

It is not hard to construct artificial examples of NP-complete problems with high density. For example, let $L$ be any NP-complete language. For a binary string $z$, let $w(z)$ denote the weight of $z$, which is the number of 1-bits in $z$. Now define
$$ L'=\{xx\,|\,x\in L\}\cup \{y\,|\, w(y)\:\mbox{is odd}\}. $$
It is easy to see that $L'$ has high density, and it still remains NP-complete.

The above example, however, is quite artificial, it is constructed for the sole reason of exhibiting this property. I expected that one could easily find natural NP-complete problems with high density, and I was surprised that this turned out harder than I thought. So, the question is:

  What are some examples of natural NP-complete problems with high density?

Edit:

From the discussion in the comments I realized that a better question would be this:

  What are some examples of natural NP-complete problems with the property that both the yes-instances and the no-instances have high density?

Comment => Answer.

In this paper, Posa shows that for some constant $c$, a graph chosen from the Erdos-Renyi random graph distribution $G(n, c \log n / n)$ has a Hamiltonian cycle with probability approaching $1$ as $n \rightarrow \infty$. If we encode the input to the Hamiltonian Cycle problem as simply a bit-string representing its adjacency matrix, the uniform distribution over $n$-vertex inputs would be exactly the $G(n,1/2)$ distribution (with some irrelevant self loops) -- much more dense than what's needed. Since the existence of a Hamiltonian cycle is a monotone property, the conclusion that the vast majority of graphs have a Hamiltonian cycle follows.

Possible approach to new question

My guess is that you get exactly that for the question of "does there exist a Hamiltonian cycle where $u$ is a neighbor of $v$". I'm not going to fully justify everything, but the reasoning may go roughly as follows.

Claim: For $G \sim G(n,1/2)$ and $u$ and $v$ designated uniformly at random, there is a Hamiltonian path starting at $v$ and ending at $u$ with at least some constant probability.

Take a random Hamiltonian cycle (many of which will exist with overwhelming probability in $G(n,p)$). We show how to transform this, with at least constant probability of success, into a Hamiltonian Path with endpoints $u$ and $v$. For simplicity, we ignore (immediately fail on) the $o(1)$ fraction of cases in which $u$ and $v$ are a distance less than $4$ apart (thus, their neighborhoods are disjoint and not adjacent in the cycle). An intuitive guess is that the two neighbors of $v$ in this cycle should have an edge with constant probability (close to $1/2$), as should $v$ to one or both of the neighbors of $u$ (probability close to $3/4$). If all this happens (probability close to $3/8$), there is a Hamiltonian Path starting at $v$, heading to a neighbor of $u$, continuing along the original Hamiltonian path in the direction away from $u$ (skipping over $v$ once we get to that point), and finally ending at $u$. $\square$

Thus, with some constant probability $c$, there should be a Hamiltonian path starting at $v$ and ending at $u$. The chance that they're adjacent is $1/2$, so with probability $c/2 = \Omega(1)$, there is a Hamiltonian cycle in which $u$ is a neighbor of $v$. Conversely, with probability at least $1/2$ the vertices $u$ and $v$ are not adjacent, so there can't possibly be a Hamiltonian cycle with $u$ and $v$ as neighbors. The conclusion follows.