# Question
Title: Why aren't we researching more towards compile time guarantees?
I love all that is compile time and I love the idea that once you compile a program a lot of guarantees are made about it's execution. Generally speaking a static type system (Haskell, C++, ...) seems to give stronger compile-time guarantees than any dynamic type system.

From what I understand, Ada goes even further with regards to compile time checking, and is able to detect a greater range of bugs ahead of execution. It's also considered fairly safe, given that, at some point in time, it was chosen for delicate fields (when programming errors may cost human lives).

Now, I wonder: if stronger static guarantees, leads to code that is more documented and safe, then why aren't we researching more in that direction?

An example of something that seems to be missing, would be a language that instead of defining a generic `int` type that has a range determined by the number of bits of the underlying architecture, one could have ranges (in the following example `Int [a..b]` describes an integer type between a and b included):

```
a : Int [1..24]
b : Int [1..12]
a + b : Int [2..36]
a - b : Int [-11..23]
b - a : Int [-23..11]

```

or (taking this from Ada):

```
a : Int [mod 24]
b : Int [mod 24]
a + b : Int [mod 24]

```

This language would select the best underlying type for the range and would perform compile time checking on the expressions. So that, for example, given:

```
a : Int [-3..24]
b : Int [3..10]

```

then:

```
a / b

```

will never be not defined.

This is just an example but I feel like there's a lot more that we can enforce at compile time. So, why there seems so little research on this? What are the technical terms that describe this idea (so that I can find more informations on this topic)? What are the limits?

# Answer
I am not in a position to tell how much *more* research should be done on the topic, but I can tell you that there *is* research being done, for example the Verisoft XT program funded by the german government.

The concepts which I think you are looking for are called **formal verification** and **contract based programming**, where the latter is a programmer-friendly way of doing the first. In contract-based programming you first write your code as normal and then insert so called *contracts* into the code. A readily usable language which is based on this paradigm is Spec# by Microsoft Research, and the functionally similar but slightly less pretty Code Contracts extension for C# which you can both try out online (they also have similar tools for other languages, check out rise4fun). The "int with range type" you mentioned would by reflected by two contracts in a function:

```
Contract.Requires(-3 <= a && a <= 24);
Contract.Requires( 3 <= b && b <= 10);

```

If you want to call that function, you then have to use parameters which are ensured to meet these criteria, or you get a compile time error. The above are very simple contracts, you can insert almost any assumption or requirement about variables or exeptions and their relation which you might think of and the compiler will check if every requirement is covered by either an assumption or something that can be ensured, i.e. derived from the assumptions. That is why where the name stems from: The callee makes *requirements*, the caller *ensures* that these are met - like in a business contract.

Under the hood, code contracts are usually combined with knowledge about the inner workings (operational semantics) of the programming language into a list of *verification conditions*. This list represents basically one big logical proposition $P(x\_1,x\_2,...,x\_n)$ with $n$ free variables - the inputs of your program. If the proposition $P$ is true for all possible variable assignments, then the program is considered correct. To check whether or not this is the case, an SMT Prover is used. From the CS side, those two are the critical parts of the process - the generation of verification conditions is tricky and SMT is an either NP-complete or undecidable problem, depending on the considered theories. There is even a competition for SMT solvers, so there certainly goes some research into this. Additionally, there are alternative approaches to using SMT for formal verification like state space enumeration, symbolic model checking, bounded model checking and many more which are also being researched, albeit SMT is, afaik, currently the most "modern" approach.

Regarding the limits of the general idea:

* As previously stated, proving the correctness of the program is a computationally hard problem, so it might be possible that the compile time check of a program with contracts (or another form of specification) takes really long or might be even impossible. Applying heuristics which work well most of the time is the best one can do about it.
* The more you specify about your program, the higher gets the probability of having bugs in the specification *itself*. This can lead to false positives (the compile time check fails even though everything is bug-free) or the false impression of being safe, even though your program still has bugs.
* Writing contracts or specifications is really tedious work and most programmers are too lazy to do it. Try writing a C# program with code contracts everywhere, after a while you will think "come on, is this really necessary?". That is why formal verification is typically just used for hardware design and safety critical systems, like software controlling airplanes or automotives.

One last thing worth mentioning which does not quite fit the above explanation is a field called "Implicit Complexity Theory", for example this paper. It aims at characterizing programing languages in which each program you can write falls into a specific complexity class, for example P. In such a language, each program you write is automatically "ensured" to be of polynomial runtime, which can be "checked" at compile time by simply compiling the program. I do not know of any practically usable results of this research, however, but I am also far from being an expert.
> 11 votes

---
Tags: programming-languages, type-theory, type-checking, software-verification
---


# Question
Title: Is there a clear definition of "computable" for models of computation which are not turing complete?
This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", but according to some papers I read, the definition is also not really clear when it comes to models of computation weaker than turing machines because of the encoding of the input and output.

The typical definition of *turing computable* is as follows:

> Definition 1: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called *turing computable* iff there is a turing machine $M$ which computes $f$ using a **suitable encoding** of the natural numbers as strings.

The definitions differ in what exactly is a *suitable encoding* is, but most refer to **binary encoding**, **unary encoding** or **decimal encoding** as the one fixed and suitable encoding. It is also possible to show that fixing one encoding is required for the definition of turing computability. But what makes, say, binary encoding of natural numbers special so that we can axiomatize it as the one suitable encoding? Probably because it fits the intuitive notion of what computability means *coincidentally*.

Now what if we look at *weaker* models of computation than turing machines? For example, let's consider the set $M\_c$ of "crippled" turing machines with the alphabet $\\{0,1\\}$ which may only move to the right, and a definition of *crippled turing computable* which is consistent with that of turing computability:

> Definition 2: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called *crippled turing computable* or *computable in $M\_c$* iff there is a crippled turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as a string.

If we define "suitable encoding" as "binary encoding", then the function $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$ is *not* computable in $M\_c$. If we axiomatize "suitable encoding" as "unary encoding", then $f$ *is* computable in $M\_c$. This seems awkward given the fact that everyone may fix one of the infinitely many intuitive encodings at will. It should be clear if a computation model can compute $f$ or not without referring to some specific encoding - at least I have never seen anyone mention what encoding is used when stating "loop programs are weaker than turing machines".

---

After this introduction I can finally phrase my question: How would one define "suitable encodings" and "computability" for *arbitrary* models of computation which do not coincide with the intuitive notion of computability? Is this possible within the framework of turing computability?

*Edit: I shortened the introduction, it didn't add to the question.*

# Answer
Some basic fact that you are missing here is that all the encodings that you mention are equivalent from the perspective of computability: there is a computable function mapping the binary encoding of a number to its unary encoding, or vice versa. Therefore for the sake of defining computability, it does not matter which of these encodings you choose for numbers. Just fix your favorite encoding.

Computability is at its core a property of string functions $f\colon \Sigma^\* \to \Sigma^\*$. When you define computability in any other domain, you have to fix an encoding. In practice, all "reasonable" encodings are equivalent in the sense of the preceding paragraph, so the exact encoding doesn't matter.

The encoding does, however, matter in restricted models of computation. To take an extreme example, suppose that you consider time-restricted Turing machines: say you want your machine to terminate in time $O(n^c)$ for some $c$, where $n$ is the length of the input (as a string). We can no longer switch between binary encoding and unary encoding, because binary encoding is much more compact. When we talk about a polynomial time computable function of *integers*, we specify that integers are encoded in binary. Even this is a somewhat arbitrary choice, since decimal encoding would lead to the same notion of polynomial time computability.

So to answer your question – the encoding is specified as part of the definition of the restricted model.
> 6 votes

# Answer
First of all, you cannot fix "suitable encoding" to be binary strings, or any other encoding. This is because you would loose too many models of computation, because different models of computation may have very different models of input and output. In other words, they may not "speak" strings.

For example, terms of the untyped lambda calculus are either variables, or the application of one term to another, or an abstraction of a lambda term. Input and output are terms, arbitrary strings. Still, the untyped lambda calculus is Turing-complete because there exists a "suitable encoding" which encodes natural numbers as lambda terms of a certain form, and under this encoding for each computable function there exists a lambda term which computes it.

You can formalize "suitable encoding" if you fix Turing machines as your reference model of computation, and then require that the encoding and decoding from and to binary strings must be carried out by a Turing machine which always halts. For example, a Turing machine would be able to translate a natural number as a binary string to a Lambda term which expresses this number, simulate the reduction in the lambda calculus, and translate the result back to a binary string.

For simpler models of computation I would expect the same approach: take a reference model of computation and fix an encoding of the natural numbers, and then make sure that the encoding and decoding is done by instances of that simple model. As you noted, for crippled Turing machines, using unary and binary encoded numbers would not yield an equivalent model of computation.
> 4 votes

---
Tags: computability, computation-models
---


# Question
Title: Why does quicksort work well with virtual memory?
*Introduction to Algorithms* said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is it just because quicksort sorts in place?

# Answer
> 6 votes
The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this:

> The hardware feature on modern computers that has the most drastic effect on the performance of algorithms is paging. Quicksort actually does not perform badly in a virtual memory situation (see \[2\]) because it has two slowly changing "localities" around the scanning pointers. In some situations, it will be wise to minimize page faults by performing the extra processing necessary to split the array into many partitions (instead of only two) on the first partitioning stage. Of course, the programs should be changed so that small subfiles are "insertionsorted" as they are encountered, because otherwise the last scan over the whole file will involve unnecessary page faults. Many internal sorting methods do not work well at all under paging, but Quicksort can be adapted to run quite efficiently.

The reference \[2\] cited there for further details is:

* B.S., Gustavson, F.G., and Mankin, E. "Sorting in a paging environment." Comm. ACM 13, 8 (Aug. 1970), 483-494.

As it was suggested in the other answer, in more modern terms, the same property is phrased as quicksort having good cache locality; this is said for example in the 1994 paper "AlphaSort: A RISC Machine Sort" by Nyberg et al.; summary; the full text of this is found for example in *Readings in Database Systems* by Hellerstein and Stonebraker.

