Delaunay tesselations and convex hulls According to Wikipedia the Delaunay tesselation in $d$ dimensions can be viewed as a convex hull problem in $d+1$ dimensions. Given a countable set of points $S\subset \mathbb{R}^d$ and a point $p\in S$, find the largest subset $X\subset S\setminus\{p\}$ with the following properties:

Every point in $X$ is a vertex of the convex hull of $X$.
$p$ is the only point in $S$ that lies in the interior of the convex hull of $X$.

Is there a relationship between the $d$-dimensional Delaunay tesselation and the set of polytopes for each point $p\in S$ as described?

The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.

I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:

http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf

What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.


What are good set size estimation algorithms for small sets (around 10-50 elements)? I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%).

I came across quite a few algorithms such as linear counting$^1$, PCSA$^2$, HyperLogLog$^3$ etc. According to their papers, their space needed varies with relative error as $1/\epsilon^2$. For my purpose, this seems really wasteful e.g., PCSA needs > 10,000 bits when the set size is 50 and $\epsilon$ is 1%.

Is there any reason why in practice, we may not need that many bits? Is there any algorithm that uses little space to estimate the size of small sets with high accuracy?

Thanks!

References:

[1] Linear Counting: Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15, 2 (June 1990), 208-229. DOI=10.1145/78922.78925 http://doi.acm.org/10.1145/78922.78925

[2] PCSA: Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2 (September 1985), 182-209. DOI=10.1016/0022-0000(85)90041-8 http://dx.doi.org/10.1016/0022-0000(85)90041-8

[3] HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm, by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Proceedings of the AofA07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127--146 (2007).

2^32 is only 4 billion; and doubtful you will saturate even a small fraction of that if you are watching IPs. Just store it all. A radix tree will compact as it saturates since you can flag entire subdomains as saturated.


Is there a result in computability theory that does not relativize? I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that

  Our axiomatization has its limit: it cannot prove any results in computability
  theory that fail to relativize to oracle computations. This is so because the
  theory can be interpreted in a variant of the effective topos built from partial
  recursive functions with access to an oracle.

This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles.

Are there results in computability theory that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle?

By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for.

It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.

Note that this statement could relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented.

Indeed, I think any non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").

On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet that doesn't relativize. (In contrast to, say, Kleene's characterization of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)

Here's a more or less trivial example:  Consider the halting problem for Turing machines that are specifically prohibited (by the definition of the computation model) from accessing an oracle.  It is undecidable relative both to no oracle and to a trivial oracle, and yet it is decidable relative to an oracle for the halting problem.  (The problem itself doesn't change relative to an oracle because it can't access the oracle, but the (unrestricted) TM that decides the problem becomes more powerful given the oracle.)

There are plenty of other examples, too.  Just play with the computation model a little and you can find other similar results.


What is the contribution of lambda calculus to the field of theory of computation? I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/reductions (crudely speaking). Some questions keep nagging at me though:

What's the point of lambda calculus? Why go through all these functions/reductions? What is the purpose?
As a result I'm left to wonder: What exactly did lambda calculus do to advance the theory of CS? What were it's contributions that would allow me to have an "aha" moment of understanding the need for its existence?
Why is lambda calculus not covered in texts on automata theory? The common route is to go through various automata, grammars, Turing Machines and complexity classes. Lambda calculus is only included in the syllabus for SICP style courses (perhaps not?). But I've rarely seen it be a part of the core curriculum of CS. Does this imply it's not all that valuable? Maybe not and I maybe missing something here?

I'm aware that functional programming languages are based on lambda calculus but I'm not considering that as a valid contribution, since it was created much before we had programming languages. So, really what is the point of knowing/understanding lambda calculus, w.r.t. its applications/contributions to theory?

$\lambda$-calculus has two key roles.

It is a simple mathematical foundation of sequential, functional, higher-order
computational behaviour.
It is a representation of proofs in   constructive
logic.

This is also known as the Curry-Howard correspondence.  Jointly,
the dual view of $\lambda$-calculus as proof and as (sequential,
functional, higher-order) programming language, strengthened by the algebraic feel
of $\lambda$-calculus (which is not shared by Turing machines), has lead
to massive technology transfer  between logic, the foundations of mathematics, and programming.
This transfer is still ongoing, for example in homotopy type theory.  In
particular the development of programming languages in general, and
typing disciplines in particular, is inconceivable without
$\lambda$-calculus. Most programming languages owe some degree of debt to
Lisp and ML (e.g. garbage collection was invented for Lisp), which are direct descendants of the $\lambda$-calculus. A
second strand of work strongly influenced by $\lambda$-calculus are
interactive proof assistants.

Does one have to know $\lambda$-calculus to be a competent programmer, or
even a theoretician of computer science?    No. If you are not interested
in types, verification and programming languages with higher-order
features, then it's probably a model of computation that's not
terribly useful for you. In particular, if you are interested in complexity theory, then
$\lambda$-calculus is probably not an ideal model because the basic
reduction step $$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$$ is powerful: it can make an arbitrary number of copies on $N$, so
$\rightarrow_{\beta}$ is an unrealistic basic notion in accounting for
the microscopic cost of computation. I think this is the main reason why
Theory A is not so enamoured of $\lambda$-calculus. Conversely, Turing machines are not terribly inspirational for programming language development, because there are no natural notions of machine composition, whereas with $\lambda$-calculus, if $M$ and $N$ are programs, then so is $MN$. This algebraic view of computation relates naturally to programming languages used in practice, and much language development can be understood as the search for, and investigation of novel program composition operators.

For an encyclopedic overview of the history of $\lambda$-calculus see History of Lambda-calculus and Combinatory Logic by Cardone and Hindley.

I have just come across this post and despite my post being rather late in the day (year!), I thought that perhaps my "penny's worth" may be of some use.

Whilst studying the subject at university, I had a similar thought on the matter; so, I posed the question of "why" to the lecturer and the response was: "compilers". As soon as she mentioned it, the power behind reduction and the art of assessing how best to manipulate it suddenly made the whole purpose of why it was and still is a potentially useful tool.

Well, that so to speak was my "aha" moment.

In my opinion, we often consider high level languages, patterns, automata, algorithm-complexity etc. useful because we can relate them to the 'task' at hand; whereas lamdba calculus seems a bit too abstract. However, there are still those out there who work with languages at a low level - and I imagine lambda calculus, object calculus and other related formalisations have helped them to understand and perhaps develop new theories and technologies from which the average programmer can then benefit. Indeed, it is probably not a core module for that reason, but (for the reasons I have stated) there will be the odd few - other than academics - who may find it integral to their chosen career path in computing.


Is a theoretically secure key exchange possible? During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.

In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the communication could not be decrypted by an eavesdropper even if he had a computer with infinite speed and memory.

My question is:

Would this be possible and can this (yes or no) be proven mathematically?

EDIT

After having read some of the answers I want to improve my question a bit:

Is it possible that some sender is sending some information to a receiver over an (insecure) channel not having any common keys nor access to a common source of randomness (or similar) in a way that it is not theoretically possible to "decrypt" the actual information from data transferred over the channel?

After a week of thinking I think I found some proof:

A is some data of the sender (such as a public/private key pair)
B is some data of the receiver
Ds is the data sent by the "sender"
Dr is the data sent by the "receiver"
Fn are mathematical functions
M is the "cleartext message" to be encrypted
The data sent by the "receiver" depends on the data received from the "sender" and from the private data B: Dr = F1(B,Ds)
The data sent by the "sender" depends on the data received from the "receiver", private data and the message: Ds = F2(A,M,Dr)
"Theoretically security" would mean that two different messages M exist which can result in the same data of the set (Dr,Ds); otherwise an attacker could search for all sets (A,B,M) which lead to a given data of (Dr,Ds) - and would know the only possible value of M
Because of Ds = F2(A,M,Dr) this would mean that different values of the set (A,M) must exist that lead to the same Ds (when Dr is given)
This would mean that the receiver (not having any additional information about A but the information contained in Ds) would also not be able to decrypt the message

I'm not sure if this proof is correct.

Can anyone tell me if it is correct?

I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated channels from Alice to Bob and Bob to Alice.

Nevertheless, if Alice, Bob, and Eve are in possession of some sort of correlated randomness, then it may be possible to construct such a scheme.

One such example is when a satellite broadcasts several random bits, and Alice, Bob, and Eve receive the bits through different binary symmetric channels with certain error probabilities. One can prove that, in this case, information-theoretical key agreement is possible, even when Eve's error probability is much lower than Alice's and Bob's.

