Applications of Game theory in computer science? As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided confirmation of its usage in computer science. I have started a formal study of game theory from the economist's perspective. Now I want to know the applications of game theory in computer science. What are some recent major achievements of computer scientists in fields like Artificial Intelligence and Complexity Theory which utilize elements of game theory? Is there a way to approach game theory that is more rooted in computer science than economics?

One of the most famous examples of game theory in computer science is Yao's minimax principle.  Let $X$ be a set of inputs for some problem, and let $A$ be a set of (deterministic) algorithms for that problem.  Yao's principle states that
$$
\max_{x\in X} \operatorname{E}\limits_{a\in A} \left[T(a,x)\right]
\ge
\min_{a\in A} \operatorname{E}\limits_{x\in X} \left[T(a,x)\right] ,
$$
where the expectations on the left and right are taken with respect to any desired probability distribution over algorithms and inputs, respectively.

For example: Any deterministic comparison-based sorting algorithm requires $\Omega(n\log n)$ time on average to sort an array permuted uniformly at random.  (Proof: In any binary tree with $N$ leaves, at least half the leaves have depth at least $(\lg N)/2$. $\square$)  So Yao's principle implies that the worst-case expected running time of any randomized comparison-based sorting algorithm is also $\Omega(n\log n)$.

Yao's minmax principle follow easily from von Neumann's minimax theorem for two-player zero-sum games, where one player provides the input and the other provides the algorithm.


Are there stronger notions of equivalence over lambda terms than beta equivalence? I should add the context that I am concerned with strongly normalizing systems like System-F.

I have what I consider a very strong notion of equivalence for lambda terms that goes something like the following (not super formal)

if $E_1$ and $E_2$ have WHNFs $\lambda x:t.E_1'$ and $\lambda x:t.E_2'$ then $E_1 = E_2$ if $\forall x:t. E_1' = E_2'$
if $E_1$ and $E_2$ have WHNFs that are not $\lambda$s then they must be constructively equivalent. If $\lambda$s are elements of $E_1$ and $E_2$ they must be in the same structural locations and be equivalent by 1.

Is this notation of equivalence stronger than beta equivalence for strongly normalizing systems? If not is it equivalent? Are there stronger kinds of equivalence (or perhaps ones in the same spirit but more formal)?

Thanks!

Alright I'll give it a crack. It seems what you are describing is close to contextual equivalence, which is defined in the following manner $t$ and $t'$ ($t\simeq t'$) are contextually equivalent iff:

$$\forall E, E[t]\!\downarrow\ \Leftrightarrow\ E[t']\!\downarrow $$
where $E$ ranges over the set of term contexts (terms with one "hole") and $t\!\downarrow$ means $t$ is normalizing. Now this definition works for all untyped $\lambda$-terms and it is possible to show that if $t$ and $t'$ are normalizing, then
$$ t\simeq t'\ \Leftrightarrow\ t=_{\beta\eta}t'$$

Here $\beta$ is the usual $\beta$-conversion and $\eta$ is the equality
$$ \lambda x.t\ x = t$$
if $x\not\in \mathrm{FV}(t)$

This shows that $\beta+\eta$ is a rather strong form of equivalence for normalizing terms in the untyped setting. However in general the statement
$$ \forall v:T,\ t\ v=_{\beta\eta} t'\ v\qquad (1)$$
in some (normalizing) typed calculus is significatnly stronger than $t=_{\beta\eta}t'$: the first one is usually undecidable, and the second is not.

If You take as a starting point $\beta+\eta$ equality at non-functional types and $(1)$ at functional types, what you get is extensional equality of terms, and it holds in most "natural" models. See e.g. Berardi et al for models of system $F$ and the classic Barendregt chapters 5 and 10.


Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE? Let me state the problem again:

  Suppose PSPACE $\ne$ EXP. Is there a language in EXP - PSPACE that is not PSPACE-hard?

Context

I have a problem that's in EXP. Currently I don't think it's in PSPACE. Besides proving it's EXP-complete, what else can I do? Since it seem not to be in PSPACE, I start to think it's PSPACE-hard. But is this necessary? That's why I asked this question.

Actually I have a related question, that is, given PSPACE $\ne$ EXP, whether there is a language in EXP - PSPACE that is not EXP-hard. A yes answer to the main question will imply a yes answer to this question. I think answering this question will also help me somehow.

The proof of Ladner's theorem doesn't use any special properties of P and NP and the same proof unchanged will show, assuming EXP<>PSPACE, there is a language L in EXP-PSPACE and not EXP-complete under either P-time or PSPACE-reductions.

You need the full Landner look-back trick to keep L in EXP.


Candidates for One-Way Function Why are the candidates for one-way functions so few?

Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!).

Why one can not generate several candidates by using advanced mathematics, for example using complex structures of combinatorics?

Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well).

What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed" (or something whose invertability would imply that of such a function). From this perspective, it is worse for the problem to be more obscure (fewer have tried it), and it may be worse that the function is more complicated (this obfuscates whether it is truly difficult or you just cannot see the solution yourself).

To put the intuition another way, a common "bad intuition" is that if a problem looks more complicated or difficult to define/understand, then it is more likely to be computationally difficult to solve. Theoretical crypto does not accept this premise. The primary evidence we have for computational hardness is a history of failed attempts, which means good candidates should be simple, well-known functions with long histories.


What is a probabilistic function and where can I learn more about them? I am reading a paper on privacy that says we can model something as an arbitrary probabilistic function from $X^M \to X^M$.  I'm trying to figure out what exactly that means.  I saw another paper that defined a probabilistic function as a function $\mathcal{F}:X \times Y \to [0, 1]$ that satisfied the condition $$\forall x \in X: \sum_{y \in Y} \mathcal{F}(x, y) \leq 1.$$  But that definition doesn't seem to make sense if the function can take on values in the space $X^M$ where $X$ is an arbitrary set of objects.  So what exactly are probabilistic functions?

Thanks so much!

The definition you give is essentially the one you need. A probabilistic function from $X$ to $Y$ assigns to each $x\in X$ a subdistribution of elements of $Y$ (rather than a single $y\in Y$). Such a subdistribution is a function $\delta:Y\to[0,1]$ such that

$\sum_{y\in Y}\delta(y)\leq 1$.

In other words, a probabilistic function $X\to Y$ is a function $f:X\to(Y\to [0,1])$, i.e. $f:X\times Y\to [0,1]$, such that for all $x\in X,$

$\sum_{y\in Y}f(x,y)\leq 1$.

In your case, both domain and codomain are $X^M$; a probabilistic function from $X^M$ to $X^M$ then is a function $f:X^M\times X^M\to [0,1]$ such that for all $x\in X^M$,

$\sum_{y\in X^M} f(x,y)\leq 1$.

The intended meaning of this is that the function still returns a single point when given some input, but this point is chosen randomly according to the relevant distribution. For example, if $M=2$, and $f(1,2) = \{(1,1)\mapsto 0.5,(2,2)\mapsto 0.5\}$ (all others being $0$), then when you call $f(1,2)$, you will get $(1,1)$ or $(2,2)$ each with probability $0.5$.


LU factorization of a 0-1 matrix I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such a matrix(whenever it exists) with entries $(a)$ from integers? $(b)$ from $\{-1,0,+1\}$?

No. Consider the 4-by-4 matrix below.

 0     1     1     1
 1     0     1     1
 0     0     0     1
 1     1     0     1


How do minimally violated k-mod cuts work (intuitive explanation)? As a background, I am not a specialist in theoretical computer science. But I have to take an exam with research-level optimization topics, and I have to learn it on my own, without lectures or tutors.

One of the subtopics I am required to learn in integer programming are maximally violated mod-k cuts. I was able to understand cutting plane methods in general, and how Chvatal-Gomory cuts work. The book I am using says that k-mod cuts are created by multiplying the system of constraining inequalities with some vector $\lambda$, then summing up all inequalities. I have difficulty picturing this and understanding why this leads to an interesting form of cut.

I tried making a numerical example for myself starting out with an easy system with 2 variables and 3 inequalities, but wasn't able to come up with any (apparently, finding them is NP-hard for the general case, I had hoped to come up with something obvious with a few tries for a very small example).

Could you please give me an explanation about the intuition behind these cuts? What do they look like, what makes them "maximally violated", how are they an improvement over other cuts?

The main text from which I have to learn is http://www.springer.com/de/book/9783642167287, and I also found exactly one paper on the topic, http://www.lancaster.ac.uk/staff/letchfoa/articles/mod_k.pdf. They are research-level sources, and I don't have enough background to build an intuitive understanding when reading the definitions.

Suppose you have an integer linear program, and it contains the following constraints:

x1 + x2 + x3 >= 1,
x1 + x2 + x4 >= 1,
x1 + x3 + x4 >= 1,
x2 + x3 + x4 >= 1.

If we set x1, ..., x4 to 1/3, we satisfy all of the constraints, but we don't have integer values.

Now multiply each constraint by 1/3 and sum them together. You obtain:

x1 + x2 + x3 + x4 >= 4/3.

Since the variables are integer-constrained, we can round up the right-hand side to obtain:

x1 + x2 + x3 + x4 >= 2.

This "cuts off" the above-mentioned fractional solution, so it is called a "cutting plane".

Since we multiplied the constraints by 1/3, the given cutting plane is a "mod-3" cut. Moreover, the fractional solution violates the cutting plane by 2/3, which is best possible. So the mod-3 cut is "maximally violated".

More generally, to obtain a mod-k cut, you multiply each constraint by a multiple of 1/k, before summing and rounding. Such a cut is "maximally violated" by a given fractional solution if it is violated by (k-1)/k.


Approximate degree of $\textrm{AC}^0$ EDIT (v2): Added a section at the end on what I know about the problem.

EDIT (v3): Added discussion on threshold degree at the end.

Question