# Answer
> 2 votes
Data locality matters a lot with sorting algorithms.

http://betterexplained.com/articles/sorting-algorithms/

Look up "Cache Oblivious Algorithms" for more general principles relating algorithms to their ability to run well in the presence of caches.

---
Tags: algorithms, algorithm-analysis, sorting, virtual-memory, quicksort
---


# Question
Title: The maximum number of statements that could be true at the same time
I've come across a programming question. I can't solve it but I can write the question in mathematical form as follow:

> Receive *k* equations,and for each equation receive 3 variables *a*, *b*, and *c* in the following form:
>
> *a*x + *b*y + *c*z \>= 0
>
> This is an example input of k = 4:
>
> 1) 2x + 1y + 0z \>= 0
>
> 2) 1x - 2y + 0z \>= 0
>
> 3) 3x + 3y - 50z \>= 0
>
> 4) -1x + 2y - 50z \>= 0
>
> You should find the maximum number of statements that could be true at the same time given that x, y, and z are positive real numbers and x \>= y \>= z. As for the following example, the answer is 3.

Please help me with the idea or the design paradigm I should use to solve this problem. The algorithm should be relatively fast. It should be able to compute k = 1,000 in 1 seconds.

# Answer
There is a $O(k^4)$ time algorithm that works by considering all possible subsets of three out of the $k$ inequalities, looking at the "intersection point" of those 3 inequalities, and counting how many of the inequalities that intersection point satisfies.

In more detail:

This can be solved if you are familiar with some basic facts from linear programming and the simplex method. Let $S$ be a set of $m$ linear inequalities in $n$ variables. $S$ defines a $n$-dimensional polytope. Then the following fact is useful:

**Fact:** If $S$ has a feasible solution, then it has a feasible solution that is one of the vertices of the corresponding polytope.

(Recall that a vertex is a single point that is a "corner" of the polytope. Each vertex can be obtained by taking a subset of $n$ independent linear inequalities from $S$, converting them to equalities by changing $\ge$ to $=$, and solving to find the unique point at their intersection.)

For linear programming, a useful consequence of this fact is that, to find the optimal value of the objective function, it suffices to enumerate only the vertices of the polytope and compute the objective function for each such point. Here we have no objective function and care only about feasibility, but this basic fact is still useful.

In particular, in your problem we have $n=3$ variables ($x,y,z$) and we want to find the largest possible subset of the inequalities, say $j$ of them, that are all consistent. Any such subset of $j$ of the given inequalities corresponds to a set $S$ of $m=j+5$ inequalities: namely, the subset of $j$ inequalities, plus the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$. In this way we get a set $S$ of $m=j+5$ inequalities on $n=3$ variables. Now if there is a feasible solution to $S$, then one of the vertices of $S$ must be a feasible solution.

Essentially, this means that we can restrict our attention to only the vertices; we can ignore all other points in the polytope.

Of course, we don't know what $S$ is, so we don't know what the polytope is. Nonetheless, we can still use this fact. This fact means that we can restrict our attention to only the "possible vertices", where a "possible vertex" is a point that is a vertex of one such polytope. In other words, consider all possible polytopes obtained by taking some subset of the given inequalities and adding the additional inequalities $x\ge 0$, $y\ge 0$, $z \ge 0$, $x \ge y$, $y \ge z$; take the union of the vertices of all of these polytopes. Then it suffices to look only at these possible vertices -- we don't need to consider any other possible value of $x,y,z$.

How many possible vertices are there? Well, each vertex is determined by choosing $n=3$ of the inequalities, converting them to equalities, and looking at their intersection. So, there are only ${k+5 \choose 3} = O(k^3)$ possible vertices. For each possible vertex, we can count how many of the $k$ inequalities it satisfies, and see which one satisfies the largest number of inequalities. That one will be the optimal solution to your problem.
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Hardness of a constrained quadratic maximization
Consider the following quadratic maximization: \begin{align} \max\_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace \mathbf{x} \in \mathbb{R}^{n} :~ \\|\mathbf{x}\\|\_{2}=1, \\|\mathbf{x}\\|\_{0}\le k \rbrace, \end{align} where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter. This problem is NP-hard, by a reduction from the max-clique problem.

I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$. In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups. We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group. That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups.

Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).

I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.

# Answer
*(I have found the answer to my question, so I am sharing a sketch here)*.

The quadratic maximization can be shown to be NP-hard by a reduction from the following problem:

* Given $k$-partite graph $G=(V\_{1}, \dots, V\_{k}, E)$, does $G$ contain a $k$-clique.

Note that the latter problem is a (seemingly) special case of the max-clique problem restricted to a particular family of graphs. It can however be shown that it is also NP-complete by a reduction from the general max-clique problem itself (See here).

Let $\mathbf{A}$ denote the adjacency matrix of $G$. Let $S$ be an arbitrary set of $k$ vertices and $\mathbf{A}\_{S}$ denote the principal submatrix corresponding to $S$, *i.e.* $\mathbf{A}\_{S}$ is the $k\times k$ adjacency of the graph induced by $S$. If the vertices in $S$ form a $k$-clique in $G$, then all off-diagonal entries of $\mathbf{A}\_{S}$ are equal to $1$, and its principal eigenvalue $\lambda\_{1}(\mathbf{A}\_{S}) = k-1$. In any other case, that is, if $S$ is not a $k$-clique, then $\lambda\_{1}(\mathbf{A}\_{S}) \< k-1$. Finally, note that since $G$ is $k$-partite, a $k$-clique (if one exists) will contain a single vertex from each of the sets $V\_{i}$, $i=1,\dots,k$.

Let $\mathbf{A}^{\prime} = \mathbf{A} + |\lambda\_{n}(\mathbf{A})|\cdot\mathbf{I}$, where $\lambda\_{n}(\mathbf{A})$ is the smallest eigenvalue of $\mathbf{A}$; $\mathbf{A}^{\prime}$ is a PSD matrix. Further, consider $k$ disjoint groups of variables corresponding to the sets $V\_{1}, \dots, V\_{k}$ of $G$. We solve the quadratic maximization with input $\mathbf{A}^{\prime}$ and the specified groups of variables. The maximum objective value will be equal to $k-1 + |\lambda\_{n}(\mathbf{A})|$ if and only if $G$ contains a $k$-clique.
> 2 votes

---
Tags: complexity-theory, optimization, np-hard
---


# Question
Title: Formal Verification of Functional Programs
So I've been interested in learning more about formal verification, and I've seen a lot of interesting things like ACSL and JML which are based on the concept of Hoare triples.

My question is, that these seem to be a way to describe the behaviour of imperative programs via specification languages that are mostly functional (plus universal and existential quantifiers). But I don't even know the keywords to search to start learning how one would perform formal verification of code in a pure functional language like Haskell.

Could anyone provide a link to material or the name of the equivalent/analogue of Hoare triples for pure functional computation? Or do you need a fundamentally different approach in the purely-functional realm?

# Answer
> 2 votes
There is probably a lot that can be said about this subject.

I'll just mention one broad approach: types. Sufficiently expressive type systems allow you to express interesting constraints on your programs. This isn't unique to pure functional programming, but such languages have a reputation of taking it farther than statically typed imperative languages. Haskell already has an expressive type system, and compiler-specific extensions allow you to write even more expressive types.

Ideally, you would be able to write a function and its type signature and if the code compiled, then you would have verified that the implementation of your function corresponds to your *specification*, namely your type signature. It's not *quite* that simple in Haskell, though, since its type system is unsound:

```
x :: a -> b
x = x

```

The above code will compile, even though that might seem a bit objectionable.

The problem is that Haskell allows such functions to potentially be non-terminating, or to effectively crash. In turn, it lets all types be inhabited by *bottom*, the computation that never completes successfully.

But, if we crank up the types to 8, we are able to transcend such inconsistencies by imposing some limitations on what our programs can express. Namely, if we are willing to force certain types of functions to be terminating, and to only use such terminating functions as building blocks in other terminating functions, we have gained some of our ability to reason about types back. This is called *total functional programming*, and now we might with more confidence equate our *types* with being *theorems*, and our *programs* with being *proofs* of such theorems.

Now we just need to crank up our types to 11 in order to reach the heights of the most expressive types that seem to have been implemented in programming languages to this day, namely *dependent types*. Such type systems lets you express arbitrary properties about your programs. The backside to such power is responsibility - you might have to take care to prove that your code actually *implements* whatever your types states that it should.

---

I think that types are very natural path to take for people who are both interested in static functional programming languages and some level of formal verification. Static functional programming languages, like Haskell, already try to encourage a certain rigour with regards to how one structures one's programs such as to take maximum benefit from the capabilities of the type system. Exploring the power and expressibility that types can bring - either as type system extensions in Haskell, or as in full-on proof assistants - can be a very natural extension of that.

# Answer
> 2 votes
You also use Hoare triples. See e.g.

You need triples even for pure functional languages because they too have an effect, namely termination. The precondition establishes whether the program exhibits this effect or not. The post-condition describes the output value.

---
Tags: functional-programming, formal-methods, software-verification
---


title: Happened-before and Causal order

text:
# Question
Title: Happened-before and Causal order
I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me.

Lamport defines the "happened before" partial order, which I understand. Then he says that "Another way of viewing the definition is to say that a -\> b means that it is possible for event a to causally affect event b".

Consider now two events a and b that are message receptions at a process P1, such that a occurs before b. Further more, suppose a and b are the only two events ever occurring at P1. According to the happened-before relation definition, we have a -\> b (which makes sense, since P1 observed those event in this order).

However, I don't see how it is possible for event a to causally affect event b. Those two events are totally unrelated and could have happened in a different order.

What am I missing here?

# Answer
Note that *causality* is an undefined term in the paper. Lamport is using it in an informal explanation. He's assuming that *could causally affect* is an intuitive concept that will mean the same thing to his readers as it does to him. I think for Lamport *$a$ could causally affect* $b$ actually means something more like *information could flow* from $a$ to $b$ or $a$ *could impact the behavior of* $b$, than the classic Aristotelian idea of $b$ *is a physical consequence of* $a$.

