Formal Definition/counter part in mathematics for “Objects” of Object Oriented Models

The answer is complicated, for two reasons.

Different people in Computer Science interpret the term "object" differently.  One is that an object consists of some data and operations packaged together.  The other is that an object is all that but also has "state," i.e., it is some form of a changeable entity.
There are deep philosophical issues to do with what "change" means (and what "entity" means, as it is constantly changing), and whether mathematical descriptions actually capture changeable entities.

Object in the sense of data + operations: That is pretty standard in mathematics.  Take any group theory text book.  It will have somewhere a definition such as $h_g(x) = g x g^{-1}$.  (It is a conjugation operator.)  The $h_g$ is an "object" in this terminology.  It has some data ($g$) and an operation $x \mapsto g x g^{-1}$.  Or you can make it more object-y by taking the pair $\langle g, x \mapsto gxg^{-1}\rangle$ or the triple $\langle g, x \mapsto gxg^{-1}, x \mapsto g^{-1}xg\rangle$.  You can construct these kind of "objects" in any functional programming language that has lambda abstraction and some way to form tuples.  Abadi and Cardelli's "Theory of Objects" deals with objects of this kind extensively.

Objects with state (or objects that change): Does mathematics have such things?  I don't think so.  I haven't seen a mathematician talk about anything that changes, not in his/her professional life.  Newton used to write $x$ for the position of a particle, which is supposedly changing, and $\dot{x}$ for its rate of change.  Mathematicians eventually figured out that what Newton was talking about was a function $x(t)$ from real numbers into a vector space, and $\dot{x}$ was another such function which was the first derivative of $x(t)$ with respect to $t$.  From this, many deep-thinking mathematicians have concluded that change doesn't really exist and all you have are functions of time.  But what was changing in Newtonian mechanics wasn't the position, but the particle.  The position is its instantaneous state.  No mathematician or physicist would pretend that a particle is a mathematical idea.  It is a physical thing.

So it is with objects.  They are "physical" things, and the states are their mathematical attributes.  For a nice discussion of this aspect, see the Chapter 3 of Abelson and Sussman's Structure and Interpretation of Computer Programs.  This is a text-book at MIT and they teach it to all scientists and engineers, who I think understand "physical" things perfectly fine.

The fact that particles aren't mathematical doesn't mean that we can't deal with them mathematically.  If you ask a mathematician to model a two-particle system, he will immediately make up two functions and call them $x_1(t)$ and $x_2(t)$.  So, the two particles reduces to two meaningless indices (1 and 2).  This is the mathematician's way of saying we don't know what those particles are and we don't care.  All we need to know is that their positions evolve independently (or separately).  So, we will model them by two separate functions.

Similarly the standard mathematical way to model object-oriented programs is to treat each object as an index into the state space.  The only difference is that since objects come and go, and the structure of the system is dynamic, we need to extend it to a "possible world" model where each world is basically a collection of indices.  Allocation and deallocation of objects would involve moving from one world to another.

There is a problem though.  Unlike in mechanics, we want the state of our objects to be encapsulated.  But the mathematical descriptions of objects put states all over the place, completely destroying encapsulation.  There is a mathematical trick called "relational parametricity" which can be used to cut things back to size.  I won't go into it now, except to emphasize that it is a mathematical trick, not a very conceptual explanation of encapsulation.  A second way of modelling objects mathematically, with encapsulation, is to finesse the states and describe the object behaviour in terms of observable events.  For a good discussion of both of these models, I can refer you to my paper titled Objects and classes in Algol-like Languages.

[Note added:]

A nice analysis of the mathematical underpinnings of objects can be found in William Cook's article "On Understanding Data Abstraction, Revisited".


How many distinct colors are needed to lower-bound the choosability of a graph?

Daniel Král and Jiří Sgall answered your question to the negative. From the abstract of their paper:

  A graph $G$ is said to be $(k,\ell)$-choosable if its vertices can be colored from any lists $L(v)$ with $|L(v)| \ge k$, for all $v\in V(G)$, and with $|\bigcup_{v\in V(G)} L(v)| \le \ell$. For each $3 \le k \le \ell$,
  we construct a graph $G$ that is $(k,\ell)$-choosable but not $(k,\ell+1)$-choosable.

So, $N(k)$ does not exist if $k\ge 3$. Král and Sgall also show that $N(2)=4$. Of course, $N(1)=1$.

Daniel Král, Jiří Sgall: Coloring graphs from lists with bounded size of their union. Journal of Graph Theory 49(3): 177-186 (2005)


Minimum number of columns making each row different

Your problem is known to be NP-hard. See for instance

  Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge:
  "Exploiting hidden structure in selecting dimensions that distinguish vectors."
  Journal of Computer and System Sciences 82, pp 521-535 (2016).


Is there such a thing as control logic complexity classes?

One should be careful about having a head that large. If your tape head can read the entire input, then technically speaking all inputs can be decided in one step. This is because "making a head so large you can read the input" is formally equivalent to making the tape alphabet so large that it contains all input strings. But if this is the case then your entire function can be encoded in the transition table of the Turing machine, so every input can be decided in one step. It makes perfect sense to have a superconstant number of symbols in the TM, but when you do that you are no longer talking about "uniform" computation (fixed-size programs) but rather "non-uniform" computation, where the size of the program can grow with the input length. In complexity theory, non-uniform computation is typically studied in the language of circuit complexity: having a polynomial-size Boolean circuit family for solving a problem is equivalent to having a "polynomial-size transition table" for solving a problem with a polynomial-time TM, and the general feeling is that circuits are more natural to reason about. But it's possible that the TM perspective could be useful too.
Allowing a specific number of states or specific structure probably will not change the definitions of the standard complexity classes. This is because there are universal Turing machines which have a small number of states and/or simple structures in the transition table, which can simulate arbitrary Turing machines with polynomial time overhead. (Sorry, don't have references at the moment.) Restricting yourself to these machines does not change the overall difficulty, up to polynomials in the running time.


Keep prices down: you can get lovely hors d'oeuvres at a $750-per-seat hotel-hosted conference, it is true, but it tends to detract from the intellectual atmosphere you can get with a $100-per-seat university-hosted conference.  Also, you don't just get the people attending who deliver talks.  Allow students at the university to attend for free;
Space parallel sessions, so that people can really move between them;
But also encourage interaction between speakers and attendees at parallel sessions beforehand, so that parallel sessions are also autonomous communities.  This encourages interaction, and the sense that parallel sessions are moving the discussion in their subfield forward.  Some conferences (e.g., the German linguistics conference, DGfS) have taken this to the conclusion of having all parallel sessions be independent workshops.


In which posets is the set of compact elements downwards closed?

The only natural condition I can think of is Berry's "I condition" ([1], Sect. 12.3):

(I) each compact element dominates finitely many elements.

The above condition is the defining property of Berry's dI-domains, which are distributive (that's what the "d" stands for) algebraic domains satisfying condition I.  This is a widely known and well studied class of domains, which served as the basis for what is known as "stable" semantics (an attempt to capture the sequential behavior of the $\lambda$-calculus).  Girard's coherence spaces [2] give a particularly simple and useful example of dI-domains.  A coherence space may be seen as the set of cliques of a reflexive graph, ordered by inclusion.  The compact elements are the finite cliques, which obviously satisfy your requirement.

I don't know if generalizations of the I condition have been studied.  A counterexample to your property is given by the ordinal $\omega+2$ ($\omega+1$ is compact but $\omega$ is not), so certainly generalizing "finite" to "well-founded+no infinite antichains" does not work.

[1]  Roberto Amadio and Pierre-Louis Curien.  Domains and Lambda-Calculi.  Cambridge Tracts in Theoretical Computer Science, 1998.

[2] Jean-Yves Girard, Yves Lafont and Paul Taylor.  Proofs and Types.   Cambridge Tracts in Theoretical Computer Science, 1989.


Which complexity class does this problem belong to?

We'll argue that the following formulation of OP's problem is complete for OPT#P under poly-time reductions:

input: A Boolean formula $\phi\big(b=(b_1,b_2,\ldots,b_n), x=(x_1, x_2,\ldots, x_m)\big)$

output: The maximum, over all assignments to $b$, of the number of assignments to $x$ such that $\phi(b, x)$ is satisfied (evaluates to true).

The problem differs from OP's problem in two minor ways.  First, the output does not include an assignment to $b$.  Second, it chooses $b$ to maximize, rather than  minimize, the number of satisfying assignments.  However, OP's problem for a given $\phi$ is essentially equivalent to this problem for the complement of $\phi$.

Lemma 1. The problem above is OPT#P-complete under polynomial-time reductions.

Proof sketch. The proof is a simple variant of the standard proof that SAT is NP-complete.

First, as I understand it, OPT#P is the class of functions of the form
$$g(w) = \max_b \#M(w, b)$$
for some non-deterministic poly-time TM $M$, where $\#M(w, b)$ is the number of accepting computation paths for $M$ on input $(w, b)$.  In the $\max$, $b$ ranges over all binary strings of length equal to some fixed polynomial $p(|w|)$.

So fix any such TM $M$ and corresponding $g$.  Given any $w$, the reduction will produce (in time poly$(|w|)$) an equivalent instance of the problem in question: a Boolean formula $f_w(B, X)$ with Boolean variables $(B, X)$ such that

$$g(w) = \max_{b} \#f_w(b),$$

where $\# f_w(b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true.

Recall that the classical Cook-Levin reduction for $M$ on a given input $(w, b)$ first produces a formula $F(W,B,X)$ with boolean inputs $W$, $B$, and $X$, where $|W|=|w|$, $|B|=|b|$, and $|X|$ is some fixed polynomial in $|w|+|y|$.  But then it adds constraints to force $W=w$ and $B=b$ (or makes these substitutions and simplifies the resulting formula), resulting in a formula $F_{wb}(X)$ such that there is exactly one assignment to $X$ that satisfies $f_{wb}(X)$ for each accepting computation of $M$ on input $(w, b)$.  (The variables in $X$ encode the non-deterministic guesses of $M(w, b)$, and also auxiliary values that encode the rest of the computation.  But the auxiliary values are determined by the non-deterministic guesses and $w$ and $b$.) In this way, $f_{wb}(X)$ is satisfiable if and only if $M(w, b)$ has an accepting computation.

