Complexity of a weighted subset selection problem.

I'm going to assume your problem is equivalent to what this computes:

max map SubsetsOfSize(N) \S (sum map attributes \A (max map S \e A[e]))

In other words, find the best set of items such that picking the best available item attribute values gives the largest sum.

Yes, it's NP-Complete. You can encode 3-Sat into it. Each variable becomes a true-row and false-row. Each clause becomes a column with a 1 in the rows corresponding to its satisfying assignments. You prevent true-row and false-rows from being selected simultaneously by adding columns with huge values in those two rows (0 everywhere else) and requiring that exactly half the rows be selected (thus the optimal solution will require each huge value, and picking a true and false will lose a huge value somewhere else). The 3-sat instance being satisfiable is equivalent to being able to select items for a total score of HugeValue*NumVariables + NumClauses.

Example transformation:

(A or B or C) and (not A or B or not C)

   uA uB uC  C1 C2
+A  9  0  0  1  0
-A  9  0  0  0  1
+B  0  9  0  1  1
-B  0  9  0  0  0
+C  0  0  9  1  0
-C  0  0  9  0  1
N = 3


Is there any work combining machine learning and the more exotic forms of complexity theory?

There is some inherent difference or dissimilarity of approaches between the two fields of applied machine learning and TCS/complexity theory.

Here is a recent workshop on the subject at the Center for Computational Intractability, Princeton with lots of videos.

  Description: Many current approaches in machine learning are heuristic: we cannot prove good bounds on either their performance or their running time. This small workshop will focus on the project of designing algorithms and approaches whose performance can be analyzed rigorously. The goal is to look beyond settings where provable bounds already exist.

Workshop: Provable Bounds in Machine Learning — August 1-2, 2012

In TCS a main area of study of "learning" sometimes maybe confusingly even also called "machine learning" is called PAC theory which stands for Probably Approximately Correct. its early 1980s origin predates much more modern research into "machine learning." wikipedia calls it part of the field computational learning theory. PAC often concerns results of learning boolean formulas given statistical samples of the distributions etc and the achievable accuracy of learning given various algorithms or limited samples.  This is studied in a rigorous theoretical way with tie-ins to complexity classes.  But it is not so much an applied study & wikipedias page on machine learning does not even list it.

The Computational Complexity
of Machine Learning PhD thesis by Kearns
Xing slides on (PAC) machine learning


Communication problems for which a deterministic direct-sum theorem is not known to hold

I think I can suggest the problem, which is not widely known, but for which I'm interested in. Suppose we have $n$ permutations $\pi_i$ in $S_3$. Alice, Bob and Carol receive first, second and third elements of all permutations, respectively. The goal is to compute $\prod_i sgn(\pi_i)$, where $sgn(\pi_i)$ is a sign of permutation $\pi_i$ (can take -1 or +1). I'm interested in communication complexity in NiH model.

Some time ago I've tried to apply direct-sum theorem, but here we have some obstacles with dependence of input of different participants. I still don't know whether $\Omega(n)$ lower bound holds for this problem.


Typing inference as a map on abstract syntax trees

Type inference for dependent type theory is undecidable in general, so what you're asking for is impossible. However, it is possible to separate the syntax into inferrable terms and checkable terms, and implement inference for the inferrable fragment. This is the approach taken by bidirectional typechecking. The paper on LambdaPi by Andres Löh, Conor McBride and Wouter Swierstra describes a tutorial implementation of a dependent typechecker in this style. More advanced typecheckers for dependently typed languages typically rely on higher-order unification to infer the types for more expressions, a good example is the paper on Higher-order Dynamic Pattern Unification by Andreas Abel and Brigitte Pientka.
Regarding your second question, this claim is false: the conversion rule of dependent type theory says that a type is inhabited if and only if its normal form is inhabited. So a type such as (\(X:Type). x) Nat is not in beta normal form but is inhabited by the normal forms zero, suc zero, ...


Yes, the occurs check is there so that the algorithm is guaranteed to terminate. Without it, when we deal with an equation $X = T$ in which $X$ may occur, substituting $T$ for $X$ everywhere does not get rid of $X$, and so we can run in circles, as your example shows.

There is a way to avoid this by allowing arbitrary recursive types. If we have an equation $X = T$ then we may replace $X$ everywhere by the type $\mathsf{fix} \,X \,.\, T$, i.e., a canonical solution to the equation $X = T$. Ocaml will do this for you if you run it with -rectypes:

$ ocaml -rectypes
        OCaml version 4.01.0

# fun x -> x x ;;
- : ('a -> 'b as 'a) -> 'b = <fun>

This says that fun x -> x x has the type $A \to B$ where $A = A \to B$.

By the way, you can find an implementation of the algorithm in my PL Zoo, see solve in the language Poly.


Relation between hardness of recognition of a graph class and forbidden subgraph characterization

Although it seems intuitive that the list of forbidden (induced) subgraphs for a class $\mathscr{C}$ of graphs which has NP-hard recognition should possess some "intrinsic" complexity, I have recently found some striking negative evidence to this intuition in the literature.

Perhaps the simplest to describe is the following, taken from an article by B. Lévêque, D. Lin, F. Maffray and N. Trotignon.

Let $F$ be the family of graphs which are composed of a cycle of length at least four, plus three vertices: two adjacent to the same vertex $u$ of the cycle, and one adjacent to a vertex $v$ of the cycle, where $u$ and $v$ are not consecutive in the cycle (and no other edges).

Now let $F'$ be the family of graphs which are composed exactly the same way, except that you add four vertices: two adjacent to the same vertex $u$ of the cycle (as before), but now two adjacent to the same vertex $v$ of the cycle, where again $u$ and $v$ are not consecutive.

Then the class of graphs which has $F$ as the forbidden induced subgraphs has polynomial-time recognition, whereas the recognition of the class which has $F'$ as the forbidden induced subgraphs is NP-hard.

Therefore, I find it hard to conceive of any general condition that a list of forbidden induced subgraphs has to satisfy when it results in a class with (NP-) hard recognition, considering that such a condition will have to separate the "very similar" $F$ and $F'$ above.


An efficient Beta-Equivalence algorithm?

The answer is no.  An old theorem of Statman states that $\beta$-equivalence in the simply-typed $\lambda$-calculus is not elementary recursive, that is, no algorithm whose running time is bounded by $2^{\vdots^{2^{|S|+|T|}}}$ for a tower of exponentials of fixed height may decide whether two simply-typed terms $S$ and $T$ are $\beta$-equivalent.
The original statement is from
Richard Statman.  The typed $\lambda$-calculus is not elementary recursive.  Theoret. Comput. Sci. 9:73-81, 1979.
A simpler proof may be found in this paper by Harry Mairson.
Edit: as observed by Martin Berger, Mairson proves that $\beta\eta$-equivalence is not elementary recursive, whereas Statman's result (and the OP's question) concerns $\beta$-equivalence, without $\eta$.  However, as pointed out by xavierm02, Mairson's result implies Statman's.  Let me fill in the details for those who are not familiar with $\eta$-long forms.
The $\eta$-long form $\eta(x^A)$ of a variable $x^A$ is defined by induction on $A$: observe that $A=A_1\to\cdots\to A_n\to\alpha$ for some $n\in\mathbb N$, some types $A_1,\ldots,A_n$ (smaller than $A$) and some atom $\alpha$, and let
$$\eta(x^A) :=  \lambda y_1^{A_1}\ldots\lambda y_n^{A_n}.x\eta(y_1^{A_1})\cdots\eta(y_n^{A_n}),$$
where the $\eta(y_i^{A_i})$ are given inductively.
The $\eta$-long form $\eta(M)$ of a simply-typed $\lambda$-term $M$ is defined by replacing every occurrence of variable $x^A$ of $M$ (free or bound) with $\eta(x^A)$.  (NB: through Curry-Howard, this corresponds to taking a sequent calculus proof and expanding it so that it has only atomic axioms).
Observe that:

$\eta$-long forms are stable under substitution, and therefore under $\beta$-reduction;
two $\eta$-long $\beta$-normal forms are $\beta\eta$-equivalent iff they are equal (up to $\alpha$-renaming, of course);
computing the $\eta$-long form of a simply-typed $\lambda$-term is elementary recursive (if you don't keep the size of type annotations, the $\eta$-long form of a term may be exponentially bigger, but that is not a problem).

That Mairson's result implies Statman's is a consequence of the following:
Claim.  Let $M,N$ be two simply-typed $\lambda$-terms.  Then, $M\simeq_{\beta\eta}N$ iff $\eta(M)\simeq_\beta\eta(N)$.
In fact, via point (3) above, an elementary recursive algorithm for deciding $\beta$-equivalence immediately gives an elementary recursive algorithm for deciding $\beta\eta$-equivalence (the one pointed out by xavierm02).
Let us prove the claim.  The right-to-left implication is trivial.  Conversely, suppose that $M\simeq_{\beta\eta} N$. This obviously implies $\eta(M)\simeq_{\beta\eta}\eta(N)$. Let $P$ and $Q$ be the $\beta$-normal forms of $\eta(M)$ and $\eta(N)$, respectively. By point (1) above, both $P$ and $Q$ are $\eta$-long (because $\eta(M)$ and $\eta(N)$ are). But of course we still have $P\simeq_{\beta\eta} Q$, so by point (2) $P=Q$, which proves $\eta(M)\simeq_\beta\eta(N)$ (they have the same $\beta$-normal form).


Finding distances in graphs where shortest path has a large number of nodes

If you accept approximations to the distances, you can take a look at distance oracles.  A good source is the paper on distance oracles by Thorup-Zwick, Approximate Distance Oracles (STOC 2001).

Distance oracles can offer constant (but approximate) look-up.


Gradient descent-like optimization on a convex landscape with noisy sampling

The problem you describe is called "stochastic convex optimization in the bandit setting". This is the problem considered and solved here: http://arxiv.org/pdf/1107.1744v2.pdf

They show that after $k$ queries, you can get within $O(1/\sqrt{k})$ of the minimum value of the function (ignoring a poly$(d)$ dependence on the dimension $d$ of the domain of the function $f$).


New Space Lower-Bound Techniques for Streaming Algorithms

A recent result of Li, Nguyen, and Woodruff shows that for any streaming algorithm in the turnstile model (where the stream consists of insertions and deletions of elements) there exists an algorithm that works by only maintaining a linear sketch and uses only slightly more space. So to prove a space lower bound in the turnstile model it is (up to some logarithmic factors) enough to prove a space lower bound for linear sketches. These can be easier to prove, for example by proving a communication lower bound in the simultaneous communication model rather than in the one-way model, or by more directly working with the linear structure of the sketch: check the paper for a lower bound on the space complexity of frequency moments proved this way.


Certainty of mutual confirmation over faulty channels?

This is known as The Two Generals' Problem (among other, similar names).


The entry in the complexity zoo is surprisingly detailed; it claims that
NLOGLOG = co-NLOGLOG in the paper

  Nondeterministic computations in sublogarithmic space and space constructibility, Viliam Geffert, SIAM Journal on Computing, 1991.

But after a brief reading, I do not see any claim about the fact that NLOGLOG is closed under complement; maybe a deeper look is needed.
And the main result they have is that there are no nondeterministic fully space-constructible unbounded monotone increasing $s(n)$ functions for $s(n) = o(\log n)$. It is known that if such functions exists, then

$\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$.

And in the conclusion the author claimed that " ...this main separation problem remains open. "

As @chazisop said, the relations of these low-level complexity classes are depended on the models, and it is stated in the entry of the zoo that

  "There are several possible definitions of this class; the most common is the class of languages which can be computed in space O(log log n) by a deterministic Turing machine with two-way access to the input. "

Which is coincident to your definition and also the paper's.


$ACC^0$ is a natural complexity class.

1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$.

2) Recently, Hansen and Koucky  proved  a beautiful result that poly-sized constant width planar branching programs are exactly $ACC^0$. Without the planarity condition, we of course get Barrington's result characterizing $NC^1$.

So the difference between $ACC^0$ and $NC^1$ is group-theoretic on one hand and topological on the other.

Added: Dana, a simple example of a solvable group is $S_4$, the symmetric group over elements. Without getting into details, any solvable group has a series whose quotients happen to be cyclic. This cyclic structure gets reflected as mod gates while building a circuit to solve word problems over the group.

On planarity, one would like to believe that planarity may impose restrictions/bottlenecks in the flow of information. This is not always true: for example, variations of planar 3SAT are known to be NP-complete. However, in smaller classes, these restrictions are more "likely" to hold.

In similar vein, Wigderson showed NL/poly=UL/poly using the isolation lemma. We do not know how to derandomize the isolation lemma over arbitrary DAGs to get NL=UL, but we know how to do so for planar DAGs.


Huffman Tree Depth, Is there any theory?

I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with different lengths. But there has been some related theory on lengths of Huffman codes:

Length-limited Huffman coding is a variant of Huffman coding where you are not allowed to use codewords longer than a given threshold. One can construct an optimal length-limited code in time $O(nL)$ where $n$ is the number of items and $L$ is the length bound; it is unknown whether this can be improved to match the time of unrestricted Huffman coding. See Larmore and Hirschberg, "A fast algorithm for optimal length-limited Huffman codes", JACM 1990, and Turpin and Moffat, "Practical length-limited coding for large alphabets", Computer J. 1995.

The length-limited problem was introduced earlier by Gilbert, "Codes based on inaccurate source probabilities", IEEE Trans. Inf. Th. 1971, who also showed that it is possible to restrict the length to log_2 n + (log log n)^{1+o(1)} while increasing the expected length by at most one. In "Restructuring ordered binary trees", J. Alg. 2004, Evans and Kirkpatrick write that restricting the length more strongly, to ceiling(log_2 n)+1, can force the expected length increase to be arbitrarily close to one. Evans and Kirkpatrick show that this strong length restriction can be obtained, even for alphabetic codes, with an expected increase in length of two.


A reading list on experimental algorithmics

Probably the single most important guide to experimental algorithmic is David Johnson's article on how to do it, which also has lots of references.
http://www2.research.att.com/~dsj/papers/experguide.pdf


Optimal random bits complexity for universal hashing

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.


Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

The key observation is that $f$ is not represented by any CNF but by a CNF where all clauses have $n$ literals with distinct variables where $n$ is the number of variables.

It is easy to see that such a CNF exists. Indeed, let $S$ be the set of solutions of $\neg f$. Each solution $s \in S$ can be seen as a conjunction of $n$ literals. For example, $s = \{x=0, y=1, z=0\}$ may be seen as $\neg x \wedge y \wedge \neg z$. Thus $\neg f = \bigvee_{s \in S} s$ and then $f = \bigwedge_{s \in S} \neg s$ which is a CNF formula.

Now this is important since the clauses of this CNF, let's call it $F$, are  in one to one correspondance with assignments of the variables: to each clause $\neg s$ of $F$, we associate $s$, the only assignment that does not satisfy the clause. For instance, the only way not to satisfy  $\neg s = x \vee \neg y \vee z$ is $s=\{x=0, y=1, z=0\}$. Thus, given an assignment, at most one clause of $F$ is not satisfied.

Now there is still something to explain. The authors claim that we can assume $m \equiv 1 \mod 3$ wlog. That is not completely true since we cannot grow the number of clauses artificially and still have the previous property. However, for the sake of their argument, it is enough to add trivial clauses such a $x \vee \neg x$ that always evaluate to $1$.