For example, suppose a computer is executing a program with two statements:

```
a: X := 1
b: print X

```

I think we could all agree that statement `a` *happens before* `b` but I would not say that "executing the assignment statement (event `a`) *caused* the program to execute the `print` statement (event `b`)". On the other hand I might say something slightly different: "event `a`, (assigning the value 1 to `X`), affected the value printed by event `b`."

Now let's take a (potentially) more controversial example.

```
a: X := 1
b: Y := 1

```

`a` *happens before* `b`, but I think most people would say, "there is no causal relationship between `a` and `b`." But in this paper *there is a causal relationship between `a` and `b`*. I'll try to explain this as succinctly as I can, but it's going to be long winded.

## The paper is about state machines

Here's what Lamport has to say about the paper on his home page:

> A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. ...
>
> This is my most often cited paper. ... But I have rarely encountered anyone who was aware that the paper said anything about state machines. People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem. People have insisted that there is nothing about state machines in the paper. I've even had to go back and reread it to convince myself that I really did remember what I had written.

Each *process* is a state machine, and the composition of the processes into a distributed system/algorithm is a state machine.

Lamport is implicitly using a short-hand notation which in digital design we call *register transfers* and each process is (implicitly) an *algorithmic state machine*. What we really care about is how each event affects the entire state of each process. Each register transfer statement is a succinct way of talking about a set of state transitions that depend on the prior state.

So in our "controversial" example the state of the machine has two parts $\langle X, Y \rangle$. The register transfer statement `Y := 1` is shorthand for four different state transitions: $\langle 0, 0 \rangle \rightarrow \langle 0, 1 \rangle$, $\langle 0, 1 \rangle \rightarrow \langle 0, 1 \rangle$, $\langle 1, 0 \rangle \rightarrow \langle 1, 1 \rangle$, and $\langle 1, 1 \rangle \rightarrow \langle 1, 1 \rangle$. So what happened in statement `a` very much impacts the final state produced by statement `b`. In our case we know that the final state is $\langle 1, 1\rangle$, and that would not be the case had `a` not executed, or had `a` been a different statment (like `X := 0`).

The paper is about how much one of the distributed state machines can know about the states of the other state machines, so it very much matters what order things happen on each individual machine.
> 7 votes

# Answer
As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does *not* imply that $a$ has physically caused $b$ (to happen).

Such causality used in Lamport's paper is often called *potential causality*. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/performance of distributed systems.

To address these issues, we can consider *explicit causality*, or application-specified causal dependencies. One common example is social network applications: Alice has read 100 comments in a conversation thread and replied to 5 of them with a single comment. Her comment's immediate happens-before dependency could only consist of these 5 comments (instead of all these 100 comments with *potential causality*).

Which is the better *causality*? Well, it depends. For example, *potential causality* prevails in the research area of debugging multi-threaded programs. There are two main reasons (in my opinion): First, we have no context/semantics which tells whether two events ($\textsf{read}$ or $\textsf{write}$ operations) are effectively causally-related or not. Secondly, we want to capture all possible causality among events and reveal as many debugs as possible.

For more discussions about *potential causality* and *explicit causality*, please refer to this paper: The Potential Dangers of Causal Consistency and an Explicit Solution.
> 8 votes

# Answer
Your missing the selection of the word **possible**. It doesn't mean that the relationship is actually causal, just that it is possible for **a** to have a causal effect on **b**. His statements are not false, you're just reading more into them than he is actually stating. Just because it's possible doesn't mean it's true. The stronger statement is the inverse, if **a** does not proceed **b** it is **impossible** for **a** to have a causal affect on **b**. It's just a matter of wording.
> 2 votes

---
Tags: algorithms, distributed-systems, clocks
---


title: Find K-th next element in O(log n) time

text:
# Question
Title: Find K-th next element in O(log n) time
> We want to store a set S of distinct positive integers and support the following operations on S:
>
> Insert(a): insert integer a !∈ S into S.
>
> Delete(a): delete integer a ∈ S from S.
>
> FindNext(a, k), where a ∈ S and k is an integer: if S consists of some elements a1 \< a2 \< · · · \< an, and a = ai (for some i, 1 ≤ i ≤ n), then return ai+k (for simplicity, assume that i + k ≤ n).
>
> The worst-case time complexity of each operation should be O(log n) where n is the size of S. An augmented data structure can be used (without any modification) “as a black box” to achieve the above goal: using the operations that this data structure provides, the algorithms for performing the above three operations are quite simple. Give an algorithm for the FindNext(a, k) operation that uses only the operations of this data structure and consists of at most 5 lines of pseudo-code.

You are allowed to make use of other operations available with this data structure, i.e. everything you can make run in the specified time.

# Answer
You can use the **order-statistic tree** which is a red-black tree augmented each node $x$ with an additional field $size(x)$. The field contains the number of nodes in the subtree rooted at $x$ (including $x$ itself).

As red-black tree, order-statistic tree supports `Query`, `Insert`, and `Delete` in $O(\lg n)$ time. Further, order-statistic tree provides two new operations:

1. `Select(i)`: find the element with rank $i$ in $O(\lg n)$ time.
2. `Rank(x)`: obtain the **rank** of element $x$ in $O(\lg n)$ time.

Then `FindNext(a, k)` can be implemented as `Select( Rank(x) + k )`. The time complexity is obviously $O(\lg n)$.

---

For more details of order-statistic tree, please refer to CLRS (Section 14.1: Dynamic order statistics, 2nd edition) or this wiki article.
> 2 votes

---
Tags: data-structures, dictionaries
---


title: How to find witnesses for big O

text:
# Question
Title: How to find witnesses for big O
I'm having trouble determining the correct way (if there is one) to find the witnesses in any given big O problem.

The example I'm struggling with: $2^x + 17$ is $O(3^x)$.

I am expected to find two witnesses such that $2^x + 17 \leq C(3^x)$ whenever $x \> k$.

Unfortunately, my textbook isn't very clear on how to actually find them and rather suggests to more or less guess until you get both constants to work. It is to my understanding that if one pair exists, infinitely many do.

How do you find these?

# Answer
In your case finding the witness is easy. We know that for all $x \geq 0$, $2^x \leq 3^x$. Also, for $x \geq 3$, $17 \leq 3^x$. So for $x \geq 3$, $2^x+17 \leq 2\cdot 3^x$.

There is no particular method at work here – just problem solving.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Sufficient condition for simple graph isomorphism?
Say I have two simple graphs, $A$ and $B$

* In $A$, I know:

+ one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
    + one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
    + etc.
* In $B$, I know:

+ one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
    + one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
    + etc.

Can I derive that graph $A$ and $B$ are isomorphic to each other? Or is there a counter-example where two graphs look the same from this distance point of view, but are not isomorphic?

It is a necessary condition, so if these simple graphs are isomorphic, they will share these distances. I am wondering if this is a sufficient condition as well.

# Answer
There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.
> 10 votes

---
Tags: graphs
---


title: Cost of shifting a number

text:
# Question
Title: Cost of shifting a number
I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001.

I was thinking that the time complexity is $\Theta(n)$, because we have to shift every number.

I need it to calculate $m\*{b^\frac{n}{2}}$, where $m$ is some number and $b$ might be 2 (in case of binary) or 10 (decimal). Therefore instead of multiplication, I just shift to multiply, and therefore complexity is $\Theta(n)$.

Am I correct or is my thinking wrong?

# Answer
> 1 votes
Time complexity is not god-given but is rather defined by the model of computation. To take a simple example, what is the time complexity needed for adding two numbers? In the RAM machine model, this operations takes constant time, as long as the numbers are not "too big". The rationale is that modern hardware implements addition as a fast machine instruction; if the numbers are not "too big" then they fit into single registers. The same reasoning holds for shifts. You have to be careful, however, that the size of the relevant quantities doesn't blow up.

# Answer
> -2 votes
O(n) and CPU execute in one Register then put the result to another Register, so the performance is quick.

Reference http://chortle.ccsu.edu/assemblytutorial/Chapter-12/ass12\_2.html

---
Tags: algorithm-analysis, runtime-analysis, arithmetic
---


title: Can a Von Neumann CPU be pipelined?

text:
# Question
Title: Can a Von Neumann CPU be pipelined?
Can you pipeline a pure Von Neumann architecture based CPU or do you need seperate data and instruction caches for this? If you include seperate instruction and data caches (then it isn't a von neumann CPU anymore, it's a modified Harvard), how do you unify the data of these caches so that they get stored in a single memory?

# Answer
A processor that can only support one memory access per cycle can still be pipelined. Such a memory interface would represents a structural hazard for load and store operations. In addition, store operations would introduce the equivalent of a control hazard since they might change instructions that have already been fetched.

The structural hazard can be detected when the instruction is decoded and the pipeline stalled at instruction fetch at the appropriate point. This allows a load or store to execute at the cost of a pipeline bubble. For stores, the processor can speculate that a store does not address memory that holds instructions which will be in the pipeline (or at least that the store not change the semantics of any such instructions). This is comparable to predicting a branch. As branch prediction requires checking the condition and target, store conflict prediction requires a comparison of the store address with the addresses of all instructions that will have been fetched by the time the store data becomes visible to the instruction fetch stage. As a branch misprediction requires flushing the pipeline so would a store conflict misprediction.

If one allows a wider front end and buffering, the impact of the structural hazard can be reduced. Such buffering, even if it is after instruction decode, *might* be considered a cache.

A processor that breaks some instructions into multiple micro-ops and executes one micro-op per cycle could benefit from such a buffer even if only one instruction is fetched per cycle. Variable length instructions would naturally benefit from a buffer of fetched instructions since a fixed width fetch would often either fetch more than one instruction or fetch only part of an instruction.

If the data access width is greater than the typical instruction length, it also becomes natural to use this greater width for fetching instructions, buffering any excess.

The structural hazard related to loads and stores can avoided by multiporting (or accessing the cache twice within a single cycle) or pseudo-multiporting (banking) the memory. The processor would still have the quasi-control hazard for stores. The main benefits of such an implementation over having separate caches would be somewhat simpler handling of stores and faster operation when running self-modifying code. The processor could still handle the store issue with separate coherent caches, but implementing coherence and handling the delay in realization of stores in the instruction cache would add complexity.