This question is mainly a reference request. I don't know much about the problem. I want to know if there has been previous work on this problem, and if so, can someone point me to any papers that talk about this problem? I'd also like to know the current best bounds on the approximate degree of $\textrm{AC}^0$. Any other information would also be appreciated (e.g., historical information, motivation, relation to other problems, etc.).

Definitions

Let $f:\{0,1\}^n \to \{0,1\}$ be a Boolean function. Let $p$ be a polynomial over the variables $x_1$ to $x_n$ with real coefficients. The degree of a polynomial is the maximum degree over all monomials. The degree of a monomial is the sum of exponents of the various $x_i$ that appear in that monomial. For example $\textrm{deg}(x_1^7x_3^2) = 9$.

A polynomial $p$ is said to $\epsilon$-approximate $f$ if $|f(x)-p(x)|<\epsilon$ for all $x$. The $\epsilon$-approximate degree of a Boolean function $f$, denoted as $\widetilde{\textrm{deg}}_{\epsilon}(f)$, is the minimum degree of a polynomial that $\epsilon$-approximates $f$. For a set of functions, $F$, $\widetilde{\textrm{deg}}_{\epsilon}(F)$ is the minimum degree $d$ such that every function in $F$ can be $\epsilon$-approximated by a polynomial of degree at most $d$.

Note that every function can be represented with no error by a degree $n$ polynomial. Some functions really do need a degree $n$ polynomial to approximate to any constant error. Parity is an example of such a function.

Problem statement

What is $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$? (The constant 1/3 is arbitrary.)

Notes

I encountered this problem in the paper The Quantum Query Complexity of AC0 by Paul Beame and Widad Machmouchi. They say

  Also, our results do nothing to close the gap in the lower bound on the approximate degree of AC0 functions.

They mention "the problem of the approximate degree of AC0" in their acknowledgements too.

So I assume there has been some work on this problem before? Can someone point me to a paper that talks about the problem? And what are the best known upper and lower bounds?

What I know about the problem (This section was added in v2 of the question)

The best known upper bound on $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$ that is know is the trivial upper bound $n$. The best lower bound I know comes from Aaronson and Shi's lower bound for the collision and element distinctness problems, which gives a lower bound of $\tilde{\Omega}(n^{2/3})$. (For severely restricted versions of $\textrm{AC}^0$, like formulas with $o(n^2)$ formula size, or depth-2 circuits with $o(n^2)$ gates, we can prove a $o(n)$ upper bound using quantum query complexity.)

Related: threshold degree (Added in v3)

As Tsuyoshi points out in the comments, this problem is related to the problem of determining the threshold degree of $\textrm{AC}^0$. The threshold degree of a function $f$ is the minimum degree of a polynomial $p$ such that $f(x)=1 \implies p(x)>0$ and $f(x)=0 \implies p(x)<0$.

Lower bounds for the threshold degree of $\mathrm{AC}^0$ have now been improved by Sherstov. He exhibits a family of constant-depth read-once formulas on $n$ variables whose threshold degree approaches $\Omega(\sqrt{n})$ as the depth goes to infinity, which is almost tight since read-once formulas have threshold (and even approximate) degree $O(\sqrt{n})$. See http://eccc.hpi-web.de/report/2014/009/. (Jan, 2014)

A paper by Mark Bun and Justin Thaler has been posted on ECCC very recently (mid-March 2017) that precisely answers this question: "A Nearly Optimal Lower Bound on the Approximate Degree of AC0"

They claim that for any $\delta > 0$, there exists a function $f$ in $\mathrm{AC}^0$ such that $\widetilde{\mathrm{deg}}_{1/3}(f) = \Omega(n^{1-\delta})$, nearly closing the gap with the trivial $O(n)$ upper bound. They achieve this with a general method to boost the approximate degree of a function with sublinear approximate degree, keeping the number of variables quasi-linear. From the abstract :

  Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a
  function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} · d^{2/3} )$. In
  particular, if $d = n^{1−Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a
  polynomial-size Boolean circuit of constant depth, then so is $F$.

That is the most recent update on the lower bound end of this problem, and it is quite a significant step forward. The Introduction and Application sections of the paper are also good sources of references for prior works and related problems.

Disclaimer: I haven't read the paper carefully yet.


Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the values of the SDPs. The CVX package seems to be very straightforward to get up and running, but I'm a bit unsure in how to convert the SDPs in this scenario and how to interpret the results. For completeness and to try to be a bit helpful, the primal and dual problems for the maximization constraint are replicated from the paper below.

Primal Problem:

maximize: $\langle Q_a, X \rangle$

subject to: $Tr_{\mathcal{Y}}(X) = \mathcal{I}_{\mathcal{X}},$

$\qquad \qquad X \in Pos(\mathcal{Y} \otimes \mathcal{X})$

Dual Problem:

minimize: $Tr(Y)$

subject to: $\mathcal{I}_{\mathcal{Y}} \otimes Y \geq Q_a,$

$\qquad \qquad Y \in Herm(\mathcal{X})$

In this case, these are the SDPs which correspond to Bob's maximum probability for winning some quantum protocol between two parties (more information is in the paper, but if you're going to take the time to help me, by all means ask if I can clarify something in a bit more detail). The variables $Q_a$ and $X$ correspond to the Choi-Jamiolkowski representation of the channel for Alice and Bob respectively. My attempt at putting this into MATLAB is as follows:

n = 3;
cvx_begin sdp
    variable Y(n,n) hermitian;
    dual variable X;
    maximize ( trace ( Y ) );
    subject to
       X : kron(eye(n), Y) >= 0;
cvx_end

Since I don't have a partial trace operation, I'm essentially flipping the roles of the primal and dual functions by swapping the maximization and minimization constraints. This may not be the right way to go about it though, so any feedback would certainly be helpful.  Basically my understanding is that if you provide the primal problem, CVX is smart enough to solve the corresponding dual (Section 3.7 of the CVX manual).

Running the above works, but yields a status failed result, leading me to think that there is something I'm most likely missing here:

Status: Failed
Optimal value (cvx_optval): NaN

The new SDP that you obtain by replacing minimize by maximize is not necessarily closely related to the first one. Right now the value is infinity, and if you replaced 0 by $Q_a$ on the right side of the constraint, the value is always going to be 0 or infinity (if it's not 0, you can just multiply any solution with positive value by an arbitrary constant, and increase the value).

The way I went about this general issue when solving these SDPs was just implementing the partial trace, and then coding the dual and primal problem separately. The implementation of the partial trace is at https://cs.uwaterloo.ca/~amolinap/prtrace.m, hope it is useful!


Are there any heuristic-free NP complete problems? Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in polynomial time? (Assuming $P \neq NP$)

See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted to $\Phi$ is trivial (answer always no).

This can be formalized by stating that no co-NP-complete set is P-immune. It is also known (again under cryptographic assumptions) that no NP-complete set is P-immune. So there is another infinite subset $\Phi'$ such that membership in $\Phi'$ is polynomial-time testable and the decision problem restricted to $\Phi'$ always has answer yes. See e.g. Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, doi:10.1137/S009753970444421X.


Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$? Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

Heller gives a relativized world where $BPP = EXP^{NP}$ which sits far outside of $P^{NP}$. Showing $BPP \neq EXP^{NP}$ unconditionally would in itself be considered a major breakthrough in derandomization.


Complexity class when reducing decision problem to function problem Given a decision problem DEC which is PSPACE-Hard and a function problem FUN.  If there is a polytime reduction from DEC to FUN, does this mean that FUN is FPSPACE-Hard?

In my case, the answer of the function problem is the one of the decision problem plus additional information.  So it seems natural to assume that it is at least as hard.  The question is whether this means that a lower bound for its complexity is the "function class" corresponding to the complexity class of the decision problem.

In the case of PSPACE and FPSPACE, the answer is yes (since DEC reduces to FUN and DEC is PSPACE-hard, FUN is FPSPACE-hard). The reason is that in PSPACE search always reduces to decision: say you want to compute a function $f(x)$. If the problem of deciding whether the $i$-th bit of $f(x)$ is 1, given $i$ and $x$, is in PSPACE, then $f$ itself is in FPSPACE. Now, if $f$ is in FPSPACE, we can use your function FUN to compute it by using FUN to compute the decision problem "is the $i$-th bit of $f(x)$ 1?" for each $i$. One way to say this is that PSPACE is FPSPACE-hard.

However, there are complexity classes where the relationship between the function and decision versions is not so clear. For example:

It is not known if the search version of Group Isomorphism (find an isomorphism) reduces to the decision version (is there an isomorphism?), when the groups are input as multiplication tables.
$P^{NP[\log]} = P^{NP}_{tt}$, but $FP^{NP[\log]} = FP^{NP}_{tt}$ is not known to hold and would imply $NP=RP$ and $P=UP$ (see Selman, A. A taxonomy of complexity classes of functions. JCSS 48(2):357-381, 1994.) But if $P^{NP}_{tt}$ were $FP^{NP}_{tt}$-hard, we would automatically have equality of the function classes.

(For reference: $P^{NP[\log]}$ is $P$ with an $NP$-oracle, but the $P$ machine is only allowed to make $O(\log n)$ queries to the oracle. $P^{NP}_{tt}$ is the problems that are polytime truth-table reducible to $NP$; this is equivalent to nonadaptive polytime Turing reductions, i.e. all the queries to be made are decided in advance, then all the queries are made, then some computation is done without queries to find the result.)


Why is the security of lattice cryptosystems not provable from $P \neq NP$? My understanding is that the Shortest Vector Problem ($\text{SVP}$) is $\text{NP}$-hard.  Therefore, $\text{LWE}$ is also $\text{NP}$-hard.  But $\text{LWE}$ is hard on average if it is hard in the worst case, so breaking certain cryptosystems based on it is also $\text{NP}$-hard, which means that secure asymmetric encryption is not only possible but known, unless $\text{P} = \text{NP}$!

That would be a rather striking result, and to my knowledge it has not been clamed in a serious paper.  What is the flaw in my reasoning?

To expand somewhat on Sasho Nikolov's comment...

  LWE is at least as hard as finding approximate solutions to SVP, but the approximation factors for which the reduction from SVP to LWE works are larger than the approximation factors for which we know NP-hardness

...the following is a reasonably complete view of things:

This was part of Oded Regev's talk at the Winter School on Lattice-Based Cryptography and Applications, held at Bar-Ilan University, Israel, in 2012.

If you are interested in a good introduction to the very basics of lattice cryptography, I'd happily recommend checking out the full record of this winter school. You can (still-- as of Summer 2017) find a large list of slides and talk videos at:

https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/


closure properties of IP(2pfa) and AM(2pfa) IP(2pfa) and AM(2pfa) are the classes of languages recognized with bounded error by private and public coin versions, respectively, of interactive proof systems with verifiers that are probabilistic finite automata with a two-way input head.

Are any closure properties of these classes known?

You can take a look at the following paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers I: the power of interaction. J. ACM 39, 4 (Oct. 1992), 800-828. DOI= http://doi.acm.org/10.1145/146585.146599

or the related paper:

Dwork, C. and Stockmeyer, L. 1992. Finite state verifiers II: zero knowledge. J. ACM 39, 4 (Oct. 1992), 829-858. DOI= http://doi.acm.org/10.1145/146585.146601


C# Generics Research Papers What are the most significant research papers on the foundations of generics in C# and .NET?

Most of the important work on generics for C# was done by Andrew Kennedy at Microsoft Research Cambridge. He has a web page devoted to the topic. A fairly recent paper discussion the foundations is this one (which definitely looks like theory to me).

More recent, but interesting, work went into the design of C$\omega$. Also looking at the rather large amount of literature on Java generics, such as Featherweight Java, will also help. If you really want to start looking at the foundations, consider Cardelli's work on Types and Semantics, and perhaps consider looking at System F (and the original papers of Reynolds and Girard).


Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$? By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.

If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\ne NP$).