Speed-up of universal computation by caching

Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P_i)$ halts in at most $2^j$ steps then $V(P_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. This means that if $U(P)$ halts in $t$ steps then $V(P)$ halts in about
$$(2^{|P|}+\log t)^2\leq \max(4\cdot 2^{2|P|},4(\log t)^2)$$
steps. But $(\log t)^2=o(t)$.


What are some real world applications for genetic algorithms?

The optimizer in relational databases. Examples are PostgreSQL and H2; other databases most likely also use a genetic algorithm. The problem is: selecting the best query plan (the one with the lowest estimated cost) is NP-hard. The fitness test is the estimated cost.


The posting on MathOverflow tells how to go from a small number of independent Uniform[0,1] random variables to a larger number of pairwise-independent Uniform[0,1] random variables. You can of course go back and forth between Uniform[0,1] and Gaussian by inverting the CDF. But that requires numerical analysis as the CDF is not closed-form.

However, there is a simpler way to from Gaussian to uniform. Given two independent Gaussians $X_1, X_2$, the angle $\arctan(X_1/X_2)$  is uniform in the range $[0,2 \pi]$.

Similarly, the Box-Muller method transforms two independent Uniform[0,1] variables into two independent Gaussian random variables.

Using these two transformations, you consume two Gaussians to produce a uniform or two uniforms to produce a Gaussian. So there is only a factor of $O(1)$ in the sampling efficiency. Furthermore, no inversion of the Normal cdf is required.


Modal logics axiomatised with nesting depth one which are unlikely to be in PSPACE?

I just realized that there is a nice solution to your problem, if you are willing to consider linear logic as your ambient logic instead of intuitionistic or classical logic. As is well-known, linear logic with the exponential modality $!A$ is not decidable. Furthermore, the exponential is a comonad featuring the duplication axiom $!A \multimap !!A$, which is evidently an axiom of nesting depth 2.

(I got this far right away, and then I got stuck -- which is why this answer is so late.)

However, I just realized that in implicit complexity, people modify the exponential $!A$ of linear logic to more precisely control the space and time usage of cut-elimination. Critically, all systems for doing so eliminate the duplication axiom! As a result, you can choose a system for which normalization likely goes past PSPACE (e.g., Elementary Affine Logic is as strong as elementary bounded Turing machines), and then the axiomatization of that will be unlikely to be in PSPACE, since that would imply that you could find cut-free proofs quickly.

Link: Ugo dal Lago and Simone Martini, Phase Semantics and Decidability of Elementary Affine Logic


Since the quantum query complexity typically denotes the bounded-error quantum query complexity, there's some ambiguity. A more precise question could be: "What is the quantum query complexity to decide nontrivial monotone graph properties with probability at least $2/3$?".

A natural example in this context is the monotone property of having a single edge. Since Grover search is optimal for this problem, its bounded-error quantum query complexity seems like the natural candidate.

update (2020 May 5):

Since the monotone property of connectivity has quantum query complexity $\Theta(n^{3/2})$ (see here), and the property of having a single edge has quantum query complexity $\Theta(n)$, there is actually no hope for a simple function $f(n)$ only dependent on $n$ to fully characterize the quantum query complexity of monotone graph properties (even up to constants). This is in contrast to what is conjectured for the classical deterministic query complexity.

Alternatively, one could ask about "the minimum possible quantum query complexity of a nontrivial monotone graph property" (as formulated in the paper by Aaronson, Ben-David, Kothari, and Tal). In this case, a simple function of $n$ might still be possible, and the complexity of having a single edge again seems like a natural candidate.

update 2 (2020 May 5):

Answering the updated question, a possible candidate for the additional property would be the (worst-case) certificate size $c$ of the property. A corresponding candidate for the query complexity would then be $\Theta(\sqrt{n^2 c})$, which describes the quantum query complexity when using Grover search on a graph that is empty apart from a single certificate (i.e., a minimal graph having the property). This would be consistent with the examples of having a single edge ($c = 1$) and connectivity ($c = n-1$).

Here's some other consistent examples:

Nonplanarity. Certificate size $c \in \Theta(n)$ (consider the graph obtained by replacing all edges of a $K_5$ graph by paths of length $\Omega(n)$). The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
Having more than $\binom{n}{2}/2$ edges. Certificate size $\binom{n}{2}/2+1$. The quantum query complexity is $\Theta(n^{3/2}) = \Theta(\sqrt{n^2c})$ (link).
Triangle finding. Has certificate size $c = 3$. The current best upper bound is $\tilde{O}(n^{5/4})$ (Le Gall), but the best lower bound is only $\Omega(n) = \Omega(\sqrt{n^2 c})$.$^1$

$^1$At the end of his QIP talk (link), Le Gall does mention that he would be "surprised" if the quantum query complexity were $\tilde O(n)$.


What is the computational complexity of Acyclic Joins?

It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values.

However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the projection of the results on the variables you still need to finish the computation. In your case, you inductively compute a relation $B_i = \Pi_{A_i,A_{i+1}}(R_1 \bowtie \dots \bowtie R_i)$. In the general case, you compute it inductively on the join tree in a bottom-up fashion and you only keep the variables that appears in the bag you are visiting. More details on this approach could be found in [1] or [2, Chapter 6].

Now you can also enumerate all tuples in the result with a polynomial time delay between two solutions. Even though you need an exponential time to enumerate all solutions, you can guarantee to have enumerated $t$ solutions after a time  $t \times poly(n)$. You can even sometimes (with extra structure) guarantee a constant delay between two solutions. You can read more in [3] or in [4] for a more generic approach.

There is a lot more you can do on acyclic conjunctive queries in polynomial time such as counting the number of tuples in the result [5] (you need to be quantifier free however, or it becomes #P-complete again). One way of uniformly explains these tractability results is through the lens of factorized databases [6]. The paper is quite dense but the main idea boils down to the following: given an acyclic conjunctive query $Q$ and a database $D$, you can compute in time linear in the size of $D$ and $Q$, a circuit computing $Q(D)$. This circuit only usess Cartesian products gates and disjoint union gates and its input are small relations. Given such a circuit, you can then show that it is tractable to enumerate the tuples of the relation it represents (you can also count and do many other interesting things).

References

[1] Flum, Jörg, Markus Frick, and Martin Grohe. "Query evaluation via tree-decompositions." Journal of the ACM (JACM) 49.6 (2002): 716-752.

[2] Libkin, Leonid. Elements of finite model theory. Springer Science & Business Media, 2013.

[3] Bagan, Guillaume, Arnaud Durand, and Etienne Grandjean. "On acyclic conjunctive queries and constant delay enumeration." International Workshop on Computer Science Logic. Springer, Berlin, Heidelberg, 2007.

[4] Idris, Muhammad, Martín Ugarte, and Stijn Vansummeren. "The dynamic yannakakis algorithm: Compact and efficient query processing under updates." Proceedings of the 2017 ACM International Conference on Management of Data. 2017.

[5] Pichler, Reinhard, and Sebastian Skritek. "Tractable counting of the answers to conjunctive queries." Journal of Computer and System Sciences 79.6 (2013): 984-1001.

[6] Olteanu, Dan, and Jakub Závodný. "Size bounds for factorised representations of query results." ACM Transactions on Database Systems (TODS) 40.1 (2015): 1-44.


Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

I think the notion you're looking for is differing-inputs indistinguishability obfuscation(diO), or originally called extractability iO:
https://eprint.iacr.org/2013/650.pdf

The definition of diO tells us: if there's a non-uniform PPT adversary that can distinguish the obfuscations of two circuits with "almost same" functionalities Obf($C_1$) and Obf($C_2$), then there exists a non-uniform PPT extractor that can extract an input(witness) $x$ where $C_1(x) \neq C_2(x)$.
(the formal definition is on page 11)

If there are only polynomially many inputs where their outputs are different evaluated on $C_1, C_2$, then the standard iO definition also implies diO, using a binary search argument on the input space.

If there are negligible(in ratio) but exponentially many different outputs , then diO is a stronger assumption than standard iO. There are some negative results on the possibility of its existence in certain cases:

https://eprint.iacr.org/2016/162.pdf

https://eprint.iacr.org/2013/860.pdf


Dorit Dor and Uri Zwick ("Selecting the Median", SODA 1995, pp 28-37) use green factories and analyze their amortized production costs.


List of NP-hard problems, where there is active research in practical heuristics

MaxSAT - people actually care about this because SAT solvers are so well-developed that often the best route for your favorite NP optimization problem in practice is to reduce it to MaxSAT and then apply one of the well-known solvers. Check out the SAT competition for benchmarks etc.

Clique-finders get used in computational biology and combinatorics, and the heuristic algorithms are shockingly good, as I recall.

Vast portions of Operations Research is devoted to algorithms, including heuristic ones, for solving cases of integer or mixed-integer linear programming.


Is sorting pairwise distances as hard as sorting arbitrary points?

This is an open question even for one-dimensional point sets.  In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.


What are the recent TCS books whose drafts are available online?

Several TCS books by Now Publishers can be found in drafts:

Foundations of Cryptography– A Primer by Oded Goldreich. This is a summarized version of his famous two-volume book on cryptography. (The draft of the two-volume version can be found in Robin's answer.)
Data Streams: Algorithms and Applications by S. Muthukrishnan.
Mathematical Aspects of Mixing Times in Markov Chains by Montenegro & Tetali.
Pairwise Independence and Derandomization by Luby & Widgerson.
Average-Case Complexity by Bogdanov & Trevisan.
A Survey of Lower Bounds for Satisfiability and Related Problems by Melkebeek.
Algorithms and Data Structures for External Memory by Vitter.
Probabilistic Proof Systems: A Primer by Goldreich. Again, this is a summarized version of a part Goldreich's book Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
The Design of Competitive Online Algorithms via a Primal-Dual Approach by Buchbinder & Naor.
Spectral Algorithms by Kannan & Vempala.
On the Power of Small-Depth Computation by Viola.
Algorithmic and Analysis Techniques in Property Testing by Ron.
Arithmetic Circuits: A Survey of Recent Results and Open Questions
by Amir Shpilka and Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039

In addition, drafts of several Springer books on "Information Security and Cryptography" can be found online:

Cryptography in Constant Parallel Time by Applebaum.
A Study of Statistical Zero-Knowledge Proofs by Vadhan.
Locally Decodable Codes and Private Information Retrieval Schemes by Yekhanin.
Concurrent Zero Knowledge by Rosen.


Presenting work-in-progress (slides now available)

It sounds from your question (the use of the word 'willing') that one deterrent is the unwillingness of students to present. Since it's in your research group, I'm assuming that being scooped is not something they need to worry about :). So the real reason is that they feel afraid: of seeming clueless, of not knowing the answer and having someone else find it in 5 minutes after they start presenting, or of people deeming their ideas to be uninteresting.

In other words, the imposter syndrome.

One of the most important transitions a grad student has to go through is the point when they realize that they can actually play in the research world, and make contributions of their own. This often comes when their first paper gets published, but can also happen the first time they talk to a "senior" researcher and realize they know more than that person about their topic of interest, or even the first time they prove a brand new result.

One advice for you might be to give such talks of your own, where you show "how the sausage is made" and show how ill-formed your own initial ideas might be. That gives them a model to work with. At the very least, you can give them examples of the winding path a research project takes.

A second advice you can give them is to remember that most likely no one knows as much about their problem as they do. They may not internalize this just yet, but repeated reminders might help :)

When they actually give the talk, Sylvain's advice is very good: however I don't think the 1/3 rule applies here since in your research group there are probably no outside experts and probably no generic audience. But I'll mention a line I heard yesterday in the context of journalism, but which applies very well for talks by inexperienced people:

  Don't overestimate the audience
  knowledge, and don't underestimate
  their intelligence.

In other words, provide all the background they need, and more. But don't prove teeny little lemmas from scratch.


Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in

  Pierluigi Crescenzi and LucaTrevisan:
  "Max NP-completeness made easy"
  Theoretical Computer Science 28, (1999), Pages 65-79


How to determine whether a proof requires "higher-order reasoning techniques"?

Briefly, every theorem stated in first-order logic has a first-order proof.

In his book "An Introduction to Mathematical Logic and Type Theory", Peter B. Andrews develops both first-order logic and a system of higher-order logic Q0, which is generally considered to be the theory basis of modern higher-order provers. (See the introduction to the HOL logic for example.)

For Q0 and similar systems, Andrews shows that the higher-order logics he describes can be considered as conservative extensions of first-order logic and writes (second edition, p. 259) that, "In summary, every first-order theorem of type theory has a first-order proof."

Given your practical concerns though, I also quote the following paragraph:

"However, some theorems of first-order logic can be proved most efficiently by using concepts which can be expressed only in higher-order logic. Examples may be found in [Andrews and Bishop, 1996] and [Boolos, 1998, Chapter 25]. Statman proved [Statman, 1978, Proposition 6.3.5] that the minimal length of a proof in first-order logic of a wff of first-order logic may be extraordinarily longer than that the minimal length of a proof of the same wff in second-order logic. A related result by Godel [Godel, 1936] is that in general 'passing to the logic of the next higher order has the effect, not only of making provable certain propositions that were not provable before, but also of making it possible to shorten, by an extraordinary amount, infinitely many of the proofs already available'. A complete proof of this may be found in [Buss, 1994]."


It appears the problem is in L by [EJT10] and thus L-complete under $\text{NC}^1$ reducibility by [CM87]. See page 2 of [EJT10]:

  Applying Theorem I.3 to the formula $\phi(X)$ expressing that $X$ is a
  simple path from $s$ to $t$ shows that the problem $\{(G,s,t) \text{ }
  | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$
  lies in L

Actually this result applies to all problems on bounded treewidth graphs which can be formulated in monadic second-order logic in L.

[EJT10] Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987)


Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

If $\mathrm{NTIME}(n) \supseteq \mathrm{DTIME}(2^{n/2000})$ (where NTIME and DTIME uses constant factor in the big-oh) then for all time-constructible $t\geq n$, we have that $\mathrm{NTIME}(t) = \mathrm{DTIME}(2^{\mathrm{O}(t)})\supsetneq \mathrm{DTIME}(2^t)$ to the contrary to your quest. So, in that case, requiring the NTM to read a tape of nondeterministic guesses are essential to separate these classes.

And it is still open that $\mathrm{NTIME}(n) = \mathrm{E}$.

Given a language $\mathrm{L}\in \mathrm{DTIME}(2^{\mathrm{O}(t)})$ decided by a TM running in time $2^{ct}$ where $c$ is some constant, construct the language $\mathrm{L}_\mathrm{pad} = \{x10^{2000*ct-1-\vert x\vert}\vert x\in \mathrm{L}\}$. Clearly, $\mathrm{L}_\mathrm{pad}$ can be decided by a TM running in time $\mathrm{DTIME}(2^{n/2000})$, i.e. $\mathrm{L}_\mathrm{pad}\in \mathrm{DTIME}(2^{n/2000})$. By our assumption, we have that $\mathrm{L}_\mathrm{pad}\in \mathrm{NTIME}(n)$, i.e. there exists an NTM deciding $\mathrm{L}_\mathrm{pad}$ in non-deterministic time $dn$ for some constant $d$. Now, we describe the NTM for $\mathrm{L}$. When given an input dtring $x$, our NTM for $\mathrm{L}$ first pads it up to length $2000*ct$ and then run the $\mathrm{NTIME}(n)$ NTM for $\mathrm{L}_{pad}$. Clearly, our NTM runs in non-deterministic time $cdt$, putting $\mathrm{L}$ inside $\mathrm{NTIME}(t)$.


Quantum algorithms based on transforms other than Fourier transforms

I would like to add some more references to Scott's comment:

Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of quantum algorithms for non-Abelian hidden subgroup problems (HSPs).

Clebsch-Gordan transforms were used by Greg Kuperberg and Oded Regev to solve the dihedral HSP in subexponential (yet superpolynomial) time. These quantum algorithms are not efficient, but they have better query complexity than classical algorithms.
Dave Bacon also used Clebsch-Gordan transforms to solve the hidden subgroup problem (HSP) over the Heisenberg group  $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$ in polynomial time. I can recommend that paper because it is quite clear.

I am also writing to add that we should not forget that both quantum Fourier transforms and Clebsch-Gordan transforms are not always indispensable, even if they can be very useful.

In Shor's algorithm (or even in quantum phase estimation) the Fourier transforms can be replaced with Hadamard tests, therefore only using Hadamard gates instead of Fourier transforms: this trick is due to Kitaev and you can read about it here.
There is yet another efficient algorithm for the HSP over $\mathbb{Z}_p^2\rtimes \mathbb{Z}_p$, by Bacon, Childs, Van Dam, that does not use Clebsch-Gordan transforms. Instead, the algorithm uses a certain type of powerful POVM known as the Pretty Good Measurement.

Of course, this list is probably  incomplete. I hope someone will point out other results that have not yet been mentioned.


What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

(Azoury and Warmuth, 2001) have shown that minimizing the KL-divergence between two exponential family distributions is the same as minimizing the Bregman divergence that corresponds to their cumulant function, i.e.

$KL(P_{F,\theta_1} || P_{F,\theta_2}) = D_F(\theta_1 || \theta_2)$

For $f = \nabla F$, and $F^*$ the Fenchel conjugate of $F$, we get the following nice relationship for Bregman divergences:

$D_F(\theta_1 || \theta_2) = D_{F^*}(f(\theta_2) || f(\theta_1))$

See Lemma 4 in this paper, which also has references to other work that discusses this connection. The above can also be written without the $f$ transfers on $\theta$. So, there is a simple relationship between these two losses, i.e. between minimizing with $\theta_1$ as the first argument or with $\theta_2$ as the first argument.

Also, I feel I should mention that we can generally talk about maximizing likelihood in terms of Bregman divergences and P(data | params), rather than KL-divergences on densities. The above linked paper shows that

$\max_\theta log \ p(data | \theta) = \min_\theta D_F(\theta | data)$

The relationship above where we swapped the two variables of interest in the loss has a correspondence here:

$p(\theta | data) \ p(data) = p(data | \theta) \ p(\theta)$

giving

$log \ p(\theta | data) = log \ p(data | \theta) + log \ p(\theta) - log \ p(data)$

Since we typically do not put a prior on data, we find that maximizing the likelihood of $p(\theta | data)$ (typically called the MAP estimate) corresponds to maximizing likelihood of the data with a prior on the parameters. Correspondingly, maximum likelihood is like the MAP estimate, with a non-informative, uniform prior on $\theta$.

K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. 2001


The question of truth in Presburger Arithmetic with bounded quantifier alternation has been answered with quite some precision by Reddy and Loveland:

C.R. Reddy & D.W. Loveland: Presburger Arithmetic with Bounded Quantifier Alternation.

The paper may be found here (sorry for the ugly link). Their main result is stated as follows:

  The membership in $\mathrm{PA}(m)$ (where $m$ is the number of quantifier alternations) of length $n$ can be decided within space
  $$ 2^{dn^{m+4}}$$
  and in (deterministic) time
  $$ 2^{2^{en^{m+4}}}$$
  Where $d$ and $e$ are constants.

Taking $m=2$, this seems to give at least an upper bound on what you want, and I suspect it's not far from tight, as you have almost full Presburger atomic formulas "at the root".


What are the best possible time/error tradeoffs for approximate solution of linear programs?

Perhaps this reference will be relevant to your question.

Grigoriadis M., Khachiyan L. A sublinear randomized approximation algorithm to matrix games// Oper. Res. Lett. 1995. V. 18. No 2. P. 53-58.

The algorithm therein is 1) randomized 2) the error is ADDITIVE, but 3) is sublinear (you need to check only tiny fraction of the input to find solutiom with high probability).