I would argue that a modified Harvard architecture that implements a Von Neumann interface (i.e., is indistinguishable to software except with respect to performance) is Von Neumann. (Recent ISAs generally avoid such guarantees. The benefit of a simpler interface is generally not considered worth the complexity/performance tradeoffs.)
> 4 votes

# Answer
Apparently the ILLIAC II had a single/unified cache (called a "fast buffer") and a primitive 3-stage pipeline. It looks like pretty much every (pipelined) processor thereafter had split (first level) caches, as long as it had caches. L2, L3+ caches are usually unified though.

There have also been some recent proposals for unified first level cache, e.g. from Intel Spain labs (which I didn't even know existed): "Virtually Split Cache: An Efficient Mechanism to Distribute Instructions and Data" (TACO 2013). The main downside is complexity if you want to preserve good throughput. The reasons for the split L1 cache status quo are explained in the paper as:

> While unified approaches usually provide higher hit rates by automatically sharing resources instead of statically partitioning them, split \[L1\] caches are the preferred configuration, mainly because of the following reasons:
>
> * Different instructions can access the instruction cache, in the fetch stage of the pipeline, and the data cache, usually in the memory stage, at the same time in pipelined processors. Unified approaches would require several access ports and, thus, more complexity to provide the same advantages.
> * The instruction cache design may be simpler, as it only needs to perform, ideally, read operations.
> * Unified caches of the same aggregated capacity imply higher latencies.

Their "virtually split cache" proposal is somewhere in between as the cache cells are unified but there are two sets of tags and indices and independent ports.

Also note that the dichotomy between Harvard and von Neumann is not that sharp in practice as most general purpose current processors (using a split L1 cache but unified lower levels of memory) are of the so-called "modified Harvard architecture", which is a combination of the best of both worlds. As I said in a comment above, the terminology "modified Harvard architecture" is somewhat arbitrary given that it applies to a hybrid; you might as well decide to call it "modified von Neumann architecture", it's just that the former has been the established term of art. Furthermore, different authors may mean different things by "modified Harvard architecture"; it could mean that the memory is unified and caches are \[mostly\] transparent so the memory as a whole appears to the programmer as in the von Neumann model, or it could also mean a weaker model in which there are different address spaces for data and programs but there are operations to copy between these; see slide 8 in this presentation, which is one of the comprehensive ones on this topic.
> 1 votes

---
Tags: computer-architecture
---


title: PCA and Eigenvectors

text:
# Question
Title: PCA and Eigenvectors
I am trying to understand how PCA works, and think I got most of it except...

By calculating eigenvalues/vectors of the covariance matrix of the original dataset allows to find those dimensions where data is least correlated (lowest covariance). Sorting them based on eigenvalues is the method which allows the sorting of dimensions.

Hence, multiplying the original dataset by the 'feature matrix' allows to discard those dimensions which are least significant.

What I don't understand is the relation between the covariance matrix and eigenvectors. Why is it that eigenvectors of the covariance matrix automatically allow us to find the directions where data is least correlated?

Hope this makes sense :)

# Answer
> 6 votes
Each eigenvector of the covariance corresponds to a new feature (which is a combination of the original features).

The principal eigenvector of the covariance matrix corresponds to the direction of *maximum* variance (not least as mentioned in the question). Subsequent eigenvectors can be computed one by one under the constraint that they are orthogonal to the ones already computed. The fact that they are orthogonal makes the new features *uncorrelated* with each other. In other words, a set of $k$ eigenvectors of the covariance corresponds to a set of $k$ new features that are uncorrelated with each other.

There are many different viewpoints on what exactly principal components are. In general, these seemingly different viewpoints have strong connections with each other. For example, the first $k$ eigenvectors (*i.e.*, the eigenvectors corresponding to the $k$ largest eigenvalues of the covariance matrix) capture the maximum cumulative variance of the data. At the same time they form a basis for a $k$-dimensional subspace (the space of new features) such that if you project your original data (each datapoint individually) on that subspace (*i.e.*, if you optimally approximate each datapoint using the new features), then the total euclidean distance between the original datapoints and their projections is the minimum possible; by minimum we mean in comparison to any other $k$-dimensional subspace.

This short article takes a look at what PCA is from a few different viewpoints.

---
Tags: machine-learning
---


title: Complexity bound on $RP^{RP}$

text:
# Question
Title: Complexity bound on $RP^{RP}$
This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in $RP$ allowed to consult an oracle in $RP$, prove the "lowest complexity bound" for a set recognized by this algorithm.

I don't think this is a very good question, it's not clear exactly what is meant by lowest complexity bound. I suppose this means any set in this class ($RP^{RP}$) must fall in which complexity class..that is, find the lowest such one and prove it.

Any ideas?

# Answer
> 1 votes
Hint: For BPP it is the case that $BPP^{BPP} = BPP$. The idea is that given a machine in $BPP^{BPP}$, we simulate each oracle call by a BPP computation, amplified so that the error probability is very small. Since there are only polynomially many oracle calls, overall the error coming from miscalculating the BPP oracle calls is small, and the resulting machine still has bounded error. (For a more complete proof, use your web search skills.) Try to emulate this line of reasoning for RP.

---
Tags: algorithms, complexity-theory, time-complexity, randomized-algorithms
---


# Question
Title: Something wrong with this definition of factorial with structural recursion?
In The Algebra of Programming page 5, the authors defined structural recursion `foldn (c, h)` over natural numbers:

```
f  0    = c
f (n+1) = h (f n)

```

They then went on to defin factorial as follows:

```
fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

```

This doesn't seem right, first of all, `foldn ((0, 1), f)` does not comply to its definition, secondly, this fold will never terminate, will it?

# Answer
> 4 votes
This definition is correct. The syntax is almost Haskell code, so you can run it in a Haskell interpreter:

```
foldn (c, h) = g where
  g 0 = c
  g n = h (g (n - 1))

fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

```

Usage in ghci:

```
Prelude> :load fact.hs
[1 of 1] Compiling Main             ( fact.hs, interpreted )
Ok, modules loaded: Main.
*Main> fact 0
1
*Main> fact 1
1
*Main> fact 2
2
*Main> fact 3
6
*Main> fact 4
24
*Main> fact 5
120

```

I don't know what you mean by “`foldn ((0, 1), f)` does not comply to its definition. If you mean that it's missing an argument, then this is not a problem. It's a function waiting to be applied. `foldn` is a curried function: it takes an argument and returns a function, which itself takes an argument and returns something; this makes `foldn` look like a function that takes two arguments (the first of which is a pair).

You can't evaluate `foldn ((0, 1), f)` any further (except to replace it by an anonymous function for which there is no source syntax) because its definition is by case on its argument: there's no way to know which one of `g 0 = …` or `g (n+1) = …` to use until you know whether the argument is 0.

Once you pass an argument, you can evaluate the call.

```
foldn ((0, 1), f) 0 = (0, 1)

```

so

```
fact 0 = (outr . foldn ((0, 1), f)) 0
       = outr (foldn ((0, 1), f) 0)
       = outr (0, 1)
       = 1

fact 1 = (outr . foldn ((0, 1), f)) 1
       = outr (foldn ((0, 1), f) 1)
       = outr (f (foldn ((0, 1), f) 0))
       = outr (f (0, 1))
       = outr (0 + 1, (0 + 1) * 1)
       = outr (1, 1)
       = 1

```

I'll let you work out other values by yourself.

The computation always terminates, regardless of the function `h` (assuming only that `h` terminates), by a simple induction argument: each nested call to `foldn` is applied to a smaller integer. For any nonnegative parameter, eventually the argument will be 0 which does not involve recursion.

---
Tags: recursion, functional-programming
---


# Question
Title: Problem with Understanding a Recursion Tree
Consider the recursion tree:

$T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$.

I determined that there are at most $1 + log\_{4}\ p$ levels, because the longest simple path from root to leaf is $p \rightarrow \frac{2p}{8} \rightarrow \frac{4p}{16} \rightarrow \frac{8p}{32} \rightarrow\ ...$.

This means that the time complexity is $O(p\ log\ p)$.

Now, I stopped all my leaves in the above recursion tree have $T(1)$, but say I have the condition $T(0) + O(1)$. Does this change my solution somehow?

# Answer
Think of it this way, you have a mathematically formal description of a recursive function. Which every function maps an element (or more than one element) To 1 element in the codomain.

What would T(0) be in terms of this functions as an input? It wouldn't change the time complexity.
> -1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?
I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max flow between vertices of the original graph can be identified with max flows between vertices of the new graph. It is ok for the new graph to have more vertices than the original graph. Said another way, consider a complete graph K-n with additional external edges in addition attached to source/sinks. Allow one of the edges of the complete graph to have negative capacity. Can I replace the complete graph with another graph with only positive capacities such that the max flow between all possible subsets of the external sources/sinks remains the same?

CLARIFICATION: We connect each vertex of the complete graph to a distinct external vertex with an edge. If it helps, picture a complete K\_6 drawn as a hexagon with an additional edge coming out of each vertex of the hexagon to 6 extra distinct vertices. Those distinct vertices are the s and t's that we are interested in considering. The edges that are not edges of the complete graph that we add are the external edges. I am interested only in cases where the original graph is the complete graph, though edges are allowed to have weight 0 or weight infinity. I hope this helps.

Thanks, Ning

# Answer
If you indeed have an edge $e$ with a *negative capacity*, and, I assume, it is a directed edge having no corresponding opposite edge, then you can reverse $e$, make its capacity positive, and, then, solve a regular max-flow problem with all capacities being non-negative. (Look at the concept of the residual network to understand what a negative capacity means.) Make sure you are not confusing edge capacities with costs.
> 1 votes

---
Tags: graphs, weighted-graphs
---


title: Why there is light source?

text:
# Question
Title: Why there is light source?
In ray tracing if we are tracing a ray from camera to the object, then why there is need for light source as in this image and also rays are going towards the light source instead of outgoing from the light source?

