Have fixed parameter integer program algorithms ever been implemented for research use? Have any fixed parameter integer programming algorithms described in  Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?

The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.

Lovasz and Scarf proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was reported in 1993 by Cook, Rutherford, Scarf, and Shallcross (this paper is available in ResearchGate).

One of the key steps in Lenstra's algorithm uses basis reduction (BR) to locate "thin directions" for the polytope. Branching on such a direction produces only a small (i.e., polynomial number) of subproblems. In a series of papers, Aardal and coauthors essentially applied this BR step to help solve (using standard MIP solvers) otherwise hard-to-solve IP instances (see, e.g., this paper and this paper). We (also see arXiv) have studied a similar, but arguably simpler and more general, approach (full disclosure: self-citation here!) to solve IP feasibility problems: apply BR to the constraint matrix $A$ of the IP feasibility problem (of the form $\{\mathbf{l} \leq A \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}$), and use standard techniques to solve the resulting reformulated IP feasibility problem. The BR could be performed using standard software tools such as NTL.


Why did Kolmogorov publish Karatsuba's algorithm? Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy of Sciences 145: 293–294.

According to Karatsuba (1995, "The complexity of computations", Proc. Steklov Institute
of Mathematics 211: 169–183), this paper was actually written by Kolmogorov (and possibly Ofman) without Karatsuba's knowledge. By modern standards this seems a strange and grave breach of ethics.

Why would Kolmogorov have done this? What did he gain?

This paper, in Russian,

  Gricenko, S. A., Karatsuba, E. A., Korolyov, M. A., Rezvyakova, I. S.,
  Tolev, D. I., & Changa, M. E. (2012). Scientific contributions of A. A.
  Karatsuba / Научные достижения Анатолия Алексеевича Карацубы.
  Современные проблемы математики, 16(0), 7-30.

states the following (items 1—3).

Karatsuba presented his algorithm at a seminar led by Kolmogorov.
Kolmogorov prepared an article that had two results of his students, Karatsuba and Ofman. One of the results was Karatsuba's algorithm, the other was an unrelated result of Ofman.
The article clearly attributed the results. It stated that the multiplication algorithm is due to Karatsuba and the other result is due to Ofman.

We can only guess why Kolmogorov did that. I am afraid that the only person who could answer the question why Kolmogorov published the paper without Karatsuba's permission or knowledge was Kolmogorov himself.  Perhaps he thought that it was a good way to publish the results of his students. Note that the article correctly attributed all results. The article of Karatsuba and Ofman was published in the Proceedings of the USSR Academy of Sciences; it is my understanding that it had to be submitted/presented by a member of the USSR Academy of Sciences.

Here is the relevant quote from the paper of Gricenko et al (in Russian):

  Этот результат был доложен Анатолием Карацубой на семинаре А. Н.
  Колмогорова в МГУ в 1960 г., после чего семинар был Колмогоровым
  закрыт. Первая статья с описанием этого метода [2] была подготовлена
  самим Колмогоровым. Там он представил два разных и не связанных друг с
  другом результата двух своих учеников, и хотя в статье Колмогоров
  четко отметил, что одна теорема (не связанная с быстрым умножени- ем)
  принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым
  умножением) принадлежит А. Карацубе, эта публикация под именами двух
  авторов надолго сбила с толку читателей, которые полагали, что оба
  автора внесли вклад в создание быстрого умножения, и даже называли
  этот метод двумя именами.

English translation:

  This result was presented by Anatoly Karatsuba in A. N. Kolmogorov's seminar at the Moscow State University in 1960, after which the seminar was closed by Kolmogorov. The first article with the description of this algorithm [2] was prepared by Kolmogorov himself.  In it he presented two different results from his two students that were unrelated to each other, and although Kolmogorov clearly noted in the article that one theorem (unrelated to fast multiplication) belonged to Y. Ofman, and the other theorem (with the first fast multiplication algorithm in history) belonged to A. Karatsuba, this publication on behalf of the two authors for a long time confused readers, who supposed that both authors had stake in the invention of fast multiplication, and even referred to the algorithm using both names.


Why economists should care about computational complexity When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and chapter 11 of Scott Aaronson's essay. These posts are accessible for computer scientists, but do not use the language of economists and are not published in venues typically read by them. Are there good arguments for the importance of the complexity of equilibiria, etc. targeted at economists? Is there a good historic overview of how economists have responded to pressure from computer scientists?
It could be argued that neoclassical economics is simply closed off and hence such papers can't exist, but there are slightly heterodox fields such as evolutionary economics and complexity (in the SFI sense) economics that justify themselves in language familiar to economists. These fields also make similar critiques as the computational complexity approach (such as moving away from assumptions of equilibria), but don't justify them as rigorously as CS does.

Related questions

Algorithmic lens in the social sciences

Computational complexity in quantitative finance

I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address.

The second is more specific: Now that computer scientists know that many problems in game theory are hard, how do we convince economists that these are important issues with or objections to their work? This may not be what you had in mind, but it seems to be an interpretation of what you wrote, so I want to address it because I think it's a bit problematic and I think there are reasons not to write an essay arguing this point (which might explain any lack of answers).

First, micro-economists are often theorists and they may be more interested in understanding the problem in their model than in ours. There is no a priori reason one approach is better than the other. As an analogy, many theoretical computer scientists are happy to design algorithms that work over real numbers even though this may require undecidable operations. Similarly, to an economist, complexity may be a detail that clouds one's understanding of what's important in their model rather than a key consideration. This seems more a matter of preference or philosophy than right or wrong.

Second, it's not clear that computer science is yet in a position to argue convincingly that our models fit the real world better than theirs, until we have experimental data to back this up. (After all, it might be for example that markets often find equilibria quickly in practice, so hardness of computing is irrelevant to real-world applications.) Without data, the disagreement is philosophical and it's hard to claim there is a right or wrong side. I don't know that we have enough data yet to make any specific claims.

Third, I think many economists to whom these issues are relevant have been taking notice. In areas like matching, for example (subject of last year's Nobel!), a computational complexity and algorithmic approach is important as they attempt to implement solutions at large scale. So if an economist claims that complexity isn't relevant to her interests, she might be right; but there are others who do take notice.

So in sum, while it seems like a worthwhile goal to help make economists aware of the results regarding complexity in economics (especially as some do take interest), I am not sure that we are in a position to argue that they should take much notice or change their approach; and I think a strong scientific argument would require more data rather than just philosophy.


Background Required to understand Quantum Monte Carlo techniques? I'm trying to decide whether or not to do a project for a professor.

The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project) about Quantum Monte Carlo. The application they have in mind is calculating the energy of a quantum system and comparing QMC to a different method of doing such calculations.

What sort of background knowledge is required to get a grip on QMC (enough to be able to understand the significance of foundational and some more recent papers in the field). The survey paper would be due sometime by the end of school.

Don't skip anything I really need to know - assume I only an average upper-level undergrad CS major's knowledge of physics and computer science.

Reference suggestions are very welcome.

Do you have a tame physicist (preferably one who is familiar with Quantum Monte Carlo techniques) that you can talk to?  I don't think it's actually all that hard, but if you try to understand it by reading about it, I strongly suspect that you'll find the books all assume you understand some moderately advanced quantum mechanics/quantum field theory (time-ordered integrals, some non-obvious properties of operators) which they don't explain, and if you don't understand these, you'll find their explanations completely incomprehensible.

I also see from Google that there are lots of different variations on the Quantum Monte Carlo method, some of which will be harder than others, and deciding which one to use for a particular problem is very likely a skilled art.


Combining subset sum and subset product problems The subset sum problem and subset product problem are NP-complete.
Is the following problem polynomial-time solvable: given a set of positive integers, find a subset whose sum is $S$ and whose product is $T$.

It is still NP-complete. Here is a very sketchy reduction from subset sum. The goal of the whole reduction will be to make $T$ unimportant.
If the inputs for subset sum are $a_i$, then add $a_i$ and $2^Na_i$ to our inputs, where $N$ is large, but still $poly(n)$.
Set $S$ to be $2^N$ times the original subset sum plus $2^N-1$.
Set $T$ to be the product of the $a_i$'s multiplied by a sufficiently big power of $2$, to be determined later.
The idea is that if the number with index $i$ was not picked, then we can pick $a_i$, while if it was picked, we can pick $2^Na_i$.
Finally, add a lot of each small power of $2$ to our input to be able to make the desired sum and product.
Notice that this gives us enough liberty to get $S$ and $T$.


Confusions about the technique for verifying implementations of linearizable objects in [Herlihy and Wing, 1990] In Section 4.3.2 entitled "Proof Method" of

Herlihy and Wing, "Linearizability: A Correctness Condition for Concurrent Objects", 1990

the authors describe the technique for
verifying implementations of linearizable objects as follows:

  Assume that the implementation of $r$ is correct,
  hence $\text{H} \mid {\small \text{REP}}$ is linearizable
  for all $\text{H}$ in the implementation.
  Our verification technique focuses on showing the following property
  (denoted $\mathcal{P}$ for later reference, by myself):
  $$\text{For all } r \in \text{Lin}(\text{H}\mid{\small\text{REP}}), \text{I}(r)
\text{ holds and } \text{A}(r) \subseteq
\text{Lin}(\text{H}\mid{\small\text{ABS}}).$$
  This condition implies that $\text{Lin}(\text{H} \mid {\small \text{ABS}})$
  is nonempty, hence that $\text{H} \mid {\small \text{ABS}}$ is linearizable.

I don't understand:

  Why is it sufficient to show that $\text{A}(r) \subseteq
\text{Lin}(\text{H}\mid{\small\text{ABS}})$ (besides the "invariant" $\text{I}(r)$ property)
  holds for the verification purpose?