Sergey


How to define list zipping categorically/inductively?

This complication is the same as in the definition of the Church predecessor function. We need to take the tail of a list, but we only have a folding operation given by (weak) initiality, which does not directly provide access to that, so we need to rebuild the tail from the right end.

It is the easiest to write the solution in a lambda calculus with products, exponentials and foldr for lists, witnessing weak initiality. In Haskell:

-- foldr :: (a -> b -> b) -> b -> [a] -> b

-- matching on whether a list is empty or non-empty
split :: [a] -> b -> (a -> [a] -> b) -> b
split as b f = fst (foldr (\a (b, as) -> (f a as, a:as)) (b, []) as)

zip :: [a] -> [b] -> [(a, b)]
zip = foldr (\a hyp ys -> split ys [] (\b ys -> (a, b): hyp ys))
            (\_ -> [])

With split we can branch on whether a list is empty or non-empty, and we rebuild the tail of the list from the end. zip can be translated back to cartesian closed categories with list objects, but of course a precise definition in that setting would be much less readable, because of the mandatory point-free definitions.


What is a good Category Theory-Domain Theory dictionary?

The best resource for this is Abramsky and Jung's handbook chapter. I recall they had a table which cross-referenced various constructions and categories of domains, with the entries saying whether the construction worked in that category and what properties it had. However, properties of arrows like being a monic tended not to have terribly slick characterizations, because the availability of flat domains tends to ensure that they are often not terribly different from their set-theoretic counterpart. OTOH, properties that make some use of the order structure (like being an embedding-projection pair) tend to have fairly pretty characterizations.