Instead, given $w$, the reduction outputs the formula $f_w(B,X)$ obtained from $F(W,B,X)$ by adding only the constraints that force $W=w$. Then, for any given second argument $b$, the number of accepting computations of $M(w, b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true.  That is, in our previous notation, for all $b$,
$$\#M(w, b) = \# f_w(b).$$
It follows that $g(w) = \max_b \# f_w(b)$ as desired.$~~~~~\Box$


This question turned out to be trivial. As Lev Reyzin said in his comment, the answer was already encoded in the figures. I should have watched them more carefully...Of course, looking at the figures, it was already evident that those hulls are cycles. What was not immediately evident to me is the obvious fact that given whatever drawing like those, you could pick whatever cycle in it (even a 3-cycle), "enlarge" it, and "throw" all the remaining nodes inside it, thus obtaining a hull. So:

As Tsuyoshi Ito pointed out, if the drawing is not requested to be planar, then every cycle is a hull, and this observation simultaneously answers all the four questions I've posted.
As Hsien-Chih Chang and Peter Shor indicated, if the drawing is requested to be planar, then the questions can be answered by using planar graph embedding algorithms.

Finally, to make things worse, it seems that the choice of the term "hull" was unfortunate: the correct term to indicate what I had in mind is "outer face" (although such term is probably meaningless for non-planar graphs).


Ways for a mathematician to stay informed of current research in complexity theory

In addition to ArXiv, you could subscribe to the Electronic Colloquium on Computational Complexity. It gets a lot of traffic from current research, and the email updates you receive are normally a succinct format of paper title/author(s)/abstract, so you won't have to invest much time to see what's just happened.


Complexity of finding an edge set yielding specified vertex degrees

What you look for in question Q1 is known as an $f$-factor of the graph. Here $f$ is a non-negative integer valued function on the vertices, $f(v)$ specifying the degree we want in the subgraph at vertex $v$.

Q2 is looking for a so called $(g,f)$ factor, where $g(v)$ is a lower bound and $f(v)$ is an upper bound on the degree of the sought subgraph at each vertex $v$.

Both problems can be solved in polynomial time, see https://www.sciencedirect.com/science/article/pii/S0012365X06005486


The question seems to be predicated on a misunderstanding: the statements “relative to a random oracle $A$, $\mathrm{P}^A=\mathrm{BPP}^A$” and “$\mathrm{Almost\text-P}=\mathrm{BPP}$” are not meant to be rephrasings of each other. The complexity zoo refers to a paper of Bennett and Gill, which proves the former statement (and many other things) in detail, but it also separately claims the second statement (though they do not use the $\mathrm{Almost\text-P}$ notation, and do not really give a proof).

The definition of $\mathrm{Almost\text-P}$ in the zoo is correct.

The proof of $\mathrm{Almost\text-P\subseteq BPP}$ goes as follows. Let $L\in\mathrm{Almost\text-P}$. Since there are only countably many Turing machines, there exists an oracle polynomial-time Turing machine $M$ such that $M^A$ computes $L$ with positive probability $\epsilon>0$. Using the Lebesgue density theorem, there exists a finite oracle prefix $A_0$ such that relative to random oracles $A$ that extend $A_0$, $M^A$ computes $L$ with probability $\ge3/4$. We can hardwire $A_0$ into the Turing machine, and simulate access to the rest of the oracle by random coin flips to obtain a randomized poly-time machine for $L$ with probability of success $\ge3/4$. Thus, $L\in\mathrm{BPP}$.


OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language $L$ (encoding the digits of $\pi$) is in the fourth level of the counting hierarchy ($\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^{\mathsf{PP}}}}$; thanks to SamiD below for pointing out a missing $\mathsf{PP}$ in the paper, which I'd simply repeated in my answer!).  The paper also explicitly discusses my question of lower bounds on the complexity of computing the binary digits of irrational numbers, though it only manages to prove a very weak lower bound for computing the binary digits of rational numbers.  This is exactly what I was looking for.

Update (April 3): An amusing consequence of the digits of $\pi$ being computable in the counting hierarchy is as follows.  Suppose that $\pi$ is a normal number (whose binary expansion converges quickly to "effectively random"), and suppose that $\mathsf{P} = \mathsf{PP}$ (with the simulation involving only a small polynomial overhead).  Then it would be feasible to program your computer to find, for example, the first occurrence of the complete works of Shakespeare in the binary expansion of $\pi$.  If that sounds absurd to you, then maybe it should be taken as additional evidence that $\mathsf{P} \ne \mathsf{PP}$. :-)


Number of k-expressions of graph (clique Width)

Cographs have clique width 2, and the number of cographs of size $n$ is asymptotically equal to $3.56^n$.

See https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices.

I am not sure how many graphs with a given clique-width $k$ exist.


$\mathtt{Prop}$ is very useful for program extraction because it allows us to delete parts of code that are useless. For example, to extract a sorting algorithm we would prove the statement "for every list $\ell$ there is a list $k$ such that $k$ is ordered and $k$ is a permutatiom of $\ell$". If we write this down in Coq and extract without using $\mathtt{Prop}$, we will get:

"for all $\ell$ there is $k$" will give us a map sort which takes lists to lists,
"such that $k$ is ordered" will give a funciton verify which runs through $k$ and checks that it is sorted, and
"$k$ is a permutation of $\ell$" will give a permutation pi which takes $\ell$ to $k$. Note that pi is not just a mapping, but also the inverse mapping together with programs verifying that the two maps really are inverses.

While the extra stuff is not totally useless, in many applications we want to get rid of it and keep just sort. This can be accomplished if we use $\mathtt{Prop}$ to state "$k$ is ordered" and "$k$ is a permutation of $\ell$", but not "for all $\ell$ there is $k$".

In general, a common way to extract code is to consider a statement of the form $\forall x : A \,.\, \exists y : B \,.\, \phi(x, y)$ where $x$ is input, $y$ is output, and $\phi(x,y)$ explains what it means for $y$ to be a correct output. (In the above example $A$ and $B$ are the types of lists and $\phi(\ell, k)$ is "$k$ is ordered and $k$ is a permutation of $\ell$.") If $\phi$ is in $\mathtt{Prop}$ then extraction gives a map $f : A \to B$ such that $\phi(x, f(x))$ holds for all $x \in A$. If $\phi$ is in $\mathtt{Set}$ then we also get a function $g$ such that $g(x)$ is the proof that $\phi(x, f(x))$ holds, for all $x \in A$. Often the proof is computationally useless and we prefer to get rid of it, especially when it is nested deeply inside some other statement. $\mathtt{Prop}$ gives us the possibility to do so.

Added 2015-07-29: There is a question whether we could avoid $\mathsf{Prop}$ altogether by automatically optimizing away "useless extracted code". To some extent we can do that, for instance all code extracted from the negative fragment of logic (stuff built from the empty type, unit type, products) is useless as it just shuffles around the unit. But there are genuine design decisions one has to make when using $\mathsf{Prop}$. Here is a simpe example, where $\Sigma$ means that we are in $\mathsf{Type}$ and $\exists$ means we are in $\mathsf{Prop}$. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \Sigma_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
we will get a program which decomposes $n$ into its lowest bit $b$ and the remaining bits $k$, i.e., it computes everything. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \exists_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
then the program will only compute the lowest bit $b$. The machine cannot tell which is the correct one, the user has to tell it what he wants.


Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

Depends what you mean by "class".

I don't know of any natural class that satisfies that, but certainly one can do the following:

Consider the set of languages that are decidable in time $2^n$ (exactly, not just any exponential). This is strictly contained in EXP by the time-hierarchy theorem.
Take the union of this set and PSPACE, and you have a class that strictly contains P (again, time hierarchy), contains PSPACE, and is contained in EXP (and presumably, if PSPACE$\neq$ EXP, then there is also strict containemnt here).


Is there an equivalent to derandomization for quantum algorithms?

There are certain classes of quantum gates which can be simulated efficiently with a classical computer. If no entanglement is present, a computation with pure states (i.e. not random states) can be simulated efficiently. Classical gates reversible gates are a subset of quantum gates, and so can obviously be simulated efficiently. These two examples are pretty trivial, however there are a number of non-trivial gate sets known.

Valiant gates as mentioned in Joshua's answer
Clifford group gates (see arXiv:quant-ph/0406196)
Match gates (see arXiv:0804.4050)
Commuting gates, etc.

Basically, most sets of operators which generate only some small subspace of $SU(2^N)$ tend to be simulable, while any that generate $SU(2^N)$ are as hard as general quantum simulation of N qubits.

It seems very unlikely that quantum mechanics is efficiently simulable, and so such a dequantization program will likely be impossible in general. There is however a regime where this has worked, which is with interactive proofs. Several different kinds of interactive proof systems with quantum verifiers have been shown to have the same power if the quantum verifier is replaced with a purely classical verifier. For an example of this, see Jain, Ji, Upadhyay and Watrous's proof that QIP=PSPACE (arXiv:0907.4737).


Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint

If the only thing that you know about $f$ is that it is non-increasing, then there is a simple adversary argument to show that you need to examine the value of $f$ on at least ${n \choose k}$ inputs (e.g., all ${n \choose k}$ different sets of cardinality $k$) in the worst case.  For instance, consider functions $f$ that are $+\infty$ on all sets of cardinality $<k$, and with arbitrary values on the sets of cardinality $k$, and $-\infty$ on all sets of cardinality $>k$.  A similar argument shows that no useful approximation is possible, either.

So, to make the problem tractable, you need to restrict the class of allowable functions in some way.


Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does not have an entropy of 1 bin/output bit.

One solution is to combine the input letters into groups and enlarge the alphabet. For example, instead of coding a byte stream (as is usually done), you can combine two bytes into a word and use a larger coding tree for the combined alphabet. The problem is that the size of the tree (e.g. instead of $2^8$ entries, now you have to deal with $2^{16}$ entries). And this is just the beginning.

One may view the arithmetic coding as taking this idea to the extreme. Instead of combining two input letters, here we combine all of them. Of course, now the coding tree is huge and cannot be explicitly built. The details of arithmetic coding deals with generating and traversing a virtual Huffman tree for this combined alphabet.


Applications of Hamiltonian Cycle Problem

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two triangles share an edge) can be a helpful way to organize data and reduce communication costs.