A classic paper on this topic is "Secret Key Agreement by Public Discussion from Common Information" by Ueli Maurer.

While it is possible in theory to construct a theoretically unnreakable cipher, e.g. a one-time pad with pad content not identifiably nonrandom,  it is not possible to prove theoretically that the key exchange was secure, because whether there was a covert channel observer that surreptitiously copied the key is an empirical matter.


How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph? I am not a computer science theorist, but think this real world problem belongs here.

The problem

My company have several units accross the country.

We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.

That means: We'll allow a employee to left his unit if someone wants his place.

Example (ficticious) request data:

Name            Origin    Destination
Maria              1  ->  2
Marcos             2  ->  3
Jones              3  ->  4
Terry              4  ->  5
Joe                5  ->  6
Rodrigo            6  ->  1
Barbara            6  ->  1
Marylin            1  ->  4
Brown              4  ->  6
Benjamin           1  ->  3
Lucas              4  ->  1

The above, plotted:

See how we have to choose between the red, blue or black options?

The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization

The goal

Having collected all the requests, how to satisfy most of them?

Theory(?) application

Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.

Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).

The question

If this problem is expressed as

  "How to find the cycles which, together, involve the biggest number of
  non-shared edges in a directed graph"?

Will we satisfy most of the requesters?

That being true, there is an algorithm to find that optimal set of cycles?

Will this greddy approach solve the problem?

Find the biggest directed cycle on $G$;
Remove it's edges from $G$;
Repeat 1 until there is not a directed cycle on $G$;

Can you help me?

Do you know another way to describe the original problem (making most of requesters happy)?

Edit: changed department to unit, to better describe the problem.

This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.

Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is almost the same as the obvious greedy algorithm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.

This is not the fastest algorithm known.

there is probably a graph theory way/formulation to solve this, but this problem sounds more like a permutation problem to me where some of all permutations are rejected and others are valid. the permutations are employees and the positions are "positions" in the company. a permutation is rejected if it doesnt fit the requirements of "person [x] wants position [y]". the distinction of units/depts/org boundaries is apparently somewhat superfluous to the solution in this case.

this type of permutation problem with constraints can be readily converted into a instance of SAT (satisfiability) problem. the boolean variable assignments represent employees, and the constraint clauses represent the "person [x] wants position [y]" constraints. there are nearby classic examples of this, one usually called the "dinner table" problem where you have seating positions and guests and not all guests want to sit next to each other (or very similarly some guests want to sit next to other guests).

and of course there are sophisticated SAT solvers for fairly large instances involving roughly up to hundreds of variables and clauses, on PC, and if the problem is not "hard", in the thousands.

see eg [1] for a professional reference and [2] for a class exercise. there is also some structural similarity to what are known as "pigeonhole problems" which are well studied in SAT circles where pigeons are assigned to pigeonholes and you have more or less holes than pigeons. in that case however the pigeons are generally seen as interchangeable. in other words the dinner table problem is like the pigeonhole problem with stronger constraints and the guests/pigeons have required preferences.

note of course/keep in mind that for these types of problems, depending on the constraints the answer may be "no such constrained solution exists".

[1] the dinner table algorithm, by crato

[2] CS402 princeton HW SAT

[3] Satisfiability problem, wikipedia


A Simple Auction Game You are playing the following game.

You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a product appears with price $p_d\leq B$ dollars. If your bid is larger than the price, you buy the product, i.e., $b_d\geq p_d$, and you lose $b_d$ from your budget. Otherwise, you will be left with the same budget as before but you don't buy the product, i.e., if $b_d<p_d$. The next day the same thing happens and so forth. You stop the game when you spend all of your budget or day $n$ is reached. Your objective is to buy as much products as possible with budget $B$.

Can we find a policy that competes against an adversary and buy a "good" number of products? Good here means, for example, a policy with low regret, so the difference between what the adversary bought and what you bought is not large. If we can't, what assumptions could we make to make the regret low?

My policy so far is:

For each day $d=1..n$, bid $b_d=B_r/(n-d+1)$, where $B_r$ is your remaining budget.

I was trying to find an input sequence that makes my policy perform badly but I didn't succeed (for large $n$). I think if $n$ is large, then we may reach a low regret with this policy. I am still trying to prove this.

The problem is equivalent to online knapsack problem. Let $n$ represents the number of items. Let the knapsack has capacity $B$. Every item $i$, has value $v_i=1$ and weight $w_i=p_i$.

The offline optimal solution:

Sort the items in increasing order of their weights ($p_{\sigma(1)}\leq p_{\sigma(2)}\leq \cdots \leq p_{\sigma(n)}$ for some permutation $\sigma$).
Let $S\gets\emptyset$.
For $i\gets1$ to $n$: add $\sigma(i)$ to $S$ unless $\sum_{i\in S}p_i>B$.
For each $i\in S$, bid $b_i=p_i$ and for each $i\notin S$, bid $b_i=0$.

Claim: No online algorithm can achieve any non-trivial competitive ratio [1].

If we assume that $p_i=o(B)$ and $L\leq p_i\leq U$, then there is a competitive ratio of $\ln(U/L)+1$ [2].

For the regret, I don't know if there is some algorithm that achieves low regret (under some assumptions).


Randomness versus Quantumness in factorization The best deterministic factorization algorithm that is currently known runs in $O(N^{\frac{1}4+\epsilon})$ arithmetic steps.

Randomness and quantumness improves upon this.

I believe Quadratic/Number field sieve run in randomized subexponential time. What is it that quantumness provides that sieve techniques cannot provide? What exact barrier does Shor's algorithm break that randomness cannot?

What is it that quantumness provides that sieve techniques cannot provide?

It is more a question why quantum computers are believed to be more powerful than classical  computation models. Short: Quantum computers provide superpositions of quantum states.

Randomized algorithms are restricted to be in a certain state with some (constant) error probablility. Quantumness provides the posibility of evaluating function on every possible state and afterwards measuring a certain state with some error probability.

What exact barrier does Shor's algorithm break that randomness cannot?

The quantum states represent the accepted states as well as the rejected states. Shor's algorithm evaluates the accepting states in such an extent that the accepting states are more likely to be measured. Also the quantum algorithm can manipulate all states at the same time. A randomized algorithm is bound to increase the probability of being in such a accepting state, looping often enough to get a certain probability (or extending some other variable).


What is the run-time of the bin packing approximation algorithm? The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $OPT + \log(OPT)$ bins,  and its expected run-time is polynomial in the total number of items. However, I could not understand from the paper, what is the exact polynomial? That is:  if there are $n$ items with different sizes, what is a number $k$ such that the run-time is in $O(n^k)$?

According to the definition of polynomial (from Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.):

An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., T(n) = O(n^k) for some positive constant k.

In their Theorem 1.2 they say "The algorithm is randomized and the expected running time is polynomial". So their are meaning that the algorithm proposed is randomized (non deterministic), but its running time is polynomial, since is within a sum over the bins.


What's new in purely functional data structures since Okasaki? Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few:

IntMap (also invented by Okasaki in 1998, but not present in that book)
Finger trees (and their generalization over monoids)

There are also some interesting ways of implementing already known datastructures, such as using "nested types" or "generalized algebraic datatypes" to ensure tree invariants.

Which other new ideas have appeared since 1998 in this area?

New purely functional data structures published since 1998:

2001: Ideal Hash Trees, and its 2000 predecessor, Fast And Space Efficient Trie Searches, by Phil Bagwell: Apparently used as a fundamental building block in Clojure's standard library.
2001: A Simple Implementation Technique for Priority Search Queues, by Ralf Hinze: a really simple and beautiful technique for implementing this important datastructure (useful, say, in the Dijkstra algorithm). The implementation is particularly beautiful and readable due to heavy use of "view patterns".
2002: Bootstrapping one-sided flexible arrays, by Ralf Hinze: Similar to Okasaki's random-access lists, but they can be tuned to alter the time tradeoff between cons and indexing.
2003: New catenable and non-catenable deques, by Radu Mihaescu and Robert Tarjan: A new take on some older work (by Kaplan and Tarjan) that Okasaki cites (The most recent version of Kaplan & Tarjan's work was published in 2000). This version is simpler in some ways.
2005: Maxiphobic heaps (paper and code), by Chris Okasaki: Presented not as a new, more efficient structure, but as a way to teach priority queues.
2006: Purely Functional Worst Case Constant Time Catenable Sorted Lists, by Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas: Answers an outstanding question of Kaplan and Tarjan by demonstrating a structure with O(lg n) insert, search, and delete and O(1) concat.
2008: Confluently Persistent Tries for Efficient Version Control, by Erik D. Demaine, Stefan Langerman, and Eric Price: Presents several data structures for tries that have efficient navigation and modification near the leaves. Some are purely functional. Others actually improve a long-standing data structure by Dietz et al. for fully persistent (but not confluently persistent or purely functional) arrays. This paper also presente purely functional link-cut trees, sometimes called "dynamic trees".
2010: A new purely functional delete algorithm for red-black trees, by Matt Might: Like Okasaki's red-black tree insertion algorithm, this is not a new data structure or a new operation on a data structure, but a new, simpler way to write a known operation.
2012: RRB-Trees: Efficient Immutable Vectors, by Phil Bagwell and Tiark Rompf: An extension to Hash Array Mapped Tries, supporting immutable vector concatenation, insert-at, and split in O(lg n) time, while maintaining the index, update, and insertion speeds of the original immutable vector.

Known in 1997, but not discussed in Okasaki's book:

Many other styles of balanced search tree. AVL, brother, rank-balanced, bounded-balance, and many other balanced search trees can be (and have been) implemented purely functionally by path copying. Perhaps deserving special mention are:

Biased Search Trees, by Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan: A key element in Brodal et al.'s 2006 paper and Demaine et al.'s 2008 paper.

Infinite sets that admit fast exhaustive search, by Martín Escardó: Perhaps not a data structure per se.
Three algorithms on Braun Trees, by Chris Okasaki: Braun trees offer many stack operations in worst-case O(lg n). This bound is surpassed by many other data structures, but Braun trees have a cons operation lazy in its second argument, and so can be used as infinite stacks in some ways that other structures cannot.
The relaxed min-max heap: A mergeable double-ended priority queue and The KD heap: An efficient multi-dimensional priority queue, by Yuzheng Ding and Mark Allen Weiss: These happen to be purely functional, though this is not discussed in the papers. I do not think the time bounds achieved are any better than those that can be achieved by using finger trees (of Hinze & Paterson or Kaplan & Tarjan) as k-dimensional priority queues, but I think the structures of Ding & Weiss uses less space.
The Zipper, by Gérard Huet: Used in many other data structures (such as Hinze & Paterson's finger trees), this is a way of turning a data structure inside-out.
Difference lists are O(1) catenable lists with an O(n) transformation to usual cons lists. They have apparently been known since antiquity in the Prolog community, where they have an O(1) transformation to usual cons lists. The O(1) transformation seems to be impossible in traditional functional programming, but Minamide's hole abstraction, from POPL '98, discusses a way of allowing O(1) append and O(1) transformation within pure functional programming. Unlike the usual functional programming implementations of difference lists, which are based on function closures, hole abstractions are essentially the same (in both their use and their implementation) as Prolog difference lists. However, it seems that for years the only person that noticed this was one of Minamide's reviewers.
Uniquely represented dictionaries support insert, update, and lookup with the restriction that no two structures holding the same elements can have distinct shapes. To give an example, sorted singly-linked lists are uniquely represented, but traditional AVL trees are not. Tries are also uniquely represented. Tarjan and Sundar, in "Unique binary search tree representations and equality-testing of sets and sequences", showed a purely functional uniquely represented dictionary that supports searches in logarithmic time and updates in $O(\sqrt{n})$ time. However, it uses $\Theta(n \lg n)$ space. There is a simple representation using Braun trees that uses only linear space but has update time of $\Theta(\sqrt{n \lg n})$ and search time of $\Theta(\lg^2 n)$

Mostly functional data structures, before, during, and after Okasaki's book:

Many procedures for making data structures persistent, fully persistent, or confluently persistent: Haim Kaplan wrote an excellent survey on the topic. See also above the work of Demaine et al., who demonstrate a fully persistent array in $O(m)$ space (where $m$ is the number of operations ever performed on the array) and $O(\lg \lg n)$ expected access time.
1989: Randomized Search Trees by Cecilia R. Aragon and Raimund Seidel: These were discussed in a purely functional setting by Guy E. Blelloch and Margaret Reid-Miller in Fast Set Operations Using Treaps
and by Dan Blandford and Guy Blelloch in Functional Set Operations with Treaps (code). They provide all of the operations of purely functional fingertrees and biased search trees, but require a source of randomness, making them not purely functional. This may also invalidate the time complexity of the operations on treaps, assuming an adversary who can time operations and repeat the long ones. (This is the same reason why imperative amortization arguments aren't valid in a persistent setting, but it requires an adversary with a stopwatch)
1997: Skip-trees, an alternative data structure to Skip-lists in a concurrent approach, by Xavier Messeguer and Exploring the Duality Between Skip Lists and Binary Search Trees, by Brian C. Dean and Zachary H. Jones: Skip lists are not purely functional, but they can be implemented functionally as trees. Like treaps, they require a source of random bits. (It is possible to make skip lists deterministic, but, after translating them to a tree, I think they are just another way of looking at 2-3 trees.)
1998: All of the amortized structures in Okasaki's book! Okasaki invented this new method for mixing amortization and functional data structures, which were previously thought to be incompatible. It depends upon memoization, which, as Kaplan and Tarjan have sometimes mentioned, is actually a side effect. In some cases (such as PFDS on SSDs for performance reasons), this may be inappropriate.
1998: Simple Confluently Persistent Catenable Lists, by Haim Kaplan, Chris Okasaki, and Robert E. Tarjan: Uses modification under the hood to give amortized O(1) catenable deques, presenting the same interface as an earlier (purely functional, but with memoization) version appearing in Okasaki's book. Kaplan and Tarjan had earlier created a purely functional O(1) worst-case structure, but it is substantially more complicated.
2007: As mentioned in another answer on this page, semi-persistent data structures and persistent union-find by Sylvain Conchon and Jean-Christophe Filliâtre

Techniques for verifying functional data structures, before, during, and after Okasaki's book:

Phantom types are an old method for creating an API that does not allow certain ill-formed operations. A sophisticated use of them can be found in Oleg Kiselyov and Chung-chieh Shan's Lightweight Static Capabilities.
Nested types are not actually more recent than 1998 - Okasaki even uses them in his book. There are many other examples that are not in Okasaki's book; some are new, and some are old. They include:

Stefan Kahrs's Red-black trees with types (code)
Ross Paterson's AVL trees (mirror)
Chris Okasaki's From fast exponentiation to square matrices: an adventure in types
Richard S. Bird and Ross Peterson's de Bruijn notation as a nested datatype
Ralf Hinze's Numerical Representations as Higher-Order Nested Datatypes.

GADTs are not all that new, either. They are a recent addition to Haskell and some MLs, but they have been present, I think, in various typed lambda calculi since the 1970s.
2004-2010: Coq and Isabelle for correctness. Several people have used theorem provers to verify the correctness of purely functional data structures. Coq can extract these verifications to working code in Haskell, OCaml, and Scheme; Isabelle can extract to Haskell, ML, and OCaml.

Coq:

Pierre Letouzey and Jean-Christophe Filliâtre formalized red-black and AVL(ish) trees, finding a bug in the OCaml standard library in the process.
I formalized Brodal and Okasaki's asymptotically optimal priority queues.
Arthur Charguéraud formalized 825 of the 1,700 lines of ML in Okasaki's book.

Isabelle:

Tobias Nipkow and Cornelia Pusch formalized AVL trees.
Viktor Kuncak formalized unbalanced binary search trees.
Peter Lammich published The Isabelle Collections framework, which includes formalizations of efficient purely functional data structures like red-black trees and tries, as well as data structures that are less efficient when used persistently, such as two-stack-queues (without Okasaki's laziness trick) and hash tables.
Peter Lammich also published formalizations of tree automata, Hinze & Patterson's finger trees (with Benedikt Nordhoff and Stefan Körner), and Brodal and Okasaki's purely functional priority queues (with Rene Meis and Finn Nielsen).
René Neumann formalized binomial priority queues.

2007: Refined Typechecking with Stardust, by Joshua Dunfield: This paper uses refinement types for ML to find errors in SMLNJ's red-black tree delete function.
2008: Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures by Nils Anders Danielsson: Uses Agda with manual annotation to prove time bounds for some PFDS.

Imperative data structures or analyses not discussed in Okasaki's book, but related to purely functional data structures:

The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, by Bernard Chazelle: This data structure does not use arrays, and so has tempted first the #haskell IRC channel and later Stack Overflow users, but it includes delete in o(lg n), which is usually not possible in a functional setting, and imperative amortized analysis, which is not valid in a purely functional setting.
Balanced binary search trees with O(1) finger updates. In Making Data Structures Persistent, James R Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan present a method for grouping the nodes in a red-black tree so that persistent updates require only O(1) space. The purely functional deques and finger trees designed by Tarjan, Kaplan, and Mihaescu all use a very similar grouping technique to allow O(1) updates at both ends. AVL-trees for localized search by Athanasios K. Tsakalidis works similarly.
Faster pairing heaps or better bounds for pairing heaps: Since Okasaki's book was published, several new analyses of imperative pairing heaps have appeared, including Pairing heaps with O(log log n) decrease Cost by Amr Elmasry and Towards a Final Analysis of Pairing Heaps by Seth Pettie. It may be possible to apply some of this work to Okasaki's lazy pairing heaps.
Deterministic biased finger trees: In Biased Skip Lists, by Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, a design is presented for deterministic biased skip lists. Through the skip list/tree transformation mentioned above, it may be possible to make deterministic biased search trees. The finger biased skip lists described by John Iacono and Özgür Özkan in Mergeable Dictionaries might then be possible on biased skip trees. A biased finger tree is suggested by Demaine et al. in their paper on purely functional tries (see above) as a way to reduce the time-and space bounds on finger update in tries.
The String B-Tree: A New Data Structure for String Search in External Memory and its Applications by Paolo Ferragina and Roberto Grossi is a well studied data structure combining the benefits of tries and B-trees.

Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15.

RRB vector: a practical general purpose immutable sequence
http://dl.acm.org/citation.cfm?id=2784739


Incremental Maximum Flow in Dynamic graphs I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/deleted with its corresponding edges to form a graph $G^1$. What is a maximum flow in newly created graph? Is there a way to prevent from recalculating maximum flow?

Any preprocessing which isn't very time/memory consuming is appreciated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maximum flow calculation, for adding a vertex $v$, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to the $v$ then goes to the destination, but problem is, this path should be simple, I couldn't find better than $O(n\cdot m)$ for this case, for $m=|E|$. (Also note that if it was just one path this could be done in $O(n+m)$ but it's not so.)

Also for removing node above idea doesn't work.

Also I already saw papers such as Incremental approach for edges, but seems they are not good enough in this case, it's more than $O(m)$ for each edge and seems is not suitable extension in this case (we just recalculate a flow). Also currently I'm using Ford-Fulkerson maximum flow algorithm If there is better option for online algorithms, it's good to know it.

The described approach may not be theoretically optimal. It is just a simple practical solution that may work for the author. I can't provide any references because I always thought it is a widely known folklore, but strangely enough nobody posted it in the answer. So I do it.

Assume we have an undirected network $G=(V,E,c)$. Assume it is stored in a data structure which allows easy vertex/arc insertions/deletions. Sometimes we will use residual network $G_f$ (i.e. with updated capacities $c_f = c - f$).

First part is how to process vertex insertions/deletion. It's more or less straightforward for insertions:

Add a new vertex with corresponding edges to the residual network.
Find a maximum flow in the updated residual network using a maxflow algorithm of your choice.

For deletions things became more complicated. Imagine we split the vertex $v$ we are about to delete into 2 halves $v_{in}$ and $v_{out}$ such that all in-arcs points to $v_{in}$, all out-arcs goes from $v_{out}$ and this new vertices are connected by an arc of infinite capacity. Then deletion of $v$ is equivalent to deletion of the arc between $v_{in}$ and $v_{out}$. What will happen in this case? Let's denote by $f^v$ the flow passing through the vertex $v$. Then $v_{in}$ will experience excess of $f^v$ flow units and $v_{out}$ will experience shortage of $f^v$ flow units right after deletion (the flow constraints will be obviously broken). To make the flow constraints be held again we should rearrange flows, but also we want to keep the original flow value as high as possible. Let's see first if we can do rearrangement without decreasing the total flow. To check that find a maxflow $\tilde{f^v}$ from $v_{in}$ to $v_{out}$ in the "cutted" residual network (i.e. without the arc connecting $v_{in}$ and $v_{out}$). We should bound it by $f^v$ obviously. If it happen to be equal to $f^v$ then we are lucky: we have reassigned the flow which was passing through $v$ in such way that the total flow wasn't changed. In the other case the total flow must be decreased by "useless" excess of $\Delta = f^v - \tilde{f^v}$ units. To do that, temporarily connect $s$ and $t$ by an arc of infinite capacity and run maxflow algorithm again from $v_{in}$ to $v_{out}$ (we should bound flow by $\Delta$). That will fix residual network and make flow constraints be held again, automatically decreasing total flow by $\Delta$.

The time complexity of such updates may depend on maxflow algorithm we use. Worst cases may be pretty bad, though, but it's still better than total recalculating.

The second part is which maxflow algorithm to use. As far as I understand the author needs not very complex (but still efficient) algorithm with small hidden constant to run it on a mobile platform. His first choice of Ford-Fulkerson (I expect it to be Edmonds-Karp) looks not very bad from this point of view. But there are some other possibilities. The one I would recommend to try first is $O(|V|^2|E|)$ variant of Dinic's algorithm because it's quite fast in practice and can be implemented in a very simple way. Other options may include capacity scaling Ford-Fulkerson in $O(|E|^2 \log C_{max})$ and, after all, different versions of push-relabel with heuristics. Anyway the performance will depend on a use case so the author should find the best one empirically.

another possibility/direction is the push-relabel maximum flow algorithm which is "one of the most efficient algorithms for maximum flow" and can have better complexity profiles depending on your data. eg as the wikipedia page states

  the implementation with FIFO vertex selection rule has $O(V^3)$ running time, the highest active vertex selection rule provides $O(V^2 \sqrt E$) complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in $O(V \cdot E \cdot log(V^2 / E))$ time. asymptotically more efficient than Edmonds-Karp


Circle graph algorithm You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?

algorithm for code

I searched for smallest enclosing circle problem but that was not for at least m?

See

Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", Algorithmica 41 (3): 147–157, doi:10.1007/s00453-004-1123-0.

This is a N algorithm

Given a set of N points P, draw a line that have at least M points at one side of it.
Name this subspace with at least M points as S
Pick a point that lays in S and call it center
Calculate the most distant point from center and call the distance as ray.

There you go, you have circle with a center and a ray.

Obs. the way you chose the center is what determinates the size of your circle


Algorithmic lens in the social sciences Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.

Thus, my question is in regard to the impact of TCS on the social sciences.

  What novel and important insights into the social sciences has TCS provided?

I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences.

Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. poverty of the stimulus) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.

References to books/surveys are appreciated.

This example is from social choice theory, and elections in particular. We know that Arrow's theorem (and the Gibbard-Satterthwaite theorem in general) rule out the possibility of elections that are fair, non-manipulatable and without other bizarre consequences. But a seminal paper by Bartholdi, Tovey and Trick showed that finding the desired 'hack' to break a voting scheme was NP-hard, and there's been a large body of work by many researchers on the complexity of problems in the realm of election design. There's a nice survey by Faliszewski, Hemaspaandra, and Hemaspaandra on this topic.

re applications of complexity theory in social science-- scott aaronson has a daring & amusing-at-times essay tying complexity theory to deep century-old questions in philosophy that I ran across recently reading his blog.

Why Philosophers Should Care About Computational Complexity
http://arxiv.org/abs/1108.1791

http://www.scottaaronson.com/blog/

another interesting area of the application of algorithmic theory to social sciences happens in economics such as studying markets or other "complex systems". the idea is that the market is composed of separate actors or "agents" that each attempt to develop algorithms to make money. a darwinian process of selection ensues. similar to genetic algorithms. (and probably now actually quite close to reality of HST, high speed trading, where there are estimates that up to 70% of market trading is due to program trading.) a leading investigator in this area is j doyne farmer

http://tuvalu.santafe.edu/~jdf/SFI%20Template/About%20Me.html

I see you mention biology on your course page. an excellent application of complexity and algorithmic theory and one under intense development is in the cutting edge problem of determining protein folding configurations. for example an early paper proved that a formalized version of the protein folding problem is NP complete.

http://en.wikipedia.org/wiki/Protein_folding

protein folding problem is NP complete by berger/leighton
http://www.brown.edu/Research/Istrail_Lab/papers/1998/p30-berger.pdf


Examples of pedantry in TCS Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):

  The most common complaint is that physicists and journalists explain
  the meaning of a p-value incorrectly. For example, if the p-value is
  0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct
  the statement: if there is no effect, then the chance of something as
  or more extreme is 0.000001.

  Fair enough. But does it really matter? The big picture is: the
  evidence for the effect is overwhelming. Does it really matter if the
  wording is a bit misleading? I think we reinforce our image as pedants
  if we complain about this.

Which got me thinking -

  Are there good examples of pedantry in TCS ? Such an example would
  consist of

  A claim that is commonly made in the popular press
  A standard correction that people insist on making
  The correct "big picture" that the claim does capture even while being imprecise.

  where the claim is mathemtically wrong  but "morally right" and the
  correction is technically correct but doesn't change the intuitive
  understanding.

To lead things off, my example would be:

Claim - NP-complete problems take exponential time to solve
Correction - No in fact we just don't know if they can be solved in polynomial time
Big picture - NP-complete problems are HARD

Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper.

Hm, its tough even to think of examples of claims about TCS that make it to the popular press.

One thing I have seen occasionally is the claim that factoring is NP-hard, when explaining cryptography. This is related to the less innocuous error of claiming that quantum computers can solve NP hard problems, but restricted to the context of cryptography, this is a relatively mild error. The point is just that we (users of cryptography) seem to believe that there is no efficient algorithm for solving the problem. The particular conjectures we use to justify this assertion are besides the point.

Scott Aaronson, while a foremost authority, seems to regularly take the media to task for not hairsplitting accurately. eg his recent column in the NYT article "Quantum Computing Promises New Insights, Not Just Supermachines" [italics added]

  Struggling to shoehorn that mathematics into newspaper-friendly metaphors, most popular writers describe a quantum computer as a magic machine that could process every possible answer in parallel, rather than trying them one at a time. Supposedly, it could do that because, unlike today’s computers that manipulate bits, a quantum computer would manipulate quantum bits, or qubits, which can be 0 and 1 simultaneously.

  But that’s a crude way to visualize what a quantum computer does, and misses the most important part of the story. When you measure a quantum computer’s output, you see just a single, random answer — not a listing of all possible answers. Of course, if you had merely wanted a random answer, you could have picked one yourself, with much less trouble.

yet the metaphor of a quantum computer processing answers in parallel is widespread & a reasonable conceptual simplification of QM computing, and referred to in many QM computing textbooks. there are probably other examples from QM theory/computing.

there is a natural tension in TCS and other theoretical research in communicating with the public/media because it sometimes tends to emphasize critical distinctions/concepts as part of rigorous training that are not known or crucial to laymen. in other words in many cases research theory works against various conceptual "big picture" simplifications that are legitimate to laymen.


Exponential Speedup in External Memory Background

The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses).  These running times are generally given in terms of $M$, the size of memory, and $B$, the number of words that can be transferred to memory at one time.  Sometimes $L$ and $Z$ are used for $B$ and $M$ respectively.

For example, sorting requires a cost of $\Theta(N/B\log_{M/B} N/B)$ and naive matrix multiplication requires $\Theta(n^3/B\sqrt{M})$.

This model is used to analyze "cache-oblivious algorithms", which do not have knowledge of $B$ or $M$.  Generally the goal is for the cache-oblivious algorithm to perform optimally in the external memory model; this is not always possible, as in the Permutation problem for example (shown in Brodal, Faderberg 2003).  See this writeup by Erik Demaine for a further explanation of cache-oblivious algorithms, including discussions of sorting and matrix multiplication.

We can see that changing $M$ causes a logarithmic speedup for sorting and a polynomial speedup for matrix multiplication.  (This result is originally from Hong, Kung 1981 and actually predates both cache obliviousness and the formalization of the external memory model).

My question is this:

Is there any case where the speedup is exponential in $M$? The running time would be something like $f(N,B)/2^{O(M)}$. I am particularly interested in a cache-oblivious algorithm or data structure that fits this description but would be happy with a cache-aware algorithm/data structure or even a best-known lower bound.

It is generally assumed in most models that the word size $w = \Omega(\log N)$ if $N$ is the input size and clearly $M > w$.  Then a speedup of $2^M$ gives a polynomial speedup in $N$.  This makes me believe that if the problem I'm looking for exists, it is not polynomial.  (Otherwise we can change the cache size by a constant to obtain a constant number of I/Os, which seems unlikely).

I am not sure I understood the question.  But it seems to me that under the assumption that $PSPACE$ contains problems requiring exponential time, such problems would fulfill your requirements, since if $M$ is $O(\log N)$ you would need an exponential number of I/O operations (since you can't "stay" in the same memory block of size $O( \log N)$ more than a polynomial number of steps without going into a cycle) and if $M=N$ you would only need a linear number of I/O operations. Also, concerning your observation that such a problem cannot belong to $P$, it is correct if the speedup must hold for values of $M$ that are $\Omega(N)$ (since it would mean we have an exponential number of operations). But if the speedup only applies to smaller values of $M$, intuitively I believe this is not true, because I feel it should be possible to design a problem that is in fact the concatenation of smaller problems of size $O(\log N)$ each requiring exponential time in its own size, and an exponential number of I/O operations (that is, $poly (N)$, since $poly(N)$ is exponential in $O(\log N)$). In practice I believe $PSPACE$-complete problems such as $TQBF$ fulfill your condition.

this question appears to veer into terra incognita ie unexplored territory. after some thinking & review here are some thoughts/ideas on this apparently very difficult/subtle question which hopefully will be intelligent but are not meant to be definitive.

Demain who you cite writes, "the principle idea [of cache oblivious algorithms] is simple: design external-memory algorithms without knowing $B$ and $M$. But this simple idea has several surprisingly powerful consequences."

it also appears to have surprisingly subtle implications. it appears hard to analyze this model for extremal behavior and it appears nobody has done this so far. there are some surveys and they seem to survey the entire field so far. this is not surprising given the field is only ~1 decade old.

the model does not appear to have been translated to Turing machines yet where more strict/formal/theoretical/general/standard analysis may be possible. the whole concept of Big-Oh notation and its implications and intuitions such as irrelevance of constants is not necessarily automatically carrying in this area of cache oblivious algorithms. for example the model already seems to be working with constants $B,M$ which measure exact memory sizes. it appears the field does not have a set of basic axioms of its dynamics so far.
TMs were invented in 1936 by Turing and the Hartmanis-Stearns time/space hierarchy theorems (which you are somewhat alluding to in this question) were discovered in 1965. thats a remarkable ~3 decades yet the time/space hierarchy theorems are now considered somewhat elementary and taught in undergraduate classes. there does not seem to be corresponding hierarchy theorems established in this model yet, and how to do that is not a trivial problem. this model actually seems to have more "moving parts" than the standard Turing machine (which already has a rather fiendishly complex dynamics), ie is like an augmented Turing machine.
another idea is to convert this external memory model to TMs somehow, which again does not appear to show up in the literature/surveys on cache oblivious algorithms, and maybe see how the Hartmanis-Stearns hierarchy theorems could translate. it appears to relate to a two tape TM where one tape is size 'M' and the other tape is infinite, and blocks are transferred to 'M' in sizes of 'B'. but also, a difficulty here is it is more of a RAM model than the Turing model which uses sequential access to the tape. on the other hand this could run into subtleties associated with conversions between single and multitape TMs.
suggest attacking this problem empirically with simulations which is where the literature tends to focus on eg as in this great survey by Kumar on Cache oblivious algorithms (2003). there are many programs and papers online for cache simulations and one could possibly answer your question without a large amount of code, using some simplifications. one basic idea is to create probabilistic algorithms which access "nearby" areas of memory based on probabilities. "nearby" here is not necessarily contiguous memory, but instead an algorithm that selects random memory pages (blocks) based on keeping track of its own most recently accessed pages. suggest using power laws to determine the probability of selecting "near" pages in the "most recently accessed" list. this appears to be the key aspect that cache-based performance improvements are related to.
heres a rough argument based on 'M' which is basically a measure of "core memory" versus disk memory. for an algorithm, one would expect as core memory increases, one only comes close [asymptotically] to a linear improvement in algorithmic speed, and adding "core memory" to get any super-linear increase in algorithm speed seems intuitively almost like exceeding the speed limit and "getting something for nothing". however, dont grasp the model well enough to prove this [but apparently no one else has either, including the authorities/founders/experts].
this cache-oblivious algorithm literature has focused on P algorithms and did not see any case at all of an analysis of a non-P algorithm so far and perhaps none exists. this could possibly be because the analysis is too difficult! in which case, questions about extremal behavior may go unanswered in this field in the long term.
it does not even seem intuitively clear, or possibly at all studied yet, about how "small" complexity algorithms such as in L, or "big" algorithms such as non-P (eg Expspace etc) behave in this model. the model is measuring memory locality, which seems to be fundamentally different, but intertwined with, time and space hierarchies.
there is a somewhat obscure measurement of Turing machine complexity called "reversal complexity" with some study, results, and papers that might be related. basically the TM can cover a certain amount of time and space, but reversals are a somewhat independent measurement of the tape head during the computation. it seems that "high reversals" might be related to "high memory locality" because in both cases the tape head is tending to stay in a "smaller" region versus moving into larger regions.
this question and model reminds me of Amdahls law and suspect some kind of yet-undiscovered similar law related to diminishing returns or balances/tradeoffs might hold or be applicable in this area. rough reasoning: cache oblivious algorithm theory is looking at a balance/tradeoff between a finite "local" memory and a cost-based external "infinite" disk. this is basically two resources that behave "in parallel" and there is likely some kind of optimal tradeoff between them.


Can Curry-Howard prove a theorem from the types in your program, that has nothing to do with your program? The following link states:

  Curry-Howard means that any type can be interpreted as a theorem in some logical system, and any term can be interpreted as a proof of its type.
  This does not mean that those theorems have anything to do with your program. Take the following function:

swap : forall a,b. (a,b) -> (b,a)
swap pair = (snd pair, fst pair)

  The type here is forall a,b. (a,b) -> (b,a). The logical meaning of this type is (a and b) => (b and a). Note that this is a theorem in logic, not a theorem about your program.

My question is: Can Howard-Curry prove a theorem from the types in your program, that has nothing to do with your program?

I'll answer the opposite question which is:

  can Curry-Howard prove a theorem for your program, which has nothing to do with the type?

The answer is yes, depending on the meaning of "nothing to do". I'll leave the Curry-Howard aspect aside somewhat, but it underlies a lot of this approach.

The key idea is Wadlers' Theorems for Free! building on ideas from Reynolds, which allow you, given a program type, to deduce something about the program. For example, a program $f$ of type

(a, b) -> (b, a)

in haskell must satify

$$ \forall x\ y,\ f\ (x, y) = (y, x)$$

and therefore be the swap function.

The type $\def\Nat{\mathrm{Nat}}\forall a b. (a,b) \rightarrow (b,a)$ corresponds to the logical statement $\forall a b : \mathrm{Prop}. a \land b \rightarrow b \land a$. $(a,b)$ corresponds to $a \land b$ and quantification over types corresponds to quantification over propositions (and of course implies corresponds to function types). This basically just expresses the fact that logical and is commutative. If you ask me this has nothing to do with a swap function even though the swap function has this type so I think your examples satisfies your question.

If you think about functions of types like $\Nat \rightarrow \Nat$ they correspond are logically equivalent to $\top \rightarrow \top$ (which is of course equivalent to $\top$). Why is $\Nat$ correspond logically equivlent to $\top$? Well inhabitants can be constructed of type $\Nat$ no matter the case which is a property only true of tautologies so $\Nat$ is a tautology. One could argue that $\Nat$ corresponds to something else that is a tautology (as mentioned $\Nat \to \Nat$ is also a tautology) but it is still equivalent to $\top$. As Andrej noted logically equivalent does not mean corresponds and I was wrong in saying this. Thinking about it now that would be like saying $\forall a b. (a, b) \to (b, a)$ corresponded to $\top$ which is clearly wrong.

Most programs have extremely boring types quite frankly. In Haskell the only real types of interest are are types involving forall, because the rest usually have some type like $\;\cdots\, \to A$, where $A$ is a trivial tautology (like a list type or a number). Languages like Agda and Coq can have far more interesting types if you are interested in this sort of thing.


To what extent is "advanced mathematics" needed/useful in A.I. research? I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in artificial intelligence. However, I am not sure how many mathematics courses I should follow. (And which CS theory courses I should follow.)

From Quora, I learned that the subjects Linear Algebra, Statistics and Convex Optimization are most relevant for Machine Learning (see this question). Someone else mentioned that learning Linear Algebra, Probability/Statistics, Calculus, Basic Algorithms and Logic are needed to study artificial intelligence (see  this  question).

I can learn about all of these subjects during my first 1.5 years of the mathematics Bachelor at our university.

I was wondering, though, if there are some upper-undergraduate of even graduate-level mathematics subjects that are useful or even needed to study artificial intelligence. What about ODEs, PDEs, Topology, Measure Theory, Linear Analysis, Fourier Analysis and Analysis on Manifolds?

One book that suggests that some quite advanced mathematics is useful in the study of artificial intelligence is Pattern Theory: The Stochastic Analysis of Real-World signals by David Mumford and Agnes Desolneux (see this page). It includes chapters on Markov Chains, Piecewise Gaussian Models, Gibbs Fields, Manifolds, Lie Groups and Lie Algebras and their applications to pattern theory. To what extend is this book useful in A.I. research?

I do not want to sound condescending, but the math you are studying at the undergraduate and even graduate level courses is not advanced. It is the basics. The title of your question should be: Is "basic" math needed/useful in AI research? So, gobble up as much as you can, I have never met a computer scientist who complained about knowing too much math, although I met many who complained about not knowing enough of it. I remember helping a fellow graduate student in AI understand a page-rank-style algorithm. It was just some fairly easy linear algebra to me, but he suffered because he had no feeling for what eigenvalues and eigenvectors were about. Imagine the things AI people could do if they actually knew a lot of math!

I teach at a math department and I regularly get requests from my CS colleagues to recommend math majors for CS PhD's becase they prefer math students. You see, math is really, really hard to learn on your own, but most aspects of computer science are not. I know, I was a math major who got into a CS graduate school. Sure, I was "behind" on operating systems knowledge (despite having decent knowledge of Unix and VMS), but I was way, way ahead on "theory". It is not a symmetric situation.

AI is an amazingly broad field with a wide range of possible routes. Some are extremely mathematical, some barely touch mathematics. Others have already given good answers for the more mathematical approaches. Of the subjects you pointed out-

"Linear Algebra, Probability/Statistics, Calculus, Basic Algorithms and Logic"

-you do basically need or will benefit from all of them. Many approaches are at least partly directly based on probability and statistics - heuristics, neural networks, genetic algorithms, fuzzy logic. Calculus is equally useful - in AI or in general computing science you will find it almost everywhere. Linear algebra is something you definitely need as well.

The two most essential subjects from a CS/AI perspective are algorithms and logic, algorithms are the real heart of computing science, and logic is the underlying 'language' of algorithms.. The key to learning algorithms though is learning how to program, proficiency and practice at basic programming is one of the most important foundations of almost all computer science or AI subjects. Programming is also a skill that universities are not always particularly good at teaching. Logic is also really essential to most branches of AI; Boolean logic, predicate calculus, symbolic logic, underlying theories of permutation, the hierarchy of design, recursion, finite state machines, Turing Machines, CPU design, etc.. Here we are really stepping away from mathematics into computing science proper..

Extending to my own field of 'Strong AI' mathematics plays an underlying but absolutely essential role. A very good understanding of basic maths is probably more important than higher maths, but really anything you pick up can be useful. The real problem in a nascent field like Strong AI is that everything is up in the air and so the field is in total flux.
Subjects that are potentially useful include - neural networks, genetic algorithms, neurology, genetics, psychology, cybernetics and robotics, 3D graphics theory, image processing theory, computer games design, philosophy, art theory, digital electronics, linguistics theory.. In a field like this reading is one of the most important ways to learn. A couple of books that were starting points for me were - The Emperors New Mind by Roger Penrose, Eye and Brain by RL Gregory, but really insights can come from almost anywhere


Everyday encounters with NP-complete problems Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?

My favorite example to use with non-CS friends is this one:

Abraham, A. Blum, Sandholm.  Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.  EC07.

Kidney exchange markets are essentially a restricted form of cycle cover.  I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!

My second favorite example is the hospitals-and-residents problem (aka the college admissions problem).  Each hospital ranks all residents (graduating medical students) and residents rank hospitals.  Each hospital has a certain number of slots.  From there it's a stable matching problem and can be solved in polynomial time.

But in reality, couples can enter the system (yes, there is indeed a system) together, so that the system won't, for example, split up married couples who are both applying for residency.  The addition of couples makes the problem NP-complete.  In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.

Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit:

Number guessing, where you can only guess single numbers till you've got it right.


find the densest subgraph of size k What is "the best" algorithm to find the densest subgraph of size k?

i.e. a subgraph of size k with the maximum number of edges inside for an unweighted and undirected graph.

For fixed k, the straightforward brute-force algorithm takes $O(n^k)$ time with n the number of nodes. I'm looking for something, like $O(2^kn)$ or so. Maybe using a recursive algorithm or dynamic programming.

An answer to your problem tells you whether there exists a clique of size k. So, any such algorithm for your problem must be at least as slow as clique algorithms. See the wikipedia section on FPT and clique for more.

This is me again, more than 3 years after asking this question.

Here is a code that can solve the weighted version of the problem in some real-world weighted graphs efficiently: https://github.com/maxdan94/HkS

Please find a paper about the method here: https://zenodo.org/record/159769/files/main.pdf

It uses branch&bound.


Is it possible to convert any tree to a B-tree or an R-tree? I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an arbitrary number of directed edges linking it to other nodes (i.e. children, parent and different grammatical relations such as subject_of, complement_of, etc.). Note that all these features are absolutely necessary to accurately represent the syntactical structure of a sentence.

Now, given such an initial tree with a totally unconstrained structure, I want to know if it is possible to convert that tree into a form that is more search-efficient (i.e. so that search involves less recursion). The only operation I really need to support is finding nodes with an arbitrary combination of type, id, value, and/or feature(s). I also need to be able to match a node back to the original tree if other operations are necessary. What is of primary importance is read-time and query efficiency.

From what I understand, B-trees and R-trees are generally search efficient. From Wikipedia, "like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory." This is exactly the situation I am in right now. However, I have very limited knowledge of the different types of trees and how they convert to another.

So, I am wondering if it is possible in theory to convert any N-ary tree (i.e. in my case, a completely unconstrained tree with an arbitrary number of children, edges and features for each node) into a B-tree or an R-tree to make it more search efficient? How would one go about doing this?

An N-ary tree is the general term describing a tree data structure containing/organizing a list of numbers.

A B-tree is an N-ary tree opimized for block/disk access. Each leaves contain ranges of elements.

An R-tree is an N-ary tree but the order imposed on the list of elements is no longer the "greater than" order on a list of numbers but a"close to" metric on points in 2D and more. The "close to" metric is approximated by bounding boxes. An R-tree can be implemented over a B-tree, technically speaking.

Furthermore, any data set in n-dimensions has representations in 1D. Therefore, given some metric, all these tree topologies are isomorphic...

Any data structure can be serialised to any data structure, provided that they can hold the same information.

Insertion works by locating the place to insert nodes through searching and insert.
If a node is full, then a split needs to be done.

Splits need to check every possible partition, giving optimal solution of O(2^{M+1})


Maximum subset of words with Hamming distance ≥ D For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D.
(The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)

Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?

Thank you very much.

In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.

Try the following command on MATLAB, as you're looking for a practical solution

squareform(pdist(dec2bin(0:255,8),'hamming')*8)

It gives you a matrix, containing the pairwise hamming distance between binary numbers from 0 to 255.
You can plot it using any tool in matlab, such as 'imtool'. But be careful about the 1-based indexing of matrices in MATLAB!


Arguments for existence of one-way functions I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?

Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:

$$(x, r) \rightarrow s$$

where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution.

This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas.

It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve.

ADDED: I now realize that this connection was already given (in more detail) in Abadi, Allender, Broder, Feigenbaum, and Hemachandra; they point out that one-way functions can give solved hard instances of SAT, and vice versa.

Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.

Would it be as easy as suggesting for example the Sine function?

Because for a given input and output the input can be increased or decreased by 360 degrees (or 2 pi if you're into radians) it is many-to-one, so you can never be sure which input you had?

Do tell me if I've misunderstood the question though.


Universities for Quantum Computing / Information? Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?

The aim here is to collect a useful list for someone considering graduate study in these fields, not to discuss which is "best".  To make this list useful, please include a brief description of the part of the university where this area is pursued (in many places this is in an interdisciplinary institute that may not be familiar to everyone), and a URL.

There are two quantum wikis which provide reasonably good list of research groups in QIP: Quantiki and Qwiki. Quantiki has better European coverage, while Qwiki has better US coverage.

The geographic area I know best is the UK. In the UK there are large theory groups in Oxford, Cambridge, Bristol, University College London and Imperial College, among other places.

In Oxford, where I have spent the last 5 years, QIP research is spread across a number of departments: Physics, Computer Science, Materials Science and Maths. There isn't much of a presence in Maths, although it is Artur Ekert's official affiliation. Computer Science has a growing group that mostly looks at category theory and quantum foundations.  Physics has quite a number of different groups ranging from experiments to theory. Materials science is weirdly the department where I have been based (although I know little about materials) and there is both a theory group there and a fair number of experimentalists. Computer Science, Materials and Physics all have taught quantum computing courses which can be taken towards the course requirement of a DPhil.

Hope this is useful.

the Perimeter institute in canada seems apparently not affiliated with a particular university but has a strong research program incl quantum foundations, quantum information processing etcetera. (questioner did mention "institute" & seems like artificial restriction to strictly limit to universities.)


Jumping (Busy) Beaver variant Is the following Busy Beaver variant known?

A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $|x_j|^i$ steps until $M_i(x_j)$ accepts; then $J$ outputs $x_j$ (if $M_i$ doesn't halt in $|x_j|^i$ steps  $J$ continues with the next $x_j$). In other words:

$$J(M_i) = min\{ x \mid M_i(x) \text{ halts and accept in less than } |x|^i \text{ steps}\}$$

Fancifully, $J(M_i)$ - when defined - represents how high the polynomial-time Turing machine $M_i$ can "jump". So, for every $n$, we can define the Jumping Beaver as the Turing machine $M$ of size $n$ that achieve the highest jump $j(n) = max \{ J(M) \mid |M| = n\}$ .

But in a similar way we can define $J'$ that "measures" the jumps of a nondeterministic Turing machine $N_i$ ($J'$ simulates all branches of $N_i$ on input $x$ for at most $|x|^i$ steps).

  Do nondeterministic jumping beavers perform better than deterministic jumping beavers? I.e. does $j'(n) > j(n)$ hold? (for some values of $n$ or infinitely often)
  What about the limit $\lim_{n \to \infty}j'(n)/j(n)$?

Note: the enumeration of the deterministic Turing machines $M_i$ is different from the enumeration of the nondeterministic $N_i$ (due to the nondeterministic transitions), so, to make $J$ and $J'$ directly comparable, we can follow this alternative approach: $J$ simulates $M_i$ on input $x_j \# 0^{|x_j|}$;  $J'$ can take as input a deterministic Turing machine $M_i$, too but simulates it on inputs $x_j \# y$ for all $y \in \{0,1\}^{|x_j|}$ and stops its search if at least one computation accepts. In this setting that seems equivalent to the formulation above (indeed $J'$ seems to capture all the power of NP), it is easy to see that $j(n) = j'(n)$.

the halting problem does not seem to be studied much for nondeterministic TMs (there is no single obvious way to extend the halting problem to NTMs) and most problems associated with undecidability seem to be defined in terms of non-NTMs (ie DTMs). however here is one generalization that could be related to your question.

A Parameterized Halting Problem Yijia Chen and Jorg Flum

  The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of differ- ent areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.


Deciding whether an NC${}^0_3$ circuit computes a permutation or not I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.

A Boolean circuit is called an NC0k circuit if each output gate syntactically depends on at most k input gates.  (We say that an output gate g syntactically depends on an input gate g′ when there is a directed path from g′ to g in the circuit as viewed as a directed acyclic graph.)

In the aforementioned question, QiCheng asked about the complexity of the following problem, where k is a constant:

Instance: An NC0k circuit with n-bit input and n-bit output.
Question: Does the given circuit compute a permutation on {0, 1}n? In other words, is the function computed by the circuit a bijection from {0, 1}n to {0, 1}n?

As Kaveh commented on that question, it is easy to see that the problem is in coNP.  In an answer, I showed that the problem is coNP-complete for k=5 and that it is in P for k=2.

  Question.  What is the complexity for k=3?

Clarification on May 29, 2013: “A permutation on {0, 1}n” means a bijective mapping from {0, 1}n to itself.  In other words, the problem asks whether every n-bit string is the output of the given circuit for some n-bit input string.

This problem with $k=3$ is coNP-hard (and therefore coNP-complete).

To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a non-bijective function).

First a preliminary definition that will be helpful:

We define a labeled graph to be a directed graph, some of whose edges are labeled with literals, with the property that every vertex has either one unlabeled incoming edge, one labeled incoming edge, or two unlabeled incoming edges.

The reduction

Suppose we have a 3-SAT formula $\phi$ consisting of $m$ clauses, each containing three literals. The first step is to construct a labeled graph $G$ from $\phi$. This labeled graph contains one copy of the following gadget (sorry for the terrible diagram) for each clause in $\phi$. The three edges labeled L1, L2, and L3 are instead labeled with the literals in the clause.

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

The gadgets (one for each clause) are all arrange in one big cycle with the bottom of one gadget linking to the top of the next.

Note that this arrangement of gadgets does in fact form a labeled graph (every vertex has indegree 1 or 2 with only edges leading to vertices of indegree 1 being labeled).

From the formula $\phi$ and the labeled graph $G$ (which was constructed from $\phi$) we next construct an $NC_3^0$ circuit (this will conclude the reduction). The number of inputs and outputs for this circuit is $n+v$ where $n$ is the number of variables in $\phi$ and $v$ is the number of vertices in $G$. One input and one output is assigned to each variable in $\phi$ and to each vertex in $G$. If $x$ is some variable in $\phi$ then we will refer to the input and output bits associated with $x$ as $x_{in}$ and $x_{out}$. Furthermore, if $l$ is a literal with $l = x$ then we define $l_{in} = x_{in}$ and if $l$ is a literal with $l = \neg x$ then we define $l_{in} = \neg x_{in}$. Finally, if $v$ is some vertex in $G$ then we will refer to the input and output bits associated with $v$ as $v_{in}$ and $v_{out}$.

There are four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Note that this output depends on only one input bit.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Note that this output depends on only two input bits.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l_{in})$. Note that this output depends on only three input bits since $l_{in}$ depends only on $x_{in}$ for whatever variable $x$ is used in the literal $l$.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. Note that this output depends on only three input bits.

Since in all cases the output depends on only three inputs, the circuit we build is in $NC_3^0$ as desired.

Correctness proof case 1: $\phi$ is satisfiable

Suppose there exists a satisfying assignment for $\phi$. Then construct the following two sets of values for the inputs.

1) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. All of the inputs associated with vertices of $G$ are given the value 0.

2) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. Consider the vertices in one clause gadget in $G$. If the value of a label is 0 (under the satisfying assignment), the input associated with the vertex at the target endpoint of the edge labeled with that label is given a value of 0. If both L1 and L2 have value 0 then the second-top vertex in the gadget (as shown above) is also given a value of 0. All other vertices are given a value of 1.