A minor point to watch out for is that there are actually two definitions of CPO in common use! Consumers of domain theory (like me) often prefer to work with omega-chains, since chains are pretty concrete objects; whereas producers of domain theory (like, er, your advisor) tend to prefer to work with directed sets, which are more general and have better algebraic properties. (Offhand I'm not sure if restricting to directed sets having countable base is equivalent to the omega-chain condition.)

Something I found very helpful in building this kind of dictionary is to work through the solution of recursive domain equations in some category of things that aren't exactly domains. Two good choices are categories of PERs (eg, in models of polymorphism) and presheaves (eg, for name allocation). Metric spaces are another possibility, but I found them to be too similar to domains to help me build intuition.


Generating a language from a given grammar

Since you want to generate -all- words of a given length, it really doesn't matter if it's stochastic/probabilistic or deterministic, you just want to see if a word is possible (the following method should be modifiable to also compute the probability of any given word.

Two methods, one theoretical and cool and programmable in a couple lines of inscrutable Mathematica, or a practical efficient algorithm which I'd rather not both to code in ML/Haskell.

you can interpret a (context free) grammar as defining a set of polynomials equations (the way the theory works, you just can't do this for context-sensitve or worse grammars). Use Groebner bases to simplify the system, and solve for the generating function, from which you can then extract the number of -derivations- (we don't now if it's unambiguous) of words of a given size. Yes, that is a short sentence to describe the work you'd have to do, and that's not even from scratch. (For a regular grammar, Groebner bases is kind of a jack hammer when all you need is the small jeweler's hammer of the Kleene algorithm to generate the regular expression for the language from the right linear grammar converted to NFA. And then the generating function can (almost!) be read straight off from the regexp.
a way to implement the above, bypassing all the intensive algebraic manipulation, don't bother with all that fix-point computation (that's really what the algebraic manipulation is doing for you). Instead, create a vector of length $n$ for each variable, set them all to 0's. Then operate on each rule thinking of union as vector addition and concatenation as vector convolution (if A <- B C, then $a_k = \sum a_j b_{k-j}$, and the base case is a terminal which is $\langle 0,1,0,0,0,0... \rangle$. (this method might work for CSGs but I think it takes longer to converge).

I'm sure there's an easier way to do it in a straightforward manner, but you know how it is, sometimes the complicated big guns that take a steep learning curve to manage are some how more familiar and easier to think about than an obvious simple solution.


Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains

I think I understand your difficulties, indeed if you consider just a programming language both a denotational semantics and a term transformation (into another language) are nothing but mappings of syntactic elements of the given language in mathematical objects (elements of a domain in the first case, terms of the language in the second case).

Notheless differences between these two semantics start to arise if you put an operational semantics in your programming language and so you want that the denotational semantics and term transformations are compatible with this operational semantic.

In the first case you would like that denotation of terms/programs that compute the same results have the same denotation, hence the denotational semantics should associates to operational convertible terms the same denotation.

In the second case you would simply like that the term transformation maps terms/programs in such a way to preserve the derivations (if you reguard terms and reduction/derivations respectively as objects and morphisms of a category you can say that a term transformation should be a functor).
In the first case we lost information about the reduction between terms in the second case we preserve it.

In the first case semantically equivalent terms are mapped in the same denotation in the second they are mapped just in operationally equivalent terms but the term translation does not guaratee that equivalent terms are mapped in the same term (and usually that's not the case).

Denotational semantics  allows to easily find different terms, supposing that the denotation-mapping is easily computable, in order to distinguish two programs we just need to compute the denotation an see if they are different values.
Nonetheless in this way we lost information about the reductions (computations of our operational semantics) which are instead preserved by the term transformations.

I hope this helps.


Basically you have been mislead by the errors in the proof in the edition of the paper you are referring to. Please refer to the published edition on "Distributed Computing'1995".

  There's almost certainly a typo/misprint when they refer to the $(s[q] \bot 1)$st write.

Yes, it is a typo. It should be "the $(s[i] - 1)$st write" (not $(s[j] - 1)$st either)

  "Let $\hat{w}$ be the $(s[j] - 1)$st write." Even assuming $s[j]−1$, what if $s[j]$ is 0 or 1?

It should be "Let $\hat{w}$ be the $(s[i] - 1)$st write."
By definition, $s$ is the timestamp of the write operation $w$ of process $i$. According to the rule of Write operation in Fig.3, we have $s[i] \ge 1$. The problem is what if $s[i] = 1$. Well, it seems that the authors have missed the edge case. Fortunately, it is obviously true that $t[i] = 0 = s[i] - 1$.

  Why does lemma 1 say that $ts(\hat{w}) \le ts(w)$?

$\hat{w}$ and $w$ are two consecutive write operations in process $i$ and $\hat{w}$ is the former one. According to the rule of Write operation in Fig.3, we have $ts(\hat{w}) \le ts(w)$. (Actually, we have $ts(\hat{w}) < ts(w)$.)

  Even if we assume $t[i] \ge s[i]−1$, why is this sufficient? Don't we need to show $s[i]=t[i]+1$?

Yes, you are right. That is exactly what are proved in the DC edition.


The only other ones I know of are also isomorphism problems: group isomorphism and ring isomorphism.  The $coAM$ protocols for both of these are essentially the same as for graph isomorphism.

Group isomorphism reduces to graph isomorphism reduces to ring isomorphism.

Interestingly, unlike (what is known for) groups and graphs, for rings, determining whether a ring has a nontrivial automorphism is in $P$, while finding a nontrivial automorphism is equivalent to factoring integers.  See Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems. Computational Complexity 15(4): 342-390 (2006).


Hyperspherical nature of K-means and similar clustering methods

K-means tends to create compact clusters, which means that geometrically, the distance between every two points is small.

K-means can create clusters which are ball-like if you use $L_2$ norm, pyramid if you use $L_1$ and hypercubes if $L_\infty$ is used.

As opposed to that there are clustering algorithms which first project the data into lower dimension (such as spectral clustering), which means not all of the points in a cluster has to be close, but rather "connected" via other points in the original space, which will make them close after the projection.

This allow you to find very nice looking clusters, such as this and that.


This is meant more as a comment than as a solution, but is a bit too long to fit in the comment box. There is a bit of handwaving and ignoring of small factors, but I can formalize the work below further if requested.

Here's a heuristic reason why (a) might be difficult to approximate within a small factor.

Consider the random-in-random PLANTED DENSE SUBGRAPH problem, which one to reliably distinguish between the Erdos-Renyi graph $G(n,p)$ and the graph $G(n,p)$ with a planted $G(n',p')$ for certain values of $n,n',p,p'$. It is a difficult problem -- conjectured hard by some -- to do this in polynomial time for $p = \frac{1}{n^{1/2}}$, $n' = n^{1/2}$, $p' = \frac{1}{n^{1/4 + \epsilon}}$. That is, it's hard to distinguish a "pure" $G(n,1/\sqrt{n})$ graph (where each induced subgraph of size $\sqrt{n}$ has average degree near $1$) from instances where some subset of $\sqrt{n}$ vertices has so many edges planted between them that the average degree is roughly $n^{1/4 - \epsilon}$.

In such instances, there's quite a large gap in the maximum edge densities in subgraphs of size at least $\sqrt{n}$. In particular, while the planted portion of the planted-instance graph has edge density roughly $\frac{1}{n^{1/4+\epsilon}}$, just about any size $\sqrt{n}$ (or higher) subgraph of the non-planted $G(n,1/\sqrt{n})$ graph will have edge density about $1/\sqrt{n}$, a gap of roughly $n^{1/4 - \epsilon}$.

Any approximation algorithm with a stronger guarantee than $n^{1/4 - \epsilon}$ can thus be used to solve a conjectured-hard class of instances of Planted-DkS.


Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

As per the comment, $K(x|y) \leq K(x|y^*) + O(1)$. Now denoting the first metric (with the *) by $d_1$ and the second by $d_2$, we have

$\displaystyle \begin{align*} d_2(x,y) &= \frac{\max \left \{ K(x|y), K(y|x) \right \} }{\max \left \{ K(x), K(y) \right \}} \\ &\leq \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \} + O(1) }{\max \left \{ K(x), K(y) \right \}} \\ &= d_1(x,y) + O(1/K) \end{align*}$

where $K = \max \left \{ K(x), K(y) \right \}$

All of the theorems in the paper give the metric inequalities and universality claims up to an additive factor of $O(1/K)$, so this fits.


Reference request: An algebraic characterisation of LTL[XF]-definable word languages

An algebraic characterisation of the restricted temporal logic (fragment using only next and eventually, but not until) is given in [1].
The expressive power of this fragment is the set of regular languages whose syntactic monoid are locally $\cal L$-trivial.
I am not sure of the result you are looking for, but this article probably contains enough material to help you.
[1] J. Cohen, D. Perrin and J.-É. Pin, On the expressive power of temporal logic for finite words, J. Comput. System Sci. 46 (1993), 271-294.


Are there alternatives to using polynomials in defining the different notions of efficient computation?

From the very beginning $P$ has drawn flak for allowing high degree polynomials to count as efficient (Edmonds essentially introduced $P$ to argue that his $O(n^4)$ matching algorithm should be considered efficient, but for computers in 1965 $O(n^4)$ was definitely not efficient), but there are very good reasons that the definition has stuck:

Polynomials have nice closure properties.  If $O(n)$ is efficient, and we allow an efficient algorithm to call an efficient subroutine a reasonable number of times, we are forced to conclude that $O(n^2)$ is efficient too, and iterating this reasoning leads us to conclude that $O(n^c)$ is efficient for all $c$ if we want to avoid a totally arbitrary cutoff.
$P$ is robust to changes in the underlying model of computation.  Complexity theory is about what problems are solvable in some reasonable model of computation.  There are a huge variety of equivalent models of computation that can simulate one another in polynomial time (Turing machines, register machines, stack machines, and other stranger models) and tons of variations (how many tapes does your Turing machine have?  How many states?), and we have no real reason to favor one over another.  If we design an algorithm for a RAM but need to preserve our definition of efficient from model to model, then we need to allow polynomial overhead for simulation.  Aliens may well have computer totally different from anything we have imagined, but their definition of $P$ would be the same.
$P$ is robust to technological advancement.  History has shown that computer science research that is not future-proof will quickly lose its relevance.  Over time, as computing power has increased, the definition of "truly efficient" has expanded to include larger polynomials, but $P$ has remained relevant.
In practice, problems requiring high degree polynomials are actually rarely an issue.  Generally, the difficult step is getting from exponential time to some polynomial, and once we have an algorithm in $P$ it is relatively easy to reduce the degree to something small.  There is an old joke that I have heard in several talks: "every time someone proves a problem is in $P$ Bob Tarjan makes it linear."


The problem is at least as hard the maximum edge-disjoint paths problem (MEDP) since we can set $d(i) = 1$ for each pair. The approximability of MEDP has been investigated extensively and in particular it is known that MEDP in directed graphs is hard to approximate to within a factor of $m^{1/2-\epsilon}$ (technically it is $n^{1/2-\epsilon}$ since the graphs are sparse). This was shown in a paper of Guruswami etal. http://www.sciencedirect.com/science/article/pii/S0022000003000667. Roughly at the same time there was another paper by Ma and Wang established hardness of $2^{\log^{1-\epsilon} n}$ for acyclic graphs. More recent work by Chuzhoy etal showed hardness results even with congestion allowed; my understanding is that the hardness holds even for instances that are acyclic and these results are stronger than the one by Ma and Wang, however, one should look more carefully at the paper to make sure or ask the authors.


Lower Bounds for Frege and Extended Frege

1, 2, 4) The best known lower bounds on extended Frege are the same as for Frege: linear number of lines, and quadratic size. This applies e.g. to the tautologies $\neg^{2n}\top$ (basically, any tautology that is not a substitution instance of a shorter tautology, and whose sum of lengths of all subformulas is quadratic). This is proved in Krajíček’s Bounded arithmetic, propositional logic, and complexity theory for Frege systems, but the argument works for extended Frege systems as well.

3) It’s not entirely clear to me how exactly you define tree-like extended Frege (there has to be a mechanism allowing reuse of extension axioms), but I am not aware of any superlinear lower bounds on the number of lines in treelike Frege or extended Frege systems.


A partial answer if TM runs in $o( |x| \log |x|)$

If TM4 is a 4-symbols TM (with alphabet $\Sigma_4 = \{\epsilon,0,1,2 \} $ ) that computes $f:\{0,1\}^* \to \{0,1\}$, i.e. decides language $L = \{ x | f(x) = 1 \}$ in $(o( |x| \log |x|))$

One tape deterministic linear-time complexity is $1DLIN = 1DTime(O(n))$

Hennie proved (1) that $REG = 1DLIN$
Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$