This answer is a bit hand-wavey.

Select a function $h$ uniformly at random from the set of all functions from w-bit words to w-bit words. For each set, maintain a w-bit fingerprint as follows:

The empty set has the fingerprint 0.
add(x) and remove(x) update a fingerprint $f$ to $f \oplus h(x)$, where $\oplus$ is xor.

Let $S \neq T$ be two sets of w-bit integers. If their fingerprints are the same, then the fingerprint of $S \triangle T$, the symmetric difference of $S$ and $T$, is 0, which happens with probability $2^{-w}$.


Are two-qubit unitaries necessary for universal quantum computation?

I think this question is probably better suited to cs.stackexchange.com, and I hesitate to answer it. That single qubit gates are not universal was stated by Deutsch, Barenco, and Ekert in 1995.  They point out that you cannot entangle un-entangled qubits with only single qubit operators.  You can also prove this without any appeal to entanglement or states in general by showing that at least one two qubit operator, namely $CNot$, cannot be constructed by single qubit operators.

Assume single qubit operators are universal. Then there must exist some $A$ and $B$  such that $A \otimes B = CNot = (P_0 \otimes I) + (P_1 \otimes X)$.  It follows then that that $A_{00}B = I$, $A_{11}B = X$, and $A_{01}B=A_{10}B=0$. For $A_{00}B$ to be $I$, it must be the case that $B$ itself is $I$. Similarly, for $A_{11}B$ to be $X$, $B$ itself must be $X$. This is a contradiction.  So, single qubit operators are not universal as they cannot carry out at least one two qubit unitary operation, namely $CNot$.


Definition for MSO2 for arbitrary structures

If I understand correctly, you just want a definition of the logic; then you can find a definition of MSO$_j$ (where 2 is a special case) by example in ''Elements of Finite Model Theory'' of Leonid Libkin.
Even if you are interested in infinite model, the definition of the logic is the same.

Quickly is just the set of formulae with existantial quantification over sets of the elements of the universe, then existantial quantifications over those sets; then a first-order formula.


Poly time superset of NP complete language with infinitely many strings excluded from it

Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that

pseudorandom generators exist, and
secure one-way permutations exist.

In other words, assuming that these two conjectures are true,
no $\mathsf{coNP}$-complete set is P-immune.
As pointed out in the comments by Lance,
this is implied by Theorem 4.4 of

Glasser, Pavan, Selman, and Sengupta, "Properties of NP-complete sets",
SIAM J. Comput. 36(2), 516–542.

(Kaveh has already shown that your question is equivalent to
whether every $\mathsf{coNP}$-complete sets
contains an infinite $\mathsf{P}$ subset.
In other language,
this is saying that no $\mathsf{coNP}$-complete set is "$\mathsf{P}$-immune." This is the language used in the above-referenced theorem.)


For what languages is there already a theory of observational equivalence?

A compositional denotational semantics $[\![ {-} ]\!]$ of a programming language (a domain-theoretic or game-theoretic one, for instance) is adequate if semantically equal terms imply that they are observationally equivalent:
$$[\![ t_1 ]\!] = [\![ t_2 ]\!] \implies t_1 \cong t_2.$$
It often happens that it is far easier to calculate denotations that to prove observational equivalence. This is a common technique with many known variants. Adequacy is defined already in Plotkin's PCF paper.


Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by this paper by Jordan, Lee, and Preskill, which shows how to simulate in polynomial time a much simpler quantum field theory than the Standard Model.


Parameterized complexity of Hitting Set in finite VC-dimension

I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there is a cover of the points by k of the unit disks. There is an easy n^O(k) time algorithm for this, and I would not be surprised if using known insights one can do n^O(sqrt{k}) (but even that is not obvious), but doing f(k)*n^{O(1)} is open, and in fact would be quite interesting. A (1+eps) approximation follows from the work of Mustafa and Ray http://portal.acm.org/citation.cfm?id=1542362.1542367.

BTW, for the continuous version where any unit disk is allowed, one can solve the problem in n^{O(k)} time. A PTAS in this case is also pretty easy using shifted grids.


The problem is known to be NP-complete: On the equal-subset-sum problem, Woeginger and Yu, IPL'92.


Fault-tolerant programming languages / paradigms?

A good place to start looking for work coming from the PL community could be the following.

Joe Armstrong's work on Erlang, see e.g. his PhD thesis. This work continues to have a profound influence on programming language design, with Scala's integration of the Akka stack being a recent example.
David Walker and his group's work on fault tolerance.
The numerous investigations into exceptions and exception handling, with a famous early publication being Randell's System Structure for Software Fault Tolerance. The literature on this subject is too large to survey.
Another strand of research is work on recovery oriented programming.


A k-approximation to k-way number partitioning

This is not an answer - it is just a reply to Neal Young's comment regarding the greedy algorithm. I claim that in the outcome of the greedy algorithm:

The largest sum is at most $\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$;
The smallest sum is at least $\operatorname{MaxMin}(S, 2k-1)$.

Proof. Let $X_1,\ldots,X_k$ be the outcome of the greedy algorithm. It is sufficient to prove the claims for an arbitrary subset from this partition, say for $X_1$. For any set $X$, denote by $v(X)$ the sum of numbers in $X$.
Proof of 1.
Let  $Z_1,\ldots,Z_{\lfloor(k+1)/2\rfloor}$ be a min-max partition.
If $X_1$ contains a single item, then it is contained in at least one $Z_i$, so $v(X_1)\leq \max_i v(Z_i)$.
Otherwise, let $x_1$ be the last item added to $X_1$. By the greedy algorithm definition, both $v(x_1)$ and $v(X_1\setminus \{x_1\})$ are smaller than $v(X_2),\ldots,v(X_k)$. So in the $(k+1)$-partition $\{x_1\},X_1\setminus \{x_1\},X_2,\ldots,X_k$, the first two elements are smallest. Therefore, their sum is at most $2/(k+1)$ of the total:
\begin{align*}
v(X_1) \leq \frac{2}{k+1}v(S)
\end{align*}
On the other hand:
\begin{align*}
\max_i v(Z_i) \geq \frac{1}{\lfloor(k+1)/2\rfloor}v(S)
\geq
\frac{2}{k+1}v(S)
\end{align*}
Therefore, $v(X_1)\leq \max_i v(Z_i)$ too.
Proof of 2.
Let $x_2,\ldots,x_k$ be the last item added to $X_2,\ldots,X_k$ respectively.
By the greedy algorithm definition, if we remove $x_2,\ldots,x_k$ from $X_2,\ldots,X_k$, then $v(X_1)$ is largest among the remaining subsets. Therefore,
\begin{align*}
v(X_1)\geq \frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\})
\end{align*}
Let $Y_1,\ldots, Y_{2k-1}$ be an optimal $(2k-1)$ partition.
The items $x_i$ belong to at most $n-1$ sets in the partition $Y$, so there are at last $n$ sets in that partition that do not contain any $x_i$; denote them by $Y_1,\ldots,Y_k$. So
\begin{align*}
\min_{i=1}^{2k-1} v(Y_i)
\leq
\min_{i=1}^{k} v(Y_i)
\leq
\frac{1}{k}v(Y_1\cup\cdots \cup Y_k)
\leq
\frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\})
\end{align*}
Therefore, $v(X_1)\geq \min_i v(Y_i)$.
So the greedy algorithm is a 2-approximation. The question of whether there exists an additive approximation remains open.


Quick Sampling from Probability Distribution: Is there a name for this algorithm?


Where does the "intuitive" understanding of Kolmogorov complexity fails

The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as in the common definition), then you need to expend bits on delimiting encodings.

Self-terminating encodings have other advantages, and even though real programming languages are always self-terminating, the pioneers of Kolmogorov complexity (Solomonoff, Kolmogorov and Chaitin) defined their notion of complexity with respect to non-self-terminating encodings. The classic monograph of Li and Vitanyi treats both variants.


As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions.

The first result concerns the reduction of linear representations of recognizable series
(= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an update of the first one, with many new additions):

[1] J. Berstel and C. Reutenauer, Noncommutative rational series with applications, Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0

(2] J. Berstel and C. Reutenauer, Rational series and their languages, EATCS Monographs on Theoretical Computer Science, 12. Springer-Verlag, Berlin, 1988. viii+151 pp. ISBN: 3-540-18626-3

In the case of sequential functions, one can adapt Nerode's construction to obtain a minimal sequential transducer. The algorithmm was first given in

[3] G. N. Raney, Sequential functions. J. Assoc. Comput. Mach. 5 (1958) 177-180.

See also Thm XII.4.2 in

[4] S. Eilenberg, Automata, Languages, and Machines. Vol. A, Pure and Applied Mathematics, 58, Academic Press (1974)

The algorithm was extended to so-called subsequential functions by Choffrut. See the survey

[5] C. Choffrut, Minimizing subsequential transducers: a survey. Selected papers in honor of Jean Berstel. Theoret. Comput. Sci. 292 (2003), 131-143.

You may also have a look at
A tutorial on sequential functions for an introduction.


Why Ramanujan graphs are named after Ramanujan?

To add some content to the answers here, I'll explain briefly what Ramanujan's conjecture is.

First of all, Ramanujan's conjecture is actually a theorem, proved by Eichler and Igusa.  Here is one way to state it.  Let $r_m(n)$ denote the number of integral solutions to the quadratic equation $x_1^2 + m^2 x_2^2 + m^2 x_3^2 + m^2 x_4^2 = n$.  If $m=1$, that $r_m(n) > 0$ was of course proved by Legendre, but Jacobi gave the exact count: $r_1(n) = 8 \sum_{d \mid n, 4 \not \mid d} d$.  Nothing similarly exact is known for larger $m$ but Ramanujan conjectured the bound: $r_m(n) = c_m \sum_{d \mid n} d + O(n^{1/2 + \epsilon})$ for every $\epsilon > 0$, where $c_m$ is a constant dependent only on $m$.

Lubtozky, Phillips and Sarnak constructed their expanders based on this result.  I'm not familiar with the details of their analysis but the basic idea, I believe, is to construct a Cayley graph of $PSL(2,Z_q)$ for a prime $q$ that $1 \bmod 4$, using generators determined by every sum-of-four-squares decomposition of $p$, where $p$ is a quadratic residue modulo $q$.  Then, they relate the eigenvalues of this Cayley graph to $r_{2q}(p^k)$ for integer powers $k$.