Specifically, to show the property $\mathcal{P}$,
are we showing that there exists an $\text{I}(r)$ and an $\text{A}(r)$
such that $\mathcal{P}$ holds?
If so, why cannot we just set $\text{I}(r) = \top$ and $\text{A}(I) = \emptyset$
which trivially satisfy $\mathcal{P}$?
If not, what is the formal definition of "verification" here?

About examples in this paper:

Section 4.3.3: in the queue example,
$\text{I}(r)$ and $\text{A}(I)$ are far from trivial.
What are the specifications that prevent us from choosing
$\text{A}(I) = \emptyset$ in this example?
Section 4.2: to motivate their definitions of
$\text{I}(r)$ and $\text{A}(r)$,
the authors also use the queue example.
At the top of page 477, it reads:

  Let $r$ be the rep value after this history.
  Because $\beta$'s Enq operation has returned,
  $\text{A}(r)$ must reflect $\beta$'s Enq.
  Because $\alpha$'s Enq operation is still in progress,
  $\text{A}(r)$ may or may not reflect $\alpha$'s Enq,
  depending on how $\text{A}$ is defined.

(Note that I have used $\alpha, \beta$ instead of
$A, B$ to denote the processes, to avoid symbol abuses.)
According to this argument,
I suppose that there are some constraints on the definition of $\text{A}$.
But what are they?

Herlihy and Wing write on p. 477:

  In conclusion, the rep invariant $\mathbf{I}$ must be continually satisfied and the abstraction function continually defined, not only between abstract operations, but also between rep operations implementing abstract operations. The abstraction function maps each rep value to a nonempty set of abstract values:
  $$
\mathbf{A}: \mathrm{REP} \to 2^{\mathrm{ABS}}
$$

I am tempted to read into this that even when an abstract operation is implemented by a sequence of multiple rep operations, the rep invariant has to hold after each of those rep operations, and when it holds, then the rep value must have at least one abstract counterpart.

Many people have addressed some of the challenges posed in this paper. One of the more interesting and recent developments is  R Jagadeesan and J Riely's Quantitative Quiescent Consistency [http://arxiv.org/abs/1402.4043].


A decomposition theorem for maximum weight matchings The following paper presents a way to solve the maximum weight matching of a bipartite graph by reducing it to computing maximum weight matchings of two lighter bipartite graphs:

M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. A decomposition theorem
for maximum weight bipartite matchings with applications to evolutionary
trees. In Proc. of the 7th Annual European Symposium on Algorithms (ESA’99),
pages 438–449, 1999.

Is there a generalization of the result which also holds for non-bipartite weighted graphs?

Thank you.

Are you actually looking for a polynomial time algorithm solving maximum weight matching for general graphs, or a specific way to solve it using a kind of decomposition?

In the former case, the following paper gives an $\mathcal{O}\big(n(m + \log n)\big)$ exact algorithm:
H.N.Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors witk Linking. SODA'90 (1990)
And for a $(2/3 - \epsilon)$-approximation algorithm running in $\mathcal{O}(m \log 1/\epsilon)$:
S.Pettie, P.Sanders. A Simpler Linear $2/3 - \epsilon$ Approximation Algorithm for Maximum Weight Matching. Information Processing Letters, vol.91 (2004)