So $L$ is regular, and is obviously still regular over alphabet $\Sigma_3 = \{\epsilon,0,1\}$

So there is a DFA that decide L and uses only symbols in $\Sigma_3$. A one-tape, 3-symbols TM3 can be built directly from the DFA and it decides L using the same unpadded input of the original TM4.

... you cannot build it directly from TM4, but TM3 exists.

If TM4 runs in $\Omega(n^2)$ then you can shift the input and make a direct conversion from TM4 to TM3.

As noticed in the comments the difficult case is when TM4 runs in $\Omega(n\log n) \cap o(n^2)$.

(1) Hennie, One-tape, off-line Turing machine computations (1965)

(2) Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy (1985)


Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

The footnote of my paper that you cite refers to a heuristic "argument" as well, at least, what we think was Kolmogorov's intuition -- the positive resolution of Hilbert's thirteenth problem.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

In particular, it was proved by Kolmogorov and Arnold that any continuous function on $n$ variables can be expressed as a composition of $O(n^2)$ "simple" functions: addition of two variables, and continuous functions on one variable. Hence, over the "basis" of one-variable continuous functions and two-variable addition, every continuous function on $n$ variables has "circuit complexity" $O(n^2)$.

It seems Kolmogorov believed there is a discrete analog, where "continuous in $n$ variables" becomes "Boolean in $n$ variables and poly$(n)$-time computable", and where the "basis" given above becomes two-variable Boolean functions.


Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

It depends on the precise model of computation you work within.  However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor.

Uniform algorithms

Let's look at uniform algorithms.  Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a constant amount of work (or a logarithmic amount of work).  Then any such algorithm must contain a loop or backward branch.

(Why?  Such an algorithm must work on inputs of all possible lengths.  The algorithm has finite length, say length $k$.  If there are no loops or backward branches, then this means that any execution of the algorithm must involve at most $k$ steps, where $k$ is fixed.  This means there exists $n$ large enough so that, when the input is $n$ bits long, the algorithm can't even read the entire input using $k$ steps of computation. Consequently, any such algorithm without loops cannot possibly be correct on all inputs.)

This doesn't seem useful for proving non-trivial lower bounds on the complexity of factoring.

Non-uniform algorithms

Non-uniform algorithms don't require loops.  In particular, if there is a non-uniform algorithm (possibly with loops) that takes $T(n)$ time on $n$-bit inputs, then there is a non-uniform algorithm without loops that takes $O(T(n)^2)$ time on $n$-bit inputs and has size $O(T(n)^2)$.

(Why?  Simply unroll all loops.  Since the algorithm takes $T(n)$ time, each loop will execute at most $T(n)$ times, so you can unroll it and make $T(n)$ copies.)

Other notes

Your question claims "there must be an if-then statement which tests if $1<x<n$, $x|n$ or any other mathematically equivalent test", but this claim is not justified and I don't think it is correct.  There could be algorithms that contain a loop with some other loop condition.  Also, your heuristic is clearly false.  The output of $\gcd(a_i,n)$ isn't anything like a uniformly distributed number from $\{1,\dots,n\}$.  So the direction you're taking seems like it is based on faulty premises and seems like a dead end.


Scott's normal form for $\exists y \forall x R(x,y) $

Your solution is correct. It suffices to see that the formulae $\exists{y} P(y)$ and $\forall{x} \exists{y} P(y)$ are equi-satisfiable, which allows you to put your formulae in the desired form.


The problem is at least NP-hard, by a reduction from 3-SAT.

First consider the problem of finding a path from the Start to the Exit of the following directed graph with the restriction that no path may visit all three (square) nodes of a clause:

For this graph, such a path only exists if the formula $(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$ can be satisfied. We can build such graphs for arbitrary formulas in 3-CNF, and finding such a path is NP-complete.

We transform these graphs to a switch network. For this we use three gadgets:

Every circle node and bidirectional edge becomes a Wire, forming the connections between switches.
Every directed edge becomes a One-way gadget consisting of a single switch (see below).
Every square node represents one of the three switches that are part of a Clause gadget (see below).

In the following illustrations, switches are drawn as two incoming arrows, one of which is dashed (disabled). The target direction is drawn with a black circle (such that the solid arrow must eventually be on the side of the circle).

Remark: We will use boldface to distinguish the Exit of the graph from exits of gadgets.

For the One-way gadget, entrance $A$ cannot be reached from exit $B$ until $B$ has been reached from $A$.
For the Clause gadget, entrances $X1$, $X2$ and $X3$ lead to exits $X1'$, $X2'$ and $X3'$, respectively.

Recall that for the original graph, finding a path that led to the Exit and did not visit all three square nodes of any clause was NP-complete.
Now consider the problem of reaching the Exit of the transformed graph without worrying about the target positions of the switches.

Observe that any path that is a solution for the original graph problem is also a solution for the transformed graph.
So assume a path for the transformed graph is not a solution for the original graph.
This may happen in two cases:

A One-way gadget is traversed in the unintended direction ($B$ to $A$).
A path traverses all three paths of some Clause gadget.

In the first case, the One-way gadget must have first been traversed in the intended direction, in which case the path might as well have avoided traversing it in the first place.

So consider the second case where the path traverses all three switches of some Clause gadget.
Then that gadget will have all its three switches flipped (see below). This is where we make use of the target positions.
Notice that the gray backbone of the Clause gadget can no longer be reached, meaning that the switches can no longer be directed to their target positions.
In this case, we say that this Clause gadget is unrecoverable.

It remains to show that for any solution of the original graph problem, the switches of the transformed graph can be placed in their target position.
For this, we make use of the fact that the Exit wire can only be reached when there is a solution, or some Clause gadget becomes unrecoverable.

To place switches in their target position, we can now add additional One-way gadgets from the Exit wire to the entrance of every existing One-way gadget, as well as to the three exit wires of all Clause gadgets.
Then, once the token reaches the Exit, all the additional One-way gadgets can be traversed (and thereby put in their target position), and also put the remaining switches in their target positions (unless there is an unrecoverable clause).
Finally, the token can return to the Exit and the puzzle is solved.

We should remark that Clause gadgets can only be recovered when entered from an untraversed exit; and due to the One-way gadgets that are placed between Clause gadgets and the next variable, this cannot happen until the Exit wire is reached.

Hence, the switch network problem is NP-hard.

It is still unclear if the problem is in NP or PSPACE-hard.
An NP-hardness reduction constructing a planar switch network will have great implications for restricted variants of Sokoban, namely because all switches are equivalent to the Sokoban gadget below.


How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

At worst you have to check one element of each repeated prime cycle, https://oeis.org/A186202 Smaller than n! but still large.


Why exactly are complexity theorists interested in closed timelike curves?

Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity theory studies the resources (especially time) required in theory to solve them. How hard are these problems really at some fundamental level, and how are they classified by resource requirements? This question is considered interesting regardless of how many or what kinds of resources puny humans happen to have at their disposal.

(For instance, an $n^{100000}$ time algorithm for SAT would totally upend our view of complexity theory even if it never impacted any algorithms we could run in this universe. A $2^{0.00000001n}$ time algorithm for SAT would change our understanding of complexity much less, even though it would have huge practical implications.)

The question of how much time is needed in theory to solve a problem changes if you allow CTCs, therefore they are interesting to complexity theory by definition.

So I feel your first question is like asking why computability theorists would study Turing degrees higher than zero; it's what they do.


Evaluating the expected value of negatively correlated random variables

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed?


The Hamiltonian Cycle Problem asks to decide, given a graph $G$, whether $G$ is Hamiltonian. This is the decision version. The function version(FNP) asks to actually find a Hamiltonian cycle in $G$ (if any).

I suggest looking at FNP, and related classes (such as NPMV and NPSV) in the Complexity Zoo.

In addition, a quick search in Google Books reveals many books in which you may find more info.

Please be more specific if you have more questions in mind.


If $P=BPP$, then Is it correct that $IP=NP$?

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

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

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


What is the proof that visibility graphs can be used to compute the shortest path?

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113.

  With the above result it is immediate to realize that the shortest
  path problem with line segments as obstacles can be solved by first
  constructing the graph G=(V,E), called visibility graph, where V
  consists of the two distinguished points and the set of 2N endpoints
  of the given N line segments, E is the set of edges each of which
  connects two vertices i and j of V without intersecting any obstacle
  except possibly at the endpoints (i and j are visible according to Definition 4.2); and the weight
  associated with each edge (i,j) of E is the Euclidean distance between
  points i and j; and then applying a well known shortest path algorithm
  to G.

However this is only for with line segments as obstacles, not polygons as obstacles.


Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?

this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a Denial of Service attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures.

one famous example from history is the so-called Ping of Death which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, & Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category.

there are large amounts of research into DoS prevention techniques eg refs below.

[1] Hackers’ Most Destructive Attacks, DailyBeast

[2] Preventing Internet Denial-of-Service with Capabilities Anderson, Roscoe, Wetherall

[3] Denial of service attacks and how to defend against them Razmov

[4] Internet denial of service attacks and defense mechanisms Abliz


Density of distinct satisfying assignments for uniquely satisfiable formulas

If I understand your question correctly, you are asking for asymptotic growth of $f:\mathbb{N} \to \mathbb{N}$ such that $f(n)=k$ iff there are $k$ different 3-CNF formulas on $n$ variables such that each of them has a unique satisfying assignment. As Tsuyoshi Ito, points out you can construct a 3-SAT instance $\phi$ from a given Boolean string $x=b_{n-1},\dots,b_0$ such that $x$ is the only satisfying assignment of $\phi$. This follows from Cook-Levin, theorem as you can write description of T.M which accepts the input iff the input bit string $y$ is equal to $x$, and then using the Cook-Levin construction convert it into a 3-SAT formula where the variables would correspond to input bits. But size of $\phi$ can be polynomial in $n$ (I am not sure if Tsuyoshi Ito was referring to this construction). Also Valiant-Vazirani lemma which  sates that 3-SAT instance on $n$ variables can be reduced (using a randomized algorithm which succeeds on $\frac{1}{8n}$ fraction of random choices) to U-SAT, can be used to deduce that from a 3-SAT instance $\phi$ on $n$ variable we get at least $\frac{1}{8n}$ 3-SAT instances on $2n$ variables (Valiant-Vazirani lemma uses hash functions, and the number of variables it adds to the formula is $k \in [n]$, which denotes the logarithm of number of satisfying assignments of the old formula, and hence to make the formula obtained by the randomized algorithm in the reduction uniformly on $2n$ variables we'll add clauses involving dummy variables). Hence $f(2n)\geq \frac{1}{8n}2^{r(n}g(n)$ where $g(n)$ is the number of different 3-SAT instances and $r(n)$ is the randomness used by Valiant-Vazirani reduction..


Are there strongly normalizing lambda terms that cannot be given a System F type?

As you found out yourself, the answer to your question is yes.  You found a rather convoluted example, a much simpler example is the following:
$$(\lambda zy.y(zI)(zK))(\lambda x.xx)$$
where $I$ and $K$ are the identity and first-projection combinators.  This may be found at p. 204 of Sørensen and Urzyczyn's Lectures on the Curry-Howard Isomoprphism.  They attribute it to Ronchi Della Rocca and Giannini, and also give a seemingly even simpler example, which is $c_2c_2K$, where $c_2$ is, I believe, the Church integer 2 (I'm not sure about their notation so I may be wrong).


Bouziane’s transformation of the Petri net reachability problem and incorrectness

Found another article that helped me understand:

COMPEXITY OF SOME PROBLEMS IN PETRI NETS*

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

This paper does a good job of explaining the difference between a k-bounded Petri-Net and an unbounded one.

A Petri net is bounded if and only if it has a finite reachability set.

Bouziane’s solution applies only to bounded Petri-Nets.


Dynamic planar exact k-nearest neighbors for pathological data

According to TOPP 63, dynamic nearest neighbors can be answered in $O($polylog$)$ time per insert, delete, or query (that is, the case $k=1$). The general case can therefore also be answered in time $O(k$ polylog$)$ per query: to do a query for $k$ points, repeatedly find and delete the nearest neighbor, then once the query is done re-insert all the points you deleted.


Bipartite vertex cover with a Very Important Vertex

Just delete D together with its indicent edges and check if you can find a vertex cover for the remaining graph that is one smaller than that for the whole graph. If so, you can add D to it to get a minimum vertex cover that includes D; otherwise, there is no such vertex cover. (This doesn't depend on the bipartiteness at all.)


Recovering a parse forest from an Earley parser?

Doing that would of course depend on the right representation for a "packed forest" that represents all parse trees for a given sentence.

I think the place you want to start looking is at Joshua Goodman's thesis (parsing inside out, Harvard, 1999). Basically, the idea is that you can define a parsing algorithm under a certain semiring. Depending on the semiring, you would be able to calculate all kind of quantities and structures instead of the bare parse tree (as a recognizer or as a parser). One semiring that you could define (which Goodman does in his thesis) is a semiring where the values are sets of parses. When you eventually finish parsing a sentence, you'd get all parse trees in the main parse node.

Again, you have to be careful about making it possible through the right representation.


Is BPP vs. P a real problem after we know BPP lies in P/poly?

Not sure how much of an answer this is, I'm just indulging in some rumination.

Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself.

For Question 2 I want to share some background and a thought. Pretty much all the techniques and ideas we have for BPP=P, as far as I'm aware, go via "derandomization": Given any probabilistic polytime Turing Machine, construct a PRG to feed it a bunch of deterministically chosen bits instead of random ones, such that its behavior is very similar to its behavior on truly random bits. So with good enough pseudorandom generators, we get BPP=P. (Goldreich's "World of BPP=P" gives evidence that any proof of BPP=P must equate to this.)

This is pretty much along the lines of BPP $\subseteq$ P/poly, except there, the PRG is the advice string which is produced by magic. Perhaps the best answer to your Question 2 is that in P we have no magic and must come up with the advice string ourselves. Derandomization is also the idea behind the 2004 result SL=L, using tools like expander graphs.

Now consider what such a proof would imply for just one particular algorithm, the Miller-Rabin primality test. It would show the existence of some deterministic generator that picks out a sequence of integers to feed to the Miller-Rabin primality test such that, if and only if all the integers passed, then the original number was prime.

As I understand it (though I am no expert), the question of whether such a list exists and how small the numbers in it can be (in particular if it sufficices to check all the numbers below some bound) seems quite a deep question in number theory and is closely related to proving forms of the generalized Riemann Hypothesis. See this question. I don't think there's a formal implication here, but it doesn't seem like something we expect to get next week as an accidental miniature corollary of a much more general PRG construction.


It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a vector $v_i$ whose first coordinate is $x_i$, second coordinate is $-x_i$, and the third coordinate is $0$. Add another vector $v_{n+1}$ with first coordinate $0$, second coordinate $S$, and last coordinate $1$. Define $t$ to have first and second coordinates $S/2$, and last coordinate $1$. Then any solution $I$ to this instance of your problem must include $n+1$, and the sum $\sum_{i \in I}{v_i}$ has first coordinate $\sum_{i \in I\setminus \{n+1\}}{x_i}$ and second coordinate $\sum_{i \in [n] \setminus I}{x_i}$, so it's only feasible if $I \setminus \{n+1\}$ is a valid solution to the Partition instance.

This can be extended to $k=2$ with a trick. Define the same instance but $v_i$ for $i \in [n]$ has only the first two coordinates. Let $A = \sum_{i=1}^n{|x_i|}$ and $b = \lceil \log_2 A\rceil$. Define $v_{n+1}$ to have first coordinate $2^b$, and second coordinate $S$, and $t$ to have first coordinate $2^b+S/2$ and second coordinate $S/2$. This forces the $b$-th bit (from the right) of the first coordinate of $\sum_{i \in I}{v_i}$ to be $1$, which can only happen if $n+1 \in I$. The rest is the same as above.


Hereditary substitution with a universe hierarchy

As of November 2018, how to do this for dependent type theories with large eliminations is an open question.

Establishing that the recursion is well-founded is not too bad; you can use Pataraia's theorem to prove the fixed point you want exists. See Robert Harper's *Constructing Type Systems Over an Operational Semantics for a how-to. (You can also do this via an inductive-recursive definition.)

The hard part is actually formulating the hereditary substitution in a nice way -- the natural direction leads you towards substituting not one term, but an entire substitution for a context, and this raises a lot of questions about when and how to establish properties of things like compositions of (hereditary) substitutions.

If it turned out to be impossible, I would be utterly shocked. However, at present no one has done it. If you want to work on this, I would suggest getting in touch with Andreas Abel, Dan Licata and Mike Shulman. (Or me, for that matter.)


Applications of sunflower lemma in theoretical computer science

Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see:
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.


I found this book to cover the topics well

Computational Geometry in C
by Joseph O'Rourke


If SAT is in PCP, for some constant q, then P = NP

Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done.

First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we know that the instance is not perfectly satisfiable and we are done). If a used predicate has two or more satisfying assignments, then, if we take a random assignment for all variables some constraint is satisfied with probability at least $2/2^q>1/2^q$. Since all other constraints are satisfied with probability at least $1/2^q$, by linearity of expectations there exists an assignment that satisfies strictly more than $1/2^q$ fraction of the constraints and we are done in this case.

Finally, suppose that all predicates used have exactly one satisfying assignment. Then the CSP is an instance of DNF-SAT, which can be decided in polynomial time (we only need to check if any two constraints have a conflict).


$O(m+n)$ really necessary for graph algorithms?

Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)?  That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe.