A reference, other than the Lubotzky-Phillips-Sarnak paper itself, is Noga Alon's brief description in Tools from Higher Algebra.


k-Vertex Cover problem is in parameterized Log space

Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space:

Say that a vertex has big degree if it has degree at least $k+1$. All vertices of big degree must be in every vertex cover of size at most $k$. If $v$ does not have big degree it has small degree. Call a vertex $v$ interesting if it has small degree and has at least one neighbor of small degree. Any inclusion minimal vertex cover of $G$ of size at most $k$ must contain all vertices of big degree, and out of the vertices of small degree, it can only contain interesting vertices.

One can easily verify that in $O(\log n)$ space one can determine whether a given vertex has small or big degree, and whether it is interesting or not. Further, we can count the number of big degree / small degree / intersting vertices before $v$ in input. Thus, given an integer $j$ we can also find the $j$'th vertex of big degree / small degree or the $j$'th interesting vertex.

The algorithm computes the number $b$ of vertices of big degree, if $b > k$ the algorithm outputs that there is no vertex cover of size at most $k$. The algorithm computes the number $i$ of interesting vertices. If $i > 2k^2$ it outputs that there is no vertex cover of size at most $k$ (because one has to cover at more than $k^2$ edges using only vertices of degree at most $k$).

Now the algorithm goes over all the $2^i$ possible binary strings on length $i$. For each such string, we interpret the $j$'th bit as whether the $j$'th interesting vertex is in the vertex cover or not.

For each string compute the total size of the proposed solution ($b$ + the number of ones in the binary string), and check whether the proposed solution is a vertex cover by going over every pair of interesting vertices, checking whether they are adjacent, and whether both are $0$ in the binary string. This concludes the algorithm.

Remark: because the number of interesting vertices is at most $O(k^2)$ and we can determine whether a given vertex is interesting or not, one could run any vertex cover algorithm on the subgraph induced on the interesting vertices (for example the $O(1.2738^k + nk)$ time algorithm by Chen, Kanj and Xia), and this would still only use $f(k) + O(\log n)$ space.


Running a BPP algorithm with a half-random, half-adversarial string

What you need is a "seeded extractor" with the following parameters: seed of length $O(\log n)$, crude randomness $n/2$, and output length $n^{\Omega(1)}$. These are known. While I'm not up to date with the most recent surveys, I believe that section 3 of Ronen's survey is enough.

The only thing you will need to show is that your source has sufficient "min-entropy", i.e. no n-bit string gets a probability of more than $2^{-n/2}$, which I think is clear in your setting.


Graph coloring minimizing the number of colors in every independent set

The following claim is known to me, but may not count because it is unpublished:
Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors,
where $B(B+1)\leq 2kn$.

This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph but also on all induced subgraphs.
I am not aware of any published results, though.


What is the Complexity Classification of Portfolio Theory in Financial Economics?

The classic Markowitz model is a quadratic programming problem. I'm not sure at all about the state of current research, but one paper that might constitute a starting point is here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.9504

By the way, there's a paper that's been making the rounds on related issues: "Computational Complexity and Information Asymmetry in Financial Products" by Sanjeev Arora, Boaz Barak, Markus Brunnermeiery, and Rong Ge. The latter has posted it along with some additional comments here: http://www.cs.princeton.edu/~rongge/derivativeFAQ.html

I tend to think the results are of theoretical interest but don't explain anything that actually happened.

My suspicion is that complexity is not the main barrier in most models (generally, anything complicated gets turned into a monte-carlo eventually anyway, and generally things get complicated fast -- so yes this opens the way to certain malicious attacks, but maliciousness in the financial world can much more easily be much more crude, general, and straightforward) so much as many other, generally well known critiques of these models (sometimes from an information theory standpoint) that aren't really appropriate for this forum.


Separations between testing and tolerant testing for (natural) classes of functions?

The recent preprint of A. Levi and E. Waingarten [1] establishes such a separation* for two "(arguably) natural" properties of functions: unateness and junta-ness.

*(for junta-ness, such a separation is shown only for non-adaptive testers.)

  Theorem 1. ([1]) Non-adaptive tolerant testing of $k$-junta-ness has query complexity $\tilde{\Omega}(k^2)$.

On the other hand, Blais [2] showed that non-adaptive testing of $k$-juntas had query complexity $\tilde{O}(k^{3/2})$, hence the separation.

  Theorem 2. ([1]) Non-adaptive tolerant testing of unateness has query complexity $\tilde{\Omega}(n^{3/2})$.

On the other hand, Baleshzar et al. [3] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n)$, hence the separation.

  Theorem 3. ([1]) Tolerant testing of unateness has query complexity $\tilde{\Omega}(n)$.

On the other hand, Chen, Waingarten, and Xie [4] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n^{3/4})$, hence the separation.

[1] Erik Waingarten and Amit Levi. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs, 2018. arXiv:1805.01074

[2] Eric Blais. Improved Bounds for Testing Juntas. APPROX-RANDOM, 2008.

[3] Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP, 2017.

[4] Xi Chen, Erik Waingarten, Jinyu Xie. Boolean Unateness Testing with $\tilde{O}(n^{3/4})$ Adaptive Queries. FOCS, 2017.


Reduction graph to planar bounded treewidth and bounded diameter graph

The diameter of $G'$ will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge $O(n)$ times, so the diameter can blow up by a factor of $O(n)$.


Additive combinatorics applications in algorithm design

Timothy Chan and Moshe Lewenstein have a paper on 3SUM and related problems in the upcoming STOC, which applies an effective version of the BSG theorem from additive combinatorics to solve variants of 3SUM faster than n^2 time.

See this link to Chan's papers.


K-Clustering of a Graph maximizing intra-cluster weights?

This problem is called MIN-SUM clustering and is NP-hard. There's a paper by Bartal, Charikar and Raz from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results.


Here is a reduction from PARTITION to this problem. Let $(a_1,\dots, a_n)$ be an instance of PARTITION. Assume that $a_1\leq a_2\leq \dots \leq a_n$.

Let $N$ be a “very large number”, e.g. $N = (\sum_{i=1}^n |a_i|) + 1$. Consider the instance
$$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$$
of our problem.