(concise?) definition of thread safety Wikipedia has the following definition:

  Thread safety is a computer programming concept applicable in the
  context of multi-threaded programs. A piece of code is thread-safe if
  it only manipulates shared data structures in a manner that guarantees
  safe execution by multiple threads at the same time. There are various strategies for making thread-safe data structures.[1][2] ... and so on ( http://en.wikipedia.org/wiki/Thread-safety )

So, code is thread-safe if it operates in thread-safe manner! Hmm...

However, precise definition seems not to be simple. A naive approach is:

Thread-safety means that program's observable behavior does not depend on eligible thread scheduling order.

Still, it may be incorrect definition. Say, threads may log  messages into log file, and reodering of log messages may be OK. So program observable behavior may vary, but the program may be considered thread-safe.

Probably, we need to specify allowed types of different program observable behaviors while being thread-safe.

Yet another complication: there may be  thread-safe (or thread-unsafe) code, not the whole program. (One may think about compositional properties of (non-)thread-safe code and so on)

So, the questions are: how to precisely define thread safety? Is there concise definition? What work was done to define thread safety?

UPDATE: Thanks for all the high quality links you supplied. The links contain answers to additional question(s) that I planned to ask. Feel free to add new (appropriate) links even though I have chosen my prefered answer.

There has been a lot of work on this, usually under the heading of "memory models".  See, for example:

The Java memory model
Foundations of the C++ Concurrency Memory Model by Boehm and Adve
Lots of recent work by Peter Sewell's group on C++ concurrency and hardware memory models


What is the state of the art in cache algorithm theory? I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a given memory segment and the speed of accessing it.

The familiar example is a program deciding when to read from / write to the processor cache, RAM and hard drive (via virtual memory).

I am particularly interested in the special case where the amount of data (including the program itself) that needs to be loaded significantly exceeds the capacity of the fastest storage available (i.e. the trivial solution of "just load up everything" is inapplicable).

I found that a Wikipedia page describing some common cache algorithms, which is almost what I want. Unfortunately, these are a bit low-level:

Many, such as LRU or MRU only make sense if you have subroutines that get accessed many times. If I have a program with a large number of subroutines, some of which are never accessed in a given run, and some of them are accessed one or two times, this strategy will never work because it can't build up enough data on what is commonly used and what is not.
Others, such as CLOCK, seem to deal with the peculiarities of implementation, rather than actually attacking the root of the problem.
I know there is a strategy where one first profiles a program during a test run, then provides the profile for the operating system to optimize accordingly. However, we must still solve the problem of providing a truly representative "example usage" while building the profile.

What I really want to learn about is this:When we abstract away all the technicalities of hardware and software, and speak in a purely theoretical context, is it possible to somehow analyze the structure of an algorithm, to work out an effective cache strategy for it based on high-level comprehension of what the algorithm is doing?

I don't know about a method for analyzing an arbitrary given algorithm to come up with a cache policy in general (this sounds quite hard), but this is essentially what's been done (optimally, in an asymptotic sense) on a case-by-case basis for most known cache-oblivious algorithms, by analyzing their divide-and-conquer structure. Cache-oblivious algorithms are known for FFT, matrix multiplication, sorting, and a few others. See the Wikipedia page and references therein.


Searching for the original definition of online algorithms I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the one that was the original reference.

Note: English is my second language.

Thanks.

With Garmow's comment I was able to find the first two references which also called on-line algorithms as on-line:

Johnson, David S. "Fast algorithms for bin packing." Journal of Computer and System Sciences 8.3 (1974): 272-314.

and

Johnson, David S. Near-optimal bin packing algorithms. Diss. Massachusetts Institute of Technology, 1973.


Assignment of values for a set Consider the following problem:

Input: the vertices of two $n$ dimensional axis-parallel cubes:
$\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and
$\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$.

Let

$P = \{ \vec{p} \in \times_{i=1}^{n} [a_i,b_i] : ||\vec{p}||_1 = 1\}$,
$X = \{ \vec{x} \in \times_{i=1}^{n} [l_i,u_i] : ||\vec{x}||_1 = 1\}$,
$W = \{ \vec{w} \in [0,1]^n : ||\vec{w}||_1 = 1\}$,

where $||\vec{v}||_1 = \sum_{i=1}^n v_i$.

Query: for all $\vec{p} \in P$
there are $\vec{x} \in X$ and $\vec{w} \in W$ such that
$x_iw_i=p_i$ for all $i = 1, \ldots, n$?

What is the complexity of this problem?

The problem as stated now is solvable in linear time.

To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\sum_{i=1}^np_i=\sum_{i=1}^nx_iw_i$, but on the other hand because of $1 = \sum_{i=1}^nx_i$ and $1 = \sum_{i=1}^nw_i$ we have $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$, so that $x_iw_j$ must be $0$ for all $i\neq j$ (using also that all the $x_i,w_i$ are nonnegative).

This implies that there is some index $k$ with $x_k=w_k=1$ and $x_j=w_j=0$ for all other $j$: indeed, since $1 = \sum_{i=1}^nx_i$, some $x_k$ must be nonzero. Then $x_kw_j=0$ means $w_j=0$ for all $j\neq k$, and because $1 = \sum_{i=1}^nw_i$, we have $w_k=1$. Analogously we get $x_j=0$ for $j\neq k$ and $x_k=1$. As a consequence, $p_k=1$ and $p_j=0$ for $j\neq k$.

The decision problem is whether this is true for all $p\in P$. Since $P$ is convex, this is only possible if $P$ only consists of one of these unit vectors, i.e. for some $k$ we have $a_k=b_k=1$ and $a_j=b_j=0$ for all other $j$; additionally, $X$ must also contain this vector, i.e. we need to have $u_k=1$ and $l_j=0$ for $j\neq k$.

EDIT: What we have are the following results:

If $p,x,w\in[0,1]^n$ with $\sum_ip_i=\sum_ix_i=\sum_iw_i=1$ and $p_i=x_iw_i$ for all $i$, then $p=x=w=e_k$ for some $k$, where $e_k$ is the unit vector given by $(e_k)_k=1$ and $(e_k)_j=0$ for all $j\neq k$.
Adding the constraints $a_i\le p_i\le b_i$ and $l_i\le x_i\le u_i$ further restricts the set of solutions to those $e_k$ which are both in $P$ and in $X$, i.e. such that $b_k=u_k=1$ and $a_j=l_j=0$ for $j\neq k$.
The decision problem given in the question is whether such $x,w$ exist for all $p\in P$; the answer to this is "yes" if and only if $P$ is a singleton set $\{e_k\}$ for some $k$, i.e. $a_k=b_k=1$ and $a_j=b_j=0$ for $j\neq k$, and additionally this $e_k$ is in $X$, i.e. $u_k=1$ and $l_j=0$ for $j\neq k$. This can be checked in linear time.


What is the most general structure on which matrix product verification can be done in $O(n^2)$ time? In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the problem of checking whether AB = C has a randomized $O(n^2)$ time algorithm.

This is interesting because the fastest known algorithm for multiplying matrices is slower than this, so checking if AB = C is faster than computing C.

I want to know what is the most general algebraic structure over which matrix product verification still has an $O(n^2)$ time (randomized) algorithm. Since the original algorithm works over all fields, I guess it works over all integral domains too.

The best answer I could find to this question was in Subcubic Equivalences Between Path, Matrix, and Triangle Problems, where they say "matrix product verification over rings can be done in $O(n^2)$ randomized time [BK95]." ([BK95]: M. Blum and S. Kannan.  Designing programs that check their work. J. ACM, 42(1):269–291, 1995.)

First, are rings the most general structure on which this problem has an $O(n^2)$ randomized algorithm? Second, I couldn't see how the results of [BK95] show an $O(n^2)$ time algorithm over all rings. Can someone explain how that works?

Here's a quick argument for why it works over rings. Given matrices $A$, $B$, $C$, we verify $A B = C$ by picking a random bit vector $v$, then checking if $ABv = Cv$. This clearly passes if $AB = C$.

Suppose $AB \neq C$ and $ABv = Cv$. Let $D = AB - C$. $D$ is a nonzero matrix for which $Dv = 0$. What's the probability that this occurs? Let $D[i',j']$ be a nonzero entry. By assumption, $\sum_{j} D[i',j] v[j] = 0$. With probability $1/2$, $v[j'] = 1$, so we have

$D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$.

Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i',j']$, i.e., $-D[i',j']$. Now, the probability of the bad event $-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$ is at most $1/2$. (One way to see this is the "principle of deferred decisions": in order for the sum to equal $-D[i',j']$, at least one other $D[i',j]$ must be nonzero. So consider the $v[j]$'s corresponding to these other nonzero entries. Even if we set all of these $v[j]$'s except for one of them  optimally, there is still equal probability for the last one being $0$ or $1$, but still only one of these values could make the final sum equal to $-D[i',j']$.)
So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j']$ are independently chosen for $j \neq j'$.)

As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?


What's complexity of this set problem which looks like "Linear Programming"? I came up with a problem below, which looks like a linear programming problem:

  Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :
  $$
\forall i=1, 2, 3,...,n\space\space \left | S_{i} \right |=k;\\
\left | S_{j_{11}}\bigcup S_{j_{12}} \right |\leqslant k_{1};\\
\left | S_{j_{21}}\bigcup S_{j_{22}} \right |\leqslant k_{2};\\
...\\
\left | S_{j_{m1}}\bigcup S_{j_{m2}} \right |\leqslant k_{m}.\\
$$
  $j_{11},j_{21},...,j_{m1},j_{12},j_{22},...,j_{m2}$ are integers between $1$ and $n$. $k,k_{1},k_{2},...,k_{m}$ are constant positive integers.
  The questions is:
  For a positive integer $q$,Do such $S_{1}, S_{2},..., S_{n}$ exsit, such that $\left| \bigcup_{i}^{n}S_{i} \right |=q$?

I came up with this problem in order to judge complexity of another graph problem. But I failed to find any relative research. So has complexity of this kind of problem been studied? Is this problem NP-Complete or just P? How to judge this problem? Thanks.
By the way, what if $k=2,k_{1}=k_{2}=...=k_{m}=3$?

If I'm not mistaken, the case you specify (with $k =2$, $k_i = 3$) is in P.

Note that the condition $|S \cup S'| \le 3$ is equivalent to saying that $S, S'$ intersect (since $k=2$). Thus, if you think of the $S_i$ as vertices, then the constraints specify a graph $G$, and your problem reduces to finding a graph $H$ such that $G$ is the line graph of $H$.

Verifying that $G$ is indeed a line graph and then finding $H$ can be done in linear time.


Matching problems that are easy for bipartite graphs but hard for general graphs Are there variants of matching problem (decision or optimization problem) that are polynomial time solvable for bipartite graphs but are NP-hard for general graphs?

The stable marriage problem with ties (a matching problem for bipartite graphs) is (trivially) solvable in polynomial time, whereas the stable roommate problem with ties (a matching problem for general graphs) is known to be NP-hard.  See Eytan Ronn:
NP-Complete Stable Matching Problems. J. Algorithms 11(2): 285-304 (1990) for details.


Biased binary search? Suppose I have some pre-existing knowledge of where within a sorted array the element I am looking for lies, in the form of a probability distribution $P(i)$ that tells me the probability of the goal element being found at position $i$.

When executing a binary search, the pivot has to be chosen at each step. I have a vague sense that I could, somehow, exploit my pre-existing knowledge of the element's location while retaining the $\Theta(\log N)$ asymptotic performance of binary search by using $P(i)$ to inform my choice of pivot at each step. If this is indeed a good idea, how should it be done?

Change the binary search procedure to pick a weighted midpoint at each time step:

1.  Input: Search key K, sorted array A, probability distribution P.
2.  Initialize m=0, M=n=len(A)=len(P).
3.  Repeat:
4.     Pick i with m <= i < M such that
5.       sum(P[j] for m<=j<i) <= sum(P[j] for m<=j<M)/2
6.     and
7.       sum(P[j] for i<j<M) <= sum(P[j] for m<=j<M)/2.
8.     Compare K with A[i].
9.     If K==A[i], return i.
10.    If K<A[i], set M=i.
11.    If K>A[i], set m=i+1.
12.    If m==M, return -1. (Fail.)

Suppose the search key is in the array - i.e., K==A[i] for some i. The algorithm halves the value sum(P[j] for m<=j<M) after each iteration. Moreover, this sum starts at 1 and must always be at least P[i]. Thus the number of comparisons is at most 1+log_2(1/P[i]).

If you want to retain the $O(\log n)$ worst case performance, you can mix a bit of the uniform distribution into your distribution. That is, run the algorithm with P'=(P+U)/2, where U is the uniform distribution. Then the number of iterations is at most 1 + log_2(1/P'[i]) <= 2 + min{ log_2(1/P[i]), log_2(n) }.


What happens if we improve the time hierarchy theorems? In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ with $f(n) \log f(n) = o(g(n))$ it is
$$ DTIME(f(n)) \subsetneq DTIME(g(n))$$
and for nondeterministic TM and time-constructable functions $f,g$ with $f(n+1)=o(g(n))$ it is
$$ NTIME(f(n)) \subsetneq NTIME(g(n)).$$
There are a lot of (old and current) results which use the time hierarchy theorems to prove lower bounds. Here are my questions:

What happens if we can prove a better
result for the deterministic or nondeterministic case?
If we can prove that there is a gap
between the deterministic time
hierarchy and the nondeterministic
time hierarchy, does this imply $P \neq
   NP$?

About your second question. No, that would not imply $P \neq NP$. Hierarchy theorems are mostly useful to determine the amount of a single resource needed by a TM so that additional problems can be solved.

For example, we know that $DTIME(n) \neq NTIME(n)$. Let $f(n) = n$, $g(n)$, $h(n)$ such that $f(n+1) = o(g(n))$ and $f(n)log(f(n)) = o ( h(n) )$.

From the hierarchy theorems it follows that $ DTIME( f(n) ) \subsetneq DTIME( g(n) )$ and $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$.
 Under those assumptions, $ NTIME( g(n) ) \subseteq DTIME( h(n) )$ is possible.

The hierarchy theorems can be used to determine relationships between resources, given an equality between them. For example , assume that
$ NTIME(2^{n}) = SPACE( n )$. We know that $NTIME( g(n) )$, for $g(n)$ such that $2^{n+1} = o(g(n))$, cannot be equal to $SPACE(n)$ , due to the NTIME hierarchy theorem.


Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems? Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space.

Since we are unable to build nondeterministic or 'lucky' computers, does it make any difference to us if a problem is $NP$-complete or $PSPACE$-complete?

This is a very nice question that I have thought about a lot: Does the fact that a problem is $NP$-complete or $PSPACE$-complete actually affect the worst-case time complexity of the problem? More fuzzily, does such a distinction really affect the "typical case" complexity of the problem in practice?

Intuition says that the $PSPACE$-complete problem is harder than the $NP$-complete one, regardless of what complexity measure you use. But the situation is subtle. It could be, for example, that $QBF$ (Quantified Boolean Formulas, the canonical $PSPACE$-complete problem) is in subexponential time if and only if $SAT$ (Satisfiability, the canonical $NP$-complete problem) is in subexponential time. (One direction is obvious; the other direction would be a major result!) If this is true, then maybe from the "I just want to solve this problem" point of view, it's not a big deal whether the problem is $PSPACE$-complete or $NP$-complete: either way, a subexponential algorithm for one implies a subexponential algorithm for the other.

Let me be a devil's advocate, and give you an example where one problem happens to be "harder" than the other, but yet turns out to be "more tractable" than the other as well.

Let $F(x_1,\ldots,x_{n})$ be a Boolean formula on $n$ variables, where $n$ is even. Suppose you have a choice between two formulas you want to decide:

$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$.

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

(That is, in $\Phi_2$, the quantifiers alternate.)

Which one do you think is easier to solve? Formulas of type $\Phi_1$, or formulas of type $\Phi_2$?