For example, you could just take a standard data structure for storing graphs and store the set of nodes $V' \subseteq V$ which have degree greater than 0.  We don't need to store any information about $V_0$, the set of nodes with degree 0, except for how many there are.

In other words, in a graph with vertices $V$ and edges $E$, if we define

$V' = \{v\in V | v \mbox{ has degree} > 0\}$

$V_0 = \{v\in V | v \mbox{ has degree }  0\}$

We can store the nodes with nonzero degree in $O(|V'| + |E|)$ space, and the nodes with zero degree in $O(\log |V_0|)$ space, giving a total of $O(|V'| + |E| + \log |V_0|)$ space.

Many algorithms that run in linear time, for example BFS and DFS, will run in time $O(|V'| + |E|)$ because the algorithm can just ignore the vertices with degree zero.  Like you say, if $n >> m$, this is much more efficient than the standard algorithm.

There are many cases where algorithms are parameterized by factors in addition to the size of the input.  Other examples of this include

Output-sensitive algorithms like range queries for range trees, which run in time $O(\log n + k)$ where $k$ is the size of the query returned.
Succinct data structures, which store data in space proportional to the entropy of the stored data
Algorithms in the external memory model (section 2 of that in particular--in fact the lecture notes for Erik Demaine's class on Data Structures deal with most of these concepts) depend on the size of a cache and the size of a block transferred from the cache to the processor.
Sparse matrix data structures, and similar structures and algorithms for sparse graphs, which are probably the most similar to what you're asking about.

Most of the references here are fairly general/low level, but there are a great deal of research papers on many of these topics.  In any case, there are sometimes good reasons to use another parameter while analyzing an algorithm's running time, but for general algorithms like DFS, it's assumed that no special data structure or storage methodology is used, leading to $O(|V| + |E|)$ time.


Talk for K-12 Students + General Audience Reference Request

As one of the topics of your lecture, the problems from combinatorics might be good candidates.Generally, a high school student has some conception on permutation, combination and high school geometry. So, following examples illustrates what i mean.

Take arbitary points on plane. Can we always find a line such that the number of points above and below the line is same? If yes, how ?
Take a point set on plane. How can we find the minimum number of points that should be added to the point set such that it contains 4 points forming a square?

etc. Actually, the many problems in combinatorial geometry are even though hard to solve, but since they mainly focuses on points, lines they can act as motivational problems.


What is a term of the type $\bot\rightarrow A$?

There are several ways of writing such a term, depending on how we write the proof terms for the elimination rule for $\bot$, which is
$$\frac{\quad\bot\quad}{A}$$
The corresponding rule in $\lambda$-calculus is
$$\frac{\Gamma \vdash e : \bot}{\Gamma \vdash \mathtt{absurd}_A(e) : A}.$$
(We call $\mathtt{absurd}_A$ an eliminator.)
Thus, the term of type $\bot \to A$ you seek is simply
$$\lambda x : \bot \,.\, \mathtt{absurd}_A(x).$$
Another way of writing the same thing is with a $\mathtt{match}$ statement. To see how this works, let us first consider a $\mathtt{match}$ statement for disjunctions. The elimination rule for $\lor$ is
$$\frac{A \lor B \qquad {\begin{matrix}A \\ \vdots \\ C\end{matrix}} \qquad {\begin{matrix}B \\ \vdots \\ C\end{matrix}}}{C}$$
The corresponding term constructor for $\lambda$-calculus can be written as
$$\frac{\Gamma \vdash e_1 : A+B \qquad \Gamma, x : A \vdash e_2 : C \qquad \Gamma, y : B \vdash e_3 : C}{\Gamma \vdash (\mathtt{match}\;e_1\;\mathtt{with}\;\mathtt{inl}(x) \to e_2 \mid \mathtt{inr}(y) \to e_3 \; \mathtt{end}) : C}$$
In general, the $\mathtt{match}$ statement which eliminates an $n$-fold sum $A_1 + A_2 + \cdots + A_n$ has $n$ cases.

The empty type $\bot$ is like a nullary sum, so it corresponds to a $\mathtt{match}$ statement with zero cases:
$$\frac{\Gamma \vdash e : \bot}{\Gamma \vdash (\mathtt{match}\;e\;\mathtt{with}\;\mathtt{end}) : C}$$
Indeed, this is how you can do it in Coq:

Definition ex_falso_quodlibet (A : Set) (x : Empty_set) : A :=
    match x with end.


This answer proved something different from what the questioner was actually interested in. Leaving it here so others won't repeat the same mistake.

  In most cases, one can formally justify the intuitive notion that
  "self loops can only slow down the walk" by a coupling argument.  In
  this case for example, one can couple the walk with the self loops
  (let's call it $A$) and the one without the self loops (let's call
  that $B$) so that $A$ takes the same steps as $B$, but delayed in
  time.  This can for example be done as follows:  Suppose that $B$
  starts at $u = x_0$ and goes through $x_i: i =1,2,\ldots,k$. Now, we
  implement $A$ as follows: $A$ also goes through the same vertices as
  $B$, except that vertex $x_i$, it waits for Geometric($p_i$) time
  where $p_i$ is the self loop probability at $x_i$.  Note that this is
  a correct implementation of $A$ (all transition probabilities are
  correct), and the form of the coupling ensures that $A$ never reaches
  any vertex before $B$, that is, we have coupled $H_t^A$ and $H_t^B$
  (the random hitting times in the two walks) so that $H_t^A \geq H_t^B$
  with probability $1$. Thus, the inequality for the expected hitting
  time follows.


Two DFA intersection emptiness connections to SETH & L vs P

The "inverse" is almost the same as

  SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in
  $O(n^{2-\epsilon})$ time.

To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$.

This kind of reduction would be very interesting because it would take an instance of one problem to a much smaller instance of another problem.  As a result, this reduction would not be one-to-one.  Actually, there would be exponentially many inputs that map to the same output.

If you know of any interesting reductions of this form, please provide a reference.  Thank you.  :)


Many-one reduction from inequality problem to equality problem

The following should yield a many-one reduction from $M_{ineq}$ to $M_{eq}$:

Given $G=(V,E)$ and $k$ construct $G'$ with

vertex set $V \times \{1,\dots,k\}$ and
edges between $(v,i)$ and $(w,j)$ if

(1) $i=j$ or
(2) $v=w$ or
(3) $(v,w) \in E$.

Because of (1), no independent set can be larger than $k$ (as all vertices in the same slice are connected). Because of (2) and (3) each independent set in $G'$ induces an independent set of $G$ and vice versa, therefore $G$ has an ind. set of size $\ge k$ if and only if $G'$ has an independent set of size exactly $k$.


What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/S0022000099916872


Looking for papers and articles on modal substructural logics

I know of work adding temporal modalities to linear logic to produce what has been called temporal linear logic (in contrast to LTL = linear-time temporal logic). This is quite interesting: a formula (without a modality) is interpreted as resources being available now. The next time modality $\bigcirc-$ is interpreted as resources being available in the next time step. The box modality $\Box-$ means that the resources can be consumed at any point in the future,
determined by the holder of the resources, whereas $\lozenge-$ means that the resources can be consumed at any point in time determined by the system. Notice the duality between the holder of the resource and the system.

Banbara, M., Kang, K.-S., Hirai, T., Tamura, N.: Logic programming in a fragment of intuitionistic temporal linear logic. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 315–330. Springer, Heidelberg (2001)
Hirai, T.: Propositional temporal linear logic and its application to concurrent systems. EICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Special Section on Concurrent Systems Technology) E83- A(11), 2219–2227 (2000)
Hirai, T.: Temporal Linear Logic and Its Application. PhD thesis, The Graduate School of Science and Technology, Kobe University, Japan (September 2000).
Kamide, N.: Temporalizing Linear Logic Bulletin of the Section of Logic Volume 36:3/4 (2007), pp. 173–182