Recursive ray tracing associates an entire tree of rays with each image location.
*Image from: Physically Based Rendering: From Theory to Implementation* by Matt Pharr, Greg Humphreys, 2010

# Answer
There are two questions that you're asking here.

The first is why there is a light source. That's the easy part. Think what happens in the real world: if there's no light source, everything is dark and you can't see anything. That's an uninteresting case in computer graphics, so we usually don't consider it.

The second question is why rays are pointing to the light source instead of away from it. Physically, photons are emitted by light sources, and scatter around the physical environment, before hitting the imaging device (e.g. eye, camera).

It's possible to produce an image this way, like this for example:

Richard Keene produced this image in 1991. It was produced by tracing almost 30 billion photons from the light sources, which scattered around the scene until they hit the virtual camera lens. This took a month of compute time on 100 SPARCstations, each with 10MHz CPUs, and it's still quite noisy.

Keene repeated the experiment in 2004, this time using volunteers around the Internet donating computer time. I can't recall how long this one took, but 382 billion photons were traced in total:

The important thing here is that this technique is highly impractical. If you need to render an 85 minute movie at 24 frames per second, and allow a year of compute time, this turns out to be less than 5 minutes per frame. Clearly you can't spend 100 CPU-months on each image.

The problem is that if you trace photons from light sources, most photons don't hit the camera lens most of the time. If you continue scattering until they do hit the camera lens, they're usually so attenuated by that point that they contribute very little to the final image.

Ray tracing fixes this problem by tracing from the camera lens instead. Mathematically, a ray is the adjoint of a photon. This ensures that every trace contributes to the final image. However, you do then have the opposite problem. If you trace a photon from a light source, there's no guarantee that it will end up in the camera lens, but if you trace a ray from the camera, there's no guarantee that it will end up at a light source.

For this reason, most modern rendering algorithms (well, the ones that attempt to solve Kajiya's rendering equation) actually work in both directions. Photon mapping, bidirectional path tracing, and the Metropolis light transport algorithm (to pick but three) use information both from the camera and the light sources to try to spend most of the computer time on light paths which contribute to the final image.

If you're reading the book that I think you're reading, you'll get to all this in time.

**EDIT** Richard Keene himself chimed in, but unfortunately doesn't have enough rep yet to post comments on questions. So here's the link to his Photon Soup paper.

Richard, welcome to cs.se!
> 15 votes

---
Tags: graphics
---


# Question
Title: Is the following statement about turing machines true?
Here's the statement:

> Take a set of finite inputs from some alphabet. If for any two turing machines:
>
> 1. All inputs in the set produce the same output for both machines
> 2. In both machines, the following is true: every state transition (i.e. every row in the state table) occurs at least once for at least one of the inputs in the set before halting
>
> Then both machines will produce the same output as each other for *any* input.

This is an informal statement, it probably needs a bit of refining. But for now the question is, is this true?

# Answer
> 3 votes
This is an interesting statement, but it is not true. I'll give a proof sketch and leave the construction of the actual machines to you (*read as: I am too lazy :)* ). For example, take two functions

$f : \mathbb{N} \setminus \\{0\\} \to \mathbb{N}, n \mapsto n^2$

$g : \mathbb{N}\setminus \\{0\\} \to \mathbb{N}, n \mapsto 2^n$

and two turing machines $M\_f, M\_g$ which compute $f$ and $g$, respectively. Without loss of generality, we may exclude $0$ because I think it might require special handling in $M\_g$, but this depends on the actual construction of the turing machine - it does not matter this way.

It is safe to assume that minimal turing machines for $f$ and $g$ would need each of its transitions for any value bigger than $1$ since they both have to implement some kind of looping scheme. This comes from the fact that $f$ and $g$ can be defined primitive-recursively, where $0$ and/or $1$ are the recursion base cases (depending on your exact definition). Now if we look at the values of these two functions:

$\begin{align} n&:& &1,& &2,& &3,& &4,& &5,& ... \\ f(n)&:& &1,& &\color{green}{4},& &9,& &\color{green}{16},& &25,& ... \\ g(n)&:& &2,& &\color{green}{4},& &8,& &\color{green}{16},& &32,& ... \\ \end{align}$

We see that for an input set $I = \\{ 2, 4 \\}$, then $M\_f$ and $M\_g$ compute the same value for all input values, and since $\forall n \in I : n \> 1$, they would also need all of their transitions. Still for any input value $n \geq 1, n \notin I$, they would differ.

To generalize: Take any two sequences of numbers which are recursively defined and computable and also equal in at least two places, then the statement does not hold.

---

I overcame my laziness and did one turing machine for the calculation of $2^n$ in unary. The code can be executed on this turing machine simulator to check that for inputs $11$ and $1111$, every state transition is required.

```
; Compute 2^n in unary
; First go to the end of the input string and write a single 1.
; The tape content is then <input>01
 0 1 1 r 0 ; Move right until we are at the end of the input string.
0 _ 0 r 1 ; Write 0 separator
1 _ 1 l 2 ; Write an initial 1, since this is the value of 2^0.

; Then rewind to the beginning
2 1 1 l 2 ; Keep moving left without altering 1s
2 0 0 l 2 ; Keep moving left without altering 0s
2 _ _ r 3 ; We move back to the start.

; Now we double the string after the separating zero until
; there are no more 1s in the beginning (= decrement counter until 0)
3 1 _ r 4 ; Remove the first 1, this is equal to decrementing the counter
3 0 _ r halt ; if there are no more 1s, we are finished.
4 1 1 r 4
4 0 0 r 5 ; Move right till the separator is found
5 1 1 r 5 ; Move to the end of the result string
5 _ _ l 6
6 1 _ r 7 ; And replace the last 1 with a blank, the initial position marker.
7 _ 1 l 8

; Now comes the actual doubling
8 1 1 l 8 ; Move left until the blank marker is found
8 _ 1 l 9 ; Move left until the blank marker is found
9 1 _ r 10 ; Shift the blank marker to the left
10 1 1 r 10 ; Move to the end of the string...
10 _ 1 l 8 ; ... and write a 1.
9 0 0 l 11 ; Once we hit 0, we are finished doubling

; And again rewind to the beginning
11 1 1 l 11 ; Keep moving left without altering 1s
11 _ _ r 3 ; We move back to the start.

```

The computation of $n^2$ is similar, except that for doubling the output $n$ times, you add $n$ to $n$ exactly $n$ times.

---
Tags: turing-machines
---


title: Collecting data(images) using a crawler

text:
# Question
Title: Collecting data(images) using a crawler
Please let me know, if this goes here, if not, please point out where I should post this. Thanks in advance.

So I require huge number of training data, mostly images. This is a pet project, only for learning. So how and where do I collect them, free of cost?

Will it be suitable if I use a crawler and pull out images, tagged with, say for example: "Cat". Or is there another way to do this.

Thanks in advance.

# Answer
Do you need a license? What kind of images do you need? Images of animals?

If you want to start small, you can try images of hand-written digits: http://yann.lecun.com/exdb/mnist/

If that is not what your looking for, you have different options depending on your system. For Linux I myself use wget. It works like a charm and is fairly easy to use.

Like so: https://stackoverflow.com/questions/4602153/how-do-i-use-wget-to-download-all-images-into-a-single-folder

It takes only a few hours to learn how to make a shell script, to download in bulk.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Turing Machine That Accepts Machines With Undecidable Languages
So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) is undecidable }. (in words, a Turing machine that accepts encodings of machines that accept undecidable languages.)

I'm trying to reduce the accepting Turing machine (A TM) to Undecidable TM in the following manner:

1. Take Turing machine M and string x as inputs.
2. Create M' that works as follows: For input y, M' simulates M on x. If M accepts x, then M' acts on y as some Turing machine that accepts an undecidable language. Else, M rejects y.
3. Pass M' to Undecidable TM. Iff Undecidable TM accepts M', then M must accept x, else M' does not accept an undecidable language. Thus, we can decide whether a machine M accepts input x.

The problem is that I cannot create a machine that accepts an undecidable language to put inside M' for this reduction. I have read my lecture notes and looked for advice on Google, but haven't made any headway. I'd appreciate it if someone has some insight on how to finish this proof or approach this another way. Thanks a lot.

# Answer
> 4 votes
The language you are describing is called an "index-set", which means that it is accepting languages, rather than machines specifically. More formally, if we have two machines $M\_1, M\_2$, and $L(M\_1) = L(M\_2)$, then $M\_1 \in Undecidable \iff M\_2 \in Undecidable$.

There's a theorem called Rice's Theorem that says that index sets are always undecidable. The proof on the Wikipedia page shows how you can reduce the halting problem to any index set.

# Answer
> 1 votes
A machine that accepts an undecidable language is the *universal Turing machine*. It accepts $A\_\text{TM}:=\\{ \langle M,w\rangle \mid \text{TM $M$ accepts $w$}\\}$ but this language is undecidable.

If you run into this trouble again, try to argue about the complement. If the complement is undecidable, then your language is also undecidable. You approach would then ask for a TM that accepts a decidable language as a submodule.

# Answer
> 0 votes
You must clarify the `undecidable language` term, Undecidable means not decidable, so Turing Recognizable (recursively enumerable) languages are undecidable and languages that are not Turing Recognizable are undecidable too.

---
Tags: computability, turing-machines, reductions, logic, undecidability
---


# Question
Title: How to find a subset of potentially maximal vectors (of numbers) in a set of vectors
I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats).

I say a vector u "covers" a vector v if, in every dimension 1..d, u\[i\] \>= v\[i\]. So for d=3, (3,3,2) covers (2, 3, 1), but (3, 3, 1) doesn't cover (2, 2, 2).

I am interested in finding a subset T of S, such that for every v in T, there is no u in S with u != v, such that u covers v. Alternatively, I'm interested in removing from S those vectors that are covered by other vectors in S.

What is an efficient algorithm for this? Barring that, what is at least the "real name" of this problem to help me search for it?

An O(n^2) algorithm is obvious: for every vector in S, check it against every other vector in S, and add it to T if nothing covers it. I'm having trouble doing much better than that.