One would think that the obvious choice is $\Phi_1$, as it is only $NP$-complete to decide it, whereas $\Phi_2$ is a $PSPACE$-complete problem. But in fact, according to our best known algorithms, $\Phi_2$ is an easier problem. We have no idea how to solve $\Phi_1$ for general $F$ in less than $2^n$ steps. (If we could do this, we'd have new formula size lower bounds!) But $\Phi_2$ can be easily solved for any $F$ in randomized $O(2^{.793 n})$ time, using randomized game tree search! For a reference, see Chapter 2, Section 2.1, in Motwani and Raghavan.

The intuition is that adding universal quantifiers actually constrains the problem, making it easier to solve, rather than harder. The game tree search algorithm relies heavily on having alternating quantifiers, and cannot handle arbitrary quantifications. Still, the point remains that problems can sometimes get "simpler" under one complexity measure, even though they may look "harder" under another measure.


How to find a non-zero point of a non-zero polynomial of low degree? Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one deterministically find another point $X' \neq X$, such that $P(X') \neq 0$.

Basically, it is a standard Polynomial identity testing with only one new twist: we know that the solution exists. You can say that it is in some sense problem from $FRP \cap PPP$ (this is very informal statement, I am not sure that this problem is in $PPP$, but it has the same flavor).

I would be glad if someone can point to some positive or negative results about this problem.

If  (ceil(degree/n))+1  is "large", then there doesn't actually need to be such an X$\hspace{.02 in}$'.

$\Bigg(\hspace{-0.08 in}$The polynomial can be $\;\;\; \displaystyle\prod_{i\hspace{.02 in}\in \hspace{.02 in}\text{coordinates}} \: \left(\displaystyle\prod_{c\hspace{.02 in}\in (\mathbb{F}\hspace{.03 in}-\{0\})} (x_{\hspace{.02 in}i}-c)\hspace{-0.07 in}\right) \;\;\;$ and X can be the origin.$\hspace{-0.08 in}\Bigg)$

If "large" means larger than 1 plus [the minimum over the variables of the degree in that variable], then there's a uniform NC$^0$ algorithm that will, with no access to the polynomial, with neither

bit operations nor field operations nor equality tests on field elements ($\hspace{.03 in}$just copying them and

moving them around), output a polynomial-length list of elements of $\mathbb{F}^n$ such that at least one

of those elements is such an X'.  (When B is an upper bound on the bracketed expression from

the previous sentence, the algorithm will have B+2 distinct hard-coded field elements and output the  n$\cdot$(B+2)  results of replacing one of X's coordinates with one of the B+2 field elements.)

Thus, you need to either consider fields of "intermediate" size, or allow polynomials of

large (superpolynomial) degree.  (Arithmetic circuits can easily have exponential degree.)

A problem that's closer to canonical for  FRP ∩ PPP  (and is actually obviously in PPP) is

Input:    A (circuit encoding a) function  f : {0,1}n+1 -> {0,1}n

and a (circuit encoding a) function  g : {0,1}n -> {0,1}n+1

Correct Outputs:    elements x of {0,1}n+1 such that  g(f(x)) ≠ x
.


Quantum algorithms for determining whether two sets intersect Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether two sets of size $\sqrt{N}$ intersect (so there are $N$ ordered pairs with one element from each set)? Do they beat the $\Theta(\sqrt{N})$ time of Grover's algorithm?

It's not completely obvious to me that this problem can be reduced to element distinctness (ED). What if the two sets are disjoint, but the sets contain repeated elements? If you just solve ED on the union of the two sets, ED will return YES, but the sets are disjoint.