We wish to show that these two sets of inputs yield identical outputs and therefore that the $NC_3^0$ circuit does not encode a permutation.

Consider the four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Since $x_{in}$ is the same for both sets of inputs, outputs of this form will always be the same across the two sets of inputs.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Examining the gadget whose copies make up $G$, we see that all such edges consist only of pairs of vertices whose input values are always 1s under the second set of inputs. Thus $v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$ under the first set of inputs and $v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$ under the second set of inputs. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l)$. If $l$ is false under the assignment then $v_{in}$ is 0 under both sets of inputs; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$ under both sets of inputs. If $l$ is true under the assignment, $v_{in}$ is 0 under the first set of inputs and 1 under the second; also note that in the gadget, the only labeled edges $(u, v)$ have vertices $u$ which always have $u_{in} = 1$ under the second set of inputs. As a result we see that under both sets of inputs, $u_{in} = v_{in}$ whenever $l$ is true; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. There are two such vertices in each gadget. The top vertex and the second-from top vertex. We consider those two cases separately.

4a) When $v$ is the second-top vertex in a gadget, $u$ and $w$ are the two target endpoints of the edges labeled L1 and L2. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff L1 has value 0 under the satisfying assignment (aka $u_{in} = L1$); similarly, $w_{in}$ is 0 iff L2 has value 0 under the satisfying assignment (aka $w_{in} = L2$); and finally, $v_{in}$ is defined to be 0 iff both L1 and L2 have value 0  (aka $v_{in} = L1 \lor L2$). Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4b) When $v$ is the top vertex in a gadget, $u$ is the second-top vertex and $w$ is the target endpoint of the edge labeled L3. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff both L1 and L2 have value 0 (aka $u_{in} = L1 \lor L2$); $w_{in}$ is 0 iff L3 has value 0 (aka $w_{in} = L3$); and finally $v_{in} = 1$. Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$ where the equality $(L1 \lor L2 \lor L3) = 1$ holds by definition in a satisfying assignment for every clause. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