$PP$ is the class of decision problems analog for $\#P$ and $P\subseteq PP\subseteq PSPACE$,

but neither $P=PP$ nor $PP=PSAPCE$ is known. But is it true that

$coNP^{\#P}=NP^{\#P}=P^{\#P}$?

It is an open problem in complexity theory for many years if $\mathsf{PH}^{\mathsf{\#P}}$ collapse,
where $\mathsf{PH}$ is the polynomial time hierarchy. It is also an open problem to construct
an oracle to separate $\mathsf{P}^{\mathsf{\#P}}$ from $\mathsf{PSPACE}$.


Can a two counters machine decide $n^2$? Can a standard two counters ($c_1,c_2$) machine with the following instructions:

1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

decide the following language:

$$L = \{ n^2 \mid n \geq 1 \}$$

(the input is initially loaded in the counter $c_1$)?.

Is it still an open problem? (cf. Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972])

The problem has been solved in:

Oscar H. Ibarra, Nicholas Q. Trân, A note on simple programs with two variables, Theoretical Computer Science, Volume 112, Issue 2, 10 May 1993, Pages 391-397, ISSN 0304-3975, http://dx.doi.org/10.1016/0304-3975(93)90028-R.

Let $TV$ be the class of languages recognized by two-counter machines.

Theorem 3.3: For any fixed integer $k \geq 2$, $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Note: it's strange that in the Ibarra&Tran's paper

Theorem 3.4 Let $f$ be a total function with infinite range and such that the relation $f(a + bn)=f(a)+cn$ for all $n \geq 0$ does not hold for any triple $(a,b,c)$; then $f$ cannot be computed by any two-counter machine.

is proved and the authors say that it has been derived in a slightly different form in:

I.M. Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), Russian, Algebra i Logika 1 (1963) 42-51

but don't cite Rich Schroeppel's paper (1972) in which the theorem is also derived ... :-)


How to contribute incrementally to Theoretical CS - similar to github I have been through all the basic undergrad classes in CS. I have finished a masters in CS. I have learned a decent amount about applying Haskell to engineering. I haven't studied abstract math yet. I have attended two STOC conferences. I have about 2 hours per week that I could contribute in some way to move Theoretical CS forward in some way.

For Haskell, I could spend that time writing documentation, adding test suites, or implementing features for open source Haskell libraries on github. Is there an equivalent way incrementally contribute as a beginner to theoretical CS? Is there anything like github or are people using github for such purposes?

The best idea I have currently is to try to teach undergrad discrete math or algorithm courses.

As mentioned in a comment above, you can contribute to the TCS Wikipedia Project led by Shuchi Chawla:

  Wikipedia is a great resource for people outside of the TCS community to learn about TCS topics, and provides an educational and outreach opportunity for our community. Our community should ensure that important TCS topics get adequate and accurate coverage in Wikipedia through articles written by experts. Unfortunately, writing or editing articles for Wikipedia, and ensuring that the edits are not overwritten, can be a daunting task. It is a task best addressed as a community effort rather than by a few individuals.


Ambiguity of regular expressions Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can be written in the unambiguous form 'a*`. The answer to this question gives an algorithm for deciding whether a regular expression is ambiguous.

Is there an algorithm for finding an equivalent unambiguous form of any given RE?
Are there REs that are inherently ambiguous?

(This question seems relevant by title; not by content)

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the sense described in the question. This is a classic result in automata theory:
 R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and expressions, IEEE Transactions on Computers 20(2) (1971) 149–153.
See also this question over at MO for more details and a reference: https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous


Complexity of Acyclic Hypergraph Isomorphism It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and some other complete problems for deterministic logspace." DIRO, Université de Montréal. 1997)

I would like to know whether something similar is known for the hypergraph isomorphism problem. In that case instead of trees we would have alpha-acyclic hypergraphs (see Characterization 15 on page 20 of https://arxiv.org/abs/1403.7076 for the definition of alpha acyclicity).

So, I am asking whether some non-trivial complexity bounds for the following problem are known:
Given two alpha acyclic hypergraphs G and H, is there an isomorphism between G and H?

Of course if something is known for other forms of acyclicity (e.g. beta or gamma) that would be interesting too.

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.


Separated 3Sum versus 3Sum problem Does it matter in the 3Sum problem if the numbers to be summed belong to the same set or to distinct sets?

Let's define

the problem "$k$-Sum" as follows: given a single finite set of integers $X\subset N$ of size $n$, decide if there exists $k$ integers $x_1,\ldots,x_k\in X$ such that their sum $\sum_{i=1}^k x_i$ is null; and
the problem "Separated $k$-Sum" as follows: given $k$ finite sets of integers $X_1,\ldots,X_k\subset N$ of respective sizes $n_1,\ldots,n_k\in[1..n]\subset N$, decide if there exist a vector $(x_1,\ldots,x_k)\in X_1\times\ldots\times X_k$ such that their sum $\sum_{i=1}^k x_i$ is null.

I was assuming that those two problems were equivalent, and I was using the second one as a pedagogical example for some parameterization technique (while there is an algorithm running in $O(n^2)$ for both, the second one can take advantage of variations in the size of the sets to solve the problem much faster, down to $O(n_1 n_3+\sum n_i\lg n_i)$ and $O(n_1 n_2 \lg \frac{n_3}{n_2}+\sum n_i\lg n_i)$).

But I realized today that I did not know how to prove this equivalence, and I might even start to think that they are not.

You can reduce the SEPARATED k-SUM problem to a (k+1)-SUM problem in the following way:

Given $X_1,...,X_n$, let $b$ such that $2^b > \max( abs(X_1) \cup ... \cup \;abs(X_n))$, where $abs(X_i) = \{ |x| \mid x \in X_i \}$, and let $c$ such that $2^c > k 2^b$

For  $i = 1,...,k$ build $Y_i = \{ 2^{c+ki} + 2^{b} + x_j \mid x_j \in X_i \}$;
let $u = - \sum_{i=1}^k 2^{c+ki} -k2^b$

Build an equivalent (k+1)-SUM problem picking $X =  \{ u \} \cup Y_1 \cup ... \cup Y_k$

Note that every $Y_i$ contains only positive elements.

Informally we require a $k+1$ elements subset $C$ from $X$ whose elements sum to zero.
We cannot build a solution only with the negative element $u$; so we must include in $C$ at least one element $y$ from one of the $Y_i$; but the $2^{c+ki}$ "component" of $y$ can be balanced only if $u$ is also included; but including $u$ implies that exactly one of the elements of each $Y_i$ is included (the  $- \sum_{i=1}^k 2^{c+ki}$ component of $u$ allows to keep the separation between the elements of the original $X_i$). But we also have $\sum_{j=1}^k (2^b + x_j) = k2^b$ and this implies that the original $x_j$s (coming from distinct $X_i$s as seen above) sum to zero.


k-Vertex Cover problem is in parameterized Log space $k$-Vertex Cover:

Given a graph $G = (V, E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$,
the $k$-Vertex Cover problem determines if there exists a subset of vertices $V'$ of $V$ of size at most $k$, such
that every edge of $E$ has at least one vertex in $V'$.

Can we solve $k$-Vertex Cover problem in $f(k)+c\log|V|$ space where $c>0$ is some constant?

yes. (proof given in link page number 126 and Theorem 2.3).
Can you give Simple proof?

Can we get all mimimum vertex covers of size $k$ from this proof with in
 $f(k)+c\log|V|$ space?

There is an other method (bounded search tree method proof given in [link] (http://www.mrfellows.net/papers/CCDF97_AdviceClasses.pdf) page number 127 proof(2)) to show that k-Vertex Cover problem is in parameterized Log space.

Other method goes as follows:
There are 2^k possible vertex covers. Think $P$ is at most $k$ length 0's and 1's bit string. For each value of $P$, we can generate the vertex set of size at most $k$ and it may become potential vertex  cover.  Clearly we can say $P$ is the path in bounded search tree.
For generating for all $P$'s need 2^k space.
Now we need to find vertex cover for given $P$ and $P$ is at most $k$ length 0's and 1's bit string.

Function $F(P,1)$ returns us first vertex by choosing the lex least edge and then the lex least vertex and this function will take constant space.

Function $F(P,2)$ returns us vertex of lex least edge not connected to the first one ($F(P,1)$).

$F(P,2)$ needs output of $F(P,1)$ and enumerate edges to find the lex least edge not connected to the first one.
$F(P,2)$  needs one logspace

Function $F(P,3)$ returns us vertex of lex least edge not connected to $F(P,1)$ and $F(P,2)$.
But we are not store the output of $F(P,1)$ and $F(P,2)$.
We need to enumerate the edges and find the  lex least edge not connected to  $F(P,1)$ and $F(P,2)$.
For this for each edge, we call $F(P,1)$ and $F(P,2)$ sequentially and check whether edge connected to $F(P,1)$ and $F(P,2)$.
For each edge we need one logspace and $F(P,2)$ one logspace
$F(P,3)$ needs two logspace

Similarly $F(P,i)$ returns us vertex least edge not connected to $F(P,1) \cdots F(P,i-1)$.
we are not store the outputs of $F(P,1) \cdots F(P,i-1)$. We need to call sequentially.
We need to enumerate the edges and find the  lex least edge not connected to  $F(P,1) \cdots F(P,i-1)$.
For this for each edge, we call $F(P,1) \cdots F(P,i-1)$ sequentially and check whether edge connected to $F(P,1) \cdots F(P,2)$.
So $F(P,i)$ needs (i-1)  logspace

Clearly $F(P,k)$  needs k.logspace. But algorithms should takes only $f(k)+c\log n$ space?.

Am I missing something?. Please help out this process where it went wrong?

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

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

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

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

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

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

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


NP-Hardness for an optimization problem I want to prove that the following optimization problem is NP-Hard.

max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$

subject to

$x_j \in \{0,1\}\text{  } \forall j$

$\sum_{j=1}^M x_j \le T$

given

$R_{ij} \in \{0,1\}\text{ } \forall i,j$

As you can see the expression is quite unwieldy, and there does not seem to be any clear way to proceed with the reduction. I tried variants of Knapsack (which seemed closest), as well as other standard reductions but nothing seems to work very easily. The fractional form of the expression, combined with the product makes it quite hard to do reductions. Any help is appreciated!

Problem Clarifications

There's a few things worth mentioning about the problem you asked.

First of all, we need to make sure that the expression you are maximizing is well defined, so the denominator must be non-zero. Simply adding the constraint that $\sum_{j=1}^Mx_j \ge 1$ is enough.

Second, I'd rather not get into the problem of talking about whether an optimization problem is NP-hard, so I'm going to explicitly state a decision version of the problem and then the rest of this answer will talk about that.

For the decision problem, the following are the inputs (note: variables follow the naming scheme from the question except $G$ which I introduce here and stands for "goal"):

Two positive integers $N$ and $M$
A collection of values $R_{ij}\in\{0,1\}$ specified for every pair of $i$ and $j$ with $1 \le i \le N$ and $1 \le j \le M$
A positive integer $T$
A value $G$

And the output is yes if and only if there exists an assignment of values to the variables $x_j$ for $1 \le j \le M$ such that

for all $1 \le j \le M$, $x_j \in \{0,1\}$ and
$1 \le \sum_{j=1}^Mx_j \le T$ and
$\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$

This problem is NP-hard

Reduction

We prove this by reduction from dominating set. The dominating set problem asks for a given graph and number $k$ whether some choice of $k$ vertices has the property that every vertex in the graph is either chosen or next to a chosen vertex.

Suppose we are given an instance of dominating set consisting of a graph $G = (V, E)$ and a number $k$.

For convenience, label the vertices of $G$ as $v_1, v_2, ..., v_{|V|}$.

Then we construct an instance of the problem in question as follows:

$N = M = |V|$
$R_{ij} = 1$ if and only if $(v_i, v_j) \in E$ or $i=j$
$T = k$
$G = 0$

Polynomial Time

Very little needs to be done in the reduction to construct the instance, so this reduction is clearly polynomial time.

Answer preserving

Every instance generated by this reduction has $G = 0$. Therefore the condition that $\prod_{i=1}^N\left(\frac{\left(\sum_{j=1}^Mx_jR_{ij}\right)^2}{\sum_{j=1}^Mx_j}\right) > G$ is equivalent to the condition that for every $i$ with $1 \le i \le N$, $\sum_{j=1}^Mx_jR_{ij} \ne 0$. That in turn is equivalent to the condition that for all $i =1, ..., N$, there exists some $j \in \{1, ..., M\}$ such that $x_j = R_{ij} = 1$.

In other words, once we work in the fact that $N = M = |V|$ and $T = k$, we see that the instance is a yes instance if and only if there exists an assignment of zeros and ones to the variables $x_j$ such that

at least one and at most $k$ values of $j$ have $x_j = 1$ and
for all $i =1, ..., |V|$, there exists some $j \in \{1, ..., |V|\}$ such that $x_j = R_{ij} = 1$

That in turn is equivalent to choosing between $1$ and $k$ indices (the ones for which $x_j = 1$) such that for all $i =1, ..., |V|$, some one of the chosen indices $j$ has $R_{ij} = 1$.

But $R_{ij} = 1$ if and only if $i = j$ or $(v_i, v_j) \in E$. Thus solving the instance is equivalent to choosing between $1$ and $k$ indices from $1$ to $|V|$ such that for every $i$, either $i$ is chosen or $v_i$ is adjacent in $G$ to some $v_j$ with j chosen.

Restating this one last time, the answer to the instance generated by the reduction is the same as the answer to the following question: is it possible to choose between $1$ and $k$ vertices in $G$ such that each vertex is either chosen or adjacent to a chosen vertex. This is the original dominating set instance.

We have shown that the reduction is answer preserving, so this concludes the proof that the decision problem in question is NP-hard.


For what languages is there already a theory of observational equivalence? For a correctness proof, I'm looking for a usable notion of program equivalence $\cong$ for Barendregt's pure type systems (PTSs); missing that, for enough specific type systems. My goal is simply to use the notion, not to investigate it for its own sake.

This notion should be "extensional" — in particular, to prove that $t_1 \cong t_2$, it should be enough to prove that $t_1\; v \cong t_2\; v$ for all values $v$ of the appropriate type.

Denotational equivalence

Denotational equivalence easily satisfies all the right lemmas, but a denotational semantics for arbitrary PTS seems rather challenging — it'd appear hard already for System F.

Contextual/observational equivalence

The obvious alternative are then various forms of contextual equivalence (two terms are equivalent if no ground context can distinguish them), but its definition is not immediately usable; the various lemmas aren't trivial to prove. Have they been proved for PTS? Alternatively, would the theory be an "obvious extension", or is there reason to believe the theory would be significantly different?

EDIT: I didn't say what's hard above.

Easy part: the definition

Defining the equivalence is not too hard, and the definition appears in many papers (starting at least from Plotkin 1975's study of PCF, if not earlier — the source might be Morris's PhD thesis from 1968).
We $t_1 \cong t_2$ if for all ground contexts $C$, $C[t_1] \simeq C[t_2]$ — that is, $C[t_1]$ and $C[t_2]$ give the same result. You have a few choices here with lots of alternatives: For instance, in a strongly normalizing language, if you have a ground type of naturals, you can say that ground contexts are the ones that return naturals, and then $a \simeq b$ means that $a$ and $b$ evaluate to the same number. With nontermination, for reasonable languages it is enough to use "X terminates" as observation, because if two programs are equivalent when observing termination, they're also equivalent when observing the result.

Hard part: the proofs

However, those papers often don't explain how hard it is to actually use this definition. All the references below show how to deal with this problem that, but the needed theory is harder than one thinks. How do we prove that $t_1 \cong t_2$? Do we actually do case analysis and induction on contexts? You don't want to do that.

As Martin Berger points out, you want to use, instead, either bisimulation (as done by Pitts) or a logical equivalence relation (that Harper simply calls "logical equivalence").

Finally, how do you prove extensionality as defined above?

Harper solves these questions in 10 pages for System T, through considerable cleverness and logical relations. Pitts takes more. Some languages are yet more complex.

How to deal with this

I'm actually tempted to make my proofs conditionally on a conjectured theory of equivalence for PTS, but the actual theories require nontrivial arguments, so I'm not sure how likely such a conjecture would be to hold.

I'm aware (though not in detail) of the following works:

Andrew Pitts (for instance in ATTAPL for an extended System F, and in a few papers, such as the 58-page "Operationally-Based Theories of Program Equivalence").
Practical Foundations of Programming Languages (chapters 47-48), which is inspired by Pitts (but claims to have simpler proofs).
A logical study of program equivalence. I can't find an English abstract, but it seems to spend a great deal of effort for side effects (references), which seems an orthogonal complication.

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


recursion schemes that prune Probably the most common recursion scheme is the catamorphism, or fold.  This is a recursion that takes a data type and "deconstructs" it into something else.  For example, we can calculate the length of a list using a fold (with Haskell syntax):

length :: [a] -> Int
length xs = foldr 0 (+1) xs

One property of all folds that I've seen is that they look at all elements of the data type.  But is there work formalizing recursion schemes that do not look at all elements?  That is, they prune some of them away.

If the type of foldr :: (a -> b -> b) -> b -> t a -> b, then the pruning fold would look something like prunefold :: (???) -> (a -> b -> b) -> b -> t a -> b, where ??? is the pruning rule.  I can imagine many different possible forms of these pruning rules just for folds, and I imagine other recursion schemes would have even more.

Motivating example 1:  We could search a binary search tree using a fold.  This fold would perform a depth first search.  But this is very inefficient.  Instead, we would prefer to have a "pruning rule" that on each iteration removes removes half the tree.  This pruning fold gives us the same answer, but reduces the complexity from $O(n)$ to $O(\log n)$.

Motivating example 2:  We can express $\pi$ as a sum over an infinite sequence.  A standard fold over this sequence would never terminate.  But we could use a pruning rule to stop our fold after a certain amount of accuracy has been reached.  When used on an infinite data structure, the pruning fold is strictly more powerful.

I think my comment was a little cryptic, so let me unpack. The key intuition behind hylomorphisms is that they let you reify the call graph as a data structure. You unfold a datastructure to build a representation of the call graph, and then you fold over the intermediate structure to consume and finish the computation.

Lists are a little misleading, because in a recursive algorithm over a list, the call graph will also form a list. However, in general this will not be the case: the call graph will have a different shape than your input data, and so you'll need to introduce a new datatype to represent it. As an example. here's your binary search example. I'll use Ocaml, since I'm more familiar with it, but it should be fairly easy to transcribe it to Haskell.

First, let's introduce a datatype of binary search trees. We'll just assume they maintain the invariant in a node Node(l, x, r) that the left subnode l contains the elements smaller than x and the right subtree r contains the elements bigger than x.

type tree = Leaf | Node of tree * int * tree

Now, let's introduce a datatype to represent the call graph of a binary search. A binary search will finish with failure if the tree is a Leaf, finish with success if you have a Node whose value is what you're looking for, and keep going otherwise.

We'll represent this with a datatype result that is either a Done b, where b is a boolean with success or failure, or else gives you a Next thunk with a computation which will give you a new result. (In Haskell, you wouldn't need the unit -> 'a thing because all datatypes are lazy.)

We'll split result into a functor resultF, and tie the recursive knot in this datatype explicitly, so that we can easily program the map functional for functor.

type 'a resultF = Done of bool | Next of (unit -> 'a)
type result = Rec of result resultF

let map_resultF f v =
  match v with
  | Done b -> Done b
  | Next thunk -> Next (fun () -> f (thunk()))

Now, we can define a fold operation for the result type.

(* val fold_result : ('a resultF -> 'a) -> result -> 'a *)
let rec fold_result f (Rec result) =
  f (map_resultF (fold_result f) result)

Here's a function that uses the fold function to force all the Next steps until you get to the boolean final answer.

(* val finish : result -> bool *)
let finish  =
  fold_result
    (fun r ->
       match r with
       | Done b -> b
       | Next thunk -> thunk())

We finally get to the interesting part. Here's the unfold operation for the result type:

(* val unfold_result : ('a -> 'a resultF) -> 'a -> result *)
let rec unfold_result f  seed =
  Rec (map_resultF (unfold_result f) (f seed))

Now, you can see how to use an integer and a tree to construct a result:

(* val mem' : int -> tree -> result *)
let mem' x =
  unfold_result
    (fun seed ->
      match seed with
      | Leaf -> Done false
      | Node(l, y, r) ->
          if       x < y then Next (fun () -> l)
          else if  x > y then Next (fun () -> r)
          else                Done true)

The really critical is that we're using the unfold to incrementally take the input, and building a result which we use to control the shape of the computation. This is where the pruning is taking place, and you can change it to whatever you like. Also, note that if you want to do something fancy (e.g., use intermediate estimates to control the pruning), you can change the result type to contain it, and update your unfold to compute it.

Finally, you can see the mem function as the fold followed by an unfold, of the result type:

(* val mem : int -> tree -> bool *)
let mem x tree = finish (mem' x tree)


Difference between theory and practice of security and cryptography? What interesting differences are there between theory and practice of security and cryptography?

Most interesting will of course be examples that suggest new avenues for theoretical research based on practical experience :).

Answers might include (but are not limited to):

Examples where theory suggests something is possible but it never gets used in practice
Examples where theory suggests that something is safe that is not safe in practice
Examples of something in widespread practical use has little theory behind it.

...

Caveat

If your answer is essentially of the form "Theory is about asymptotics, but practice is not," then either the theory should be really central, or the answer should include specific examples where the practical experience on real-world instances differs from the expectations based on the theory.

One example I know of: secure circuit evaluation.  Very powerful in theory, but too complicated to ever use in practice, because it would involve taking your code, unrolling it into a circuit, and then doing secure evaluation of each gate one at a time.

Oh boy, where to start.

The big one is definitely black boxes. Crypto researchers make a fuss about things like uninstantiability problem of the Random Oracle Model. Security researchers are at the other extreme and would like everything to be usable as a black box, not just hash functions. This is a constant source of tension.

To illustrate, if you look at the formal analysis of security protocols, for example BAN logic, you will see that symmetric encryption is treated as an "ideal block cipher." There is a subtle distinction here — BAN logic (and other protocol analysis techniques) don't claim to be security proofs; rather, they are techniques for finding flaws. Therefore it is not strictly true that the ideal cipher model is involved here. However, it is empirically true that most of the security analysis tends to be limited to the formal model, so the effect is the same.

We haven't even talked about practitioners yet. These guys typically don't even have a clue that crypto primitives are not intended to be black boxes, and I doubt this is ever going to change — decades of trying to beat this into their heads hasn't made a difference.

To see how bad the problem is, consider this security advisory relating to API signature forgeability. The bug is partly due to the length-extension attack in the Merkle-Damgard construction (which is something really really basic), and affects Flickr, DivShare, iContact, Mindmeister, Myxer, RememberTheMilk, Scribd, Vimeo, Voxel, Wizehhive and Zoomr. The authors note that this is not a complete list.

I do think practitioners deserve the lion's share of the blame for this sad state of affairs. On the other hand, perhaps crypto theorists need to rethink their position as well. Their line has been: "black-boxes are impossible to build; we're not even going to try." To which I say, since it is clear that your constructions are going to get (mis)used as black boxes anyway, why not at least try to make them as close to black boxes as possible?

The paper Merkle-Damgard Revisited is a great example of what I'm talking about. They study the security notion that "the arbitrary length hash function H must behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher." This kind of theoretical research has the potential to be hugely useful in practice.

Now let's get to your example of circuit evaluation. I beg to disagree with your reasoning. It's not like you would take a compiled binary and blindly turn it into a circuit. Rather, you'd apply circuit evaluation only to the underlying comparison function which is usually quite simple. Fairplay is an implementation of circuit evaluation. A colleague of mine who's worked with it tells me that it is surprisingly fast. While it is true that efficiency is a problem with circuit evaluation (and I do know of real-world instances where it was rejected for this reason), it is far from a showstopper.

The second reason I disagree with you is that if you think about some of the typical real-life scenarios in which you might conceivably want to carry out oblivious circuit evaluation — for example, when two companies are figuring out whether to merge — the computational costs involved are trivial compared to the overall human effort and budget.

So why then does no one use generic secure function evaluation in practice? Great question. This brings me to my second difference between theory and practice: trust actually exists in practice! Not everything needs to be done in the paranoid model. The set of problems that people actually want to solve using crypto is much, much smaller than what cryptographers imagine.

I know someone who started a company trying to sell secure multiparty computation services to enterprise clients. Guess what — no one wanted it. The way they approach these problems is to sign a contract specifying what you can and cannot do with the data, and that you will destroy the data after you're done using it for the intended purpose. Most of the time, this works just fine.

My final point of difference between theory and practice is about PKI. Crypto papers frequently stick a sentence somewhere saying "we assume a PKI." Unfortunately, digital certificates for end users (as opposed to websites or employees in a corporate context, where there is a natural hierarchy) never materialized. This classic paper describes the hilarity that ensues when you ask normal people to use PGP. I'm told that the software has improved a lot since then, but the underlying design and architectural issues and human limitations are not much different today.

I don't think cryptographers should be doing anything differently as a consequence of this lack of a real-world PKI, except to be aware of the fact that it limits the real-world applicability of cryptographic protocols. I threw it in because it's something I'm trying to fix.


What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion? What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion?

I read some papers on the dynamic transitive closure problem with both edge insertion and deletion. However, is there any better algorithms for that with only edge insertion?

An old paper by Italiano (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) gives a data structure that supports edge insertions in $O(n)$ amortized time and reachability queries in constant time. I'm not aware of better incremental algorithms.


Proving PSD-ness of matrices Diagonally dominant matrices are known to be positive semidefinite (PSD). What are some other families of (symmetric) matrices which are known to be PSD?
Given an arbitrary matrix A, the positivstellensatz or 'sum of squares' machinery can be used as a tool towards showing that A is PSD. What are other simpler methods/tools that can be used towards proving that a matrix is PSD?

To get the obvious out of the way first, to show that the $n\times n$ matrix $M$ is PSD, it is enough to show that it is the Gram matrix of $n$ vectors, i.e. $m_{ij} = \langle u_i, u_j\rangle$ where $u_1, \ldots, u_n \in \mathbb{R}^n$. (This is a "sum of squares" proof of positive semi-definiteness, because it shows that the bi-linear form $x^T M x$ can be written as a sum of squares of linear functions of $x$.  I am wondering if you meant something more sophisticated by "sum of squares".)

You get a useful class of PSD matrices from positive definite functions. A function $f: \mathbb{R}^d \to \mathbb{R}$ is positive definite if for all sequences $u_1, \ldots, u_n \in \mathbb{R}^d$, the $n\times n$ matrix $M$ defined by $m_{ij} = f(u_i - u_j)$ is PSD. It is not very hard to see that if $f$ is the Fourier transform of a finite measure, then $f$ is positive definite. I.e. it is sufficient that there is a finite Borel measure $\mu$  on $\mathbb{R}^d$ such that for all $x$
$$
f(x) = \int{e^{i\langle x, y\rangle} d\mu(y)}.
$$
A classical theorem of Bochner shows that this condition is necessary as well.

A special class of positive definite functions are the functions $f(x) = g(\|x\|_2)$, for which the matrix $M$ becomes $m_{ij} = g(\|u_i - u_j\|_2)$. Another classical result of Schoenberg shows that such an $f$ is positive definite if and only if there exists a finite Borel measure $\mu$ on $[0, \infty)$ so that for every $t \geq 0$
$$
g(t) = \int_{0}^\infty{e^{-t^2s}d\mu(s)}.
$$

The original motivation for Schoenberg's theorem was to determine what functions $g$ have the property that for any $u_1, \ldots, u_n \in \mathbb{R}^d$, the metric space with metric $d(u_i, u_j) = g(\|u_i - u_j\|_2)$ embeds isometrically into Euclidean space.

This blog post has a simple proof of Schoenberg's theorem and many links.


Are quasi-polynomial sized circuits for 3-SAT trivial? Suppose we consider 3-SAT with $v$ variables and $c$ clauses.  I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within an error that can be adjusted to an arbitrary amount.  However, there is a catch.

This method requires a set of precomputed values, after which it can solve an arbitrary 3-SAT problem fitting the above description.  The precomputed values are a set of size $O(v^{2+\log c})$ with each value taking $O(1)$ space.  The real problem is that each of these values could take $O(2^v)$ time to compute.  There is a chance that I can find a way to speed up these calculations.

I'm thinking that the bounds itself beats the upper bounds presented in this question (for small $c$).  So I'm wondering, is there a trivial way to reach the upper bounds I describe if we allow $O(v^{2+\log c})$ precomputations?

I'd like to continue this research and hopefully publish my results if everything works out, but first I'd like to know if there is a trivial way to do as well or better.

UPDATE

I have been studying related problems in addition to researching this algorithm.  I asked This question on StackExchange's IT Security site relating to password cracking and SAT, if you are interested.  At least one of the answers reflects this.

If what you are studying worked out, it definitely would not be trivial.

It would imply that 3SAT has (non-uniform) circuits of size $n^{O(\log n)}$. Then, every language in $NP$ (and the polynomial time hierarchy) would have quasi-polynomial (i.e., $n^{O(\log^c n)}$) size circuits.

Even if it took $2^{2^n}$ preprocessing time to produce a data structure of size only $2^{O(\log^2 n)}$ which could then correctly answer arbitrary 3SAT queries of size $n$ in $2^{O(\log^2 n)}$ randomized time with high probability, 3SAT would have quasi-polynomial size circuits, using the known translation of randomized algorithms to circuits. This would not improve the known algorithm time bounds because of the preprocessing, but it would still be extremely interesting as a non-uniform result.

What do you mean by "to within an error that can be adjusted to an arbitrary amount"? Is the algorithm randomized?


Deciding emptiness of intersection of regular languages in subquadratic time Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.

Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M_1,M_2$, but I was wondering if anything more efficient is known.

  Is there a $o(n^2)$ algorithm for deciding whether $L_1\cap L_2\neq \emptyset$? What is the fastest known algorithm?

Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.

We will prove a stronger theorem and then the simple answer will follow.

Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time, then any problem that's non-deterministically solvable using only n bits of memory is deterministically solvable in $poly(n)\cdot2^{(\delta n/2)}$ time.

Justification: Suppose that we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time.  Let a non-deterministic Turing machine M with a read only input tape and a read/write binary work tape be given.  Let an input string x of length n be given.  Suppose that M doesn't access more than n bits of memory on the binary work tape.

A computation of M on input x can be represented by a finite list of configurations.  Each configuration consists of a state, a position on the input tape, a position on the work tape, and up to n bits of memory that represent the work tape.

Now, consider that the work tape was split in half.  In other words, we have a left section of $\frac{n}{2}$ cells and a right section of $\frac{n}{2}$ cells.  Each configuration can be broken up into a left piece and a right piece.  The left piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the left section.  The right piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the right section.

Now, we build a DFA $D_1$ whose states are left pieces and a DFA $D_2$ whose states are right pieces.  The alphabet characters are instructions that say which state to go to, how the tape heads should move, and how the work tape's active cell should be manipulated.

The idea is that $D_1$ and $D_2$ read in a list of instructions corresponding to a computation of M on input x and together verify that it is valid and accepting.  Both $D_1$ and $D_2$ will always agree on where the tape heads are because that information is included in their input characters.  Therefore, we can have $D_1$ verify that the instruction is appropriate when the work tape position is in the left piece and $D_2$ verify when in the right piece.

In total, there are at most $poly(n) \cdot 2^{n/2}$ states for each DFA and at most $poly(n)$ distinct alphabet characters.

By the initial assumption, it follows that we can solve intersection non-emptiness for the two DFA's in $poly(n) \cdot 2^{(\delta n /2)}$ time.

You might find this helpful: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

CNF-SAT is solvable using $k+O(\log(n))$ bits of memory where k is the number of variables.  The preceding construction can be used to show that if we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time, then we can solve CNF-SAT in $poly(n) \cdot 2^{(\delta k/2)}$ time.  Therefore, the simple answer holds.

Comments, corrections, suggestions, and questions are welcomed.  :)


how to achieve a topological sort of an given sequence with minimum swaps For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum swaps

This problem is NP-complete. I will prove NP-hardness below

Source Problem

Colored Token Swapping on Cliques:

In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on two adjacent vertices switch places. We are given a number $k$ and asked whether a sequence of at most $k$ swaps can result in each vertex having a token of the target color for that vertex.

In the colored token swapping on cliques problem, the graph is a clique (and so a swap can occur between any two tokens). Also, we can assume without loss of generality that the target coloring is reasonable; that is, we assume that for each color, the number of tokens of that color equals the number of vertices with that color as the target color.

This problem is shown NP-hard in Lemma 18 of http://www.lamsade.dauphine.fr/~bonnet/publi/token-swapping.pdf.

Reduction

We are given a colored token swapping on cliques instance. In other words, we are given

$n$, the size of the clique. WLOG we can assume that the vertices of the clique are $1, 2, \ldots, n$.
A function $t$ assigning a target color to each vertex. Since there are at most $n$ colors, we will also number the colors $1, 2, \ldots, n$ (some colors may be left unused).
A function $s$ assigning a starting token color to each vertex.
A number $k$.

Since we can reorder the vertices without changing the problem, we can assume WLOG that in $t$, all vertices with the same target color are numerically contiguous (if vertices $i$ and $j$ have the same target color then every vertex numerically between them also has that same target color). Furthermore, assume WLOG that the color values are chosen so that $t$ is increasing (which we can do since we can permute color names without changing the problem).

Now we will construct an instance of your problem (given a set of constraints, a sequence, and a value $k$, can the sequence be reordered in at most $k$ swaps so that the result is a topological sort of the DAG implied by the constraints.)

The value of $k$ we will use for your problem will equal the value $k$ from the token swapping instance.

The sequence we will use for the instance of your problem is $[1, 2, \ldots, n]$.

Next, construct a permutation $p$ on $\{1, 2, \ldots, n\}$ such that $t(x) = s(p(x))$. Notice that this is just a matching between $\{1, \ldots, n\}$ and $\{1, \ldots, n\}$ such that $i$ can be matched to $j$ only if the target color at vertex $i$ matches the color of the token initially at $j$.

Define $C_x$ to equal $\{p(i)~|~t(i) = x\}= p(\{i~|~t(i) = x\}) = p(t^{-1}(x))$. Notice that $C_1, C_2, \ldots, C_n$ partition $\{1, \ldots, n\}$. We add constraints so that if $i < j$, all the elements of $C_i$ must come before all the elements of $C_j$. This set of constraints is satisfied if and only if the elements of $C_1$ in any order occur before the elements of $C_2$ in any order, which themselves occur before the elements of $C_3$ in any order, etc...

Correctness

There is a correspondence between a token swapping instance and the instance of your problem produced by this reduction. Assign each token a number from $1$ to $n$. In particular, assign the token initially at vertex $i$ (according to $s$) the value $i$.

Now the correspondence is that at all times, token $i$ is at vertex $j$ if and only if the value $i$ is at position $j$ of the sequence.

Certainly this correspondence holds at the beginning: each vertex $i$ contains token $i$ and the initial sequence is $[1, 2, \ldots, n]$, which if 1-indexed has value $i$ at position $i$.

Under this correspondence, a swap in the token swapping instance corresponds to a swap in the sequence. If we have tokens $x_1$ and $x_2$ at vertices $y_1$ and $y_2$, then swapping those two tokens results in $x_1$ at $y_2$ and $x_2$ at $y_1$. Similarly, if we have values $x_1$ and $x_2$ at positions $y_1$ and $y_2$ of the sequence, then swapping those two values results in $x_1$ at position $y_2$ and $x_2$ at position $y_1$. Clearly, if we correspond swaps in this way, the invariant given by the correspondence is maintained.

Finally, under this correspondence, a solved token swapping instance (each token at a vertex whose target color matches the token's color) corresponds to a sequence that satisfies all constraints. This is not obvious, so here's a proof:

A sequence satisfies all the constraints if and only if the elements are in the order of $C_1$ elements first, then $C_2$ elements, etc... But the number of $C_1$ elements is $|C_1| = |p(t^{-1}(1))| = |t^{-1}(1)|$, which is the number of vertices with target color $1$. Since $t$ is increasing, these are the lowest-indexed vertices. Notice that the elements of $C_1$ have the lowest-indexed positions. Thus, the indices of the positions of $C_1$ elements exactly correspond to the indices of vertices with target color $1$. Next, $|C_2| = |t^{-1}(2)|$, so the next $|C_2|$ lowest indices belong to the positions of elements of $C_2$ and to the vertices with target color $2$.

We can continue applying the same logic. This shows that a sequence satisfies all the constraints if and only if for each $i$, each element $x$ of $C_i$ has a position $y$ whose corresponding vertex has target color $i$. Under the correspondence, element $x$ has position $y$ if and only if token $x$ is at vertex $y$. This shows that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C_i$, the vertex containing token $x$ has target color $i$. Remember, however, that $C_i = p(t^{-1}(i))$ and therefore that $s(C_i) = s(p(t^{-1}(i)))$. Then by the definition of $p$ (that $t(x) = s(p(x))$), we have that $s(C_i) = t(t^{-1}(i) = i$. Thus, for every element $x$ of $C_i$, $s(x) = i$. Substituting this fact, we see that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C_i$, the vertex containing token $x$ has target color $s(x)$. But token $x$ has color $s(x)$, so a sequence satisfies all the constraints if and only if every token is at a vertex whose target color matches that token.

Thus we have shown that the correspondence holds: a swap corresponds to a swap, the initial situations correspond, and situations that match the "victory conditions" also correspond. Thus, since the target number of swaps $k$ is the same, the two instances are equivalent.


Storage system for large quantities of unique key value pairs optimized for insert Background

I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we have a need to store large quantities (~100s of millions) of small pieces of unique data. The data looks like this:

ID, 20 bytes (immutable)
Hits, unsigned 64bit int (mutable)
Value1, arbitrary length byte array (immutable)
Value2, arbitrary length byte array (immutable)

I currently have this data stored in two parts, a B+Tree index which maps the keys to unsigned 64bit integer values. Those values are file offsets in a data file which contains a structure like:

[Hits] UInt64
[LengthOfValue1] UInt32
[Value1DataBlob] N-bytes
[LengthOfValue2] UInt32
[Value2DataBlob] N-bytes

As new values are posted to this data store, the code performs a lookup in the B+Tree. If the tree contains the value, the hit count is incremented in the data file. If the value is not there, a new entry is appended to the end of the data file, it's start offset the inserted into the B+Tree.

Later, after this process is complete, we will enumerate the data performing more processing on it. What is important here though is that, if the key is already in our system, we are incrementing the hits on that key. This is essentially a cache, which is tracking hits on each piece of data as it's encountered.

What we are finding is that as the B+Tree grows larger, insert times become VERY slow. Lookup remains very fast (as you might expect).

Question

So -- Does anyone know of another way to do this, where unique checks are lightening fast, and so are inserts? We really don't care about later search performance, because once we go through the initial build of this dataset, all we will use it for is to enumerate the results. We're not going to be doing random searches against the dataset, in a long term manner.

Please do not suggest any kind of off-the-shelve database system. We've tried a lot of them, and this custom solution is faster than any of them, with a smaller data storage footprint.

We're just trying to improve our custom solution, and have hit a wall with our collective CS knowledge. Maybe this is the fastest way to do this, or maybe a different structure would perform better than the B+Tree for inserts at this scale?

B-trees and their various modified versions are the standard way to index arbitrary data while keeping insert times within a reasonable frame. Insertion happens in O(logn) time, which I believe cannot be improved, unless your key range is limited enough to make a bitmap usable.

That said, there a few things that can make B-trees and their variations faster:

Watch your keys. Non-random keys can cause pathological situations. You are using a hash, so key-dependent pathological situations are rather improbable.
Benchmark the application. Find out if the B-tree implementation achieves that O(logn) time for large datasets. Note: for large datasets. Only compare datasets for which the B-tree size significantly exceeds the size of your physical memory. Smaller datasets will have minimal disk seeks due to the OS cache and will seem lightning-fast. E.g. if you have 4GB of RAM, try comparing an 8GB, a 16GB, a 32GB and a 64GB index. If you do not see an O(logn) time curve, you may have a problem in your specific implementation.
Profile the application. Find out where the bottleneck is. Is it the CPU (not very probable)? Disk seeks (here's my money)? What part of the code produces the bottleneck?
Measure your B-tree index alone without the backing file. Does the application speed-up significantly without the backing file seeks? Would it make sense to store some data (e.g. the hit count) in the B-tree nodes themselves, to avoid the extra seeks? Storing some common data in the B-tree nodes should provide a major performance increase.
Use a shorter and faster intermediate hash. It does not have to be cryptography-level, just sufficiently random. I have used MurmurHash3 with pretty good results. Use that hash as the key in the B-tree, and an external mechanism (e.g. linked lists) to handle collisions. Using shorter keys will speed up your B-tree significantly, because each node can fit more ranges.
Optimise for less I/O and fewer disk seeks. In your case it's quite probable that the performance killer lies in your disk. Try using larger B-tree nodes.


Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we weaken our notion of security from "impossible" to "it would take exponentially long to break" we get some other results. In How to Fool an Unbounded Adversary with a Short Key Russel and Wang show how to encrypt high entropy messages using a small symmetric key such that we can safely conclude that an adversary would have to perform an exponential number of steps to decide anything about our message. This is a problem because most of the messages I send are quite predictable. This caveat is always mentioned when I see entropic-security mentioned. It seems to me that there exists a way to encrypt messages of low entropy using this method, however.

Solution:
  Alice wants to send $M \in \{0, 1\}^n$ to Bob. Alice and Bob have agreed on $K_\mbox{rw} \in \{0, 1\}^{\ell + 128}$ as a key to be used in Russel ang Wang's entropically secure encryption algorithm. Alice generates a one-time pad $K \in \{0, 1\}^n$ by sampling from a uniform distribution. Alice encrypts $K$ using $K_\mbox{rw}$ and sends the results Bob. Bob now knows $K$. Alice now encrypts $M$ using $K$ and sends it to bob. Bob uses $K$ to decrypt the message and now Bob knows $M$.

$K$ would have maximal entropy and thus would meet Russel and Wang's requirement. The second message gives no information about $K$, $M$, or $K_rw$ and thus can't be used to attack the original message (At least that's how I understand it).

The only downside I can see to it is that it requires sending twice the amount of information you'd otherwise have to send but for many applications that's quite acceptable. This would seem to imply that Russel and Wang's method is far more widely applicable. You likely wouldn't use this method for video streaming but you might very well use it for sending information to your bank or you might use it for browsing the web.

The lack of mention of this a) In their paper, b) on Wikipedia and c) in a couple other papers that cite Russel and Wang that I've skimmed leaves me thinking that I've overlooked something. Is there a security issue that I've overlooked? Is this method or something equivalent/better mentioned somewhere else? Are there any other drawbacks that I'm not seeing? Even if I've done something wrong here then is something like this still possible? Specifically, can we use Russel and Wang's algorithm to encrypt low entropy messages by sending some extra information drawn from a high entropy source (as I believe my "solution" does)?

Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low entropy (there are only two possibilities for $K$). If the eavesdropper stores the first message (which was an encryption of $K$), then she can use it to figure out which of the two candidate values for $K$ is plausible (i.e. is consistent with some short key $K_{RW}$) once she sees the second message.

This problem is essentially unavoidable: taken together, the two messages form an encryption of $M$ (the fact that they were sent separately doesn't affect a passive eavesdropper who sees both). It is easy to show that, using only a short key, one cannot achieve even Russell and Wang's relaxed notion of security in a setting where $M$ has low entropy.

For a lower bound on the key length (as well as further constructions), see Dodis and Smith: https://eprint.iacr.org/2004/219
[Disclaimer: I am an author.]


`f_equal` isn't doing anything I'm trying to do the following thing: take a set (here, nat, for the sake of simplicity), define a subset of "valid" values (here, even numbers), and then prove that two valid values with the same value are the same.

My problem is that my valid values are represented by records. And when I try to prove what I want, I try to use the f_equal tactic on that record and it does nothing. I imagine this is because both parts of the record are dependent, but I really don't know (I'm new to these).

Here is my code. Define a boolean predicate for valid values:

Fixpoint valid (n: nat) : bool :=
  match n with
    | 0 => true
    | 1 => false
    | S (S p) => valid p
  end
.

Define the type for valid values using the predicate and records:

Record valid_nat : Type :=
  { VN_value : nat ;
    VN_prop  : valid VN_value = true }
.

Prove that when the values are the same, the records are the same. I know this implies proof irrelevance, but that's not my main problem yet:

Theorem valid_nat_unique:
  forall (m n: valid_nat), VN_value m = VN_value n -> m = n
.
Proof.
  intros m n H.
  destruct m as [m_value m_prop].
  destruct n as [n_value n_prop].
  simpl in H.
  f_equal.    (* does nothing *)

Here is the goal before and after the f_equal tactic:

m_value : nat
m_prop : valid m_value = true
n_value : nat
n_prop : valid n_value = true
H : m_value = n_value
============================
 {| VN_value := m_value; VN_prop := m_prop |} =
 {| VN_value := n_value; VN_prop := n_prop |}

I was expecting to get m_value = n_value /\ m_prop = n_prop (then hypothesis H and proof irrelevance should be enough to finish. And now I'm stuck.

My Coq version is: The Coq Proof Assistant, version 8.5 (February 2016)

Any help would be highly appreciated. Thank you by advance.

The f_equal tactic does not do anything because what you are trying to prove is not true. You assumed that the first components (VN_value) of m and n are equal, but what about the second components (VN_prop), how do you intend to prove they are equal?

Also note that we cannot decompose the equation

{| VN_value := m_value; VN_prop := m_prop |} =
 {| VN_value := n_value; VN_prop := n_prop |}

into

m_value = n_value

and

m_prop = n_prop

because the second equation is not well typed: the left-hand side has type valid m_value = true and the right-hand side valid n_value = true. Instead, we need to transport m_prop from the type valid m = true to the type valid n = true.

So, you need transport and you need an extra assumption. Here is how you can do it:

Fixpoint valid (n: nat) : bool :=
  match n with
    | 0 => true
    | 1 => false
    | S (S p) => valid p
  end.

Record valid_nat : Type :=
  { VN_value : nat ;
    VN_prop  : valid VN_value = true }.

Definition transport {A : Type} (B : A -> Type) {a b : A}: a = b -> B a -> B b.
Proof.
  intros [] ?; assumption.
Defined.

Lemma valid_nat_unique (m n : valid_nat) (p : VN_value m = VN_value n):
  transport (fun k => valid k = true) p (VN_prop m) = VN_prop n ->
  m = n.
Proof.
  destruct m; destruct n.
  simpl in * |- *.
  destruct p.
  intros [].
  reflexivity.
Qed.


Will core decomposition get a maximal clique? I have read David Eppstein's paper about maximal clique enumeration by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree iteratively.

And I pick up with a theorem:
If we remove the vertex with the smallest degree iteratively until the smallest degree is |S|-1, where S is the remaining graph, is S a maximal clique?

example graph:

In this graph, we will delete vertex a whose degree is the smallest one ( deg(a)=2 ), and then delete vertex f. And we will get the 4-maximal clique {b,c,d,e}.

I cannot prove this theorem but I also can't find a counterexample. Is there anyone can help me figure out this theorem right or wrong?

PS:

Clique is a subgraph whose every vertex is adjacent to each other. And maximal clique is a clique that cannot be contained by another clique, it means the maximal one cannot be extended.

I can prove the remaining graph that above algorithm produced is not a maximum clique which is the largest one in the graph, but I can't prove this graph whether is a maximal clique.

Also notice that when the vertex v is removed from the graph, all it's neighbors' degree will decrease one.

No. The illustration shows a graph (the graph of a cube with one corner truncated) and a valid removal sequence such that the vertices left at the point when the minimum degree equals $|S|-1$ (the two red vertices) do not form a maximal clique.

In this example, some other valid removal orderings could still produce a maximal clique. Probably there are more elaborate versions of this example that force the remaining clique to be non-maximal for all valid removal orderings.


The significance of NP-Hard Problems in Cryptography I didn't refer any literature but thought this was ideal to get views from people here..

Assuming that P=NP is proved would cryptography(only provable security) be impossible? Since the adversary can break any scheme in polynomial time.

Aren't the NP-hard problems enough to save the day? I've heard of crypto-systems based on "subset problems". Since P=NP would not affect the nature of NP-hard problems.

It would also be great if can suggest any interesting articles regarding this..

Thanks!

P.S: Please feel free to edit if you find any naive statements in the question.

Hardness of NP-complete problems is not sufficient for cryptography.  Even if NP-complete problems are hard in the worst-case (P≠NP ), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106


Reference to lower bound on separator in a grid? It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane, and remove all its vertices). It is also not too hard (but definitely not immediate) to verify that any separator has to be of size $\Omega(n^{d-1})$. Anybody knows a refenence to this?

Looks like the book "Graph separators, with applications" by Arnold Rosenberg and Lenwood Heath answers your question (see section 4.3.4.), but it could happen that I misunderstood their notation (please, let me know). Anyway, this book is a very comprehensive reference on separators.

EDIT. Here is a download link on Springer: http://www.springerlink.com/content/978-0-306-46464-5


Algorithm to sort pairs of numbers I already asked this question on stackoverflow, but maybe it is better suited for this site.

The problem is:

I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped at any point.  Sometimes there is no solution, so I need to throw an exception then.

Example:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5
6 5     <-- swapped
8 3     <-- swapped

^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result.
or

in pairs:
1 5
6 9

out:
not possible

Thanks

edit:

Tom Sirgedas on SO proposed the best solution. It is really easy to implement and works in O(log(n) * n). Thank you all for the answers and interest. I really enjoyed mjqxxxx analysis.

Say that two pairs $p_1=(a_1,b_1)$ and $p_2=(a_2,b_2)$ are no-swap compatible if they can be placed in either order in the sorted list without swapping either one.  This is true if either $(a_1 \le a_2 \wedge b_1 \ge b_2)$ or $(a_2 \le a_1 \wedge b_2 \ge b_1)$.  Note that $p_1$ and $p_2$ are no-swap compatible if and only if they are two-swap compatible (since the partial order defined satisfies $p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$, where $*$ denotes the swap operation).  Finally, $p_1$ and $p_2$ are one-swap compatible if they can be placed in either order in the sorted list with exactly one of them swapped.  This is true if $p_1^{*}$ and $p_2$ are no-swap compatible.  In the remaining cases, $p_1$ and $p_2$ are simply incompatible: they cannot satisfy the order condition regardless of their swap state.

The problem can now be solved as follows.  Test every pair of pairs.  If any pair is incompatible, there is no solution, and we can throw an exception.  Otherwise, consider the graph with nodes corresponding to the original pairs, and edges between those pairs of nodes that are not one-swap compatible.  Each such pair of nodes must have the same swap state in any properly sorted list, and therefore all nodes in each connected component of the graph must have the same swap state.  We need to determine if these component-wide swap states can be consistently assigned.  Test all pairs of nodes within each connected component.  If any pair is not no-swap compatible, there is no solution, and we can throw an exception.  Now test all pairs of connected components (i.e., for components $C_1$ and $C_2$, test all pairs of nodes $p_1 \in C_1$ and $p_2 \in C_2$).  We know that each pair of components is at least one-swap compatible, but some pairs may also be no-swap compatible (because each pair of nodes not connected by an edge is at least one-swap compatible, and may also be no-swap compatible).  Consider a reduced graph with nodes corresponding to the connected components, and an edge between two nodes if the corresponding components are not no-swap compatible.  There is a solution to the original problem if and only if this graph is $2$-colorable.  If there is no $2$-coloring, there is no solution, and we can throw an exception.  If there is one, then swap all nodes in all components of a single color.  We are now guaranteed that any two nodes are no-swap compatible, and so we can properly sort the list of pairs using the defined partial order.

Each step in the algorithm, and hence the entire algorithm, can be performed in $O(N^2)$ time.

UPDATE: A much more elegant construction is the following.  If a pair of pairs is not no-swap compatible, connect the corresponding nodes with an edge (forcing them to be different colors in any 2-coloring).  If a pair of pairs is not one-swap compatible, connect the corresponding nodes with a chain of length 2 (forcing them to be the same color in any 2-coloring).  There is a solution if and only if the resulting graph is 2-colorable.  To construct a solution from a blue-red coloring of the graph, swap just those pairs whose corresponding nodes are blue, then sort the resulting list.


A least sized partition of a set under a distance metric What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows:

Input:

A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are of some type $T$.
A distance metric $D:T\rightarrow [0, \infty)$.
A radius $r:[0, \infty)$

Output: A partition $S_1,\ldots,S_m$ of $S$ such that

$S_i\cap S_j=\emptyset, i\neq j$ and
$S=\cup_{i=1}^m S_i$ and
$D(s,t) \leq r$, $s,t \in S_i$ and
There is no other partition with the same properties of size $m^{\prime} < m$.

NOTE: I am saying "a partition" not "the partition", because there may be multiple partitions of least size for the same set of points.  For example consider $2 n$ points on a large circle where the points are spaced such that each pair of points is distance $r$ apart.  In this case there are $2 n-1$ distinct least-sized partitions of minimum size $n$.

NOTE: The following algorithm will produce a partition with desired properties except that it is not guaranteed to be least size:

$i=1$
While $|S| > 0$:

Choose $e \in S$ and set $S:=S-\{e\}$
$S_i=\{x\in S: D(e,x) \leq r\}$
Set $S:=S \setminus S_i$
Set $i:=i+1$

NOTE: It has been suggested that this is an NP-hard problem, but the above partial solution is $O(n^2)$.

NOTE: This problem is an abstraction of this geographic problem.

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

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

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

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


How many more colours do you need if you add to $G$ a maximum matching from $G^c$? The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$.
How large can the difference between the chromatic number of $G$ and the chromatic number of $G+M$ be?
That is, can we say anything about $\max_M \chi(G+M)-\chi(G)$? (at least some bounds).
I would like to keep the problem in the general setting. If it matters, I am more interested in the special case when $G$ is a regular graph.
Thank you.

One always has $\chi(G+M)\leq 2\chi(G)$, and this bound does not seem improvable in general. To see the bound itself, note that the only edges of the matching $M$ that can possibly ruin an optimal coloring of $G$ are those between two vertices of the same color class; in particular, we can color $G+M$ by simply creating two new colors for every original color and placing the two nodes on any such violating edge with distinct colors.
To see that this is tight, for any $k$, consider a $k$-partite complete graph with an even number of nodes in each part. It is easy to see that the original graph is $k$-colorable and that adding any perfect matching (which only can have edges within each part) will increase the clique number to $2k$, and so the chromatic number is at least $2k$.


What is the correct name for the space of genotypes and fitness? I'm looking for a formal definition of the space that consists of the dimensions gene 1-N and the fitness.

In literature there is often the search space mentioned, but it only contains all genes. If I extend the search space by the fitness dimension, how can I call this space?

In the context of evolution and evolutionary algorithms it's called a fitness landscape.  In other areas such as statistical physics it's called an energy landscape.

If you have a continuous landscape (in evolution you typically don't) things are fairly straightforward.  From Wikipedia:

  In mathematical terms, an energy landscape can be defined as a pair $(X, f)$ consisting of a topological space $X$ representing the physical states or parameters of a system together with a continuous function $f: X → \mathbb{R}$ representing the energies associated to these states or parameters such that the image of $f$ represents a hypersurface in $\mathbb{R}^n$."

In discrete landscapes things are more complicated since we need to specify which states neighbour each other, essentially giving us a graph underlying the set of solutions.  What you end up with is not as clean as you'd like.  It's a triple $(X,N, f)$, where $X$ is the set of solutions (i.e., possible genotypes), $N:X\to 2^X$ is a neighbourhood function, and $f:X\to\mathbb{R}$ is the fitness function.

For a treatment of these discrete fitness landscapes that should satisfy you with regard to mathematical rigour I would direct you to this survey paper by Reidys and Stadler.