I have considered trying to use kd-trees and range trees, but this is for a real world problem, and in practice d is too high and the number of vectors too low, so that e.g. the O(n * log^d(n)) running time is actually worse than the naive O(n^2). (d is approximately 20-40, and the number of vectors is in the millions).

**Edit - Particular Problem Details**

As requested, more information about the specific problem I am trying to solve.

The implementation problem at hand involves several sets of vectors, approximately 60-100 sets, each with about 10-20 vectors in them. For every set s, for every vector v in s, v has dimension d, and all axes of v are zero save for one which is positive. A result vector is formed by choosing precisely one vector from each set and adding them together, and a given result vector is strictly worse if it is covered (or apparently the real word is 'dominated') by another result vector. You can assume the non-zero axis of a base vector varies uniformly in \[.9, 1.1\]. In practice most intermediate results appear to be dominated, and size(T) \<\< size(S)

# Answer
You're looking for a set of Pareto-optimal alternatives. If you're looking for all such possibilities (i.e., looking to make $T$ as large as possible), you're looking for the Pareto-optimal front. You asked for keywords or names to search for this -- those are standard terms for this concept. See https://en.wikipedia.org/wiki/Multi-objective\_optimization.

For specific situations, if the data is structured, it may be possible to take into account knowledge of the structure of the data to find a better algorithm -- but this will depend on the nature of the data.

---

In your specific case, there are algorithmic techniques that might lead to significant improvements in running time. In particular, in your setting, each vector $v \in S$ is obtained as a sum of some component vectors $v = \sum\_i v\_i$, where we have a collection of sets $S\_1,S\_2,\dots,S\_k$ and each $v\_i$ is chosen from some set $S\_i$.

Let me establish some notation and definitions, prove some mathematical results, and then show them how to compute the Pareto-optimal front for your specific situation.

**Definition.** We say that $u$ dominates $v$ if $u\[j\] \ge v\[j\]$ for all dimensions $j$. (This is the same as what you call "covers", but "dominates" is the more standard term.)

**Definition 1.** If $S,T$ are sets, then $S+T$ is defined to be the set $S+T=\\{s+t : s \in S, t \in T\\}$.

**Definition 2.** If $S$ is a set of vectors, define $P(S)$ to be the Pareto-optimal front of $S$, i.e., the set of vectors $s \in S$ such that there does not exist any vector $t \in T$ that dominates $s$.

Your problem is the following: given sets $S\_1,\dots,S\_k$ of vectors, find the Pareto-optimal front of $S\_1+\dots + S\_k$, i.e., compute $P(S\_1 + \dots + S\_k)$. I'll show an algorithm to compute this.

The following lemmas will be helpful:

**Lemma 1.** If $u$ dominates $v$, then $u+w$ dominates $v+w$.

**Lemma 2.** If $u\_i$ dominates $v\_i$ for each $i$, then $\sum\_i u\_i$ dominates $\sum\_i v\_i$.

**Lemma 3.** $P(S+T) = P(P(S)+P(T))$.

(Lemmas 2 and 3 follow immediately from Lemma 1.)

We'll now use Lemma 3 repeatedly to compute $P(S\_1 + \dots + S\_k)$. We build a binary tree over the $k$ leaves $S\_1,\dots,S\_k$. At each node, we compute the Pareto-optimal front of the sum of the two sets corresponding to its two children.

In other words, here's how we compute the Pareto-optimal front for several values of $k$:

$$P(S\_1+S\_2) = P(P(S\_1)+P(S\_2)).$$

$$P(S\_1+S\_2+S\_3+S\_4) = P(P(P(S\_1)+P(S\_2)) + P(P(S\_3)+P(S\_4))).$$

(In other words, to compute $P(S\_1+S\_2+S\_3+S\_4)$, we first compute $U\_1 = P(S\_1+S\_2)$ efficiently using Lemma 3 and $U\_2 = P(S\_3 + S\_4)$ using Lemma 3, then we compute $P(U\_1+U\_2)$ and use Lemma 3 to conclude that this is equal to $P(S\_1+S\_2+S\_3+S\_4)$.)

You can see how this works recursively. To compute $P(S\_1+\dots + S\_k)$, we divide the sets in half, recursively compute $X=P(S\_1+\dots + S\_{k/2})$ and $Y=P(S\_{k/2+1} + \dots + S\_k)$ using the efficient algorithm, and then compute $P(X+Y)$.

At each stage of the binary tree, we are filtering out all dominated vectors. If you're lucky, this greatly reduces the number of possibilities that remain at each level of the binary tree.

I suggest you try this on your specific application. If, as you say, the final size of $P(S\_1+\dots + S\_k)$ is not too large (say $m$), then this should be efficient: the size at each internal node of the tree will be no larger than $m$, so the time to merge the two children of any node will be $O(m^3)$ \[using the trivial quadratic algorithm mentioned in the question\], and the total running time will be at most $O(m^3 k)$. In practice, the actual running time might be significantly faster than that.

---

You could also explore different algorithms for computing $P(\cdot)$, the Pareto-optimal front of a set. There are basically two standard algorithms: the "simple cull" algorithm \[which is the same as the quadratic-time algorithm you mentioned in the question\], and a recursive divide-and-conquer algorithm.

The simple cull algorithm has $O(n^2)$ worst-case running time, as you say. Actually, if we know that the Pareto-optimal front has size $m$, the running time is a bit better: the running time is $O(mn)$. (In other words, if we let $n=|S|$ and $m=|P(S)|$, then you can compute $P(S)$ from $S$ in $O(nm)$ time.) The divide-and-conquer algorithm has $O(n (\log n)^{d-1})$ worst-case running time, which as you say in the question will likely be too small for your parameters.

However, it is also possible to combine the two techniques, where you use the recursive divide-and-conquer algorithm but once the problem size becomes small enough you switch to the simple cull algorithm. Whether this will lead to any improvement in your actual setting can probably only be determined through experimentation.

For an overview of these algorithms, see for example Section of the following paper:

A Calculator for Pareto Points. Marc Geilen and Twan Basten. Design, Automation & Test in Europe Conference & Exhibition 2007 (DATE'07), IEEE.

To compute $P(P(S)+P(T))$, the best algorithm I know is to compute $S'=P(S)$ and $T'=P(T)$ using one of the above methods, then compute $S'+T'$ using the obvious quadratic-time algorithm (combine all pairs), then compute $P(S'+T')$ using one of the above methods.
> 2 votes

---
Tags: algorithms, computational-geometry, discrete-mathematics
---


# Question
Title: Classification when some classes are dependent
I think my problem can easier be explained via an example: Assume we have a dataset containing the images of 10 different mammals, let's say lion, elephant, cat, ... and horse. We have a 20-class image classification task where we want to detect whether an image belongs to lion-male or lion-female or cat-male or cat-female or ... horse-male or horse-female. As you see, the classes can be simply clustered into 10 mammal classes, i.e., (some) classes are highly dependent.

This example is a kind of made up. Two strategies, imaginable to solve this problem is either we ignore this dependency and treat it as a 20-class classification task or use a hierarchical structure to first classify them into 10 class of mammals and then into male or female. The later however, ignores the fact that there might be (and in fact is) some shared properties in all males or in all females that can be used to discriminate them.

I was wondering if there is a methodological way to address this type of classification tasks. I'm looking for a keyword to google it. Thanks

# Answer
> 1 votes
I'm afraid there is no exact answer to your question. In the scenario you described above male and female mammals are very similar, similar enough that the average person wouldn't notice the difference. In such a case, I would suggest going with the first option of classifying into 10 classes of mammals and then building 10 classifiers of male-female.

This of course isn't an answer that applies to all cases, it is strongly dependent on a few factors, mainly on the classification scenario at hand. The size of the dataset is also a significant parameter. Unfortunately I don't think there is a methodological way to address this issue, only experience can point you towards the best solution.

---
Tags: machine-learning, classification
---


# Question
Title: Using Huffman Encoding to improve Lempel-Ziv Encoding
Can anyone think of a way to use Huffman Encoding to improve the compression rate of Lempel-Ziv Encoding?

My initial idea was to encode with higher probabilities given to shorter strings (i.e. the string "e" would have a higher probability than the string "ef").

Does anyone know of a good way?

# Answer
> 2 votes
Huffman encoding is already used this way.

Huffman encoding is already used together with LZ77 to improve its compression rate. The most widely used instance of LZ77-style compression is DEFLATE. DEFLATE combines LZ77 with Huffman encoding. See https://en.wikipedia.org/wiki/LZ77\_and\_LZ78#Implementations and https://en.wikipedia.org/wiki/DEFLATE.

Huffman encoding is commonly used together with standard LZW (Lempel-Ziv-Welch) encoders to improve their compression rate. See the Wikipedia article on LZW and other standard resources on LZW coding for details: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

---
Tags: data-compression, encoding-scheme
---


# Question
Title: Assistance with Notation in the Paper Entitled: "Search Through Systematic Set Enumeration"
So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free. I'm having a problem with the notation in the following definition presented bellow:

> The *Set-Enumeration* (SE)-tree is a vehicle for representing and/or enumerating sets in a best-first fashion. The *complete* SE-tree systematically enumerates elements of a power-set using a pre-imposed order on the underlying set of elements. In problems where the search space is a subset of that power-set that is (or can be) closed under set-inclusion, the SE-tree induces a complete irredundant search technique. Let *E* be the underlying set of elements. We first index *E*'s elements using a one-to-one function ind: E -\> $ \mathbb{N} $. Then, given any subset *S* $\subseteq$ *E*, we define its SE-tree view:
>
> **Definition 2.1** A Node's View
>
> $View(ind,S) \stackrel{def}{=} \\{e \in E | ind(e) \gt max\_{e' \in S} ind(e')\\}$

In the paper there is an example of a tree made with what appears to be E={1,2,3,4}. I have some familiarity with set-builder notation, but much of the other parts of the "node's view" is confusing me. I skimmed ahead to see if there were clarifications, but I didn't manage to find them so either: a) the author is assuming a competency I do not have, b) the explanation is there and I couldn't find it, or c) the author is doing a horrible job as an author.