Clearly, we see that the outputs are the same for two different sets of inputs and therefore that the $NC_3^0$ circuit enacts a non-bijective function.

Correctness proof case 2: $\phi$ is unsatisfiable

Suppose now that there exists no satisfying assignment for $\phi$. Then assume for the sake of contradiction that some two different sets of inputs lead to the $NC_3^0$ circuit having the same output.

Clearly, the two inputs must have the same values for $x_{in}$ for every variable $x$ in $\phi$. Thus we may now unambiguously refer to the value of $x$.

Define $S$ to be the set of vertices $v$ in $G$ such that $v_{in}$ is different in the two sets of input values.

We will prove the following lemmas below:

Lemma 1: If in some gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertices above those three in the gadget are in $S$.

Lemma 2: If in some gadget the top vertex is not in $S$ then in the next gadget up no vertex is in $S$.

Since the gadgets form a loop, this implies that if in any gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertex in $G$ is in $S$ (in other words $S$ is empty).

However, consider a gadget associated with a clause $(L1 \lor L2 \lor L3)$ that is not satisfied. In this gadget all three labels have value 0. We know that edge $(u, v)$ labeled $L$ must satisfy $v_{out} = v_{in} \oplus (u_{in} \land L)$, but $L = 0$, so $v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$. Thus since the output is the same for both inputs, the values of $v_{in}$ must also be the same across the two sets of inputs. In other words, we have shown that $v$ is not in $S$. Thus we see that in this particular gadget, the three vertices at the target endpoints of the labeled edges are not in $S$.