There are a few papers adding all sorts of modalities to linear and affine logic:

Kamide, N.: Linear and affine logics with temporal, spatial and epistemic logics. Theoretical Computer Science 252, 165–207 (2006).
Kamide, N: Combining Soft Linear Logic and Spatio-Temporal Operators. J Logic Computation (2004) 14 (5): 625-650.

The work on temporal linear logic has been applied in agent-oriented programming and coordination, making essential use of the interpretation of the modalities described above:

Kungas, P.: Temporal linear logic for symbolic agent negotiation. In: Zhang, C., W. Guesgen, H., Yeap, W.-K. (eds.) PRICAI 2004. LNCS, vol. 3157, pp. 23–32. Springer, Heidelberg (2004)
Pham, D.Q., Harland, J., Winikoff, M.: Modelling agent’s choices in temporal linear logic. In: Baldoni, M., Son, T.C., van Riemsdijk, M.B., Winikoff, M. (eds.) DALT 2007. LNCS, vol. 4897, pp. 140–157. Springer, Heidelberg (2008)
Clarke, D. Coordination: Reo, Nets and Logic.
FMCO proceedings, LNCS, vol.  5382. (2008)


Lower bound of real valued bounded function

You have to specify a loss -- say, $\ell_1$ for simplicity, so the risk of a hypothesis $h$ is $E|h(X)-Y|$. Then at the very least, by reduction to the VC case, to achieve accuracy $\epsilon$ you will need at least
$$\Omega(d_F(\epsilon)/\epsilon^2)
\qquad (*)$$
examples, where $d_F(\epsilon)$ is the fat-shattering dimension of the class $F$ at scale $\epsilon$. Just take an $\epsilon$-shattered set of size $d_F(\epsilon)$ and put uniform point masses on the $x$'s, while setting the $y$'s to be $\pm\epsilon$ with appropriate probabilities (just as in the binary case -- which is carefully worked out in these notes:
https://www.cs.bgu.ac.il/~asml162/wiki.files/agnostic-pac-lb.pdf
).

I don't know if this is the tightest bound possible; the best upper bound I know, given here,
https://www.sciencedirect.com/science/article/pii/S0022000097915579
behaves as
$$ O(\Omega(d_F(\epsilon/5)\log(1/\epsilon)/\epsilon^3.$$

Update.
The lower bound $(*)$ is for excess risk -- i.e., in the agnostic PAC setting. The realizable PAC lower bound can be straightforwardly be adapted to give a lower bound of $\Omega(d_F(\epsilon)/\epsilon)$ for the absolute risk.


Is CoC inconsistent with cnat_ind axiom?

One way to show that it is consistent to add cnat_ind is to internalize parametricity, i.e., we extend the type system with enough structure so that it can prove its own parametricity, from which it then follows that the Church encoding of natural numbers does indeed give natural numbers. See for instance the PhD dissertation Internalizing Parametricity by Guilhem Moulin.


How can I find the PhD thesis of C.A. Ellis?

You can find a pdf with the thesis in the following way:

Find the wikipedia page for Clarence Ellis;
On the wikipedia page find the link to his thesis "Probabilistic languages and automata";
Click on this link to find the corresponding archive.org page;
Download the thesis at archive.org.


If you ask questions like that, I feel that the only answers you could get are problems that "reduce to the maximum clique". That would be a mistake. There are many problems in practice where finding a maximum clique is thought of as a subroutine, as it is not the most expensive part of the algorithm.
Finding cliques is known to be NP-Hard, and depending on the instances it is or it is not. NP Hard does not mean anything in practice.
My (reduced) own experience tells me that I would prefer 1000 times to deal with a maximum clique problem that with a TSP, or worse : an integer multiflow.  Max clique is for me one of the "kind" NP-hard problems.
And it means that I sometimes reduce problems to Max Clique because it can be done this way, and because I know that I will get the result fast in practice (and also because I already have all the functions available, so there is nothing new to code).

If you are interested in pratical problems that can be formulated immediately as a max clique problem, I am afraid you will not find many. Practical problems have their own aspect. However, I solved one thousand time "Max Clique" problems, often on optimization problems which would not have required it, because Max Clique is, somehow, an easy problem, and because it is so general of aspect.

I guess the last time I computed a maximum independent set (which is exactly the same) was in order to obtain a decomposition of a graph (a partition of its edges into copies of a given graph).

The graph had hundreds of nodes, and solving the max clique problem on it was very far from being the bottleneck.

Hoping it helped,