So with the hope that it is one of the first two:

* I'm assuming that the prime in e' is for the complement of the set e, so if e = {1}, then e' = {2,3,4}. Is this correct?
* What is this ind function? What would ind({3,4}) be for example?
* $max\_{e' \in S}$? Is this the maximum height of the sub tree of the complement of e?

Any assistance on this would be most appreciated.

# Answer
> 1 votes
No, the prime is not complement, $e'$ is just a different variable than $e$.

In words, $\text{View}(\text{ind},S)$ is the set of all edges whose index is higher than the indices of edges in $S$. The function $\text{ind}: E \to \mathbb{N}$ gives a number to each edge, and $\max\_{e' \in S}\text{ind}(e')$ is simply the highest index of $S$.

Then $\text{View}(\text{ind},S)$ is the set of all edges whose index is higher than $\max\_{e' \in S}\text{ind}(e')$.

# Answer
> 1 votes
Please, one question per question.

The answer to your first question: No, prime most likely does not indicate complement, absent some specific indication of that. It is just another variable. $e$ is one variable; $e'$ is another variable (the author could have used a different letter, like $f$ or $x$ or something, but chose to use $e'$ instead).

The answer to your second question: The ind function is defined in the text immediately preceding the definition. Read it again?

Yes, it's possible you might lack the necessary mathematical background. You might try taking an online course (or working through a textbook) on discrete mathematics for computer science.

---
Tags: trees, sets, enumeration
---


title: Complexity of self-reducible set

text:
# Question
Title: Complexity of self-reducible set
I am trying to solve the following problem:

> A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\right| \< \left|x\right|$, $\left|r(x)\right| \< |x|$, and $l$ and $r$ are both deterministic polynomial time computable functions. What is the maximum possible complexity of a self-reducible set (you can choose $l$ and $r$)? For your complexity estimate, prove upper and lower bounds.

Now, I think $S \in P$, because to decide if $x \in S$, we can simply iterate $l$ and $r$ until they both get to $1$ or not, and since the length must decrease each time, the time taken will be polynomial in the length of $x$. Is this correct?

Also, what could the problem mean by a lower bound? By defining $l$ and $r$ to be $1$, we get $\Sigma^\*$, the set of all strings, which is regular...

# Answer
> 3 votes
Suppose for simplicity that $|l(x)| = |r(x)| = |x|-1$. If $L(n),R(n)$ are the time complexities for computing $l,r$ on inputs of length $n$, then the time complexity for computing membership in $S$ satisfies the recurrence $$ T(n) \geq L(n) + R(n) + 2T(n-1). $$ Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.

If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c \< 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).

So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.

---
Tags: complexity-theory, formal-languages, computability, time-complexity
---


# Question
Title: How many thresholds and distance matrix are in Eigenface?
I edited my question trying to make it as short and precise.

I am developing a prototype of a facial recognition system for my Graduation Project. I use Eigenface and my main source is the document Turk and Pentland. It is available here: http://www.face-rec.org/algorithms/PCA/jcn.pdf.

My doubts focus on step 4 and 5.

I can not correctly interpret the number of thresholds: If two types of thresholds, or only one (Notice that the text speaks of two types but uses the same symbol). And again, my question is whether this (or these) threshold(s) is unique and global for all person or if each person has their own default.

I understand the steps to be calculated until an matrix O() of classes with weights or weighted. So this matrix O() is of dimension M'x P. Since M' equal to the amount of eigenfaces chosen and P the number of people.

What follows and confuses me. He speaks of two distances: the distance of a class against another, and also from a distance of one face to another. I call it D1 and D2 respectively. NOTE: In the training set there are M images in total, with F = M / P the number of images per person.

I understand that threshold(s) should be chosen empirically. But there must be a way to approximate. I was initially designing a matrix of distances D1() of dimension PxP. Where the row vector D(i) has the distances from the vector average class O(i) to each O(j), j = 1..P. Ie a "all vs all."

Until I came here, and what follows depends on whether I should actually choose a single global threshold for all. Or if I should be chosen for each individual value. Also not if they are 2 types: one for distance classes, and one for distance faces.

I have a theory as could proceed but not so supported by the concepts of Turk:

Stage Pre-Test:

Gender two matrices of distances D1 and D2: In D1 would be stored distances between classes, and in D2 distances between faces. This basis of the matrices W and A respectively.

Then, as indeed in the training set are P people, taking the F vectors columns D1 for each person and estimate a threshold T1 was in range \[Min, Max\]. Thus I will have a T1(i), i = 1..P

Separately have a T2 based on the range \[Min, Max\] out of all the matrix D2. This define is a face or not.

Step Test:

Buid a test set of image with a 1 image for each known person Itest = {Itest(1) ... Itest(P)}

For every image Itest(i) test:

```
Calculate the space face Atest = Itest - Imean

Calculate the weight vector Otest = UT * Atest

Calculating distances:

```

dist1(j) = distance(Otest, O (j)), j = 1..P

Af = project(Otest, U)

dist2 = distance(Atest, Af)

```
Evaluate recognition:

```

MinDist = Min(dist1)

For each j = 1..P

If dist2 \> T2 then "not is face" else:

If MinDist \<= T1(j) then "Subject identified as j" else "subject unidentified"

Then I take account of TFA and TFR and repeat the test process with different threshold values until I find the best approach gives to each person.

Already defined thresholds can put the system into operation unknown images. The algorithm is similar to the test.

I know I get out of "script" of the official documentation but at least this reasoning is the most logical place my head. I wondered if I could give guidance.

EDIT:

i No more to say that has not already been said and that may help clarify things.

Could anyone tell me if I'm okay tackled with my "theory"? I'm moving into my project, and if this is not the right way would appreciate some guidance and does not work and you wrong.

# Answer
> 2 votes
I'll begin with an apology since I will probably not answer your question as you expect (mostly because I don't understand exactly what you are asking).

Let's recap the process of face recognition using Eigenfaces.

1. take each image of $d\_1$ by $d\_2$ and treat it as a $d\_1\cdot d\_2$ vector (images should be in greyscale).
2. compute the mean of the vectors in hand, i.e. if you have m images, $X\_{mean}=\frac{1}{m}\sum\_{i=1}^mX\_i$ and move your samples such that the a-prior mean is is zero, (this is an important step that is commonly forgotten).
3. compute the covariance matrix, $X^TX$. I assume in your scenario $d\_1\cdot d\_2\>\>m$, so you obtain the same information by finding $XX^T$ eigenvalues, this could improve your running time significantly.
4. project the $m$ images over the $p$ eigenvectors corresponding to the largest eigenvalues.
5. Given a new image, project it using the matrix $\[u\_1,...,u\_p\]$ and run K-Nearest-Neighbour (it should be more than sufficient for your purpose).

I think your original question is regarding the classification process after you have projected the images over the principal components. I the algorithm above, I suggest using KNN.

A few notes:

1. Eigenfaces don't work so well in reality, you must use images with very similar orientation, otherwise you won't achieve good results.
2. How to choose the k in the nearest neighbour algorithm? it depends on the number of training examples you have, obviously, there is no point of choosing k to be larger then the number of examples per person.
3. regarding point 3 above, $X^TX\in M\_{(d\_1\cdot d\_2)\ x\ (d\_1\cdot d\_2)}, XX^T\in M\_{mxm}$, so if your images are over 100 by 100, it's practically a must.
4. a couple of useful links:

Good Luck!

Addition:

* http://en.wikipedia.org/wiki/K-nearest\_neighbors\_algorithm
* After obtaining the first p Eigenfaces (which are the first p eigenvectors of $X^TX$), you have a matrix $O\in M\_{(d\_1\cdot d\_2)\cdot p}$, given a new image $x\in \mathbb{R}^{d\_1\cdot d\_2}$, project $O^Tx$, this is a vector in $\mathbb{R}^p$.
* Now you have your samples in $\mathbb{R}^p$, your original training samples, and a new image that was projected over $O$, you know want to ask yourself how to classify the new image, one way is to decide by finding the closest vector using $L\_2$ or $L\_1$ this is the same as using KNN with k=1.
* I suggest you read about KNN from the link above.

**to sum it up:**

* compute the projection matrix $O$
* project your training data $z\_i=O^Tx\_i$.
* given a new sample, $\overline{x}$, compute $\overline{z}=O^T\cdot\overline{x}$
* now you have vectors in $\mathbb{R}^p$, you run the KNN which is an iterative way to find the k closest vectors, and classify your new vector as the majority of the k vectors.

---
Tags: algorithms, facial-recognition
---


# Question
Title: How to solve this recurrence using recursion tree method
How to solve this using the recursive tree method? I'm stuck with the $\max$.

$$T(n) = T\left(\left\lceil \frac{n}{\max\\,\\{\sqrt{n},2\\}}\right\rceil\right) + n\\,.$$

# Answer
Break it up into parts you can handle.

$\max\\,\\{\sqrt{n},2\\} = \sqrt{n}$ if, and only if, $n\>3$, so rewrite the recurrence as

$$\begin{align\*} T(n) &= T(\lceil\sqrt{n}\\,\rceil) + n && \text{for } n\>3\\ T(n) &= T(\lceil n/2\rceil) + n &&\text{for } n\leq 3\\,. \end{align\*}$$

At that point, I think it's reasonable to solve the $n\leq 3$ part by direct substitution and then use required method for the $n\>3$ case.

By the way, you also need a case for $T(1)$, since the general equation gives $T(1) = T(\lceil\tfrac12\rceil)+1 = T(1)+1$, which is impossible.
> 5 votes

---
Tags: recurrence-relation
---