If there is a solution $x_1,\dots, x_n$ to PARTITION then
$$\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$$
is a solution to our problem.
If there is a solution $(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ to the instance of our problem (which we reduced an instance of PARTITION to), then $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$. Thus $$\sum_{i=1}^n a_i y_i = 0. $$
That is, $(y_1,\dots, y_n)$ is a solution to PARTITION.


Looking for reference on NP-Completeness of proofs of length n

See this paper: On Godel’s Theorems on Lengths of Proofs II:
Lower Bounds for Recognizing $k$ Symbol Provability by Samuel R. Buss, 1995.

  This paper discusses a claim made by Godel in a letter to von
  Neumann which is closely related to the P versus NP problem.
  Godel’s claim is that $k$-symbol provability in first-order logic can
  not be decided in $o(k)$ time on a deterministic Turing machine.
  We prove Godel’s claim and also prove a conjecture of S. Cook’s
  that this problem can not be decided in $o(k/ \log k)$ time by a
  nondeterministic Turing machine. In addition, we prove that the
  $k$-symbol provability problem is NP-complete, even for provability
  in propositional logic.


What is the best known FPT result for 3-hitting set?

According to the Parameterized Complexity Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the PhD thesis of Magnus Wahlström.


Proof of the pumping lemma for context-free languages using pushdown automata

I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! Update: I submitted this proof on arXiv, in case this is useful to someone: http://arxiv.org/abs/1207.2819

$\DeclareMathOperator{\fp}{fp}$
$\DeclareMathOperator{\lp}{lp}$
$\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$
$\newcommand{\lpp}[1]{\widehat{\lp{#1}}}$

Let $L$ be a context-free language over an alphabet $\Sigma$. Let $A$ be a
pushdown automaton which recognizes $L$, with stack alphabet $\Gamma$. We denote
by $|A|$ the number of states of $A$. Without loss of generality, we can assume
that transitions of $A$ pop the topmost symbol of the stack and either push no
symbol on the stack or push on the stack the previous topmost symbol and some
other symbol.

We define $p' = |A|^2 |\Gamma|$ and $p = |A| (|\Gamma|+1)^{p'}$ the pumping
length, and will show that all $w \in L$ such that $|w| > p$ have a
decomposition of the form $w = u v x y z$ such that $|vxy| \leq p$, $|vy| \geq
1$ and $\forall n \geq 0, u v^n x y^n z \in L$.

Let $w \in L$ such that $|w| > p$. Let $\pi$ be an accepting path of minimal
length for $w$ (represented as a sequence of transitions of $A$), we denote its
length by $|\pi|$. We can define, for $0 \leq i < |\pi|$, $s_i$ the size of the
stack at position $i$ of the accepting path. For all $N > 0$, we define an
$N$-level over $\pi$ as a set of three indices $i, j, k$ with $0 \leq i
< j < k \leq p$ such that:

$s_i = s_k, s_j = s_i + N$
for all $n$ such that $i \leq n \leq j$, $s_i \leq s_n \leq s_j$
for all $n$ such that $j \leq n \leq k$, $s_k \leq s_n \leq s_k$.

(For an example of this, see the picture for case 2 below which illustrates an $N$-level.)

We define the level $l$ of $\pi$ as the maximal $N$ such that $\pi$ has an
$N$-level. This definition is motivated by the following property: if the size
of the stack over a path $\pi$ becomes larger than its level $l$, then the stack
symbols more than $l$ levels deep will never be popped. We will now distinguish
two cases: either $l < p'$, in which case we know that the same configuration
for the automaton state and the topmost $l$ symbols of the stack is encountered
twice in the first $p+1$ steps of $\pi$, or $l \geq p'$, and there must be a
stacking and unstacking position that can be repeated an arbitrary number of
times, from which we construct $v$ and $y$.

Case 1. $l < p'$. We define the configurations of $A$ as the couples
of a state of $A$ and a sequence of $l$ stack symbols (where stacks of size less
than $l$ with be represented by padding them to $l$ with a special blank symbol,
which is why we use $|\Gamma| + 1$ when defining $p$). By definition, there are
$|A| (|\Gamma| + 1)^l$ such configurations, which is less than $p$. Hence, in
the $p+1$ first steps of $\pi$, the same configuration is encountered twice at
two different positions, say $i < j$. Denote by $\widehat{i}$ (resp.
$\widehat{j}$) the position of the last letter of $w$ read at step $i$ (resp.
$j$) of $\pi$. We have $\widehat{i} \leq \widehat{j}$. Hence, we can factor $w =
u v x y z$ with $y z = \epsilon$, $u = w_{0 \cdots \widehat{i}}$, $v =
w_{\widehat{i} \cdots \widehat{j}}$, $x = w_{\widehat{j} \cdots |w|}$. (By $w_{x
\cdots y}$ we denote the letters of $w$ from $x$ inclusive to $y$ exclusive.) By
construction, $|vxy| \leq p$.

We also have to show that $\forall n \geq 0, u v^n x y^n z = u v^n x \in L$, but
this follows from our observation above: stack symbols deeper than $l$ are never
popped, so there is no way to distinguish configurations which are equal
according to our definition, and an accepting path for $u v^n x$ is built from
that of $w$ by repeating the steps between $i$ and $j$, $n$ times.

Finally, we also have $|v| > 0$, because if $v = \epsilon$, then, because we
have the same configuration at steps $i$ and $j$ in $\pi$, $\pi' = \pi_{0 \cdots
i} \pi_{j \cdots |\pi|}$ would be an accepting path for $w$, contradicting the
minimality of $\pi$.

(Note that this case amounts to applying the pumping lemma for regular languages
by hardcoding the topmost $l$ stack symbols in the automaton state, which is
adequate because $l$ is small enough to ensure that $|w|$ is larger than the
number of states of this automaton. The main trick is that we must adjust for
$\epsilon$-transitions.)

Case 2. $l \geq p'$. Let $i, j, k$ be a $p'$-level. To any stack
size $h$, $s_i \leq h \leq s_j$, we associate the last push
$\lp(h) = \max(\{y \leq j | s_y = h\})$ and the first pop
$\fp(h) = \min(\{y \geq j | s_y = h\})$.
By definition, $i \leq \lp(h) \leq j$ and $j \leq \fp(h) \leq
k$. Here is an illustration of this construction. To simplify the drawing, I omit the distinction between the path positions and word positions which we will have to do later.

We say that the full state of a stack size $h$ is the triple formed
by:

the automaton state at position $\lp(h)$
the topmost stack symbol at position $\lp(h)$
the automaton state at position $\fp(h)$

There are $p'$ possible full states, and $p' + 1$ stack sizes between $s_i$ and
$s_j$, so, by the pidgeonhole principle, there exist two stack sizes $g, h$ with
$s_i \leq g < h \leq s_j$ such that the full states at $g$ and $h$ are the same.
Like in Case 1, we define by $\lpp(g)$, $\lpp(h)$, $\fpp(h)$ and $\fpp(g)$ the
positions of the last letters of $w$ read at the corresponding positions in $\pi$.
We factor $w = u v x y z$ where $u = w_{0 \cdots \lpp(g)}$,
$v = w_{\lpp(g) \cdots \lpp(h)}$,
$x = w_{\lpp(h) \cdots \fpp(h)}$,
$y = w_{\fpp(h) \cdots \fpp(g)}$,
and $z = w_{\fpp(g) \cdots |w|}$.

This factorization ensures that $|vxy| \leq p$ (because $k \leq p$ by our
definition of levels).

We also have to show that $\forall n \geq 0, u v^n x y^n z \in L$. To do so,
observe that each time that we repeat $v$, we start from the same state and the
same stack top and we do not pop below our current position in the stack
(otherwise we would have to push again at the current position, violating the
maximality of $\lp(g)$), so we can follow the same path in $A$ and push the
same symbol sequence on the stack. By the maximality of $\lp(h)$ and the
minimality of $\fp(h)$, while reading $x$, we do not pop below our current
position in the stack, so the path followed in the automaton is the same
regardless of the number of times we repeated $v$. Now, if we repeat $w$ as many
times as we repeat $v$, since we start from the same state, since we have pushed
the same symbol sequence on the stack with our repeats of $v$, and since we do
not pop more than what $v$ has stacked by minimality of $\fp(g)$, we can follow
the same path in $A$ and pop the same symbol sequence from the stack. Hence, an
accepting path from $u v^n x y^n z$ can be constructed from the accepting path
for $w$.

Finally, we also have $|vy| > 1$, because like in case 1, if $v =
\epsilon$ and $y = \epsilon$, we can build a shorter accepting path for $w$ by
removing $\pi_{\lp(g)\cdots\lp(h)}$ and $\pi_{\fp(h)\cdots\fp(g)}$.

Hence, we have an adequate factorization in both cases, and the result is
proved.

(Credit goes to Marc Jeanmougin for helping me with this proof.)


Is the Chi-square divergence a Bregman divergence?

$\chi^2$-divergence is not a Bregman divergence.

I'll show it for sample size $n=1$. We would have
$$
(x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$
If $y=0$ and $x>0$ this says
$$x=f(x)-f(0)-xf'(0),$$
$$1=\frac{f(x)-f(0)}x-f'(0).$$
Taking $x\to 0^+$ this gives the contradiction $1=0$.


A least sized partition of a set under a distance metric

Ken Supowit proved that the following problem is NP-hard: Given a set $P$ of $n$ points in the Euclidean plane and an integer $k$, partition $P$ into $k$ clusters so that the largest cluster diameter is minimized.

  Kenneth J Supowit: "Topics in Computational Geometry"
  Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (1981), Report UIUCDCS-R-81-1062

Tomás Feder and Dan Greene proved that even the problem of approximating the smallest possible cluster diameter within a factor of $1.97$ is NP-hard.

  T Feder, D.H Greene: "Optimal algorithms for approximate clustering"
  Proceedings of the 20th Annual ACM Symposium on the Theory Computing (1988), pp. 434-444


There is an article on Langtons ant, published in the
SCTPLS Newsletter ( Society for Chaos Theory in Psychology & Life Sciences   Vol. 26, No. 2 February 2019 ) It introduces a first order recurrence relation for the cellular automata 'Langtons ant'   A copy can be downloaded from

http://buzwordsalad.com/lit/SCTPLS_LAWE_bw.pdf


Resources to find the "best" algorithm for a problem?

There's an attempt to build such a resource. It's called the Complexity Garden and is "the botanical companion to the Complexity Zoo". Also see this meta discussion.


Select in union of sorted arrays: Already known?

Frederickson and Johnson obtained an optimal result in the 80s. Let $p=\min(k,t)$, then there exist an algorithm solves your problem in $O(k+p \log \frac{t}{p})$.

Reference

G.N. Frederickson, D.B. Johnson "The complexity of selection and ranking in x+y and matrices with sorted columns"
J. Comput. System Sci., 24 (2) (1982), pp. 197–208


Containment problem of an acyclic NFA in an NFA

This is coNP-hard even if $B$ is also acyclic.

Let $D = \bigvee_{i=1}^m T_i$ be a DNF on variables $x_1, \dots, x_n$. We can easily contruct an NFA $B$ accepting exactly the satisfying assignment of $D$, that is, the words $w \in \{0,1\}^n$ such that the assignment $a$ defined as $a(x_i) = w_i$ satisfies $D$.

To do this, you build an automaton $B_i$ with $n+2$ states recognizing $T_i$ and add an initial state that non-deterministically chooses $i$ and jumps into $B_i$ with an $\epsilon$-transition.

$B_i$ has states $q_1, \dots, q_{n+1}$, and $reject$. Initial state is $q_1$. When in state $q_j$ for $j \leq n$: if $x_j$ does not appear in $T_i$, then you go in state $q_{j+1}$ for every value of the next letter. If $x_j$ appears positively in $T_i$, then you go in $q_{j+1}$ only if you read letter $1$. If you read letter $0$, you go in state $reject$. If $x_j$ appears negatively in $T_i$, you do the same by swapping $0$ and $1$. $q_{n+1}$ is the only final state.

Now you build $A$, acyclic, which accepts every word of length $n$ (same construction as before for $T_i$ empty).

It is clear that $L(A) \subseteq L(B)$ iff $D$ is a tautology, which is
coNP-complete.


Layman Interpretation: Quantum Factoring Algorithm

The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time.

The most general representation of the quantum state of $n$ qubits is the $2^n \times 2^n$ density matrix $\rho$, where the diagonal entries correspond to the probability of finding the system in a particular classical state, and the off diagonal entries indicate the phase of the superposition (going to 0 for classical probability distributions).

Any quantum algorithm can be seen as a unitary operation followed by some measurement in the computational basis. Given an initial input state $\rho$, it will evolve to $\rho' = U\rho U^\dagger$. The most general set of measurements that can be performed are called positive operator valued measurements(POVMs), where each measurement outcome $i$ is associated with a positive sei-definite Hermitian operator $P_i$ and the probability of outcome $i$ is given by $p_i = \mbox{Tr}(P_i \rho)$ (and hence $\sum_i P_i = \mathbb{I}$).

Within these constraints the operations you describe simply are not possible.


What is the enlightenment I'm supposed to attain after studying finite automata?

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole.

Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. Understanding this difference for Turing machines is at the core of (theoretical) computer science. NFAs and DFAs provide the simplest example I know where you can explicitly see the strict gap between determinism and non-determinism.
Computability != Complexity. NFAs and DFAs both represent regular languages and are equivalent in what they compute. They differ in how they compute.
Machines Refine Languages. This is a different take on what we compute and how we compute. You can think of computable languages (and functions) as defining an equivalence class of automata. This is a fundamental perspective change in TCS, where we focus not just on the what, but the how of computation and try to choose the right 'how' when designing an algorithm or understand the space of different how's in studying complexity classes.
The Value of Canonical Representation. DFAs are the quintessential example of a data-structure admitting a canonical representation. Every regular language has a unique, minimal DFA. This means that given a minimal DFA, important operations like language inclusion, complementation, and checking acceptance of a word become trivial. Devising and exploiting canonical representations is a useful trick when developing algorithms.
The Absence of Canonical Representations. There is no well accepted canonical representation of regular expressions or NFA. So, despite the point above, canonical representations do not always exist. You will see this point in many different areas in computer science. (for example, propositional logic formulae also do not have canonical representations, while ROBDDs do).
The Cost of a Canonical Representation. You can even understand the difference between NFAs and DFAs as an algorithmic no-free-lunch theorem. If we want to check language inclusion between, or complement an NFA, you can determinize and minimize it and continue from there. However, this "reduction" operation comes at a cost. You will see examples of canonization at a cost in several other areas of computer science.
Infinite != Undecidable. A common misconception is that problems of an infinitary nature are inherently undecidable. Regular languages contain infinitely many strings and yet have several decidable properties. The theory of regular languages shows you that infinity alone is not the source of undecidability.
Hold Infinity in the Palm of Your Automaton. You can view a finite automaton purely as a data-structure for representing infinite sets. An ROBDD is a data-structure for representing Boolean functions, which you can understand as representing finite sets. A finite-automaton is a natural, infinitary extension of an ROBDD.
The Humble Processor. A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata.
The Algebraic Perspective. Regular languages form a syntactic monoid and can be studied from that perspective. More generally, you can in later studies also ask, what is the right algebraic structure corresponding to some computational problem.
The Combinatorial Perspective. A finite-automaton is a labelled graph. Checking if a word is accepted reduces to finding a path in a labelled graph. Automata algorithms amount to graph transformations. Understanding the structure of automata for various sub-families of regular languages is an active research area.
The Algebra-Language-Combinatorics love triangle. The Myhill-Nerode theorem allows you to start with a language and generate an automaton or a syntactic monoid. Mathematically, we obtain a translation between very different types of mathematical objects. It is useful to keep such translations in mind and look for them in other areas of computer science, and to move between them depending on your application.
Mathematics is the Language of Big-Pictures. Regular languages can be characterised by NFAs (graphs), regular expressions (formal grammar), read-only Turing machines (machine), syntactic monoids (algebra), Kleene algebras (algebra), monadic second-order logic, etc. The more general phenomenon is that important, enduring concepts have many different mathematical characterizations, each of which brings different flavours to our understanding of the idea.
Lemmas for the Working Mathematician. The Pumping Lemma is a great example of a theoretical tool that you can leverage to solve different problems. Working with Lemmas is good practice for trying to build upon existing results.
Necessary != Sufficient. The Myhill-Nerode theorem gives you necessary and sufficient conditions for a language to be regular. The Pumping Lemma gives us necessary conditions. Comparing the two and using them in different situations helped me understand the difference between necessary and sufficient conditions in mathematical practice. I also learnt that a reusable necessary and sufficient condition is a luxury.
The Programming Language Perspective. Regular expressions are a simple and beautiful example of a programming language. In concatenation, you have an analogue of sequential composition and in Kleene star, you have the analogue of iteration. In defining the syntax and semantics of regular expressions, you make a baby step in the direction of programming language theory by seeing inductive definitions and compositional semantics.
The Compiler Perspective. The translation from a regular expression to a finite automaton is also a simple, theoretical compiler. You can see the difference between parsing, intermediate-code generation, and compiler optimizations, because of the difference in reading a regular expression, generating an automaton, and then minimizing/determinizing the automaton.
The Power of Iteration. In seeing what you can do in a finite-automaton with a loop and one without, you can appreciate the power of iteration. This can help understanding differences between circuits and machines, or between classical logics and fixed point logics.
Algebra and Coalgebra. Regular languages form a syntactic monoid, which is an algebraic structure. Finite automata form what in the language of category theory is called a coalgebra. In the case of a deterministic automaton, we can easily move between an algebraic and a coalgebraic representation, but in the case of NFAs, this is not so easy.
The Arithmetic Perspective. There is a deep connection between computation and number-theory. You may choose to understand this as a statement about the power of number theory, and/or the universality of computation. You usually know that finite automata can recognize an even number of symbols, and that they cannot count enough to match parenthesis. But how much arithmetic are they capable of? Finite automata can decide Presburger arithmetic formulae. The simplest decision procedure I know for Presburger arithmetic reduces a formula to an automaton. This is one glimpse from which you can progress to Hilbert's 10th problem and it's resolution which led to discovery of a connection between Diophantine equations and Turing machines.
The Logical Perspective. Computation can be understood from a purely logical perspective. Finite automata can be characterised by weak, monadic second order logic over finite words. This is my favourite, non-trivial example of a logical characterisation of a computational device. Descriptive complexity theory shows that many complexity classes have purely logical characterisations too.
Finite Automata are Hiding in Places you Never Imagined.  (Hat-tip to Martin Berger's comment on the connection to coding theory) The 2011 Nobel Prize in Chemistry was given to the discovery of quasi-crystals. The mathematics behind quasi-crystals is connected to aperiodic tilings. One specific aperiodic tiling of the plane is called the Cartwheel Tiling, which consists of a kite shape and a bow-tie shape. You can encode these shapes in terms of 0s and 1s and then study properties of these sequences, which code sequences of patterns. In fact, if you map 0 to 01 and 1 to 0, and repeatedly apply this map to the digit 0, you will get, 0, 01, 010, 01001, etc. Observe that the lengths of these strings follow the Fibonacci sequence. Words generated in this manner are called Fibonacci words. Certain shape sequences observed in Penrose tilings can be coded as Fibonacci words. Such words have been studied from an automat-theoretic perspective, and guess what, some families of words are accepted by finite automata, and even provide examples of worst-case behaviour for standard algorithms such as Hopcroft's minimization algorithm. Please tell me you are dizzy.

I could go on.(And on.)* I find it useful to have automata in the back of my head and recall them every now and then to understand a new concept or to gain intuition about high-level mathematical ideas. I doubt that everything I mention above can be communicated in the first few lectures of a course, or even in a first course. These are long-term rewards based on an initial investment made in the initial lectures of an automata theory course.

To address your title: I don't always seek enlightenment, but when I do, I prefer finite automata. Stay thirsty, my friend.


Derivation of cut rule in sequent calculus

The fact that a system is complete for proving valid formulas without the cut rule doesn't mean you can derive the cut rule from other rules.

In fact it is not difficult to construct counter-examples. Consider
$\Rightarrow A \rightarrow B$ and $\Rightarrow A$. From these assumptions it would follow that $\Rightarrow B$. But you cannot derive it without using a cut.


Bidirectional typing for dependent types: Why are Sigma, Pi synthesized?

IMHO, it's not like constructors are checked, but introduction rules (including tuples, lambdas, data constructors, etc.) are checked (while elimination rules are synthesized). The kind constructors you mentioned are called formation rules, which are not introduction rules. You can also think this way: if a constructor is checked, then it has a corresponding eliminator which is synthesized. If type constructors should be checked, there should be a corresponding thing synthesized. But there's no such thing (you can't pattern match on $\cal U$).


Is SAT with two "opposite" solutions NP-hard?

Turning my comment to an answer:
The problem you describe is known as Not All Equal SAT (NAE-SAT), but is phrased differently. A NAE assignment for a CNF-formula $\phi$ over variables is one where in each clause there is at least one false variable and one true variable.

It is easy to see that an assignment is NAE iff its inverse is also NAE.

Showing that NAE-SAT is NP-complete is a well-known exercise, and it can be easily solved by splitting it to two parts.

First, given a 3-CNF formula, we can convert it to a 4-CNF formula by adding a variable $w$ and converting every clause of the form $(x\vee y\vee z)$ to $(x\vee y\vee z\vee w)$.

It is easy to see that the original formula is satisfiable iff the resulting formula is in NAE-SAT.

Then, standard techniques can be used to convert this formula back to 3-CNF, while maintaining the NAE property.


I assume you are given an undirected network $G$, and two vertices $s,t$, and you wish to maximize the flow from $s$ to $t$, while directing the edges of $G$. In this case, you can just use the normal Ford-Fulkerson algorithm with the following modification:

Every time you take an augmenting $s$-$t$ path in $G$ and send flow along it, direct the edges along the path. Eventually, your algorithm will stop, and all edges (except those with flow 0) will have a direction. The flow will be maximal, which can be proven using the max-flow-min-cut theorem.


Using game-based proofs in simulation-based proofs

One paper that deals with the issue is Games and the impossibility of Realizable Ideal Functionality by Datta et al, but it does't seem to address the issue in full generality. I am not aware of any general statement that guarantees simulation-based security of the whole protodol based on specific game-based security properties of its sub-protocols (unless of course the game-based definitions imply simulation based security, in which case the generic composition theorems by Canetti should apply).

However, there do exist specific instances in which one can obtain simulation-based security from game based security. The most telling example in my view is a constant-round zero-knowledge (ZK) argument for NP by Feige and Shamir (see e.g. Feige's PhD), which builds on witness indistinguishabille (WI) and witness-hiding (WH) sub-protocols. Both WI and WH are (arguably) game-based definitions, and yet the entire protocol can be proved to be ZK (which is the mother of all simulation-based definitions, at least for interactive protocols).


Resolution vs Nondeterministic Search Problems

If I understood correctly the question, the so-called Buss-Pudlak game provides a simple transformation from a proof system to such a decision tree (see Buss-Pudlak '94 http://math.cas.cz/%7Epudlak/howtolie.ps). The queries are formulas (not just variables). The tree is also completely deterministic.

Other decision trees that correspond to different propositional proof systems exist: e.g., Linear Decision Trees correspond to Res(lin) refutations (cf., http://www.csc.kth.se/~sokolovd/files/papers/splitting.pdf and http://cs.rhul.ac.uk/home/tzameret/Res-Lin-Two.pdf). But there are many other examples (cf., Tonian Pitassi's work on CP-like proof systems).


I found the solution of the solution of this algorithm in this book: Handbook of Scheduling: Algorithms, Models, and Performance Analysis .

In Theorem 3.4, they show an optimal algorithm for the preemptive case.
The largest processing time first algorithm has worst case bound of $\frac{4}{3} − \frac{1}{3k} $ if $t_i=0, \forall i$ for non-preemptive case

I will apply this largest processing time first to the general case and see how it works in practice.


What are the open ended questions for an CS Undergraduate to think about?

Of course, for us in academia, most problems are fun anyway: we would not be there otherwise ;) But I understand that you might be more interested in problems which do not require much background and/or which are related to mundane topics like social games. Note that it might be harder (and more important) for you to find someone willing to comment on your solution and help you to improve it than to find a fun problem itself. For this reason,  asking a professor in your department might be a better starting point. That said, here are some suggestions as to where to find ideas, and a modest proposal of mine.

Have a look at the  proceedings of the conference "Fun with Algorithms": they should provide you with a good selection of "Fun" problems to work on, and a venue where to submit your results for feedback.
Check the publications of people known to consider fun problems and problems for fun. For instance:

Kurt Mehlhorn has several, one of the latest being a study of a variant of the game "Master Mind", published in "The Query Complexity of Finding a Hidden Permutation" (another one of his is a mathematical model for how a mold can compute the path of minimal length in a maze).
Erik Demaine has a long sequence of such problems, one of the latest being the study of variants of the game "Instant Insanity".
Elkhanan Mossel wrote a nice study of the "Mine Sweeper game".

Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!

Levitating Towers

As an undergraduate, you probably know the problem of the Hanoi Tower. If you want to "have fun", you might consider simple variants of it. Here is a very simple variant you might be interested in, which I designed for an assignment while I was a TA for an algorithm course, but never gave to students because I found it too hard for undergraduate (at least too hard for a marked assignment).

Consider the case where you insert and remove disks always in the middle of the tower (defined in a symmetric way when the number of disks is even, so that you always remove the last disk that you inserted), while keeping at all time the constraint that no disk stands upon a smaller one. In how many moves can you move a tower of $n$ disks from one peg to another?

The exact answer is not known. I obtained at the time a complicated upper bound of $2^{n/2}$ via a combination of 3 recursive functions. The graph of all possible states and transitions (a classical way to study the original Hanoi tower problem) is fragmented. I believe there should be a reduction to the original problem but did not find it when I played with it.

Play with it. An example of the difficulty of the analysis (say, for symmetric rules removing the lower middle disk when the number of disks on a peg is even, and inserting below the center disk when the number of disk is odd) is the case where there is $1$ small disk (e.g. $1$) on the destination peg and $2$ larger ones (e.g. $8,9$) on the source peg. This particular sub-tower of height $2$ can be moved without any intermediate peg in $2$ moves (as opposed to $3$ moves and one intermediate peg in the traditional Hanoi tower): the removal order of the source peg is the same as the insertion order of the destination peg.


The theoretical complexity of Go - The state of the art

The state of the art for the theoretical complexity of go is well summed up on Wikipedia, with relevant references.

The main remaining open problem is for rules using a superko, i.e. repeating any past position is forbidden. This is the rule used for instance in China  and western countries. It is simple to state, but could bring some difficulties to actually play in some situations, as players need (in theory) to remember all the history of the game. In reality, these situations are so rare that it does not matter. For this rule, as you mention, we only know that deciding the winner from a given position is PSPACE-hard and in EXPSPACE.

On the other hand, it is known from Robson that Go with Japanese rules is EXPTIME-complete. These are the rules using local ko, only forbidding to repeat the last  position, and declaring draw if a longer cycle occur. These rules have to include many special cases to settle the situation for particular configurations, and although they are considered more practical for human players, especially for beginners to learn about the ko rule, they are not elegant mathematically.

You can see a sketch of Robson's proof that Go with Japanese rules is EXPTIME-hard here, with fun go positions using ladders to encode boolean formulas.


Clustering of letters - what approach would give the best results?

Check my project ImSim at sf.net: http://sourceforge.net/projects/imsim Actually it's just a very short, simple and single script in Python. It can be adjusted for the purpose of clusterizing very easily.
P.S. Remove resizing from it -- I guess you need not it.
P.P.S. Surely you know PIL library.


I don't have an actual answer, but here's some evidence that the problem is open:

It's not mentioned in Ming Li, Luc Longpré and Paul M. B. Vitányi, "The power of the queue", Structures 1986, which considers several other closely related simulations
It's not mentioned in Martin Hühne, "On the power of several queues", Theor. Comp. Sci. 1993, a follow-on paper.
It's not mentioned in Holger Petersen, "Stacks versus Deques", COCOON 2001.
Burton Rosenberg, "Fast nondeterministic recognition of context-free languages using two queues", Inform. Proc. Lett. 1998, gives an O(n log n) two-queue algorithm for recognizing any CFL using two queues. But a nondeterministic pushdown automaton can recognize CFLs in linear time. So if there were a simulation of a stack with two queues faster than O(log n) per operation, Rosenberg and his referees should have known about it.


Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?

BQPSPACE can only use polynomial qbits, but its computation is driven by a classical machine. This classical machine also only gets a polynomial number of bits. Thus, the classical computer limits the number of steps to simply exponential, regardless of what the quantum computer does.

The limitation of exponential length circuits by polynomial size algorithms is due to the computer creating the circuit getting in an infinite loop, not about the state or details of the circuit itself. Quantum circuits are no different.


Is an NP-hardness proof of an NP-hard problem considered a contribution?

There are venues that are interested by elegant proofs of existing results, see for instance the Symposium on Simplicity in Algorithms.

So yes, in some cases an elegant proof can be considered as a contribution, especially if it offers new insights.


Why use two separate tables in cuckoo hashing?

One reason is that when there is only one set of slots, there will be some keys such that $h_1(k) = h_2(k)$.


randomness extraction of real valued sequences of numbers

First, it depends how the quantization of the real values is performed.
Using 8 bits can be really different from using 16 for example.

Assuming that a fixed number of bits is chosen, hash functions are a good and simple way to extract randomness.

Universal Hash Functions are families of hash functions that can be securely used in this context (not all hash functions are suitable for this).


How do journals serve the TCS community?

The process of journal reviewing shakes out bugs. Conference reviewers tend not to look at papers with a fine-tooth comb; the program committee process gives them too many papers to review in too short a time to do that. The main things that one should get out of a conference review are whether there are obvious flaws (these are rare) and whether the results are interesting. A journal review should evaluate those things too, of course, but it also needs to check the details of the proofs to make sure that they all work and are clearly and correctly stated.

If you are treating your journal reviewing tasks as if they were conference reviews, and only giving them a high-level interestingness check, you are doing it wrong, and depriving journal authors of a valuable service. If you are treating your conference reviews like journal reviews, spending the time to go over them carefully, and making sure that papers don't get accepted until all the details are correct, congratulations and thank you for doing such a good job, but I don't think that's the case for most STOC/FOCS/SODA program committee members.

Secondarily, many conferences still have artificially small page limits, and the journal provides space to fill in the details. The preprint version does that, too, but doesn't provide any assurance that someone has checked it carefully.

If I see a paper published five or more years ago in a conference, making claims that are not backed up by full and clearly-written detail in the proceedings, and with no journal version, I am likely to consider it untrustworthy. Is that the future you want for your research?


I don't have access to the Poljak et al. paper, but the abstract here seems to indicate that recognizing line-graphs of $r$-hypergraphs is NP-complete for $r \geq 3$, not $4$. Also, the citation in Edge intersection graphs of linear 3-uniform hypergraphs, Skums et al. (pdf) seems to indicate that this is the case:

  The situation changes principally if one takes $k=3$ instead of $k=2$. Lovasz posed the problem of characterizing the class $L_3$, and noted that it has no characterization by a finite list of forbidden induced subgraphs (a finite characterization) [10]. It has been proved that recognition problems "$G \in L_3$" [17] and "$G \in L^l_k$" for $k\geq3$ [5] are NP-complete.

Reference 17 in that paper is the aforementioned Poljak et al. (1981). $L_3$ is the class of 3-uniform hypergraphs and $L^l_3$ is the class of linear 3-uniform hypergraphs.


Properties expressible in 2-CNF or 2-SAT

A family of bitvectors is the class of solutions to a 2-SAT problem if and only if it has the median property: if you apply the bitwise majority function to any three solutions you get another solution. See e.g. https://en.wikipedia.org/wiki/Median_graph#2-satisfiability and its references. So if you can find three solutions for which this is not true, then you know it cannot be expressed in 2-CNF.


Assumption: Exponential time hypothesis.
First cited in: While being folklore, it was first formalized in the following paper: Russell Impagliazzo and Ramamohan Paturi. 1999. The Complexity of k-SAT. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 237-240.
Use(s): It assumes that no NP-complete problem can be decided in sub-exponential time, and therefore implies that P ≠ NP.
Status: Open.


Joy comes to mind. It's a simple concatenative language that involves manipulations on a stack. It's essentially a reverse Polish notation for combinatory logic with quoting, developed by a professor of logic and programming so presumably it was taught in class. :)

I'm not 100% sure what qualifies as as denotational semantics, but, there is an algebra for it:

http://www.kevinalbrecht.com/code/joy-mirror/j04alg.html


How to benchmark #2-SAT counting algorithms?

I am not aware of any collections of 2CNF benchmark instances.

However, one practical way of constructing #2-SAT instances that are provably hard for state-of-the-art model counters is as follows: generate a $d$-regular expander for some constant $d$ (so in practice a random $d$-regular graph), then, as holf suggested, construct the 2CNF-formula that has for every edge $uv$ the clause $x_u\lor x_v$. By this paper

https://arxiv.org/abs/1411.1995

of Bova et al, the resulting formulas do not have small circuits of the form that is called DNNF in knowledge compilation, as subfield of artificial intelligence. Then by connections between DPLL-based model counting and DNNF that can be found in

Huang, Jinbo, and Adnan Darwiche. "DPLL with a trace: From SAT to knowledge compilation." IJCAI. Vol. 5. 2005.

it follows that all DPLL-based model counters will take exponential time to solve the above instances. Since all exact model counters that I am aware of (except for this knowledge compiler that can also used for counting http://www.cril.univ-artois.fr/KC/eadt.html ) are based on exhaustive DPLL, this should answer your alternative question.

Note that the results of Bova et al. are rather asymptotic (there are some small hidden constants in the analysis) but from my experience with similar problems, actual implemented model counters should fail quite early on those instances.

Note that these instances might not be the ones you are looking for: instead of challenging state-of-the-art model counters, they just outright break them provably. So to work around this, you would have to completely change the approach from DPLL to something else similarly to the compiler I linked above (which I don't think will work on these instances, either).


Does the physical Church-Turing thesis imply that all physical constants are computable?

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment.

I don't believe (b) is the case. Generally, the way that constants are measured is by measuring the ratios of some physical quantity that we can measure directly, like time, and using this ratio to compute the constant. The smallest unit of time that exists is believed to be on the order of the Planck time, which is $5.39 \times 10^{ −44}$ s. The age of the universe is $4.32 \times 10^{17}$ s. Thus, if we constrain our experiment to take no more time than the age of the universe, we can measure time to at most 61 digits of accuracy, so this is the limit of accuracy for the fine structure constant. This constant can easily be hard-coded in a Turing machine.

Is (a) the case? That may be a matter for philosophers. If changing the 100th digit of a physical constant has absolutely no impact on the dynamics of the universe, does that constant really have an infinite nuber of decimal places?

UPDATE: The best you could hope for (and I don't believe physicists currently know how to do this) is an experiment that measured $k$ digits of the fine structure constant in time $2^k$. In this case, the strongest version of the physical Church-Turing thesis would imply that the fine structure constant is computable. But you would be able to simulate an experiment that took $2^k$ years to carry out by using an oracle that gave you $O(k)$ bits.


How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Indeed: Eppstein has shown that the TSP can be solved in time $O(1.26^n)$ if all vertices are of degree at most 3.

  David Eppstein:
  The Traveling Salesman Problem for Cubic Graphs.
  J. Graph Algorithms Appl. 11(1): 61-81 (2007)

Some tiny improvements of this result are also known, for instance by Liśkiewicz and Schuster (2014) to $O(1.255^n)$.


Complexity of #PP2DNF where we also count on the number of clauses

The problem is #P-hard, as we prove in a recent preprint: https://arxiv.org/abs/1908.07093

The way the preprint is phrased is closer to the equivalent formulation of the problem given at the end of my question: you have a bipartite graph $(X \cup Y, E)$ and you want to know how many triples $(X', Y', E')$ of subsets $X' \subseteq X$, $Y' \subseteq Y$, $E' \subseteq E$ there are such that we keep two vertices in $X'$ and $Y'$ connected by an edge in $E'$, i.e., $E' \cap (X' \times Y')$ is non-empty. This can again be equivalently reformulated in database or first-order logic terminology, which is what the preprint uses: you have a structure consisting of facts $R(a_1), \ldots, R(a_n)$, $T(b_1), \ldots, T(b_m)$, and $S(a_{i_1}, b_{j_1}), \ldots, S(a_{i_k}, b_{j_k})$ coding the bipartite graph (without multi-edges, i.e., $(a_{i_p}, b_{j_p}) \neq (a_{i_q}, b_{j_q})$ for all $p \neq q$), and you want to know how many subsets of these sets of facts satisfy the conjunctive query $\exists x \, y ~ R(x) \land S(x, y) \land T(y)$.

In the terminology of the preprint, this query is a self-join-free non-hierarchical conjunctive query (indeed, it is the simplest such example of a query, which we call $Q_1$), and hardness of this problem (the so-called model counting problem) is shown in the preprint: this is the simplest case of Theorem 4.2, with $r=1, s=1, t=1$.


What are good approximation algorithms for the subset sum problem so far?

Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme.

Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. In addition, answering your question on "relatively fast running time", they noted that (based on computational results) that the scheme efficiently solves instances with up to $5000$ items with a guaranteed relative error smaller than $1/1000$.

I am unsure if there are any newer results. As noted, because subset sum is a special case of the knapsack problem, one will probably find even more results when searching for that.

UPDATE: You might also want to take a look at The Design of Approximation Algorithms, Williamson and Shmoys, 2011, see the chapter starting at page 65 about the Knapsack problem. They give a FPTAS (on page 68) for the Knapsack problem that runs in $O(n^3/\epsilon)$ time. It might be that the algorithms specifically designed for the Subset sum problem are faster than the more general ones for the Knapsack.


Emptiness of PDA without constructing the corresponding CFG

Quick Answer: Yes, there is a really lovely algorithm that solves non-emptiness for pushdown automata that does not involve constructing the equivalent CFG.

Possible Drawback: Correct me if I am wrong, but it doesn't appear to be more efficient than the approach where you convert to a CFG.

Basic Idea: It can be viewed as a sort of dynamic programming algorithm where you solve reachability without ever constructing the possibly exponential length paths that you need to consider.

You start with a state diagram for a Pushdown Automata. Let's call a transition that doesn't manipulate the stack a resting transition. You proceed with a series of stages.

Start of Stage: You combine all compatible push and resting transitions. Next, you combine all compatible pop and resting transitions. Then, you combine all compatible pairs of resting transitions with each other.  Finally, you combine all compatible push and pop transitions.  Now, you throw in all of the new transitions into the state diagram.  End of Stage.

You go through stage after stage repeating this process.  There are only so many possible transitions.  Eventually, you either get a transition that leads from the start state to a final state or you must run out of possible transitions to add.  At this point, you know whether the automata's language is empty or not.

Question: Can you provide me with any books or papers that give a good exposition of this algorithm?  Whenever I searched for it several years ago, it seemed that this algorithm is unpopular or not well known.  I personally really like it.

Thanks for asking the question!  I really appreciate it and I hope this helps a little bit.  Have a nice day!  :)


Is there an $\mathcal{L}$-theory and a formula $\phi$ for which Kolmogorov(proof($\phi$)) $<$ Kolmogorov($\phi$)?

In most "standard" proof systems, the formula $\varphi$ being proved is usually part of the proof itself by definition of the proof system, in which case for all $\varphi$, $K(\varphi) \leq K(\text{proof}) + O(1)$ (the extra constant is for the part of the program which says, basically, "extract the last line of the proof" - anyways, additive $O(1)$ errors are the best one can hope for in Kolmogorov complexity).

Even in a proof system where all that is required is that the formula $\varphi$ appear somewhere amongst the lines of the proof $\pi$, one can still get $K(\varphi) \leq K(\pi) + O(\log|\pi|)$, where here the extra $\log|\pi|$ bits are used to describe the index $i$ of the line of the proof that corresponds to $\varphi$.

In the much more general Cook-Reckhow style of proof system (or its computable analog) - that is, a polynomial-time computable function $f$ (resp., just a computable function $f$) whose range is exactly the set of true sentences of your theory - again, $K(\varphi) \leq K(\text{proof}) + O(1)$, where here the $O(1)$ extra bits describe the function $f$.

(Note that the trick of hard-coding certain tautologies into your proof system, pointed out by Kaveh, is handled by this latter case, as the hard-coded tautologies must be encoded directly into $f$, so they contribute to/are handled by the $O(1)$.)


Real representation versus communication complexity

The minimal degree of a real polynomial representing the parity function of $n$ variables is $n$. However, the deterministic communication complexity is at most $2$ bits.


Is the transducer version of BPP closed under complement?

No. For example, if your input is a CNF with few solutions, then you can randomly generate non-satisfying assignment: just generate an assignment and keep it if it's non-satisfying. But generating a satisfying assignment is NP-hard.


See Venema, Yde. Temporal Logic. The blackwell guide to Philosophical Logic.


In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part.  [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.]  They also describe a more complicated dictionary data structure, based on biased skip lists, that supports merges in $O(\log n)$ amortized time.

On the other hand, a worst-case bound of $O(\log n)$ is impossible.  Consider two binary search trees with $n$ nodes, one storing the even integers between $2$ and $2n$, the other storing the odd integers between $1$ and $2n-1$.  Merging the two trees creates a new binary search tree storing all integers between $1$ and $2n$.  In any such tree, a constant fraction of the nodes have different parity than their parents.  (Proof: The parent of an odd leaf must be even.)  Thus, merging the even and odd trees requires changing $\Omega(n)$ pointers.


Is it sometimes better to not publish at all?

I was just referred to this question by graduate students that, in my opinion, were far too influenced by the answers. So let me start with two generic advises.

To the aspiring scientist: Don't assign too much weight to any answer on such matters, and don't assume that a small and highly non-random sample represents the common views among senior (or non-senior) people in the community. In general, think for yourself!
See http://www.wisdom.weizmann.ac.il/~oded/advice.html for more details...
To the senior scientist: Be careful about what you say, since it may be misinterpreted in harmful ways and/or have more impact than what you intend and/or perceive.

Re the discussion itself, I think that the idea that credits are non-monotone is not only utterly non-intuitive but also utterly wrong, and I am talking as a person who sat on numerous committees that took various career decisions. A person who has $X$ fundamental contributions, $Y$ important contributions, and $Z+1$ nice/legitimate contribution is ranked higher than one who has $(X,Y,Z)$, regardless of the numerical values of $X,Y,Z$ and assuming that quality captured by the $(X,Y,Z)$ triples is exactly the same. Trade-offs between different types is a different question, ditto re how much credit does each increase give...

In other words, for any set of works $S$ and any additional work $a$,
the credit of $S \cup \{a\}$ is (strictly) bigger than to $S$ [i.e., strict monotonicity].

In my opinion, people who claim the opposite just assume that a larger number $Z$ implies a decrease in what the value of $X$ (or $Y$) could have been. But this assumption may be wrong and more importantly is irrelevant to the comparison at hand. That is, if you compare a case of $(X,Y,Z)$ to one of $(X,Y,Z+1)$, you must rule that the second person (called B) was able to meet the performance of the first (called A) although B also did another work of 3rd type; so B is clearly better. Indeed, you may think that B could have done better investing more energy in Type 1 (which is not always true - see below), but that's a comparison against an imaginary B, not against A. (And when you have a case of $(X,Y,Z)$ against $(X,Y,Z+10)$, the same holds is stronger terms.)

In addition, I think there is also a confusion between the works and the publications. If a work already exists in writing, and assuming that it has its merits, then it can only be advantageous to publish it in a adequate venue, where by adequate I mean one that is intended for works of this profile (wrt quality and scope - publication in a too prestigious conference may actually hurt, since it may generate some annoyance and even bad opinions re the author). But if one still has to develop a work from an initial idea (or "only" write it - which always involves some more research...), then one may consider the trade-off between the amount of time required versus the importance of the work.

Finally, as I hinted above, it is not clear that one is better off aiming all the time at Type 1 (i.e., fundamental work). Firstly, this is infeasible and thus problematic/harmful. Secondly, and more importantly, one is always better off following the inherent logic of his/her own interests and ideas/feelings, and aiming to do as well as possible. See more in the aforementioned webpage.

Oded Goldreich