Is there such a thing as a weak coalgebra homomorphism? Given an endofunctor $F : Set \rightarrow Set$, we can define observation functions as functions that are polymorphic for any $F$-coalgebra, that is $obs$ is defined for any $F$-coalgebra $\langle A, c : A \rightarrow FA\rangle$.
$$
obs : \forall \langle A, c \rangle . A \to B
$$
Another way of looking at observation functions is as functions of the final $F$-coalgebra if it exists. We get the polymorphism automatically by composing the observation function with the unique homomorphism to the final $F$-coalgebra. But this only works if the final $F$-coalgebra exists.

One of the defining characteristics of an observation function is that it cancels any coalgebra homomorphism composed to the right, due to its polymorphism. If $hom$ is an $F$-coalgebra homomorphism, then:
$$
obs = obs \circ hom
$$
During my research, in an attempt to define a notion of observational consistency between one coalgebra and another, I had the idea of a weak coalgebra homomorphism. The idea is that we can "fake" a coalgebra homomorphism if we know the observation function ahead of time. Thus, we might satisfy,
$$
obs = obs \circ hom
$$
but only for one particular $obs$.

For example, let $FX = \{0,1\} \times X$, and let $obs$ be defined as
$$
obs : \forall \langle A, c\rangle. A \to \{0,1\}^2
$$ $$
obs = \langle (\pi_1 \circ c), (\pi_1 \circ c \circ \pi_2 \circ c) \rangle
$$
That is, $obs$ takes the first two elements of a stream.

Then, an F-coalgebra homomorphism would need to ensure that it preserves all the elements of the stream, whereas a weak homomorphism for $obs$ only needs to preserve the first two elements of the stream.

In my research, this notion would be useful in order to show that one coalgebra is observationally consistent with another by showing that every finite linear observation function has a weak homomorphism from the first coalgebra to the second coalgebra. In other words, every finite linear observation on the first coalgebra can be reproduced on the second coalgebra.