# Question
Title: Particular function communication complexity computation
Consider a boolean function $f:\\{0,1\\}^n\rightarrow\\{0,1\\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then communication complexity of function is $\Omega(n)$. This is claim $4.23$ in Jukna's book. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with atleast $r$ number of $n$ of $0/1$ vectors $x$ each of Hamming weight $1$, then is communication complexity of function $\Omega(r)$? Could this possibly have truth?

# Answer
There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x\_1,\ldots,x\_r) = f(x\_1,\ldots,x\_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works for $g$, so we get a lower bound of $\Omega(r)$ for $f$.
> 1 votes

---
Tags: complexity-theory, lower-bounds, communication-complexity
---


title: Residence time in multi server system

text:
# Question
Title: Residence time in multi server system
I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is:

```
R = S + QS

```
* S is service time
* Q is number of customers ahead
* R is residence time

Then he describes a case with a single queue and two servers and says that the equation becomes

```
R = S + 1/2 SpQ

```
* p is per-server utilization 0 \< p \< 1.

I don't understand why p is a factor here. Wouldn't all servers be busy whenever there are customers waiting in line? Why is this different from the single-server case? The explanation given in the book is copied on slide 25 here. I don't understand the reasoning. Why do we need `p`?

# Answer
$Q$ represents the average of a discrete random variable. Sometimes there are no customers waiting in line, sometimes there's one, and sometimes there are many. So there is some probability distribution for $Q$. The difference between a two-server queue and a single-server queue that's twice as fast, is the expected service time when the queue is empty except for the one customer receiving service. That's the transition from state 1 to state 0 in the Markov chain:

Intuitively, when a customer reaches the head of the queue the service in the two-server system will take twice as long as with the single server that's twice as fast. The expected service time with the two-servers is $S$, while the expected service time with the single fast server is $S/2$. What's less intuitive is that customers will, on average, spend somewhat less time waiting to get to the head of the queue with the two-server system.

To see this, consider the case of a customer that arrives when there is one customer currently being serviced. In the two-server case the arriving customer immediately gets the other server. The total expected response time in this case is $S$, but that's all service time, no waiting time. In the fast single-server case the arriving customer waits, on average $S/2$ time for the preceding customer to finish and then gets, on average, $S/2$ amount of service. The total expected response time in this case is also $S$, but it's half service time and half waiting time. Let's work out the exact difference:

## Fast Single-Server

This is an M/M/1 queue with arrival rate $X$ and completion rate $S/2$. The steady state distribution, $\pi\_i$ for the Markov chain in the fast single-server case is $$\pi\_i = (1-U)U^i$$ where $U$, the server utilization, is $XS/2$.

Then the expected number of customers in the queue is $$ Q\_f = \sum\_{i=0}^\infty \pi\_i i = \sum\_{i=0}^\infty (1-U)U^i i = (1-U)U\sum\_{i=0}^\infty U^{i-1} i = \frac{(1-U)U}{(1-U)^2} = \frac{U}{1-U}.$$

Then by Little's law $$ R\_f = \frac{Q\_f}{X} = \frac{U}{X(1-U)} = \frac{XS/2}{X(1-U)} = \frac{S/2}{1-U}, $$ but we want to represent $R$ as service time + waiting time, so $$ R\_f = \frac{S}{2} - \frac{S}{2} + \frac{S/2}{1-U} = \frac{S}{2} + \frac{-S/2 + SU/2 + S/2}{1-U} = \frac{S}{2} + \frac{US/2}{1-U} = \frac{S}{2} + \frac{S}{2}Q\_f. $$

So we have that the waiting time is $$ W\_f = \frac{S}{2}Q\_f = \frac{SU}{2(1-U)}.$$

## Two Slow Servers

This is an M/M/2 queue. We will again let $U = S X/2$ (this is Little's law for the utilization of each of the two servers, the reason the result is the same as in the fast-server case is that now $X$ is halved rather than $S$ being halved.) The steady state distribution is: $$ \pi\_0 = \frac{1-U}{1+U} $$ and $$ \pi\_i = 2 U^i \pi\_0, \\;\\;\\; i \geq 1.$$

Now $$ Q\_s = \sum\_{i=0}^\infty \pi\_i i = \frac{2U}{1-U^2}.$$ (Derivation left as an exercise.)

Then by Little's law we get $$ R\_s = \frac{Q\_s}{X} = \frac{S}{1-U^2} = \frac{2}{1+U}R\_f, $$ which we want to represent as service time ($S$) plus waiting time.

$$ R\_s = S - S + \frac{S}{1-U^2} = S + \frac{SU^2}{1-U^2} = S + \frac{S}{2} U Q\_s, $$ and the waiting time is $$ W\_s = \frac{S}{2} U Q\_s = \frac{SU^2}{1-U^2} = \frac{2U}{1+U} W\_f.$$

## Summary

The two slow servers always have a service time twice that of the fast server. The two slower servers have a total response time that is $2/(1+U)$ times the fast servers' total response time. ($0\leq U\<1$, so the response time is always worse.) But the two slow servers have a waiting time that is $2U/(1+U)$ times the fast server's waiting time, and so there's *less* waiting time with two slow servers.
> 1 votes

---
Tags: algorithm-analysis, distributed-systems, queueing-theory
---


# Question
Title: identities property of squaring functor?
From page 31 of The algebra of programming :

> Next, consider the squaring functor $()^2: Fun \leftarrow Fun$ defined by
>
> $$ A^2 = \\{(a, b) | a \in A, b \in B\\} \\ f^2(a, b) = (f a, f b) $$

Functors are required to preserve identities and composition:

$$ F(id\_A) = id\_{FA} \\ F(f \circ g) = Ff \circ Fg $$

The second property is easy:

$$ (f \circ g)^2 (a, b) = ((f\circ g) (a), (f\circ g) b) \\ (f^2 \circ g^2) (a, b) = f^2 (g (a), g (b)) = ((f\circ g) (a), (f\circ g) (b)) $$

But I can't figure out how the squaring functor preserve the identity property. Could anyone help?

# Answer
> 2 votes
Ok, I have worked it out:

$$ id^2 (a, b) = (id(a), id(b)) = (a, b) = id\_{A^2} (a, b) $$

---
Tags: category-theory
---


title: Definition of opposite category

text:
# Question
Title: Definition of opposite category
From page 29 of The algebra of programming :

> For any category C the opposite category $C^{op}$ is defined to have the same objects and arrows as C, but the source and target operators are interchanged and composition is defined by swapping arguments:
>
> $$ f \cdot g \text{ in } C^{op} = g \cdot f \text{ in } C. $$

This doesn't makes sense. Suppose C is the categories of all functions, and we have $f: A \leftarrow B$ and $g: B \leftarrow C$, then $g \cdot f$ doesn't even exist. Or, suppose $f: A \leftarrow B$ and $g: B \leftarrow A$, then $f \cdot g : A \leftarrow A$, and $g \cdot f : B \leftarrow B$, this is not interchanging source and target, this is changing both!

# Answer
> 4 votes
The problem in your first example is that the arrows don't compose. In the first, you have $f: A \leftarrow B$ and $g: C \leftarrow B$, so $f\circ g$ is not in $C$, hence in $C^{op}$ $f : B \leftarrow A$ and $g : B \leftarrow C$, and they still don't compose.

If you had $f: A \leftarrow B$ and $g: B \leftarrow C$, then they compose to $f\circ g =h : A \leftarrow C$ in $C$. In $C^{op}$ you have $f : B \leftarrow A$ and $g : C \leftarrow B$ and get $g\circ f = h : C \leftarrow A$ (remember in $C^{op}$ you want every thing running backwards) .

Your second example is fine, you just have $f : A \leftarrow B$ and $g : B \leftarrow A$ in $C$ and hence $f\circ g : A\leftarrow A$ and $g\circ f:B\leftarrow B$ in $C$. In $C^{op}$, they switch: $f :B \leftarrow A$, $g : A \leftarrow B$ are in $C^{op}$ and so are $g \circ f : A \leftarrow A$ and $f\circ g : B\leftarrow B$.

I wonder perhaps if the phrasing used by Bird is causing a problem. The rule is better stated:

> If $h = g \circ f$ in $C$ , then $h = f \circ g$ in $C^{op}$.

There's also a kind of name overloading going on here, from a programmer's perspective, reusing the same names for the opposite versions is a bit odd, it might make more sense to think along the lines (restating one of the rules):

> If $f : X \leftarrow Y$ is in $C$, then $f^{op} : Y \leftarrow X$ is in $C^{op}$.

---
Tags: functional-programming, category-theory
---


title: Quantum lambda calculus

text:
# Question
Title: Quantum lambda calculus
Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to think about different types of problems, and different fields use different formulation for this reason.

When I work with quantum computing, however, I only ever think about the circuit model. Originally, QC was defined in terms of quantum Turing machines but as far as I understand, this definition (although equivalent to quantum circuits if both are formulated carefully) has not been nearly as fruitful. The 3rd formulation (in terms of lambda-calculus or similar functional settings) I am completely unfamiliar with. Hence my questions:

* **What are useful definitions of quantum lambda-calculus (or other functional paradigms)?**
* **What subfields of QIP gain deeper insight from using this formulation instead of the circuit model?**

---

### Notes

I am aware that I am ignoring many other popular formalisms like cellular automata, RAM-models, etc. I exclude these mostly because I don't have experience with thinking in terms of these models classically, let alone quantumly.

I am also aware that there are popular alternatives in the quantum setting, such as measurement-based, topological, and adiabatic. I do not discuss them because I am not familiar with the classical counterparts.

# Answer
> 17 votes
here is a half-baked answer: I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular:

Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi.

I am saying it's a half-baked answer, because I haven't had chance to read any of his works.

# Answer
> 13 votes
Apologies in advance for the shameless plug, but there is a paper of mine on a quantum lambda calculus that you may find interesting. It is called *The Dagger Lambda Calculus* and provides a higher-order representation for the diagrammatic circuits that the categorical school of quantum computation have introduced:

http://arxiv.org/abs/1406.1633

You can also check my talk on YouTube for more info:

https://www.youtube.com/watch?v=2pDPVd1BukI

Other works in the area include the Selinger-Valiron quantum lambda calculi, and the lambda calculus by Andre van Tonder: \[Sel04a\], \[Sel04b\], \[vTD03\], \[vT04\], \[SV04\], \[SV08\], \[SV10\].

---
Tags: lambda-calculus, quantum-computing, reference-request, computation-models
---