But this problem (let's call it Set Disjointness or SD) has query complexity $\Theta(n^{2/3})$ when the two sets are of size $n$.

To show a lower bound of $\Omega(n^{2/3})$, we can reduce ED to SD. Here's a simple probabilistic reduction: Take any ED instance. Randomly partition it into two parts and solve SD on this instance. If it was a NO instance of ED, it will be a NO instance of SD. If it was a YES instance, then with probability >= 1/2, it will be a YES instance of SD.

For an upper bound of $O(n^{2/3})$, I can't, off the top of my head, think of a reduction to a known problem. The easiest way I can think of is to use Ambainis' algorithm for ED, but modify it to work for this problem. It is known that Ambinis' algorithm actually works for any two-place relation R(.,.), not just the relation EQUALITY(x,y), which is 1 iff x and y are the same. So we can use the relation R(x,y) = 1 iff x = y and x and y are from different sets.


How much computational power fits into a cubic centimeter? This question is a followup on the question about DNA algorithms asked by Aadita Mehra.

In comments there, Joe Fitzsimmons said, in part:

  [T]he radius of the system must scale proportionately to the mass to avoid this. The computational power scales at most linearly in the mass. Thus your exponential amount of machinery has an exponential radius. Since you can't signal faster than light, a signal from one side to another takes an exponentially long time to reach the other side, and so if all the machinery contribute to the answer, it is impossible to solve the problem in less than exponential time.

My question has two parts.

(1) What is the best way/ways to formalize a statement like, "The computational power scales at most linearly in the mass" ?  Is this statement really not up for debate?

(2) Suppose the statement is true.  Even so, could nature already have done an exponential amount of preprocessing that we might be able to make use of, for example evolution's creation of vision systems through "brute force randomization."

I've heard and read a fair number of soft (pseudoscientific) answers to questions of this sort, and I'd be grateful for any answers here, but I'm most interested in how (1) and (2) can be recast in TCS rigor.

The statement I made wasn't particularly well written. I was referring to a combination of the Margolus-Levitin theorem (which gives the minimum time to move between two orthogonal states, and hence a lower bound on the time required to perform a gate) and the Schwarzschild radius (which gives the minimum radius of a system of some fixed energy before it forms a black hole). Combining the two of these leads to an upper bound on the number of gates which can be performed in a fixed region of spacetime. You can think of this as the maximum number of gates per unit time which can be performed.

The idea to combine the two theorems comes from Seth Lloyd, who uses such an approach to show limits on the computational power of the universe(link). He also has another paper where he looks at the maximum performance that can be achieved by a 1kg computer of volume 1liter  (something he calls the ultimate laptop and which is almost exactly your question). See arXiv. He obtains a limit of $10^{51}$ operations per second on $10^{31}$ bits.
Due to the finite age of the universe and the finite speed of light, when combined with Lloyd's results, you obtain a constant upper bound on preprocessing.


VC-dimension of triangles in 2D space I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7.
The issue is that, for the case when 4 points lying on a straight line with alternating signs (like - + - +), I don't see why a triangle could separate the points. Where am I making mistake?

[1] http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf

As Sasho and Huck mentioned in their comments, "shattering means that you have to be able to separate all +/- labelings of the same set of points, given the function class."

Therefore, since the set of points on a line is never separable by the class of triangles, it is not a valid set of points to decide the VC-dimension this class.


Metric graph theory database search algorithms I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News.  One chapter discusses current software implementations, and the database searches (and other applications) don't seem to take advantage of as much information about the graphs as they could.  On the other hand, perhaps more theoretical algorithms would be too hard to implement.  It seems like a potential open area, though.

So here's my question:

Is there an overview (or a small handful of references) that discusses theory and implementation (hopefully) of algorithms of databases of graphs with metric information?  (Each edge is a distance, and each vertex has a volume.)  A chemistry-free description of an example problem would be: given a database of graphs, find all of them that contain a particular subgraph.

This seems to be related to the subgraph isomorphism problem which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in certain cases, though.

If chemo- is anything like bioinformatics you will probably be interested in approximation algorithms in order to deal with noise, anyway. Also, given database lookup as application, there might be clever ideas for preprocessing that give you good amortised runtimes.

Found (not read) those:

http://www.springerlink.com/content/4751121q3575v041/

http://bioinformatics.oxfordjournals.org/content/23/2/232.full

http://portal.acm.org/citation.cfm?id=1368898

Disclaimer: Again, sorry for comment-style answer; I am not yet allowed to comment.


Does the isomorphism conjecture imply exponential lower bounds on witnesses density? The Isomorphism Conjecture of Berman and Hartmanis states that all $NP$-complete sets are polynomial time isomorphic to each other. This means that $NP$-complete problems are efficiently reducible to each other via polynomial time computable and invertible bijections. The conjecture implies $P\neq NP$.

The isomorphism conjecture implies an exponential lower bound on the density of $NP$-complete sets since Satisfiability problem is dense. I am wondering if it also implies an exponential lower bound on the density of witnesses for $NP$-complete set.

  Does the isomorphism conjecture imply exponential lower bounds on witnesses density? Does it imply that $NP$-complete problems can not be in $FewP$?

The best result I am aware of is the following:

If $P=UP$ and $NP=EXP$ then the isomorphism conjecture holds.

Density $D$ of a set $S$ refers to the number of strings of length less than $n$ in the language. A set $S$ is exponentially dense if its density is $D=\Omega(2^{n^\epsilon})$ for some $\epsilon \gt 0$ and for infinitely many $n$ and sparse if $D$= $O(poly(n))$.

I don't see how that would immediately follow: the isomorphism conjecture is about languages, and doesn't seem to have any implications about the witness structure of NP verifiers. (Every language has infinitely many different verifiers for it, and you could potentially rig those verifiers to do odd things.)

But your question reveals another very natural intriguing question, about the following strengthening of the Isomorphism Conjecture:

"Are all verifiers for NP-complete sets poly-time isomorphic?"

I.e., we want not only a poly-time isomorphism $\phi_{L,L'}$ between any two NP-complete languages $L,L'$ defined by verifiers $V,V'$, but also isomorphisms $\psi_{V,V'}$ between their sets of input-witness pairs which respect the isomorphism $\phi_{L,L'}$. (Note: There are multiple ways one might formally define this.) All $NP$-hardness proofs I can think of give you a one-to-one correspondence of this kind, as well. This stronger "Witness Isomorphism Conjecture" would imply some sort of yes-answer to your question.

A quick Google search (typing 'witness isomorphism conjecture') found a survey of some approaches to this kind of question:

Eric Allender. Investigations Concerning the Structure of Complete Sets. Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Springer, 2014


An improper planar coloring with monochromatic component size $\leq 2$ Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color.  A monochromatic component is defined to be a connected component in the subgraph induced by the set of vertices that receive the same color, and the question is to ask for the minimum number $\lambda$ of colors needed to color a graph such that largest monochromatic component has size no more than $C$.
The traditional coloring can be considered as $[\lambda,1]$-coloring in this setting.   Hence to find the minimum number of $\lambda$ is NP-hard for planar graph in general.

My question is, how about $[\lambda,2]$-coloring of planar graphs, or more generally, $[\lambda,C]$-coloring for $C \geq 2$?

This can be viewed as a dual problem of what is studied by Edwards and Farr, where $\lambda$ is fixed, and one is asked to find the minimum size of $C$.

2-colorable perfect matching in cubic planar graphs is very similar to your problem which was stated to be NP-complete by Schaefer in his famous dichotomy theorem paper although he did not give the proof for cubic planar graphs. The problem asks for the existence of two coloring of cubic planar graphs such that every vertex has exactly one neighbor of the same color as itself.

EDIT:
Defective coloring is the decision version of your problem. A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. The decision problem (2,1)-coloring with defects, which is equivalent to your optimization problem, was shown to be NP-complete even for planar graphs.


Most important topics for a short introduction to Prolog Suppose you were teaching an introductory course on logic as part of a TCS curriculum. Furthermore, suppose that you had one week (= two 90 minute lectures) to spare for introducing Prolog on the basis of a theoretical discussion of predicate logic and (definite) logic programming. What would be the topics you'd pick apart from the syntax and procedural semantics of Prolog? Would you introduce SLDNF resolution first or by way of the cut-fail "construction" to implement negation in Prolog programs? What sort of examples would you choose for an audience made up of people who do not know automata and might not even know graphs? There has to be something better than "mere" logic puzzles for more elaborate examples.

My idea is to teach them enough to write simple provers for (fragments of) the systems of logic used elsewhere in the course.  I had lots of experience writing interpreters from other courses in my curriculum, so I would have been prepared for that sort of approach.  Introduce SLDNF as the basis of sketching the limitations of using prolog in such a fashion, so they can reason about what's going to be hard and what's going to be easy to do in prolog for the remainder of the course.  Of course, my approach needs prolog to be introduced early instead of the last week.  If you like this approach, I suggest giving them libraries to render the proof trees or whatever that you use in the rest of the course.


Resources on Cryptographic Applications of Expander Graphs I want to read papers on cryptography like
How to Recycle Random Bits
or Security Preserving Ampliﬁcation of Hardness. They use random walks on expander graphs.

I need a short introduction to the subject of expander graphs and random walks on them. I prefer one that has cryptography in mind.

PS: In another post, Dai Le introduced the paper Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson as an excellent paper on expander graphs. Unfortunately, it is too long (123 pages) to be useful for me.

I suggest you look at a survey by Oded Goldreich, called A computational perspective on sampling. In that survey he presents some basic facts on expanders (along with pointers to more extensive material). These facts seem to be sufficient to at least understand the "Security Preserving Amplification of Hardness" paper. In particular, in appendix A he surveys random walks on expanders, and in C.4 he presents the expander hitter, which is what is essentially done in that paper.


Getting started with Program Synthesis There some internet pages:

http://en.wikipedia.org/wiki/Program_synthesis
http://research.microsoft.com/en-us/um/people/sumitg/pubs/synthesis.html
https://sites.google.com/site/asergrp/bibli/program-synthesis

But, honestly, i can't find entrance to that topic. There are a lot of advanced level talks but only a few "hello world" examples(or completely none).

So where can one start learning about program synthesis ?

Start with the notes form Ras Bodik's course, Program Synthesis for everyone: http://www.cs.berkeley.edu/~bodik/cs294fa12

The slides from the recent summer school are also useful: https://excape.cis.upenn.edu/summer-school.html


Streaming Algorithms: Motivations for estimating frequency moments The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:

Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The kth frequency moment is defined to be

$$\displaystyle F_k = \sum_{i=1}^n m_i^k.$$

Alon et al. give a streaming algorithm that approximates $F_k$ using roughly $O(n^{1-\frac{1}{k}}(\log n + \log m))$ space. They also use communication complexity techniques to obtain a lower bound of $\Omega(n^{1-\frac{5}{k}})$ for $k > 5$. For $k = 0,1,2,$ they provide more or less matching upper and lower bounds.

There have been more work in this area which have improved upon the results of this paper:

For $F_k$, there is a matching upper and lower bound of $n^{1−2/k}$ for $k>2$. The upper bounds are by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.

There has also been some related work on approximating $F_\alpha$ where $\alpha$ is not necessarily an integer. http://www.stat.cornell.edu/~li/SODA09_CC.pdf

This question talks about the improvements: Bounds on approximating frequency moments

My question is regarding the motivations of this line of work. The AMS paper talks about the application of $F_2$ to compute the surprise index, the moments give the skewness of the data which helps to select appropriate algorithm for data partitioning of a database. Other sources and papers mention applications in databases.

Other than these, is there any motivation for using these moment estimating algorithms in statistics? What I am thinking about is how relevant is this line of work to the statistics community?
I was presuming a scenario that these moments may be useful to compute some statistic of the data for some statistical estmation or test of hypothesis, but if they use higher moments like k>6, the linear lower bounds on space motivate the approximation of such statistic using only lower moments or formulation of different statistic that uses only lower moments which can be computed in sublinear space. But, I am not aware of such scenario and couldnt find one. Can you please help me find?

[Though not sure, I presume using estimates of these moments,  one can also approximate central moments. Please comment and correct me on this as well.]

Also, if you add any motvation not mentioned here, it will be heplful.
Please dont hesitate to improve my question.

$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful.

Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful.

$F_1$ counting, or frequency estimation is also very useful:

Example: There's work on building statistical language models that involve counting frequencies of pairs of words, triples of words, and so on. You can't maintain counts for all such triples, so you often want "frequent" ones, or "heavy hitters".


What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$? We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$.

We also know there are degree $3$ bipartite graphs that are planar whose perfect matching count is in $P$.

What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
Is there a cutoff degree $\alpha\in[2,3]$ such that if max degree $3$ holds then counting perfect matching count is in $P$?
Is there any relevant literature?

You can take any degree 3 bipartite graph $G$ and take its disjoint union $G'$ with a cycle $C$ of length 2m. The new graph $G'$ is bipartite, and has average degree $\frac{3n + 2m}{m+n} = 2 + \frac{n}{n+m}$. Also, the number of perfect matchings in $G'$ is exactly twice the number of perfect matchings in $G$, because the perfect matchings of $G'$ are the disjoint unions of a perfect matching of $G$ and a perfect matching of $C$, of which there are two. So, there is a polytime parsimonious reduction from counting perfect matchings in 3-regular bipartite graphs to counting perfect matchings in graphs with maximum degree 3 and average degree $2 + \frac{1}{\mathrm{poly}(n)}$.


Surveys on pseudo-random number generator design? I am interested in generation of pseudo-random numbers for cryptography. Besides Chapter 5 of Menezes/Oorschot/Vanstone; Chapter 8 of Stinson; and Chapter 3 of Goldreich, where else could I find more? I'm interested in general principles for designing PRNGs (desirable properties, tests, etc).

You might want to check out

Chapters 5 and 6 of Katz and Lindell
Pseudorandomness by S. Vadhan
Parwise Independence and Derandomization by Luby and Wigderson
Pseudorandomness and Combinatorial Constructions by Trevisan
Goldreich's webpage on pseudorandomness, where he has pointers to other sources.


Different definitions of complexity I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes me as odd is that the definitions I have encountered so far seem to differ greatly. In particular, the differences that I have noted are

Difference between the uniform and logarithmic cost models: this can, for example, make a difference, when evaluating the time complexity of something like
for i = 1, 2, ..., n do c(i),
where c(i) is an instruction such that the number of bits involved depends on i.  When dealing with, say, sorting algorithms, all references I have ever come across adopt the uniform cost model, while in Cryptography, the time complexity of algorithms is always calculated in terms of bit operations.
Another difference is the definition of the size of an input: again, in sorting algorithms, the size of the input is simply the length of the vector that has to be sorted (as in graph searching algorithms, the number of nodes and edges). In Cryptography and Computational Number Theory, instead, the size of the input is always the number of bits involved. I don't know if this distinction is considered part of 1. , but it certainly makes a huge difference, since an algorithm that is linear using the first criterion, becomes exponential when adopting the second. Factorizing integers would be linear (actually, $O(\log{n} \sqrt{n})$) if we considered the input size of $n$ to be $n$.

One could justify these discrepancies with arguments such as "well, in Number Theory we are dealing with large integers, so adopting a more realistic model makes more sense". But this defies the whole purpose of evaluating asymptotic expressions for the complexity of algorithms! If, in certain contexts, we knew that all inputs were smaller then a fixed quantity, then everything would be $O(1)$. Also, how can it be possible to define, without ambiguity, complexity classes and other rigorous Computer Science concepts, when the definition of complexity varies from field to field?

The definition of, e.g., class P is unambiguous.

However, what is ambiguous is something like "the running time is $O(n)$". As you have observed, there are two sources of ambiguity:

What is a single time step? This depends on the model of computation.
What is $n$? This depends on the problem.

To make it completely unambiguous, you would state something like "the running time in the RAM model is $O(n)$, where $n$ is the number nodes."

Usually, we can afford to be a bit sloppy. The model is often clear from the context; in the case of algorithms, it is usually the RAM model unless otherwise specified. Moreover, there are various conventions regarding the definition of $n$. For example, in the context of graph algorithms, $n$ almost always denotes the number of nodes (and $m$ is the number of edges) – these are just conventions that you have to learn.

If you are really interested in logarithmic factors, then you have to be careful with these details. The same algorithm might be $\Theta(n)$ or $\Theta(n \log n)$ or $\Theta(n/\log n)$ if you slightly vary your model of computation or your definition of $n$.

However, if something like "polynomial time" is good enough for you, then you can ignore most of these details. Typical models of computation can simulate each other with a polynomial overhead (time $x$ in one is at most time $\mathrm{poly}(x)$ in the other), and typically an input can be encoded in $\mathrm{poly}(n)$ bits, no matter what happened to be your precise definition of $n$. For example, an $n$-node graph can be encoded as a string of $n^2$ bits. Hence you can usually say "runs in polynomial time" without worrying too much about the details ("polynomial in what?", "polynomial number of what?").


In homotopy type theory, is there a IsManifold predicate? Any type $A: \mathcal{U}$ can be thought of as a homotopy type, or a sufficiently nice topological space up to homotopy equivalence. Now, manifolds are topological spaces with some extra structure.

Some questions in manifold theory are still interesting up to homotopy, for example 2-manifolds are isomorphic whenever they are homotopy equivalent, and it is suspected that 4d extended topological quantum field theories only carry homotopy information.

Other questions in manifold theory are exactly whether homotopy equivalence implies isomorphism under certain circumstances, for example the question of homotopy spheres.

So I'm wondering whether it's possible to define a predicate like $\text{IsManifold}: \mathcal{U} \to \mathcal{U}$, such that $\text{IsManifold}(A)$ is inhabited by possibilities of defining a manifold that is homotopy equivalent to $A$.

As an application, we can define any homotopy invariant of manifolds (like the genus of surfaces) on types satisfying this predicate.

Since in all generality, this is probably too much to ask for a start, so here is an easier version:

Surely it is feasible to define a type of simplicial sets $\text{sSet}$. Can we define a proposition $\text{IsManifold}': \text{sSet} \to \text{Bool}$ that decides whether the realisation of a given simplicial set is a manifold?

I'm afraid I don't have a clear answer to your question. As I imagine you know, the basic definition of being a manifold cannot even be formulated in HoTT, since it crucially relies on the topology of the space in question, which does not exist for every type!

The primitive notion in HoTT is that of the path space $I_X$ of a type $X$. But, as far as I know, this does not in general define a topology over $X$, which is required in the usual definition of manifolds.

Another point is the property vs structure problem that seems to underly your question. It is certainly possible to define a manifold structure over a type: a manifold is a tuple $(X, T, A)$ where $X$ is a type, $T$ is a topology over $X$, and $A$ is an atlas, etc.

Given such a structure (which may include proofs of the various properties that underlie the structure), you can of course ask whether it is homotopy equivalent to another $Y$, as a homotopy type. This means that being a manifold is first defined as being a structure, and only then can you ask the question whether another type has the property of being homotopy equivalent to some manifold.

This is just what you do in "ordinary" math though, and doesn't seem to nicely use the synthetic properties of HoTT. As far as I can tell, the machinery required to talk about manifolds in a synthetic way is still being worked out, and certainly hasn't been well explored yet in any of the current (semi-)implementations of HoTT. This is an exiting avenue of research though. It seems to be structural, and thus requires adding constructs to "ordinary" HoTT.

The most notable proponent of this approach is Urs Shreiber (though Mike Shulman certainly is a close second, and might be able to give a more informed answer), and some pointers can be found here and here (n-Cat Lab).


SAT algorithms not based on DPLL Are there any algorithms for SAT solving which are not DPLL based?
Or are all algorithms used by SAT solvers are DPLL based?

Resolution Search (just applying the resolution rule with some good heuristics) is another possible strategy for SAT solvers. Theoretically it's exponentially more powerful (i.e. there exist problems for which it has exponential shorter proofs) than DPLL (which just does tree resolution though you can augment it with nogood learning to increase its power - whether that makes it as powerful as general resolution is still open as far as I know) but I don't know of an actual implementation that performs better.

If you don't limit yourself to complete search, then WalkSat is a local search solver which can be used to find satisfiable solutions and outperforms DPLL-based search in many cases. One can't use it to prove unsatisfiability though unless one caches all the assignments that have failed which would mean exponential memory requirements.

Edit: Forgot to add - Cutting planes can also be used (by reducing SAT to an integer program). In particular Gomory cuts suffice to solve any integer program to optimality. Again in the worst case, an exponential number may be needed. I think Arora & Barak's Computational Complexity book has a few more examples of proof systems that one could in theory use for something like SAT solving. Again, I haven't really seen a fast implementation of anything apart from DPLL-based or local search based methods.


Is Isomorphism of bounded degree hyper-graphs in P? Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices.

A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain subsets of the vertex set of $V$. An example of hyper-graph is given below and for example edge $e_3$ is a subset contain $v_3,v_5,v_6$ and similarly for other edges.

Isomorphism :
Two hyper graphs $G(V,E)$ and $H(V,E')$ are isomorphic if there is a permutation $g$ on $V$ such that,  $\forall $ $e \in E$, $$e\in E \iff g(e) \in E'$$

Reference: https://en.wikipedia.org/wiki/Hypergraph

Let me define the degree of a vertex in a hyper-graph:

$$D_v = |\{e_i \mid v\in e_i, e_i \in E\} |$$

Question : Is Isomorphism of bounded degree hyper-graphs in P ?

It depends on whether the uniformity of your hypergraphs is bounded.

Bounded uniformity In this case, you can represent each hypergraph with a colored bipartite graph which has vertices on one side (colored blue) and hyperedges on the other side (colored red). A vertex and a hyperedge are connected if the hyperedge connects the vertex. We can get rid of the colors in any number of ways, for example attach to each red a vertex a very long path which will force any isomorphism between two such graphs to match vertex colors. These graphs have bounded degree, and so GI for this class of graphs is in P.

Unbounded uniformity In this case the problem is GI-complete. Given a graph $G$, create a bounded degree hypergraph whose vertices are the edges of $G$ and whose hyperedges correspond to vertices of $G$; a hyperedge contains a vertex if the corresponding vertex of $G$ belongs to the corresponding edge of $G$. This hypergraph has maximum degree 2. Two graphs are isomorphic if and only if the corresponding hypergraphs are isomorphic (this requires some argument but seems correct).


A survey on separators? There are by now mountains of results on separators in graphs, from planar separator, tree separator, bounded tree width graphs, bounded genus graphs, etc, etc, etc. Is there any good updated survey about this, and their applications?

Not exactly the most recent (published in 2001), but the text by Arnold L. Rosenberg, Lenwood S. Heath, "Graph Separators, with Applications" may be a good place to look. The Google book link is provided here:
http://books.google.ca/books/about/Graph_Separators_with_Applications.html?id=7DNKE5ZiNZYC&redir_esc=y


With equirecursive types are there downsides to making all types potentially recursive? By this I mean to ask, is it a bad idea to have all type constructor term expressions abstracted with $\mu$ just in case they need to be recursive? For example,

$Bool : Type;$

$Bool = (\mu Bool' . (Unit \lor Unit));$

The value constructors would still just be $(inj_0 unit)$ and $(inj_1 unit)$ in a system with equirecursive types, right? It seems like it would just be $O(x + 1)$ for an $O(x)$ type checking algorithm using unification, or maybe not even that.

I understand why $Bool$ is not written this way by default, especially considering recursive types are usually added to a theory after-the-fact and therefore the value constructors would differ depending on the variant of the recursive type theory. It's much less intuitive to read $(\mu X . \tau)$ than just $\tau$ when programming or proving theorems but are there any reasons of real consequence for not doing this? I can't find any.

The reason I ask this question is because I am writing a program to translate a functional programming language into a core dependent type theory with equirecursive types.

My advice would be to make sure that your translation function is  compositional and straightforward, i.e., for a typical construct $A * B$ the translation function $t$ should have the form $t(A * B) = s(t(A), t(B))$, where $s$ is the translation of $*$. Thus the translation should follow the syntax of the input language. If you want to perform any "optimizations", those should come as convinient tactics that get used after the translation phase. This will make it easier to pove that your translation works correctly.

Concretely, if your input language has a construct for defining recursive types, such as data in Haskell, then you should translate those to $\mu \cdots$ even if they are not actually using the recursion, because that is what they are. You can always have a simple lemma afterwards which shows that $\mu$ can be omitted in certain cases. If you set up your tactics the right way, the theorem prover will simplify things by itself (and do much more if needed). But you should not put $\mu$ in front of a definition that cannot be recursive, such as newtype. In other languages, for example in Ocaml, the only way to introduce a new type is with type, which may be recursive, so there you'd put $\mu$ in front of everything.


Learning road map for functional programming from the viewpoint of category theory I am now considering about studying functional programming from the viewpoint of category theory. There are a lot of books about functional programming and category theory, I want some suggestions regarding some comprehensive books and reference materials (like online notes, courses etc)that would contain category theory viewpoint rather than plain functional programming. I have a solid background in Abstract Algebra,commutative algebra, functional programming and bit of category theory too.

There's no agreed upon "bible" for CT for computer science in the same way as for mathematicians (Mac Lane), probably because the field is younger and a bit broader. It really depends on whether you want to understand . Here are a few computer science concepts with category theory counterparts:

Simple types (which correspond to Cartesian Closed Categories)
dependent types (Locally Cartesian Closed Categories)
Abstract data types (categorical algebras, coalgebras, as described in e.g. Uustalu & Vene)
Programing with effects (Monads, monoidal categories, building on the foundational observations of Moggi)
Ressource aware programing (Closed Monoidal Categories (?))
CPS translations can be interpreted through the lens of the Yoneda lemma (see here for a brief explanation)

I'm missing a few, there are applications of category theory from everything to domain theory to database management.


Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time? The $k$-cycle problem is as follows:

Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.

Question: Does there exist a (proper) $k$-cycle in $G$?

Background: For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$ time.

  Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J.  Discrete Math. 10(2): 209-222 (1997)

However, it is not known if we can solve 3-cycle (i.e. 3-clique) in less than matrix multiplication time.

My Question: Assuming that $G$ contains no 4-cycles, can we solve the 3-cycle problem in $O(n^2)$ time?

David suggested an approach for solving this variant of the 3-cycle problem in $O(n^{2.111})$ time.

Yes, this is known. It appears in one of the must-cite references on triangle finding...

Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf) It is a simple procedure based on properties of breadth-first search.

So, if your graph is 4-cycle free and there is a triangle, their algorithm must output it, because it cannot output a 5-cycle or larger.


How to understand the "Availability" of the CAP theorem? As we know, in the CAP theorem, "A" means "Availability". On wikipedia, the explanation of "Availability" is:

  Availability: a guarantee that every request receives a response about
  whether it was successful or failed

However, from the perspective of engineering, there is no ABSOLUTE availability. We can only say that the availability of a system is 5'9'(99.999%), or even 8'9', but we cannot say that the availability of a system is 100%, 100% available system does not exit in reality, even if the system has millions of duplicated nodes, right?

The CAP theorem proves that no system could satisfy the 3 requirements simultaneously. My question is, if a system claims to satisfy both "A" and "P", what is the accurate meaning of this "A"? 6'9' or even higher?

Your question is mixing two somewhat orthogonal interpretations of the term "Availability".

The "reliability theory"/"engineering" interpretation, where availability is basically
the ratio of time the system is not failed.

The "distributed computing" interpretation, which is centered around the idea that

"every request received by a non-failing node in the system must result in a response"

So, let's consider a system of two nodes, that crash at midnight, and are resume operation at noon, every day.
So in the first interpretation we have 50% availability, that is, no nines at all. However, the system can still fulfill the second interpretation.


What is the state of the art research in analysing algorithms on GPU architectures? I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved when using a specific GPU.

However I could not find a lot of papers on theoretically analysing algorithms, proving bounds etc when working in this new model.

Is it because that is too difficult to do or not very interesting?

research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations shared by some physics researchers, some universities (eg specializing in supercomputing) spent significant money on GPU clusters which are not largely utilized (eg in physics simulations contexts?), but what factor that may be due to is not clear. a forthright appraisal might observe that historically GPU companies might have overhyped the potential somewhat akin to the Gartner hype curve.

a possibly helpful paradigm for understanding the GPU role in parallel computing is the Berkeley framework of 7 "dwarves" & there is some brief mention of GPU there. another recent success story, at one point GPUs for a time period/ window were heavily used in bitcoin mining, but they are now almost entirely eclipsed by custom ASIC solutions.

from the theoretical pov there may not be so much interest due to that they are to some degree "just a hardware implementation detail" and possibly at best leading to linear speedups (albeit for sizeable/ worthwhile constants) even with ingenious implementations.

what kind of problems lend themselves well to gpu computing? scicomp.se
on GPU algorithms (wrt TCS community) Suresh Venkatasubramanian (tcs.se mod) & commentary by other researchers
Where is the Data? Why You Cannot Debate CPU vs. GPU Performance Without the Answer Gregg / Hazel
Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization Lustig/ Martonosi
techniques to reduce cpu to gpu data transfer latency stackoverflow
CUDA memory transfer overhead
The Landscape of Parallel Computing Research: A View from Berkeley


Is the N Queens problem NP-hard? The N-queen problem is this:

Input : N

Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal.

Doing a google search on this, I found that many slides by many professors claim this is an NP-Hard problem.(eg. web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

However I havent been able to find a proof (or derive one).
The reason I ask this question is because I think I have an algorithm that solves certain instances of the problem i.e. with N not a multiple of 2 or 3 (N is the number of queens)
Related Issue - Can we consider the input size to be N (where N is the number of queens)? Or do we take the input size to be log(N), since the number 'N' can be represented in log(N) bits?

As stated, the answer to this question is NO.

References :
A polynomial time algorithm http://dl.acm.org/citation.cfm?id=101343 [courtesy: vzn]

Another much simpler technique : http://dl.acm.org/citation.cfm?id=122322 [courtesy: Jeffe]


Complexity of interval cover problem Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.

It is not hard to see that $Q$ can be solved in polynomial time (see below).

Now consider the following slightly modified problem $Q’$: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).

My question: Can $Q’$ be solved in polynomial time?

Here are two ways to solve $Q$ efficiently:

A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.

An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.

Thanks for any hints, and also for references!

Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l_i,r_i]$, covering a consecutive sequence of demand points (=integers $d_i$).


Is true randomness and the physical Church-Turing thesis incompatible? As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are incompatible? The reason is that there is a physical process which can generate a random sequence of digits (i.e. a random oracle), but a Turing machine can not. Moreover, generating a random sequence of digits should never hit a "wall". We can continue generating them forever without issue. Once the heat death of the universe hits, random numbers will be generated automatically.

Of course, this might be like asking if Turing machines can toast toast, but I don't think so. Generating a sequence of numbers if a purely computational task, and it would seem that if a Turing machine can not generate a physically realizable sequence of numbers, then that would disprove the physical Church-Turing thesis. Also, it is normally assumed that the physical Church-Turing thesis implies that the universe is simulatable (it a Turing machine can't toast toast, but it can simple toasting). Randomness seems to forbid this.

So, are the physical Church-Turing thesis and true-randomness incompatible, or not?

The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random output (for a given input)? There is at most one (random) output occurring with probability $>\frac{1}{2}$, so taking that output if it exists (and undefined otherwise) as definite value could be a reasonable definition. (One might argue that $\frac{1}{2}$ is too small for physical implementation and one should take $\frac{2}{3}$ instead, but I guess that is not really important for this answer.) The Church-Turing thesis now asserts that even this extended notion of computability for (partial) functions $\mathbb{N} \to \mathbb{N}$ still leads to the same set of computable functions.

If we are willing to leave the strict setting of (partial) functions $\mathbb{N} \to \mathbb{N}$, then we risk those toasting toast discussions. (Based on the older mustard watches or montres à moutarde parody by Jean-Yves Girard.) I prefered Martin Berger's and Neel Krishnaswami's position in that discussion over Scott Aaronson's position, but most everybody else seems to agree with Scott. I guess even Andrej Bauer would be unable to change that outcome. Scott's position is not meant as a parody:

  To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question. What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code? Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?

I previously wrote "So if a theoretical machine had access to a random source which its opponent could not predict (and could conceal its internal state from its opponent), then this theoretical machine would be more powerful than a Turing machine." But that argument takes place in a game theoretic setting (and idealization of some real world scenario) different from the context of the Church-Turing thesis. The simulation argument (explained by Martin Berger in the above discussion) could reduce that setting back to TMs by simulating all interactions between the random source enhanced Turing machines, but that misses my original point, about the random source being a separate idealization which can fail in its own ways. But if already clear concepts like higher-level formalisms gets dismissed, then there is little point in elaborating such fine interpretative points.

It might be possible to keep the "$\mathbb{N} \to \mathbb{N}$" part, and replace the "(partial) functions" part with something else (I am thinking here of an analogy Fermions <-> "(partial) functions", Bosons <-> "something else"), but the Church-Turing thesis would probably still hold in such modified settings.


What are the consequences of Parity-L = P? Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space. Solving a linear system of equations over ℤ2 is a complete problem for Parity-L, and so Parity-L is contained in P.

What other complexity class relations would be known, if Parity-L and P were equal?

parity-$L$ is in $NC^2$ and parity-$L=P$ would mean that $P$ can be simulated in parallel $\log^2$ time or in $\log^2$ space (since $NC^2$ is in $DSPACE(log^2 n)$)


parameterized algorithms for geometric set cover Are there any parametrized algorithms $W$-hardness results known for the computational problem Geometric Set Cover?

It is known that set cover problem is $W[2]$ hard when parametrized by the solution size? There might be some advantages when the sets are defined by geometric objects.

The paper D. Marx: Efficient approximation schemes for geometric problems?, in ESA 2005, gives W1-hardness for covering points with unit squares. A draft is here.


Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP? Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution.

For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.

However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.

Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?

Yes, in some sense at least.  See the following paper:

Megiddo, Nimrod. "On finding primal-and dual-optimal bases." ORSA Journal on Computing 3.1 (1991): 63-65. PDF available here.

It shows that:

  if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and
  the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for
  the general linear programming problem.

(Note the details of the result though: it is about finding an optimal basis and deals with strongly polynomial-time algorithms.)


NP vs co-NP and second-order logic Assume that NP=co-NP and polynomial $p(x)$ bounds the length of the proof of unsatisfiability for a 3-CNF instance $x$. Then are there any results on what form any proof of unsatisfiability for $x$ of length $\leq p(x)$ can take?
I.e. in general, would such a proof have to, for instance, use the full power of second-order logic over infinite structures (I am aware that the proposition to prove - that a formula is unsatisfiable can be expressed in second-order logic over finite structures but intermediate steps in the proof to get to that might require reasoning over infinite structures).
Since there is no effective, complete and sound system of inference for second-order logic, would it be possible to use such a result to prove NP $\neq$ co-NP?

If there is an optimal pps (pps = propositional proof system, an optimal pps is a pps that can p-simulate any other proof system) then the pps EF (Extended Frege) strengthened with propositional axioms stating the soundness of the optimal propositional proof system will be optimal. More generally EF + Soundness of pps P can p-simulate P for any P. So EF has a kind of generality that you don't need to change the logic or the underlying pps structure, but just add propositional axioms to it to get any arbitrary strong pps.

In particular, if there is a super pps (a pps which has polynomial size proofs for all tautologies) then EF + Soundness of that pps will be a super pps. Note that $NP = coNP$ is equivalent to the existence of a super pps.

Soundness of a pps P is a (sequence of) propositional formulas stating that if $\pi$ is a proof in P for $\varphi$, then $\varphi$ is true.

In summery, there is no need to go outside propositional logic.

ps: Note that all pps are effective by definition, a pps has a polynomial time verifier, and therefore its theorems are computably enumerable. $NP=coNP$ means that there is a super pps for the propositional formulas. Being propositional is important here. We know that there is no such thing for stronger logics but their nonexistence does not seem to have any effect on $NP$ vs $coNP$.


What’s the best way to test if a sphere is a polytope? (the Simplicial Steinitz Problem) This is a cross-post from MathOverflow.

The problem of testing whether a simplicial face lattice (informally, a poset of faces) is polytopal is sometimes called the Steinitz Problem.

Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether the face lattice of a simplicial sphere was also realizable as a polytope.

The method uses oriented matroids. The problem is NP-hard, so their algorithm requires exponential time in the worst case, but they reported that the algorithm often converged quickly. Lars Schewe has recently shown that the same method can be adapted to make use of optimized SAT solvers, although the underlying technique seems to be the same.

I'm curious if newer approaches have been developed in the intervening decades since Sturmfels and Bokowski published their result. Is their method still the state of the art?   Further, are there any software implementations available that solve this problem -- even using the older approach?

In the MathOverflow discussion, Joe O'Rourke pointed out that Polymake has a feature that seems to compute geometric realizations of simplicial complexes [GEOMETRIC_REALIZATION], but this doesn't guarantee polytopality as far as I know.

This is not an answer, just a comment.
Frank Lutz in Berlin is one of the experts on this topic, and you might ask him.
He maintains a nice web page,
The Manifold Page, which includes lots of information and references, including
descriptions of
Barnette's non-polytopal 3-sphere and
Grünbaum-Sreedharan's non-polytopal 3-sphere.

Incidentally, I believe this related problem is still open (if not, I'd like to know of its resolution):

  Does every triangulation of a genus 1 torus have a geometric realization (embedding) in $\mathbb{R^3}$?

For sufficiently large genus (I think 5?), there are non-realizable examples.


Why can a Predictive Parser contain E' -> TE' | ε I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused as to why

E' -> TE' | ε is valid

because

E -> E + T is not valid since we have "left recursion" (a variable that calls itself).

in other words, why doesn't E' -> TE' | ε or T' -> *FT' have left recursion? To me it looks a lot like E' and T' are calling themselves.

... is not valid since we have "left recursion" (a variable that calls itself).

That's not what a left recursion is. That's simply recursion.

Direct left recursion is when a rule $A \to A\alpha$ exists for arbitrary $\alpha$.

Indirect left recursion exists when there's a rule $A \to^* A\alpha$ for arbitrary $\alpha$. Note the star, implying possibly many derivation steps (and if we're being precise, more than one, otherwise it's just direct left recursion).

Only left recursion (whether indirect or direct) is problematic for $\text{LL}(1)$. But your grammar doesn't contain left recursion, only right recursion. Right recursion has the form $A\to^* \alpha A$. See the difference?


Turing degree of Solomonoff semi-measure We define the Solomonoff semi-measure $m$ on finite strings $x$ by

$$m(x) = \sum_{p: U(p) = x} 2^{-l(p)},$$

where $U$ is a universal prefix Turing machine, $U(p) = x$ means $U$ outputs $x$ on input $p$, and $l(p)$ is the length of $p$.
What is the Turing degree of (computing the first $n$ digits of) $m(x)$?

Note that from $ m (0) $ you can compute a version of Chaitin's $\Omega $. Moreover $ m (x) $ is left-c.e. uniformly in $ x $. So $ m $ has Turing degree $0'$.


CPA security for block ciphers? Reading Introduction to Modern Cryptography by Katz and Lindell, I noticed that they talk about CPA security for block ciphers (in Section 3.6.4 where they explain mods of operation) -- and mention that most modes of operation described there are CPA-secure. Then they prove that CTR mode is CPA-secure using the key length as security parameter: "${\tt Gen}(1^n)$ chooses a random function ..." and later, in the displayed equation,
$\left[ {\tt PrivK}^{cpa}_{{\cal A},\tilde\Pi}(n)=1 \right]\leq \frac{1}{2} + {\tt negl}(n)$".

However, in Chapter 5 (paragraph about "Attacks on block ciphers") they also mention that any pseudorandom permutation is secure againse CPA attacks, and that it makes no sense to use asymptotic notions of security for block ciphers, since their block and key length are fixed (and that makes perfect sense to me).

So I am confused now -- what is the point of the previous demonstrarion, on Chapter 3, that CTR mode is CPA-secure?

Or, making this question not specific to this book in particular: how do people define security against CPA (and known-plaintext, CCA etc) for block ciphers?

The book introduces two concepts, and warns not to confuse them with each other:

Encryption schemes: Which can have varying key lengths; and
Block ciphers: Which have fixed-length black and key lengths.

Chapter 3 of the book mainly speaks about encryption schemes. For instance, take a look at the proof of CPA-security of the CTR mode (Theorem 3.29, and Figure 3.8): The permutation $F_k$ used at the heart of the CTR construct can have varying key lengths.

However, chapter 5 mainly discusses block ciphers. These are practical constructs based on the theoretical ideas of encryption schemes (as the chapter title implies). The security of block ciphers (DES, AES, etc.) cannot be formally proved (at least at the present), since there exists no notion of concrete security, in contrast to asymptotic security.

That said, there has been some attempts at defining security notions for concrete security as well. Rogaway, for instance, has written a nice paper on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).

A related question on CSTheory is Hardness Guarantees for AES, where the OP asked about provable measures for the AES block cipher.


Planarity of planar finite automata intersection It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it possible to provide a planar automata intersection algorithm which instantly preserves planarity? Namely, suppose I have two planar automata $M_1$ and $M_2$. Is there exist an algorithm to construct an intersection of $M_1$ and $M_2$ which acts better (in terms of complexity or in terms of the size of the final automaton) than planarization (using results of Ivona and Martin) after the classical intersection? Also, is it possible to define a respective product of automata (and respective product of adjacency matrices)?

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: for two languages $L_1$ and $L_2$, let $L_1 Ш L_2$ denote their shuffle (aka interleaving). Let $L_d = (a_1b_1)^* Ш \ldots Ш  (a_db_d)^*$. This language can be expressed as the intersection of the $d$ languages $L_i = (\Sigma\setminus\{a_i,b_i\})^*(a_ib_i)^*(\Sigma\setminus\{a_i,b_i\})^*$. The minimum DFA for $L_d$ is isomorphic to the $d$-dimensional hypercube and has $n=2^d$ states. On the one hand, in (Gruber/Holzer, DLT '09) a lower bound of $2^{\Omega(n/\sqrt{\log\log n})}$ on required regular expression size for $L_d$ is shown. On the other hand, it is proved in (Ellul/Krawetz/Shallit/Wang, JALC '05) that an $s$-state planar  NFA can be converted into an equivalent regular expression of size at most $2^{O(\sqrt s)}$. This shows that $s$ must be in$\Omega(\frac{n^2}{\log\log n})$, as desired.
References:

Keith Ellul, Bryan Krawetz, Jeffrey O. Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. J. Autom. Lang. Comb. 10(4): 407-437 (2005)
Hermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287


What is the Relationship between QMA and AM? I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$.

I was surprised about this assertion. So what is the proper relationship between $QMA$ and $AM$?

No relationship is known to hold between QMA and AM, and it is reasonable to conjecture they are incomparable.

If QMA were proved to be contained in AM, it would be an absolutely enormous result in quantum complexity.  Of course it would imply that BQP is in PH, which itself would be huge, but it would go beyond that -- it would surely require major revelations about the structure of quantum algorithms and quantum certificates.

Having said that, the evidence against is not very convincing.  An oracle relative to which QMA is not contained in AM would help, and it seems like such a result may not be far off -- but we don't even have this yet.

A proof of the reverse containment, AM in QMA, would also be huge.  At least here we have an oracle relative to which AM is not contained in QMA (and in fact is not even contained in PP).


Post correspondence problem for finite monoids The Post correspondence problem has the following version for finite monoids:

Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$

Question: is there a natural number $k\geq 1$ and indices $i_1,\ldots, i_k\in \{ 1,\ldots, n\}$ such that $m_{i_1}\cdot\cdots \cdot m_{i_k} = m_{i_1}'\cdot\cdots \cdot m_{i_k}'$?

Is it known whether this problem is decidable?

Yes, it is decidable.  Build a graph where each vertex is a pair $(r,s)$ of elements from $M$.  Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$.  Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$.  This can be answered using standard reachability algorithms (e.g., DFS).  The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.