(What I mean by linear observation function feels mostly irrelevant, but for the sake of sharing... A linear observation function is more or less one that uses each state of the carrier set only once. I'm trying to model an oracle, and the user is not allowed to go back and pretend it never asked a question.)

My questions are thus:

Has this been researched? Do "weak coalgebra homomorphisms" exist already, under some other name perhaps?
Is there a more "category theory" way to present this?

Edit: Removed two questions which aren't that important.

The `weak morphisms' you describe do have a name in a slightly restricted setting. They can also be defined quite generally, as I'll explain.

In the case where $T : \mathsf{Set} \to \mathsf{Set}$ preserves weak pullbacks (many natural functors on $\mathsf{Set}$ do) it is known that behavioural equivalence coincides with coalgebraic bisimilarity. Then your morphisms are known as functional $\alpha$-step bisimulations where  $\alpha$ is an ordinal. Admittedly I've only ever seen them defined for ordinals $\alpha \leq \omega$. Prior to coalgebra, modal logicians had studied n-step bisimulations for Kripke frames, which amount to n-step bisimulations for coalgebras for the powerset functor. Your requirement that they be functions as opposed to relations makes them functional n-step bisimulations.

On the other hand, you can define the concept you are talking about in a far more general setting without referring to coalgebraic bisimulations. For any category $\mathbb{C}$ which has limits of ordinal-indexed cochains and any functor $T : \mathbb{C} \to \mathbb{C}$ one can define $T$ 's terminal sequence. The condition regarding limits is actually rather weak e.g. many categories (including $\mathsf{Set}$) are actually complete i.e. have all small limits. The terminal sequence is a diagram in $\mathbb{C}$ and looks like:

$1 \quad \xleftarrow{!_{T1}} \quad T1 \quad \xleftarrow{T !_{T1}} \quad T^2 1 \quad \xleftarrow{T^2 !_{T1}} \quad \dots \quad T^\omega 1  \quad \xleftarrow{f_\omega^{\omega + 1}} \quad T(T^\omega 1) \quad \xleftarrow{Tf_\omega^{\omega + 1}} \quad \dots$

Here $1$ is the terminal object in $\mathbb{C}$ (limit of empty cochain). For example in $\mathsf{Set}$ this can be taken to be the one element set $1 = \{*\}$. The map $!_{T1} : T1 \to 1$ is the unique morphism into the terminal object e.g. in $\mathsf{Set}$ is simply maps every element of $T1$ to $*$. Each $T^n 1$ is computed by iterating $T$ and $T^\omega 1$ is the limit of the cochain preceding it. One can then continue beyond $\omega$, if necessary. Intuitively $T^\alpha 1$ is the collection of  $\alpha$-step behaviours.

Now any $T$-coalgebra $(Z,\gamma)$ induces a cone over this sequence i.e.  a collection of $\mathbb{C}$-morphisms $\mathsf{beh}_\gamma^\alpha : Z \to T^\alpha 1$ for each ordinal $\alpha$. I'll just define them for $\alpha < \omega$:

$\mathsf{beh}_\gamma^0 : Z \to 1$ is the unique map into the terminal object.

$\mathsf{beh}_\gamma^{n+1} = T\mathsf{beh}_\gamma^n \circ \gamma : Z \to T^{n+1} 1$

Intuitively these maps send a state in $Z$ to its $\alpha$-step behaviour. Now we can describe what you are talking about. Suppose we have two $T$-coalgebras $(A,\gamma)$ and $(B,\delta)$. Then a $\mathbb{C}$-morphism $f : A \to B$ preserves $\alpha$-step behaviour iff:

$\mathsf{beh}_\delta^\alpha \circ f = \mathsf{beh}_\gamma^\alpha$

That is, the $\alpha$-step behaviour of $f(z)$ in $\delta$ is precisely the $\alpha$-step behaviour of $z$ in $\gamma$.

Anyway, I hope this is helpful. You can find various references by googling 'terminal sequence coalgebra' or 'final sequence coalgebra'.


Logics for timed resource control I'm studying proof theory and I've seen that linear logic can be used as a way to control resource usage, since by the propositions-as-types it is equivalent to the linear lambda calculus.

Is there a logic that allows resource control (like linear logic) and can express properties that vary over a notion of time like linear time temporal logics (LTL)?

Any reference or point to literature is highly appreciated.

As time can be a resource, it is a bit unclear to me what you seek.

Nevertheless, you might want to look at weighted extensions of LTL, like Metric Temporal Logic first defined here. (Specifying real-time properties with metric temporal logic)


What are interesting algorithmic questions for groups in table representation? I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{NP}$ and $\text{co}\mathcal{NP}$ and even for groups whose derived series has length two, we don't how to do isomorphism in $\mathcal{NP}$ $\cap$ $\text{co}\mathcal{NP}$.

Question 1 : What are the interesting algorithmic questions to answer about nilpotent group class or its sub-class   ( which is non-abelian ) other than isomorphism problem?

Question 2 :  What are interesting questions to answer about groups when given in the table representation other than isomorphism? A non-interesting question is to find the intersection of two group or to find the order of any element. Testing membership is also not interesting as the input given is a table.

First, is it a group at all?  A fundamental problem is checking whether a given operation (in table form) is associative.  The obvious approach is cubic time, Rajagopalan and Schulman do it in near-quadratic time.


H-induced Containment problem In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fixed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph class and H is a planar graph.

However, My failure to find a specific algorithm led me to ask the following question.

  If G is a bipartite graph , and H is a tree then is there any polynomial time algorithm to
  find if H is contained in G using only vertex deletion and edge contraction as the graph
  operations.

The algorithm is described in the proof of Theorem 9. For every proper minor closed class $\mathcal{F}$ and every planar graph $H$ there is a constant $c(\mathcal{F}, H)$ such that if the tree-width of $G\in\mathcal{F}$ is at least $c$, then the answer is positive. Furthermore, the property of containing $H$ as an induced minor is an MSO definable property (and the length of the formula depends on $H$ only). Hence you first check whether the tree-depth of $G$ is smaller than $c$ and compute a tree-decomposition (e.g. by Bodlaender's algorithm). If so, you take an MSO model-checker and check whether $H$ is an induced minor of $G$ by testing whether $G$ satisfies the appropriate formula. If not, you simply answer yes.

Note though that the constant $c$ depends on the class $\mathcal{F}$ and if you don't have an explicit list of excluded minors, there might be no constructive way to find them. You cannot just take a bipartite graph and apply the theorem. The graph must be from some class $\mathcal{F}$ with the above properties.


Error reduction with expanders and derandomization In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a good error probability to begin with, say 1/n, without expanders we need to run it only O(n/log n) times to achieve the same error and use $n^d\times O(n/\log n)$ random bits.
If I'm correct with expanders it doesn't help (beside a little in the first step), meaning we still need $n^d+O(n)$ random bits.
There exist some method, such that a good algorithm does have an affect on it (uses say $n^d+O(n/\log n)$ random bits)? There exist some barrier for achieving such a result?

*The question refers to the randomized algorithm in a black-box manner.

You can't expect this to be true since you can reduce the error of a constant-error algorithm to $1/n$ using an additional $O(\log n)$ bits using expanders (and by the way you don't really need even these extra bits to do that). So if an error of $1/n$ can go down to $\exp(-n)$ error using only $O(n/\log n)$ additional bits, then you could always go from constant error to $\exp(-n)$ error using $O(\log n)+O(n/\log n)=O(n/\log n)$.


Algorithm Design for only Mutual Information Sharing Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their exchange their actual bit strings... how can they do this? Keep in mind that even once they both hold the AND of their two bit strings, they should still not be able to calculate the other person's string exactly (unless of course one of their strings was all 1s).

I asked this on Stack Overflow and got yelled at to move it here. Not really sure how to tag it either if anyone knows what it would fit under better please feel free to edit. I know that I have seen something similar before in some sort of mutual key system/voting system but I couldn't remember where. It has to be something like make a private random key, xor it and use that somehow... but I couldn't work out the details. Any clever encryption design people out there?

What you want to do is called "Private Set Intersection". You can think of Alice and Bob as each holding sets (the indices for which their strings are "1"), and they want to compute the intersection (the bitwise AND) so that neither of them learns anything about the other's set except what is implied by the intersection itself.

This problem is well studied. See, for example, Freedman, Nissim, and Pinkas: http://www.pinkas.net/PAPERS/FNP04.pdf


Closed term and alpha-conversion In the simply-typed lambda calculus, do we ever need alpha-conversion in a small-step call-by-value reduction of a term that is closed?

The evaluation rule that uses substitution is:
$(\lambda x.t_1)~v_2 \to [x\mapsto v_2]t_1$

But if $(\lambda x.t_1)~v_2$ is closed, then $v_2$ is closed and $t_1$ only has $x$ has a free variable. Since $v_2$ has no free variables, substitution won't need alpha-conversion. $[x\mapsto v_2]t_1$ is also closed because the only free variable, $x$, has been substituted by a close term. So the result of the reduction is also closed.

It's also easy to show that for the other rules, if $t$ is closed and $t \to t'$, then $t'$ is closed.

Therefore, since we only substitute closed terms, $\alpha$-conversion is not needed.

Do you agree?

Edit: Actually, what needs to be shown is that if $t$ is closed and $t \to t'$ then in any immediate reduction $t_1 \to t_1'$ used to derive $t \to t'$, $t_1$ is closed. This is not true when reducing under binders.

This is true as long as you're only reducing towards a weak head normal form. But if you want to go further, you start reducing under lambdas. If you're looking at the pure lambda-calculus (typed or not), you must be reducing under lambdas if you're reducing closed terms. And when you're reducing under lambdas, you're no longer operating on closed terms.

Here's an example that starts with a closed lambda-term where all binding sites use unique names, proceeds to a term with repeated but non-capturing binders, then reaches a term with capture, which requires alpha-conversion to proceed. The initial term is not simply-typed, but you can remedy this by changing it to $(\lambda w. (\lambda z. w z z) (\lambda x. \lambda y. x y))$ which is simply-typed and shows the same binding-related issues.

$$
\begin{array}{rl}
(\lambda \underline{z}. \underline{z} \underline{z}) \underline{(\lambda x. \lambda y. x y)}
\quad \to &
(\lambda \underline{x}. \lambda \color{blue}{y}. \underline{x} \color{blue}{y}) \underline{(\lambda x. \lambda \color{red}{y}. x \color{red}{y})}
\\ \to &
(\lambda \color{blue}{y}. (\lambda \underline{x}. \lambda \color{red}{y}. \underline{x} \color{red}{y}) \underline{\color{blue}{y}})
\\ \to &
(\lambda \color{blue}{y}. \lambda \color{red}{y}. \color{blue}{y} \color{red}{y})
\end{array}
$$

That last step requires alpha-conversion, to make the blue $y$ and the red $y$ distinct.

Your proof sketch is correct as long as you apply the beta rule in a context that does not bind any variable. If you extend the proof to the lambda context case, it fails when $x$ is in the context.


Reconstruction Conjecture and Partial 2-trees Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.

Searching relevant literature, I found that the following classes of graphs are known to be reconstructible :

trees
disconnected graphs, graphs whose complement is disconnected
regular graphs
Maximal Outerplanar Graphs
maximal planar graphs
outerplanar graphs
Critical blocks
Separable graphs without end vertices
unicyclic graphs (graphs with one cycle)
non-trivial cartesian product graphs
squares of trees
bidegreed graphs
unit interval graphs
threshold graphs
nearly acyclic graphs (i.e., G-v is acyclic)
cacti graphs
graphs for which one of the vertex deleted graph is a forest.

I recently proved that a special case of partial 2-trees are reconstructible. I am wondering if partial 2-trees (a.k.a series-parallel graphs) are known to be reconstructible. Partial 2-trees do not seem to fall into any of the above mentioned categories.

Am I missing any other known classes of reconstructible graphs in the above list ?
In particular, are partial 2-trees known to be reconstructible ?

I believe that it has not been shown that bidegreed graphs are reconstructible. Bidegreed graphs are edge-reconstructible. Kocay did some work on reconstruction of bidegreed graphs, but did not reach a comprehensive result that I have been able to find. The notion that it has been proven that bidegreed graphs are reconstructible seems to be a bit of misinformation circulating on the web.


K-Clustering of a Graph maximizing intra-cluster weights? I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A complete graph G with non-negative integer weights on edges and an integer $K\ge 2$.

Output: A $K$-partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of $P$, i.e.:
$$
M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right)
$$
where $w$ is the edge-weight function.

Thanks in advance for any suggestion.

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.


shortest path algorithm taking into account angular deviation I am using Floyd-Warshall(1) to compute shortest paths on a road network in order to ultimately compute betweenness centrality of road segments. At present, I am weighting the paths by metric length of road segment. I would also like to take into account angular deviation. The goal would be to favor routes that involve fewer, smaller turns (in addition to some distance weighting).

My attempts at writing a Floyd-Warshall or a Dijkstra that takes into account angle have not been working. Not sure whether this is just an implementation issue, or whether I am making a serious theoretical mistake in thinking that these types of shortest-path algorithms can take into account geometric properties like angle. The issue, I realize, is that to compute angular deviation, the algorithm will need a history of its previous path as it recurses through the network.(2)

Is this possible, and if so, any suggestions for how I can go about implementing a shortest path algorithm that takes into account angular deviation?

(1) I am using an implementation included in the NetworkX library (Python).

(2) I found this related question, but I am afraid I cannot understand if it has any implications for my question.

My first guess would be to do a simple graph transformation and running the shortest-path algorithm on the transformed graph. This way, we could convert angular deviation between two roads into an additional shortest path cost along the path and thusly penalize paths involving heavy turns.

The conversion would go along the following lines: say, we are at some node 'n' of degree 'd'. Then, we could substitute this 'n' with a complete graph on 'd' nodes, with each node in this complete graph associated with an edge incident to 'n'. In addition, a 'u-v' edge in the complete graph would have cost proportional to the angle between the edges corresponding to 'u' and 'v'. Exactly how you set the proportion is a matter of taste: I would first try a linear function and experience with different scaling factors.


a polynomial representation of boolean functions I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) mappings and their application.

For three variables, the transformation matrix is given below:

I have posted this with some details and a description for reducing 3-SAT to checking the existence of specific term in an ordinary polynomial product on math.stackexchange (here). I have not got much feedback there. I was wondering if someone here could help.

If this is not the right forum to ask this sort of questions, or more details are needed, please let me know in comments.

EDIT: I found similarities to Zhegalkin polynomials and the $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ -1,1 \right \}$ representation described here with the difference that this is a $f:\left \{ -1,1 \right \}^n \rightarrow \left \{ 0,1 \right \}$ representation.

Well done on your independent discovery.

This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc.

Ryan O'Donnell's notes on Analysis of Boolean functions available here which are now published as a book, Claude Carlet's chapters on Boolean
functions here are easily accessible online.

Just use the order $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ which corresponds to lexicographic order over the integers, and apply the corresponding permutation to the columns as well.

In that order your matrix is simply the 3-fold Kronecker product $$H_2 \otimes H_2\otimes H_2$$of the basic 2 by 2 Hadamard matrix.

$$
H_2=\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}
\right),
$$

This paper considers efficient evaluation of Hadamard representation coefficients.


Publishing by showing falsity of existing results Is it valid to publish a minor result related to computer science complexity theory and classes that disproves and falsifies an existing result?
Would that be a valid and respectable endeavor?

If you respectfully show that an important, i.e., often used/cited, result is false, I think that would be a significant contribution, since obviously those are often the results that have been scrutinized the most and people might build additional work off those results.


What is the proof-theoretic significance of the existence of a Brown-Palsberg self-interpreter for system $F_\omega$? In A Self-Interpreter for F-omega, Brown and Palsberg construct for each term of each type $x:T$ a representation $\bar x : \Box T$ (a metatheoretical function which can't be represented in the language), and an interpretation function $u_T : \Box T \to T$. This is reminiscent of GL provability logic, which in particular abstracts how PA can represent its own proof theory. But while the representation looks like the axiom $\vdash T \implies \vdash \Box T$, the second $\vdash \Box T \to T$ is inconsistent with GL.

So what sort of gadget is this, in logical terms?

Can it be used at all to talk about the metatheory of F-omega?

What would a representation operation that satisfies the axioms of GL look like?

There is no proof significance, since already Gödel's $T$ has a Brown-Palsberg self-interpreter for free. We need a better definition of a typed self-interpreter.


How to measure programming language succinctness? I want to explore the notion of quantifying the amount of succinctness a programming language provides.  That is, the amount a high-level language reduces the complex.

This idea of "simplification" is a factor of text-wise reduction (fewer characters needed to express a complex concept, à la Algorithmic Information Theory) and another, less easy-to-quantify concept of maintainability. Fleshing out this latter concept, it is clear it has to do with how easily one can establish programmer consensus for the given task (i.e. how many programmers of the language would put it back the same way you've expressed it or otherwise agree on the best implementation between different implementations of the same problem?).

I will define the "Kolmogorov Quotient" so that higher numbers for a given language denote a reduction in the complexity of solving the problem in the given language.

The metric for "text-wise reduction" should incorporate a constant factor based on (non-identifier) symbols used in the language and source text.  These factors will be the same across all languages implemented (i.e. designed) for a given architecture (e.g. VonNeumann architecture vs. Symbolics) and will be a measure of the significance of the symbol; i.e. the topology of the language tokens.  (These terms, alas, will also need to be fleshed out and defined.)

Once the basic premise and a methodology above is agreed to, it is only a matter of a rough constant of difference for any specific implementation/architecture. (That is, as long as the architecture is the same across all measurements, the number should be valid and comparable between languages.)

But it could go something like this: Pick a language "close to the machine", like C or Assembly, and measure the amount of bytes of machine code it used to implement a standard suite(*) of common, non-threaded programming tasks (base_language_count). Then code the exact same functionality in the language you are wanting to measure (without using external libraries) and count the number of bytes of source code (test_language_count).

KQuotient = (base_language_count / test_language_count) / number_of_equal_programs.

"number_of_equal_programs" is the number of programs fluent programmers of the language agree that are the best and equal solutions to the problem. (I will define "equal programs" as those who's output is the same for every input.)

The first ratio should always be greater than 1.0.  My only concern is that for each programming language, one could reduce the KQuotient number simply by changing each keyword to a single character.

(*) "standard suite of common programming tasks...":  I see two main categories:

Data-processing suite, limited to simple text I/O (computation towards the machine)
GUI suite (computation towards the user)

The purpose of this idea is to end the tiring "language wars" about whose language is the best.  By giving a quantitative metric, people can at least argue better.

The ideas the question expresses are interesting but maybe insufficiently
fleshed out.  I can see a couple of points that deserve further
refinement.

It is difficult to "code the exact same functionality". In part that
is because what counts as "the exact same functionality" depends on
the chosen notion of program equivalence. For terminating programs
in sequential programming languages there's a canonical definition,
but when you move to concurrent, non-terminating programs,
canonicity vanishes, and you are left with multiple, reasonable
choices that are mutually incompatible. Secondly, but related to the
first point, different programming languages are fundamentally
different: things you can do in a low-level language can often not
be done in a high-level language. A typical example is to do with
speed.  Certain tasks can be solved intrinsically faster in assembly language
than in e.g. Prolog or Javascript (assuming conventional
compilation).
The KQuotient is subjective, in the sense that for any
given task, programmers A and B will likely have different length
base and test language implementations.
Moreover, the KQuotient is also task dependent, meaning that, given
a pair of languages, the KQuotient for Task A will in general be
different from the KQuotient of Task B.

Finally, even though I find the idea of measuring maintainability via
query numbers to reach consensus intriguing, I suggest to be more
clear about what kind of queries are relevant here (syntax?
semantics?), and how the concept of programmer consensus can be made
precise.


Uniform hierarchy of problems that span complexity and computational hierarchies Does anyone know of a set of problems that vary uniformly and span one of the "interesting" hierarchies of complexity and computability? By interesting, I mean, for example, the Polynomial Hierarchy, the Arithmetic Hierarchy, or the Analytic Hierarchy. Or maybe (N)P, (N)EXP, 2(N)EXP, $\ldots$

More concretely: You can give a uniform set of problems that characterize the Arithmetic Hierarchy: $0, 0', \overline{0'}, 0'', \overline{0''},\ldots$. But these aren't always the most useful for reducing to actual problems.

On the other hand, the book by Harel, Kozen and Tiuryn has a set of varying tiling problems that are NP, $\Pi^0_1$, $\Sigma^0_2$ and $\Sigma^1_1$ complete. The problems are useful for showing reductions, but it isn't entirely clear if they generalize uniformly to cover the other levels of the hierarchies they sit in.

Does anyone know of such a set of concrete, uniform problems that span a hierarchy?

EDIT: Just for clarification, I know that the 3 hierarchies I give above all have standard definitions in terms of alternating quantifier strength. That's not what I'm looking for. I'm looking for something different, like a game on a graph or a puzzle played with tilings.

[Building off of Kaveh's insight in the comments.] It seems unlikely that someone could come up with a family of problems that is significantly different from quantified boolean formula, without disproving the PH-analog of the Berman-Hartmanis isomorphism conjecture.  Without that, any problem you come up with would be not only equivalent to $QBF_k$, but in fact isomorphic to it. One way to define isomorphism between two languages here is to take a single abstract language, but encode its objects (in this case, quantified boolean formulae) using two different boolean encodings.

On the other hand, isomorphism isn't necessarily a good judge of what's useful for people to come up with proofs.  After all, in the arithmetic hierarchy, Myhill's Isomorphism Theorem proves the arithmetic analog of the BH isomorphism conjecture (in fact, that's history backwards since BH was motivated by Myhill).  Yet, as the question points out, there are several "different-looking" characterizations of various levels, some of which are more useful for proofs than others.

Although it seems unlikely that anyone will come up with such a uniform family of languages for every level of PH, the two surveys (one, two) by Schaefer and Umans discuss natural problems that at least "look different" from QBF for the first few levels of PH.


What algorithms/reading matter would you recommend on resolving transactions / read-write locks? A simplified classical database transaction can be viewed as:

reading M items
performing some calculation based on those reads
writing some N results based on these calculations, which may include the elements originally read.

When performing these transactions (concurrently) the ACID properties need to be maintained.

Exactly the same requirements (N updates based on M reads transactionally) exist in other non-DBMS concurrent systems.

I'm interested in finding out what algorithms exist for performing/resolving these transactions, and what the relative strengths and weaknesses of these algorithms are. Could you recommend some reading? This could be books or online references/tutorials.

Clarification:

So for example, a naive algorithm might be each transaction taking a single global lock, in effect forcing single threading and removing concurrency. A slightly more complicated algorithm would be individual item read/write locks, with an ordering to avoid deadlock). Etc, etc. Is there a good source documenting various algorithms for solving this problem. Even an answer which only pointed to a single algorithm with it's strength and weaknesses would be useful.

The book Transactional Information Systems by Weikum and Vossen covers quite a lot of the area, both in theoretical and practical terms, from different perspectives, not just transactions. It's about 1000 pages long, so will keep you busy for a weekend or two. On the other hand, it's nearly 10 years old, so there might be something more up-to-date available. Other books in the line include Concurrency Control and Recovery in Database Systems by Bernstein, P., Hadzilacos, V., and Goodman, N, Addison-Wesley, 1987, Transaction Processing: Concepts and Techniques by Jim Gray and Andreas Reuter, and Principles of Transaction Processing by Philip A. Bernstein and Eric Newcomer, 2009. I haven't seen the latter one, but being the most recent it could be a good place to start, although your solution may well be found in older texts. A trip to the library may be worthwhile.

A monumental text in this area is Atomic Transactions by Nancy Lynch et al. It presents a formal account and proofs of a number of the kinds of algorithms you are interested in. It's rather formal, and tedious, so may not be to your taste.

A lot of recent work is devoted to Software Transactional Memory, which is applying the transaction ideas to multi-threaded applications. There are tens of publications on this topic each year: the wikipedia page provides plenty of references.


Monotone bijections between lists of intervals I have the following problem:

Input: two sets of intervals $S$ and $T$ (all endpoints are integers).
Query: is there a monotone bijection $f:S \to T$?

The bijection is monotone w.r.t. the set inclusion order on $S$ and $T$.
$$\forall X\subseteq Y \in S, \ f(X) \subseteq f(Y)$$

[I am not requiring the reverse condition here. Update: if the reverse condition were required, i.e., $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$, then this would be in PTIME because it amounts to isomorphism testing of the corresponding inclusion posets (which have order dimension 2 by construction), which is in PTIME by Möhring, Computationally Tractable Classes of Ordered Sets, Theorem 5.10, p. 61.]

The problem is in $\mathsf{NP}$: we can check efficiently if a given $f$ is a monotone bijection.

  Is there a polynomial-time algorithm for this problem?
  Or is it $\mathsf{NP}$-hard?

The question can be stated more generally as
existence of a monotone bijection between two given posets of
order dimension 2.

Using a reduction inspired by the answers to this question,
I know that the problem is $\mathsf{NP}$-hard
when dimensions are not restricted.
However, it is not clear
if the reduction would also work when dimensions are restricted.

I am also interested to know about tractability when
the dimension is just bounded by some arbitrary constant (not just 2).

Here is an attempt to prove that the problem without the reverse condition is NP-hard.

The basic idea is that disjoint intervals in $S$ like this one:

 [S]  +-a-+ +-b-+
      +---c-----+  c<a, c<b (here < is interval inclusion)

can have a valid mapping to a "pyramid" in $T$:

 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+
      +-z-----+  z<x, z<y OK

The reduction is from Unary 3-Partition (which is NPC).
Given $3m$ integers $A = \{a_1,a_2,...,a_{3m}\}$ and an integer $B$, does exists a partition of A in $m$ sets $A_1,...,A_m$ such that every $A_i$ have exactly 3 elements and their sum is $B$?

Suppose that $max = \sum a_i + 3m$

We construct $S$ adding $3m$ base intervals $BI_i$ of length $3*max$ (red lines in the figure),
on top of each base interval  we add a marker pyramid of $max$ intervals of increasing length (green lines in the figure).
To base interval $BI_i$ we also add $a_i$ disjoint unit intervals of length 1 (black lines in the figure). Finally we add a long interval $L$ to cover all $BI_i$ (blue line in  the figure).

Then we construct $T$ starting from a copy of $L$, then we add $m$ sum groups $G_j$, each one  made with a copy of three stacked base intervals stretched in such a way that their marker pyramids don't intersect (see red+green lines at the bottom of the figure).
Then we add on top of the three base intervals of $G_j$ a sum pyramid of $B$ intervals of increasing length (disjoint from the marker pyramids).

Suppose that there exists a bijection between S and T that preserves the interval inclusion (in one direction from S to T).

Then each marker pyramids of S must correspond to a marker pyramid in T (the only way to have an inclusion chain of $max$ intervals), so exactly three base intervals ($BI_{j_1},BI_{j_2},BI_{j_3}$) of $S$ must be mapped to each group $G_j$. Furthermore, the unit intervals of $BI_{j_k}$ must be mapped to the sum pyramid of $G_j$ and cannot be "exchanged" between different groups.

In a similar way it can be proved that if there exists a bijection then the original unary 3-partition problem has a solution.

Reduction example from the unary 3-partition problem $m=2, A = \{3,3,2,2,2,2\}, B = 7$

Note: as observed in the comments the blue intervals L in S and T are not essential for the reduction.

If the reverse condition is also required, then you can build two DAGs using the relation $I_i \subseteq I_j$ to build arcs $(I_j \rightarrow I_i)$. A bijection that preserves interval inclusion in both directions exists iif the two DAGs are isomorphic. So the problem cannot be harder than the DAG isomorphism problem, which is GI-complete (and if you prove that it is NP-complete then you prove that GI is NP-complete, too).


Binary Search with Errors Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that

the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and
at least one of the coins is unbiased (i.e. $\exists i~~\mathbb{P}[C_i=1]=\frac12$).

Your task is to find an approximately unbiased coin. That is, you must find $i_*$ such that $\mathbb{P}[C_{i_*}=1] \in [\frac13,\frac23]$. To do this, you should flip as few coins as possible.

Here is an algorithm that completes the task by flipping $O(\log n \cdot \log \log n)$ coins: Perform a binary search over the coins - this takes $O(\log n)$ steps. For each step, flip the coin $O(\log \log n)$ times so that the bias of the coin can be approximated to within $0.1$ with probability at least $1-1/O(\log n)$. A union bound shows that this will be correct with high probabiliy.

Can we do this using $O(\log n)$ coin flips?

A good old trick is that it's sufficient to give an algorithm that achieves this with $O(\log n)$ expected number of coin flips and $99\%$ probability, as if we are exceeding the expected running time a lot, we can just output anything, using Markov's inequality this won't ruin our error much. And this we can do as follows.

Always keep an active interval that is supposed to contain an approximately unbiased coin (but might not). Then repeat the following.

1, Halve the size of the active interval by flipping its middle coin a couple of times. Update the active interval (if the middle coin showed no bias, then arbitrarily).

2, Flip both ends of the active interval a couple of times to check that we made no errors. If an error is detected, then go back to the previous active interval.

This way, with a constant number of coin tosses we halve the size of our active interval with high probability and double it with small probability. Thus, in $O(\log n)$ expected time, we reach size $1$, which means one coin. We can check this coin with $\log n$ further coin tosses (though I'm not sure if this is necessary).


Solving "all-marginals" problem for independent sets on grid Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\cdot \lambda_{i_2,j_2} \cdots\lambda_{i_k,j_k}$. Let $p_v$ be the probability that vertex $v$ in this grid is occupied, how do I compute $p_v$ for every vertex $v$ in the grid?

For instance, when $n=2$, the four probabilities are the ratios below

Motivation: comparing accuracy of "correlation decay" based approximate counting with exact for some not-too-large graphs

Clarification 11/6: This is the same $p_v$ as in the first formula of page 3 of [Weitz, 2006]

Here's a dynamic-programming algorithm that is fast enough to solve a given 18 x 18 grid in about 20 minutes.  The algorithm is a modification of the algorithm from this paper for counting independent sets in a given $m\times n$ grid.

Fix the input: the grid dimension $n \times n$ and the values $\lambda_{ij}$ for $i,j\in\{1,\ldots,n\}$.  Represent each independent set in the grid by its 0/1 incidence matrix $M$ where $M_{ij}$ is 1 if the grid vertex $(i,j)$ is in the independent set, and 0 otherwise.
Let $S_n$ denote the set of 0/1 vectors of dimension $n$ with no two consecutive 1's.  (I think the size of $S_n$ is the $n+2$nd Fibonacci number, so $|S_{18}|=6765$.)

An $n\times n$ 0/1 matrix $M$ represents an independent set if and only if the following two conditions hold:

Each row $M_i$ of $M$ is in $S_n$.
Every two consecutive rows $M_i$ and $M_{i+1}$ are compatible, meaning that there is no $j$ such that $M_{ij}$ and $M_{i+1,j}$ are both 1.

Construct directed acyclic graph $G=(V,E)$ where $V$ and $E$ are defined as follows.  The vertex set $V$ contains source and sink vertices $s$ and $t$, and, for each row $i\in\{1,\ldots,n\}$ and $x\in S_n$, a vertex $v(i, x)$.  The edge set $E$ contains the following edges: for each $x\in S_n$, an edge from $s$ to $v(1, x)$ and an edge from $v(n, x)$ to $t$; for each $i\in\{1,\ldots,n-1\}$, and each $x\in S_n$, edges from $v(i, x)$ to $v(i+1, y)$ for every $y\in S_n$ that is compatible with $x$.

The $s$-$t$ paths in $G$ correspond bijectively to the independent sets in the grid.  Each $s$-$t$ path is of the form $(s, v(1, x_1), v(2, x_2), \ldots, v(n, x_n), t)$, corresponding to the independent set whose incidence matrix $M$ has $M_i = x_i$ (that is, the $i$th row of $M$ is $x_i$).

Assign weights to the vertices of $G$ as follows.  Give $s$ and $t$ weight $w(s)=w(t)=1$.  Give each vertex $v(i, x)$ weight $w(v(i,x)) = \prod_{j:x_j=1} \lambda_j$.  Then, for any $s$-$t$ path in $G$, the product of the weights of the vertices on that path is the product of the $\lambda_{ij}$'s of the vertices in the corresponding independent set in the grid.

Now, for every vertex $v$ in $G$, define $P(v)$ to be the sum, over all paths from $s$ to $v$, of the product of the weights of the vertices on the path.  Define $P'(v)$ to be the sum, over all paths from $v$ to $t$, of the product of the weights of the vertices on the path except for $v$.  Compute these two quantities for every vertex in $G$.  This can be done in time linear in the size of $G$ (assuming constant-time exact arithmetic) using a standard dynamic-programming approach.  E.g. use $P(s) = 1$ and, for $v\ne s$,
$$P(v) = w(v)\sum_{u: (u, v)\in E} P(u).$$

For each vertex $v$ in $G$, define $Q(v) = P(v)P'(v)$.  This is the sum, over all $s$-$t$ paths in $G$ that go through $v$, of the product of the weights of the edges on the path.  Then $Q(s)$ is the sum, over all independent sets in the grid, of the product of the $\lambda$'s for the vertices in the independent set. For each vertex $v(i, x)$, then, $Q(v(i,x))$ is the sum, over all independent sets $M$ in the grid whose $i$th row $M_i$ is $x$, of the product of the $\lambda$'s for the vertices in the independent set.

Finally, for each vertex $g=(i,j)$ in the grid graph, compute $p_g$ as the sum, over all $x\in S_n$ such that $x_j = 1$, of $Q(v(i, x))$, divided by $Q(s)-1$.  (Subtract 1 as the problem specification doesn't count the empty set in the denominator.)

For the instance with $n=18$ and each $\lambda_{ij}=1$, this Python script computed the answer in about 17 minutes.  (The graph $G$ had about 122K vertices and 159M edges.)  For non-uniform lambdas, in the probability calculations, you'll need to take some care regarding arithmetic precision.  (If you want exact answers, you'll need to use rational arithmetic.  You could compute close approximations using floating-point arithmetic, but then you'll probably have to be careful about the order in which the sums are performed.)

Here's the output of the script for the instance with $n=7$ and each $\lambda_{ij}=1$. Each entry of the 7 x 7 matrix below is the probability for the corresponding vertex of the grid, times the denominator (which for $\lambda_{ij}=1$ is the number of non-empty independent sets in the grid).

N = 7

denominator = 1280128949

402968942 298303063 333041917 316303258 333041917 298303063 402968942
298303063 296843520 279776968 292351405 279776968 296843520 298303063
333041917 279776968 296033698 285917681 296033698 279776968 333041917
316303258 292351405 285917681 293815906 285917681 292351405 316303258
333041917 279776968 296033698 285917681 296033698 279776968 333041917
298303063 296843520 279776968 292351405 279776968 296843520 298303063
402968942 298303063 333041917 316303258 333041917 298303063 402968942


Relation between OSAs and grammars Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)?

If I'm not mistaken, according to [1], there is an equivalence between order-sorted and many-sorted algebra (MSA) (they are the same up to an isomorphism), and hence the question may be reformulated between MSA and
grammars.

[1] Goguen, Joseph A., and Jose Meseguer. Order-sorted algebra. Oxford University. Computing Laboratory. Programming Research Group, 1989.

I find the answer to my own question in [2]:

Let $G = \langle N, \Sigma, P \rangle$ be a context-free grammar. We can make $G$ into a many-sorted algebra by taking $N$ as the set of sorts and

$$
G_{w, n} = \{\, p \in P \,\mid\, p = (n, w') \land \operatorname{nt}(w') = w \,\}
$$
as an $N^* \times N$-sorted family ($\operatorname{nt}(\alpha)$ returns the ordered sequence of non-terminal symbols in $\alpha \in (N \cup \Sigma)^*$).

The initial $G$-algebra contains the parse trees for all the derivations in the grammar.

Conversely, if $\Sigma$ is an $S$-sorted operator domain, the initial algebra obtained under the previous construction with the grammar

$$
\hat{\Sigma} = \langle S, \Sigma \cup \{(,)\}, P \rangle\quad P=\{\, (s, \sigma(s_1\cdots s_n)) \,\mid\, \sigma \in\Sigma_{s_1\cdots s_n,s} \,\}
$$

is isomorphic to the initial $\Sigma$-algebra.

[2] Goguen, Joseph A., et al. "Initial algebra semantics and continuous algebras." Journal of the ACM (JACM) 24.1 (1977): 68-95.


Log Rank Conjecture Collaborative Approach Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects.

I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-polymath-projects/219639#219639 which has been well received so far

I feel that this is a good project for collaborative approach.

I know this is a fundamental open problem in CS.

1. Is there a list of possible avenues of research that could open up if progress comes on this topic? For example, I know there are connections to Matrix Rigidity.

2. Could we have a list of possible impact of Log Rank Conjecture and related research in CS?

it seems researchers might be cautious/ unlikely to conjecture/ speculate solution to this problem would likely/ definitely open up other areas (eg one you list of matrix rigidity is provably nearly equivalent to the extremely hard challenge of proving nontrivial lower bounds on eg circuits etc) but it definitely provably touches many areas. here is a nice recent survey (Jan 2015) by Lovett that lists "many connections" sec 6 along with two other refs that show crosscutting connections/ formulations

Recent advances on the log-rank conjecture in
communication complexity / Lovett

6.1 Randomized protocols vs approximate rank
6.2 Quantum protocols for low-rank matrices
6.3 The structure of low-rank sparse matrices, and matrix rigidity

En Route to the log-rank Conjecture:
New Reductions and Equivalent Formulations / Gavinsky, Lovett
On the "log rank"-Conjecture in Communication Complexity / Raz, Spieker


Lower bounds for constant-depth formulae? We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC0 are also not computable by a constant-depth formula.  However, since it's an easier model, I'm guessing there are more problems known to be not computable in this model.  Has this been studied? (I'm guessing it has been, but I'm probably not using the right search terms.)

Specifically I am interested in the following question: Is there some function f, which can be computed by an AC0 circuit of size S, but needs a constant-depth formula of size at least quadratic in S, or super-polynomial in S?  What's the best known result of this kind?

In case it is not clear what I mean by constant-depth formula, I mean a formula which if you write out as a tree (with internal nodes being AND/OR/NOT gates, and leaves being inputs), then this tree has constant height. Equivalently, a constant-depth formula is a constant-depth circuit in which all non-input gates have fanout 1.

This question has been completely resolved (up to constant factors) by a recent result of Benjamin Rossman (http://eccc.hpi-web.de/report/2013/169/).

As Kaveh points out above, a depth $d$, size $S$, circuit can be converted to a depth $d$, size $S^d$ formula.

Rossman shows that this is essentially tight. For any depth $d$, he exhibits a function that can be computed by a constant-depth circuit of depth $d$ and size $S = O(n^3)$, but any constant-depth formula (or even a $\sqrt{\log n}$-depth formula) needs size $S^{\Omega(d)}$ to compute it.

(Forgot to say this before: Thanks to Benjamin Rossman for letting me know about this result.)


Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist? Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist?

What are these problems called? Where can I find out more?

Sure, there are lots of examples, at least in the spirit of your question.

Often one gets such a result from the probabilistic method. For example, one paper that I like that runs into the problem is on reconstructing graphs in the additive model.  Here, the authors show that there exists a set of $O(dn)$ queries that will (optimally) learn the target graph.  Given this set, the algorithm is efficient.  However, they use the probabilistic method to show the existence of this small set (for each problem size) that will work on all inputs, but do not explicitly construct it.  So the best they can do is just a brute-force search through an exponential family of queries because they don't have an explicit construction.


ETH based lower bound for $k$-COLORING of bounded degree graph It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (not SETH)?
Emden-Weinert et al. [2] proved that for all $k\geq 3$, $k$-COLORABILITY is NP-complete for graphs of maximum degree $k-1+\sqrt{k}$. By an alternate reduction, I can show that there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY in graphs of maximum degree $k-1+\sqrt{k}$ (assuming ETH). I suppose this is not a new result. Could you please point me to a paper that gives this result? (I hate to brand results as folklore). Thanks in advance.
References
[1] Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz, Tight bounds for graph homomorphism and subgraph isomorphism, Krauthgamer, Robert (ed.), Proceedings of SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: SIAM; New York, NY: ACM. 1643-1649 (2016). ZBL1409.68209.
[2] Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd, Uniquely colourable graphs and hardness of colouring graphs of large girth, Comb. Probab. Comput. 7, No. 4, 375-386 (1998). ZBL0918.05051.

The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction.
Also, the reduction $k$-COLORABILITY $\leq_p$ $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$) given by Emden-Weinert et al. [2] is a linear reduction.
From these observations, it follows that, unless ETH fails, there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$), .
Detailed Explanation:
Let $G$ be a graph of maximum degree $4$ as constructed in the hardness result of Cygan et al [1].
Add $k-4$ new vertices to $G$ and connect them to all vertices of $G$ as well as to themselves, the resulting graph $G'$ has an unbounded degree but, all except $k-4$ of the vertices has degree at most $k$. We do not know whether $G'$ is $k$-colorable. The number of newly added edges and vertices for a constant $k$ is $O(n)$, thus any $2^{o(n)}$ algorithm for $k$-coloring of $G'$ falsifies ETH.
The second step is to reduce the maximum degree of $G'$ by the method provided in the work of Emden-Weinert et al. [2]. Their method roughly speaking is as follows: they take a high degree vertex $u$ then remove $k$ edges of $u$ and add $k-1$ new edges to $u$ to connect it to a specific gadget with $O(k)$ many vertices. This procedure clearly reduces the degree of $u$ by one, and if we repeat this process $n-k$ times, the degree of $u$ will be at most $k$. They showed that the newly created graph after this step exhibits a similar coloring scheme as the original graph (except for the gadgets). As long as there is a high degree vertex, they repeat the mentioned degree reduction procedure. Additionally, based on their construction, we know that the maximum degree of vertices inside gadgets is at most $k-1+\lceil \sqrt{k} \rceil$, thus once the procedure ends, the resulting graph has the claimed maximum degree.
Observe that we have to perform the aforementioned procedure only on $k$ vertices of $G'$ and since their degree is $n+k-4$, after at most $O(kn)$ iterations the procedure stops. Additionally in each iteration, we add at most $O(k)$ new vertices, which means by the end of the procedure, the constructed graph has at most $O(k^2n)$ vertices. Hence, any $2^{o(k^2n)}$ algorithm for $k$-coloring of this graph, would result in a $2^{o(n)}$ algorithm for $3$-coloring of the input graph $G$. Since $k$ is a fixed constant, we conclude that any $2^{o(n)}$ algorithm for k-coloring on this graph would lead us to a $2^{o(n)}$ algorithm for $3$-coloring of $G$.


How to find interesting research problems Despite several years of classes,
I'm still at a loss when it comes to choosing a research topic.
I've been looking over papers from different areas and
spoken with professors, and
I'm beginning to think this is the wrong approach.

I've read that it helps to find an interesting problem (nevermind the area) and
to then work on that.
Textbooks mention famous unsolved ones but
I wouldn't want to tackle them directly.
Research papers only mentioned positive results,
not failed attempts.

How can I find interesting research problems?
How do you find interesting research problems?
Is there a list somewhere?

How do you decide if it is worth to work on a particular problem?

I strongly disagree with the "find a list of open problems" approach. Usually open problems are quite hard to make progress on, and I'm thoroughly unconvinced that good research is done by tackling some hard but uninteresting problem in a technical area.

That being said, of course solving an open problem is really good for academic credentials. But that's not what you are asking.

Research is a process designed to generate understanding at a high level. Solving technical problems is a means to that end: often the problem and its solution illuminate the structure or behavior of some scientific phenomenon (a mathematical structure, a programing language practice, etc).

So my first suggestion is: find a problem that you want to understand. Research is fundamentally about confusion. Are there some specific topics you are interested in, but that you feel you have a fundamentally incomplete comprehension of, or that seem technically clear, but that you lack any good intuition for? Those are good starting points. Follow Terry Tao's advice ask yourself dumb questions! A lot of good research comes out of these considerations. In fact, this whole page contains a lot of good advice. Note that if you are looking at a well-explored problem or field, it's unlikely you'll get original insights right away, so it's important to read up on literature concurrently with your own explorations.

Second, don't discount communicating with your Professors. Ask them about their own research, not necessarily about projects they want to give you. Engage in a conversation! This helps you find out what you are interested in, but also what the research landscape looks like in their field. Research doesn't happen in a vacuum, so you should speak to your fellow students, PhDs in your department, go to talks and workshops at your university, etc. You'll find that being immersed in a research environment helps you do research a lot more than finding a list or specific problem and locking yourself in your office.

Finally, I would suggest working on something small. Research is bottom-up much more than it is top down, and it's rare that a very simple task (writing a proof or a program) turns out to be as simple as you expected it to. Doing several small projects that are not research-scale (expanding on homework, writing up an explanation of something you learned) often build up into genuine research level stuff. It's common to try to "go big" at the beginning, but that's just now how our brains work.


Cubic graphs and hamiltonian paths I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you

See this answer to an earlier question for a bridgeless cubic graph in which the longest path is only polylogarithmically long.


Analogs of compressed sensing In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from the compression (the "sketch").  More formally, the standard setup is that there is a signal vector $x \in \mathbb{R}^n$ for which $\|x\|_0 < k$, and the compressed representation equals $Ax$ where $A$ is a $R$-by-$n$ real matrix where we want $R \ll n$.  The magic of compressed sensing is that one can explicitly construct $A$ such that it allows fast (near-linear time) exact recovery of any $k$-sparse $x$ with $R$ as small as $O(k n^{o(1)})$. I might not have the parameters best known but this is the general idea.

My question is: are there similar phenomena in other settings?  What I mean is that the input signal could come from some "low complexity family" according to a measure of complexity that is not necessarily sparsity.  We then want compression and decompression algorithms, not necessarily linear maps, that are efficient and correct.  Are such results known in a different context?  What would your guess be for a more "general" theory of compressed sensing?

(Of course, in applications of compressed sensing, linearity and sparsity are important issues. The question I ask here is more "philosophical".)

Your question addresses the "exact" recovery problem (we want to recover a k-sparse $x$ exactly given $Ax$). In the following though I will focus on the "robust"  version, where $x$ is an arbitrary vector and the goal of the recovery algorithm is to find a $k$-sparse approximation $x'$ to $x$ (this distinction actually matters for some of the discussion below). Formally you want to following problem (call it $P_1$):

Design $A$ such that for any $x$ one can recover $x'$ where
 $\|x-x'\|_L  \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $k$-sparse vectors.

Here,  $\| \cdot \|_L$ and  $\| \cdot \|_R$ denote the left and the right norm, and  $C$ is the "approximation factor". There are various choices possible for $\| \cdot \|_L$ and  $\| \cdot \|_R$.  For concreteness, one can think that both are equal to $\ell_2$ or $\ell_1$;  it can get more messy though.

Now to some of the analogs and generalizations.

Arbitrary basis. First, observe that any scheme satisfying the above definition can used to solve a more general problem, where the recovered signal $x'$ is sparse in an arbitrary basis (say, wavelet of Fourier), not just the standard one.   Let $B$ be the basis matrix. Formally, a vector $u$ is $k$-sparse in basis $B$ if $u=Bv$ where $v$ is $k$-sparse. Now we can consider the generalized problem (call it $P_B$):

Design $A_B$ such that  given $A_B x$, one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where  $x"$ ranges over all vectors that are  $k$-sparse in $B$.

One can reduce this problem to the earlier problem $P_1$ by changing the basis, i.e., using a measurement matrix $A_B = A B^{-1}$.    If we have a solution to $P_1$ in the $\ell_2$ norm (i.e., the left and the right norms equal to $\ell_2$), we also get a solution to $P_B$ in the $\ell_2$ norm. If $P_1$ uses other norms, we solve $P_B$ in those norms modified by changing the basis.

One caveat in the above is that in the above approach, we need to know the matrix $B$ in order to define $A_B$. Perhaps surprisingly, if we allow randomization ($A_B$ is not fixed but instead chosen at random), it is possible to chose $A_B$ from the a fixed distribution that is independent from $B$.  This is the so-called universality property.

Dictionaries. The next generalization can be obtained by dropping the requirement that $B$ is a basis. Instead, we can allow $B$ to have more rows than columns. Such matrices are called (overcomplete) dictionaries. One popular example is the identity matrix on top of the Fourier matrix. Another example is a matrix where the rows are the characteristic vectors of all intervals in {1 ... n}; in this case, the set { $Bu: \mbox{u is k-sparse}$} contains all "$k$-histograms", i.e., piecewise constant functions over {1 ... n} with at most $k$ pieces.

As far as I know there is no general theory for such arbitrary dictionaries, although there has been a fair amount of work on this topic. See e.g.,
Candes-Eldar-Needell'10 or
Donoho-Elad-Temlyakov, IEEE Transactions on Information Theory, 2004.

Sketching for histograms was extensively investigated in streaming and database literature, e.g.,
Gilbert-Guha-Indyk-Kotidis-Muthukrishnan-Strauss, STOC 2002 or
Thaper-Guha-Indyk-Koudas, SIGMOD 2002.

Models. (also mentioned by Arnab). A different generalization is to introduce restrictions on the sparsity patterns. Let $M$ be a subset of $k$-subsets of {1 ... n}. We say that $u$ is $M$-sparse if the support of $u$ is included in an element of $M$. We can now pose the problem (call it $P_M$):

Design $A$ such that for any $x$ one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $M$-sparse vectors.

For example, the elements of $M$ could be of the form $I_1 \cup \ldots \cup I_k$, where each $I_i$ corresponds to one "sub-block"of  {1 ... n} of some length $b$, i.e., $I_i$ is of the form { jb+1 ... (j+1)b} for some $j$. This is the so-called "block sparsity" model.

The benefits of models is that one can save on the number of measurements, compared to the generic $k$-sparsity approach. This is because the space of $M$-sparse signals is smaller than the space of all $k$-sparse signals, so the matrix $A$ needs to preserve less information. For more, see
Baraniuk-Cevher-Duarte-Hegde, IEEE Transactions on Information Theory, 2010 or
Eldar-Mishali, IEEE Transactions on Information Theory, 2009.

Hope this helps.


The Warren Buffett Problem Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any related work, I would appreciate references.

The Problem
The setting is that of multi-armed bandits. You have N arms. Each arm i has an unknown but fixed probability distribution over rewards that can be earned by playing it. For concreteness, let's assume that each arm i pays reward $10 with probability p[i] and reward $0 with prob. 1-p[i].

In every round t you select a set S[t] of arms to play. For each arm you select, you pay a fee of $1 up front. For each selected arm, you collect a reward that is drawn from the (unknown) reward probability distribution of that arm. All rewards are credited to your bank account, and all fees are deducted from that account. In addition, you get a credit of $1 at the beginning of every iteration.

The problem is to develop a policy to select a subset of arms to play in each iteration to maximize profit (i.e. rewards minus fees for playing) over a long enough horizon, subject to the constraint that it must maintain a non-negative account balance at all times.

I did not specify whether the per-arm reward distributions are chosen from a prior distribution or chosen by an adversary. Both choices make sense. The adversary formulation is more appealing to me, but probably harder to make progress on. Here, the adversary chooses a vector (D1, D2, .., DN) of distributions. Given the distributions, the optimal budget balanced policy is to play all arms whose expected reward is greater than $1. Let P be the per-step profit of this optimal omniscient policy. I want my online policy to minimize regret (i.e. loss of profit over a time window T) wrt this omniscient policy.

I imagine there are lots of possible approaches to this problem (many of which I'm sure you considered) -- here are a few ideas/references.

You could play this as $N$ independent parallel single-arm bandit games, deciding to pull or not pull each arm independently.  This should work especially well if the rewards are independently distributed.
Allow each set of arms to be a new arm and run an Exp3-type algorithm.  This gives a $O(2^{N/2} T^{1/2})$ regret - not so great.
In an upcoming NIPS 2010 paper, Saten Kale, Rob Schapire, and I consider the case where one plays a slate of arms at once.  In our work, however, the size of the slate is fixed.  This paper also considers a similar problem.  Another similar work appeared in ALT 2010.  Perhaps some of the ideas transfer.
If you treat it as an experts problem (each expert recommends a different one of $2^N$ subsets), by following one expert, you can get estimate the performance of other experts who have non-empty intersections in their choice of arms to pull by using importance weighting.  An Exp4 type analysis might get you $O(N\sqrt{T})$ regret but $O(2^N T)$ running time.

EDIT below:

It seems to me that the budget constraint (not going below $0$) makes the problem intractable.  Imagine you have a budget of $1$.  The adversary can make one of the  arms always pay off and the rest never pay off.  So w.p. $(n-1)/n$ you go bust in the first round while the optimal strategy gets $T$ dollars after $T$ rounds.  So your expected regret is at least $(n-1)T/n$ and you can't hope for a high probability bound at all.

It also seems that this can work for any initial budget.  Say you start with $B$ dollars.  Then the adversary can set all but one arms to pay $0$ and one arm to pay something like $2B$ w.p. $1/B$.  I guess if you have a limit on the possible payout amount and a high enough initial budget, then this might leave room for an interesting problem.


Is there a candidate for a post-quantum one-way group action? Is there a known family of group actions with a designated element

in the set that is being acted on, where it is known how to efficiently

$\:$ sample (essentially uniformly) from the groups, compute the inverse operations,

$\:$ compute the group operations, and compute the group actions

and there is no known efficient quantum algorithm

for succeeding with non-negligible probability in

$\:$ given as inputs the index of a group action and the result of

$\:$ a sampled group element acting on the designated element,

$\:$ find a group element whose action on the designated element is the second input

?

As far as I am aware, those provide the only known constructions of non-interactive statistically hiding commitments in which knowledge of a trapdoor enables efficient and undetectable equivocation, a property that is useful for zero knowledge protocols and adaptive security.

Any family of one-way group homomorphisms with the first three properties (from the third and fourth lines of this post) can be converted into such a thing by having the domains act on the codomains via $\: \langle a,b\rangle \mapsto h(a)\cdot b \:$, $\:$ with the identity elements as the distinguished elements.

A restricted version of the Pedersen commitment scheme can be obtained as a special case of applying the above conversion to the group exponential homomorphism, whose one-wayness is equivalent to the hardness of the discrete logarithm problem, although that is not hard for quantum algorithms.  (See Shor's algorithm and that page's section on discrete logarithm.)

Yes, there is an old proposal for this due to Couveignes, which was independently rediscovered by Rostovtsev and Stolbunov.

In both cases, the set of elliptic curves with some common endomorphism ring $\mathcal O$ is acted on by the ideal class group of $\mathcal O$. The secret key is essentially a description of an isogeny via its kernel ideal, and the action of a group element $[\mathfrak a]$ takes a curve $E$ to the codomain of said isogeny:
$$
    ([\mathfrak a], E) \longmapsto E/\mathfrak a = E/\bigcap_{\alpha\in\mathfrak a}\ker\alpha
    \text.
$$
There is a nice graph-walking interpretation of this action, which is described (for instance) in Section 14.1 of Luca De Feo's lecture notes. (They also contain more of the background necessary to understand this construction!)

While it is possible to invert the group action by solving an instance of the hidden-shift problem, giving rise to a subexponential quantum attack, the system remains unbroken for reasonably big parameter sizes.
A much bigger problem is that these schemes are painfully slow in practice: Even after considerable optimization effort, one computation of the group action still takes minutes.

The performance issue has been tackled by a recent proposal called CSIDH by switching to supersingular elliptic curves, which drastically improves efficiency while keeping essentially the same underlying structure. It is still slow relative to comparable pre-quantum schemes, as well as incomparable post-quantum schemes, but may have a place in a post-quantum world due to its unique features.


Modifying Hopcroft-Karp algorithm to get approximate bipartite matching I am trying to find an algorithm to find an $\epsilon$-approximate maximum matching $M_{\epsilon}$ in a bipartite graph in $O(m/\epsilon)$. The partite groups are of equal size, they are $A$ and $B$.  So the graph is:

$$G(A ∪ B, E)\ \ where\ \  |A| = |B| = n, \ \ \ \ E ⊆ A × B \  \ \ and\ \ \  |E| = m$$

The algorithm should produce an $\epsilon$-approximate maximum matching $M_{\epsilon}$ such that:

$$|M_{\epsilon}| \geq (1-\epsilon)M_{optimal} \ \ \ for\ \ \ 0 \leq \epsilon \leq 1$$

I am aware that the Hopcroft-Karp algorithm can produce an $M_{optimal}$ but I have heard one can modify Hopcroft-Karp to produce an $\epsilon$-approximate maximum matching ($M_{\epsilon}$) instead.  I am currently out of ideas in how to approach this.

To clarify: I am only concerned about unweighted matchings.

This is a combination of comments from me and Chandra Chekuri above, elaborated a bit.

As background, if you have a partial matching then its symmetric difference with the optimal matching can be decomposed into disjoint alternating paths (and possibly also some alternating cycles but those can be ignored). Hopcroft–Karp maintains a partial matching as it proceeds in a sequence of stages. Each stage exhausts all the shortest alternating paths left over from the previous stage, and increases the shortest alternating path length by at least two (because the length must be odd). Each stage takes linear time. The exact algorithm can be proven to take $O(\sqrt n)$ stages, leading to a nonlinear total runtime.

First, the additive approximation. If the shortest alternating path length is $k$, then the symmetric difference between your matching and optimal can have at most $n/k$ disjoint alternating paths, so the difference in cardinality between your matching and optimal is at most $n/k$. So if you set $k=1/\epsilon$ for your favorite constant $\epsilon$, and stop after $k/2$ stages, you should get an additive approximation of $\epsilon n$ to the optimal matching, in time $O((m+n)/\epsilon=O(m+n)$.

Now, for a multiplicative approximation, again suppose that the shortest alternating path length is $k$, and observe that each alternating path includes at least $(k-1)/2$ edges that are already part of your matching. So the ratio between the number of edges you already have in the alternating paths and the number you can get by adding one more edge per alternating path is at most $$\frac{k-1}{2}\left/\left(\frac{k-1}{2}+1\right)\right.\approx 1-\frac{2}{k}.$$ Therefore, if you set $k\approx 2/\epsilon$, and again do only $k/2$ stages before stopping, you will get a $(1-\epsilon)$-approximation, again in time $O(m+n)$.


Approximation results on scheduling under an uncommon constraint I am looking for any approximation results for unrelated multiprocessor scheduling problem with precedence constraints (minimizing makespan), i.e. $R|prec|C_{max}$, with the constraint that some tasks need to run together on the same processor. I searched a lot and the closest constraint I could find was that some tasks have to run on certain processors. I need to group tasks in classes such that each class must run on the same processor. Note that the precedence constraints prevent collapsing each class into a single big task.

I would like to find any literature on the problem  (or any non-trivial relaxation, for example removing the precedence constraints will allow the classes of tasks to be treated as one task).

Even without the additional constraints you have the unrelated machine scheduling problem with precedence constraints is not well understood. If I am not mistaken nothing better than a polynomial factor approximation is known. It is an important open problem in approximation algorithms for scheduling problems. Some positive results are known when the precedence constraints form a tree. See the following paper. http://www.springerlink.com/content/p8321031hk718413/

Can you solve your problem in the simpler case when the machines are identical or related?


Reference for NP-hardness of 3-colouring? I have a historical question.

I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard.

The tempting answer is “Karp’s original paper”, but that is wrong. Here’s a scan: Reducibility among Combinatorial Problems, Karp (1972). It proves that Chromatic number (Input: a graph. Output: $\chi(G)$) is hard. That’s a harder problem, and the reduction is different from the standard gadget construction (with 3 colours, True, False, and Ground) that implies hardness of 3-colourability.

Garey and Johnson, Computers and intractability, have $k$-colourability as [GT4] and refer to Karp (1972).

László Lovász, Coverings and coloring of hypergraphs, Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math., Winnipeg, Man., 1973, pp. 3--12, proved that Chromatic number reduces to 3-colourability.

I think, that is the first proof for NP-completeness of 3-colourability.

Here is Lovász's paper; see also Vašek Chvátal's excellent explanation to Lovász's reduction.


Origin of Church encodings In which paper did Alonzo Church first describe Church encoding? I can't find any articles that actually cite the paper, but I am interested in reading it.

It should be this one:

Church, A. (1941) The Calculi of Lambda-Conversion. Annals of Mathematics Studies
No. 6, Princeton University Press.


Formalizing the theory of finite sets in type theory Most proof assistants have a formalization of the concept of "finite set".  These formalizations, however, differ wildly (although one hopes that they are all essentially equivalent!).  What I don't understand at this point is the design space involved, and what are the pros and cons of each formalization.

In particular, I would like to understand the following:

Can I axiomatize finite sets (i.e. types inhabited by a finite number of inhabitants) in simple type theory?  System F?  What are the drawbacks of doing it this way?
I know it can be done 'elegantly' in a dependently typed system.  But, from a classical point of view, the resulting definitions seem extremely alien.  [I am not saying they are wrong, far from it!].  But I do not understand why they are 'right' either.  I understand that they pick out the correct concept, but the deeper reason for 'saying it that way' is what I do not fully grasp.

Basically, I would like a reasoned introduction to the design space of formalizations of the concept of 'finite set' in type theory.

I know it can be done 'elegantly' in a dependently typed system. But, from a classical point of view, the resulting definitions seem extremely alien.

Can you explain what you mean by "alien"? It seems to me that you
formalize the concept of finite set in precisely the same way in
type theory and in set theory.

In set theory, you proceed by defining the set $Fin(n)$ as
$$
  \mathrm{Fin}(n) \triangleq \{ k \in \mathbb{N} \;|\; k < n \}
$$
Then, you define the finiteness predicate as:
$$
  \mathrm{Finite}(X) \triangleq \exists n\in\mathbb{N}.\; X \simeq \mathrm{Fin}(n)
$$
Where $A \simeq B$ means isomorphism of sets.

In type theory, you can do exactly the same thing!
$$
  \mathrm{Fin}(n) \triangleq \Sigma k:\mathbb{N}.\; \mathsf{if}\; k < n\,\mathsf{then}\; \mathsf{Unit} \;\mathsf{else}\; \mathsf{Void}
$$
Note that $\mathrm{Fin}(n)$ is a type with $n$ elements (since the second component of the pair is
proof-irrelevant). Then, you can define the finiteness type constructor as:
$$
  \mathrm{Finite}(X) \triangleq \Sigma n:\mathbb{N}.\; X \simeq \mathrm{Fin}(n)
$$
Where $A \simeq B$ means isomorphism of types.


What is a weakly-simplicial vertex? While studying chordal bipartite graphs, I have come across weakly simplicial vertices. I have searched for some time to understand what a weakly simplicial vertex is but I haven't succeeded.

A simplicial vertex is a vertex whose neighborhood induces a clique.

So, what is the weak form of this definition?

According to the 59th slide of the following pdf:

https://grow2015.sciencesconf.org/file/174789 (A talk by D.Kratsch at GROW 2015)

we have that

  A vertex in a graph is weakly simplicial if its neighborhood is an
  independent set and the neighborhoods of its neighbors form a
  chain under inclusion.

See the slide for an illustration. The context where this definition is found in the slides is chordal bipartite graphs, so I guess this might be what you are looking for.


A function is lambda-2-definable iff it is HG computable and provably type correct in lambda-PRED2 I'm having a problem regarding Theorem 5.4.40.3 of Barendregt's Lambda calculi with types (1992), a chapter in Handbook in logic in computer science. (I'm referring to the PostScript version available on the Web.)

The theorem states that a function is $\lambda$2-definable iff it is HG (Herbrand-Goedel) computable and provably type correct in $\lambda$PRED2.  The author delegates the proof to a proceeding in FOCS, i.e., Reasoning about functional programs and complexity associated with type disciplines (1983) by Leivant.  The corresponding theorem in the proceeding is Theorem 3.1 and Corollary 3.2, although they are stated in terms of provable type-correctness in $\lambda$2, not in $\lambda$PRED2.

The first problem I'm running into is that the definition of HG computability by Barendregt doesn't make sense.  IMHO, the equation in Definition 5.4.39.1 should be replaced by
$$
\mathit{HG} \vdash p:(f_n(t^\sim) =_L (f(t))^\sim).
$$

Assuming this, I tried to prove the equivalent of Theorem 3.1 (Leivant) in terms of $\lambda$PRED2, but in vain.  Leivant's proof is informal and I have hard times formalizing it. (By using Barendregt's notation, I'm pretty sure that if $B$ is the proof of $f$'s type correctness then $[B]$ is a $\lambda$2-term that represents $f$, but I am unable to prove this.)  Besides, his proof deals with only one direction of the equivalence (provably type correct $\Rightarrow$ $\lambda$2-definable) and the rest is left unstated.  I suppose the opposite direction involves the formalization of SN, but I am unsure.

I would be the most grateful for detailed explanation of Theorem 5.4.40.3 by Barendregt.

My first advice is to take a look at chapter 15 of Girard, Lafont & Taylor Proofs & Types. In it, a weaker theorem is proved, but the basic ideas are quite similar, and the exposition should be simpler.

Second: Provably type correct is a bit of a misnomer. The property looks more like definability or accessibility. In a nutshell it expresses

$$ \forall t_1,\ldots t_n,\ \mathrm{Ind}(t_1) \wedge \ldots\wedge\mathrm{Ind}(t_n) \Rightarrow \mathrm{Ind}(f(t_1,\ldots, t_n))$$
where $\mathrm{Ind}(t)$ means the term $t$ is inductive, that is, built up from constructors. Being inductive is essentially being defined as an element of the inductive type, which makes the above property a statement about definability.

Third: You are correct, if $B$ proves that $f$ is type correct, then $[B]$ is the definition of $f$. Work through an example first: If $\mathrm{add}: \mathbb{N}\rightarrow\mathbb{N}\rightarrow\mathbb{N}$, then the statement of type correctness is:

$$ \forall x\ y,\ \mathrm{Ind}_{\mathbb{N}}(x)\rightarrow\mathrm{Ind}_{\mathbb{N}}\rightarrow \mathrm{Ind}_{\mathbb{N}}(\mathrm{add}(x, y))$$
in $\lambda\mathrm{PRED}_2$, which, erased, gives
$$ \mathrm{N}\rightarrow\mathrm{N}\rightarrow\mathrm{N}$$
in $\lambda_2$ (with $\mathrm{N}=\Pi X:*.X\rightarrow(X\rightarrow X)\rightarrow X$) which is exactly the right type for $\mathrm{add}$! So at least the types add up. Checking that the proof of type correctness of $\mathrm{add}$ gives you a good definition is more tedious, but Leivant gives the details.

Fourth: you are correct that (1 way of seeing) the converse requires examining the proofs of strong normalization. For each function definition in $\lambda_2$, you can "decorate" it into a proof of type correctness in $\lambda\mathrm{PRED}_2$, essentially using the "theorem for free" that comes with the type. A really nice exposition is Wadler, The Girard-Reynolds isomorphism, which is a highly suggested read for anyone in the field.

Fifth: I think you are correct in your correction of 5.4.39.

Edit: Elaboration on the 4th point:

Wadler defines, among other things, the Reynolds embedding from $\lambda_2$ to $\lambda\mathrm{PRED}_2$ with higher-order functions (Figure 4). This embeding sends a type to a proposition (the parametricity theorem) and sends a well tyepd term to a proof of parametricity of that same term.

The theorem you get implies "type correctness" of the defined function rather trivially. In fact I think Wadler treats this in detail in Section 5, and treats the $\mathrm{add}$ example in the appendix. The only subtle point is that the function is not directly defined over the inductive type, rather it takes the type and constructors as arguments.

At this point I really have to suggest you work through some examples.


Zero knowledge verification of an encryption protocol This seems like a straightforward application of zero knowledge techniques, but an answer eludes me.

Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess functions $E()$ and $D()$ to encrypt and decrypt arbitrary $n$-bit messages.

Charlie wishes to verify this claim, but Alice and Bob don't want Charlie to learn anything about the method.

Can Charlie verify that Alice and Bob can indeed encrypt and decrypt in a zero knowledge fashion ?

For symmetric-key encryption:

If Alice and Bob know a proof that $D_K(E_K(x))=x$ for all $x,K$, then they should be able to prove this fact in zero knowledge.  In particular, they can produce boolean circuits for $D_\cdot(\cdot)$ and $E_\cdot(\cdot)$, publish a commitment to each boolean circuit, and then turn their proof into a zero-knowledge proof.  In particular, verifying that $D_K(E_K(x))=x$ for all $x,K$ is in co-NP, and thus in IP, and there are zero-knowledge proofs for all of IP (and all of PSPACE).

Now if Alice wants to encrypt a message, she can give a zero-knowledge proof that she has encrypted some message correctly by doing the following: publish commitments $C(x),C(K)$ to her message $x$ and her key $K$; publish a commitment $C(y)$ to her ciphertext $y=E_K(x)$; and now give a zero-knowledge proof that all the commitments are consistent (the ciphertext corresponding to $C(y)$ is a correct encryption, under the boolean circuit for encryption that was committed to earlier, under the key corresponding to $C(K)$ of the message corresponding to $C(x)$).  Whether this is a useful thing to prove is another matter entirely -- it's not clear exactly what you are looking for or how you would use a solution to your problem, but hopefully this will give you some ideas.

For public-key encryption:

See Sadeq Dousti's comment.  The exposition above can be readily adjusted to fit the public-key encryption setting, along the lines Sadeq Dousti suggests.


Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints? I have the following problem:

Given a set of path existence/absence constraints C (not necessarily for all pairs of vertices) and a (fixed) set of vertices V, generate a random DAG, s.t.

it is acyclic (by definition),
it contains all vertices of V,
all constraints in C hold,
each possible DAG (given the specific constraints) should be generated with equal probability.

The type of the constraints should be self-explanatory, but in case it is not I can edit the question to provide additional information.

Intuitively I would say that the problem should be NP-hard.

The question is:

  Are there any known results on this problem?

Thanks in advance,

George

Edit: added "(not necessarily for all pairs of vertices)" in the problem definition.

There is some work concerning random orders. Good and slightly outdated survey is $[1]$. In this survey you can find description for the basic models of random orders: uniform model, model of random graphs orders and model of random $k$-dimensional orders. It should be noted that these models are derived for arbitrary random orders and maybe you won't find there results on generation of random orders which are extensions of the given partial order.

Brightwell G. Models of Random Partial Orders. Surveys in combinatorics, 1993.


Solving an LP with at most m-1 nonzeros Consider the linear program:

$$
    A x = b, ~~~~~~ x\geq 0
$$
where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$.

It is known that, if this program has a solution, then it has a basic feasible solution, in which at most $m$ variables are non-zero.

QUESTION: is there an efficient algorithm to decide whether the LP has a solution in which at most $m-1$ variables are non-zero, and find it if it exists?

The question is a special case of Min-RVLS - finding a solution with a smallest number of non-zero variables. Min-RVLS is known to be NP-hard and hard to approximate within a multiplicative factor. Finding an additive approximation is hard too.

But, here our goal is much more modest - all we want is to find a solution with one less than the maximum ($m$). Is this special case easier?

This question was previously posted in cs.SE and got no answers. I deleted it from there to avoid cross-posting.

I think the "few nonzeros" problem is NP-hard, by reduction from the partition problem. Suppose we are given $m$ numbers $a_1,\ldots,a_m$ whose total sum is $2 s$, and have to decide whether they can be partitioned into two subsets such that the sum in each subset is $s$. We can solve this problem using a linear program with $2 m$ variables. For each  $i\in[2]$ and $j\in [m]$, the variable $x_{ij}$ determines what fraction of the number $a_j$ is in subset $i$. There are $m+1$ constraints (besides non-negativity):

For each $j\in[m]$: $x_{1j}+x_{2j} = 1$
The equal-sum constraint: $\sum_{j=1}^m x_{1j} a_j =  \sum_{j=1}^m x_{2j} a_j$

There always exists a solution with at most $m+1$ nonzeros. In this solution, at most one  number is "cut" between the sets. Indeed, it is easy to solve the partition problem if we are allowed to cut one number: just order the numbers on a line and cut the line into two parts with equal sum.

Now, if we could solve the "few nonzeros" problem, then we could decide whether the above LP has a solution with at most $m$ nonzeros, which would imply a solution to the partition problem (in which no number is cut). But this problem is known to be NP-complete.

NOTE: the partition problem is considered "the easiest NP-hard problem". So, while "few nonzeros" is NP-hard, it may still be easy in practice. Alternatively, it may be possible to reduce to "few nonzeros" from a harder NP-hard problem. So its exact hardness is still open.


The complexity of LH with constant gap Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue of $H$ is either $\leq a$ or $\geq b$, with $b-a$ vanishing as an inverse polynomial in the size of the original problem. If the gap vanishes faster, the problem is not known to be in QMA, and if the gap is larger the problem is easier.
I read often, for example in wikipedia, that for constant gap QMA-hardness is a conjecture (equivalent to a quantum version of the PCP theorem). However, I sometimes read the opposite: for example Gharibian's phd thesis problem 1.7, or Gosset, Nagaj definition 4 for the qsat subcase.
Effectively, I don't understand why I cannot repeat each term in $H$ a polynomial number of times, and obtain an equivalent problem with constant gap. Is this reasoning naively wrong, or maybe I am not reading the PCP statement correctly. Maybe "constant gap" is just a fast way to say something more specific?
PS. I posted this on the quantum computing board too, where is probably more inherent. I noted the board after posting here, let me know if I have to cancel this.

Your original problem formulation is not correct. It's missing some normalization on $H$, otherwise it could be the case that all eigenvalues of $H$ are always smaller than $a$, making the problem completely trivial, so it couldn't possibly be QMA-complete.
One natural normalization is $||H||\leq 1$, which you can enforce by saying that if $H$ is expressed as the sum of $m$ local terms, then each term should have norm at most $1/m$. Now all eigenvalues of $H$ must lie in $[-1,1]$. For this normalization, the complexity of constant-gap Local Hamiltonian is conjectured to be QMA-hard. Note that this problem is NP-hard because of the classical PCP theorem.


In a resistor network, is there any relation between the shortest path and the maximum electric current path? Consider a shortest path problem between the source $s$ and sink $t$ in an undirected weighted graph. There's a well known algorithm such as Dijkstra's algorithm that solves this problem.

Naturally, this graph can be considered as a resistive network where each edge $e$ with distance (or a cost) $d_{e}$ corresponds to a resistor with resistance $d_{e}$ or conductance $1/d_{e}$. From a physical point of view, assume that we send one unit of current from s to t, say by attaching $s$ to a current source and $t$ to ground. It will induce a certain electric flow in $G$ and this flow is unique. And the approximated solution (or the approximate electric flow) can be obtained in time $\tilde{O}(m)$ where $m$ is the number of edges in the graph.

My question: what is the relation between the shortest path in a graph and the path in an electric network where the max electric current flows? Is it true that two paths are always the same when there exists a unique shortest path from $s$ to $t$?

The intuition: The electric current tends to flow through the path with the least resistance, and the least resistance between $s$ to $t$ may be interpreted as the shortest path between $s$ to $t$.

updated

8--R--7--R--+
|     |     |
|     R     |
|     |     |
+--R--6--R--+
|     |     |
|     R     |
|     |     |
+--R--5--R--+
|     |     |
|     R     |
|     |     |
+--R--3--R--4
|     |     |
|     R     |
|     |     |
+--R--2     R
|           |
|           |
|           |
+--R--1--R--0

@MarzioDeBiasi: Thank you for the picture and actual current computation. But ironically, your answer only fortifies my conjecture about the shortest path and max current path. (I apologize for not explaining my conjecture clearly if that causes some confusion.)

As you pointed out, we have the current of 33.9 mA from 4 to 0, but that's due to the superimposition of many currents. For example, the current flows 8 - 2 - 3 - 4 - 0, 8 - 3 - 4 - 0, 8 - 5 - 6 - 7 - 4 - 0 and 8 - 7 - 4 - 0 contribute to the current flow from 4 to 0. And none of them are larger than the curent of 25mA on the path of 8 - 1 - 0. On the other hand, there's only one path for the flow 8 - 1 - 0 and it sends the largest amoun of current in the circuit.

Just an extended comment to include the picture: if the following (random) resistor network is valid then the max current flow 33.9mA is not on the shortest path from $s$ (+5V) to $t$ (GND).


Infinitary Counting Logics: 1-sorted vs. 2-sorted framework There are two ways to extend infinitary logic with counting:

Grädel's way (cf. p. 11):

We extend $L_{\infty\omega}$ by introducing a counting existential quantifier:

$$ \mathcal{A} \models \exists^{\geq m} x \varphi(x) \Leftrightarrow
\textrm{There are at least $m$ $a \in A$ s.t. } \mathcal{A} \models \varphi(a).$$

Introducing such a quantifier for $\mathsf{FO}$ does not increase the expressive power because can easily define it with the usual $\exists$-quantifiers. However, $C^1_{\infty\omega}  \not\leq L_{\infty\omega}$
(One variable is sufficient to express that $|A|$ is even in $C_{\infty\omega}$ yet it is not definable in $L_{\infty\omega}$).

Libkin's way (cf. p. 8):

We define a two-sorted framework. We have two kinds of variables now

Number variables in $N^A = \{ x \in \mathbb{N} \mid 0 \leq x \leq |A|-1\}$
Vertex variables (the old type) in $A$

Additionally, we have the natural ordering on the numbers. Furthermore, we introduce

$$ \#x.\varphi \in N^A$$

which represent the numeric value how many  $x \in A$ satisfy $A \models \varphi(x)$.

  Libkin's way is at least as expressive as Grädel's way, since for
  $\exists^{\geq m} x \varphi(x)$ we write

  $$ \#x.\varphi \geq m.$$

Im trying to define Graph Canonization with Infinitary Counting Logics with finitely many variables. Libkin's way is easier on first glance since we have free numerical variables which can represent graph nodes, edges and so on. Graph Canonization with Fixed-Point Logics works very similar. However, for the Grädel way there are a lot of results like $k$-Pebble-Games and a connection the $k$-dimensional Weisfeiler-Lehman Algorithm which is a direct connection to the Graph-Isomorphism Problem.

Are the Libkin way and the Grädel way equivalent in expressiveness? Do the mentioned results work with the Libkin way? Are their respective restrictions with $k$ variables equivalent? How do I count the variables for the Libkin approach (numerical variables + vertex variables?)?

Any ideas how to define Graph Canonizations with the Grädel way?

The answer to the question "Can we diretcly express graph canonization Grädel's way" is no.

However, we can substitute each $v<w$ in a $\{E,<\}$-formula with a $\{E\}$-formula (Libkin's wy) by Logical Transduction (also known as Logical Interpretation). This $\{E\}$ formula is a sentence without free variables. Hence, we can use a construction (by Grädel and Otto in the same paper) to eliminate all number variables which results in a Grädel-formula with the same number of vertex variables.