As a result, we conclude that $S$ is empty. This however, implies that between the two sets of inputs, there were no differences, which contradicts the assumption that these input sets are different. As a result, we see that the function enacted by the $NC_3^0$ circuit is injective and therefore a bijection.

All that's left is to prove the lemmas.

To do this, we note that for every type of vertex in $G$ (indegree 1 with label, indegree 1 without label, and indegree 2), if all incoming edges come from vertices not in $S$ then the vertex in question is also not in $S$. This is because in all three cases $v_{out} = v_{in} \oplus X$ where $X$ is some function of the inputs associated with variables and/or vertices with edges to $v$. Since all such vertices are not in $S$ by assumption, the value of $X$ must be the same under both sets of inputs. Therefore $v_{in} = v_{out} \oplus X$ is also the same under both sets of inputs. In other words $v$ is not in $S$.

Now that we have the rule that a vertex is not in $S$ whenever all of its predecessors are not in $S$, the lemmas follow simply by applying the rule repeatedly to the gadget diagram above.

Not the answer the author was seeking, see comments that clarify what "permutation" is in this context.

I cranked out the size of the minimum dominating set for the monogenic permutation group inclusion digraph:
https://oeis.org/A186202

All you have to do is test one member of every prime cycle decomposition.

For each prime cycle it should be sufficent to code the elements as (10101010...), then (01010101..)?

------Clarification------
The goal of this approach is to model your 2^n test cases as a digraph. If one sucessful test case implies another sucessful test case, then you only have to test the min dominating set of this test space digraph.  In the space of permutations OEIS A186202 is the max you have to test to either detect a non-trivial subgroup or prove none exist; this number is still large but much smaller than n!.

--Musing--
By using n-1 zeros and 1 one in n iterations you can detect the fixed permutation you are looking for. After that in O( n{(n-1) \choose (k-1)}(2^(k-1)) you can test that every set of (k-1) variables does not effect each index of the shuffle.  Since k is fixed that is polynomial.  Am I missing something?