Hardness Guarantees for AES Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.

I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what is the evidence that breaking such cryptosystems is hard? (other than resistance to trial-and-error attacks)

Remark: I'm familiar with AES operations (AddRoundKey, SubBytes, ShiftRows, and MixColumns). It seems that the hardness of AES stems from the MixColumns operation, which in turn must inherit its difficulty from some hard problem over Galois Fields (and thus, algebra). In fact, I can restate my question as: "Which hard algebraic problem guarantees the security of AES?"

As David said, we do not have such reductions for AES. However, this does not mean that Rabin or RSA cryptosystem are more secure than AES. In fact, I'd trust the (at least one-way, probably also pseudorandomess as well) security of block ciphers such as  AES/DES etc.. (perhaps with a bit more rounds than standardly used) more than the assumption that factoring is hard, precisely because there is no algebraic structure and so it's harder to imagine that there will be some kind of breakthrough algorithm.

One can construct block ciphers directly from one-way functions, which is a minimal assumption for much of crpyotgraphy, but the resulting construction will be terribly inefficient and hence not used.


In the Hott book, are the most of the type formers redundant? And if so, why? In chapter 1 and Appendix A of the Hott book, several primitive type families are presented (universe types, dependent function types, dependent pair types, Coproduct types, Empty Type, Unit type, natural number type, and identity types) to form the foundation for Homotopy Type Theory.

However it seems that given universe types, and dependent function types you can construct all these other "primitive" types.  For instance the Empty type could instead be defined as

ΠT:U.T

I assume the other types could also be constructed similar to how they are in pure CC, (ie just derive the type from the inductive part of the definition).

Many of these types are explicitly made redundant by the Inductive/W types that are introduced in chapters 5 and 6.  But Inductive/W types appear to be an optional part of the theory since there are open questions on how they interact with HoTT (at least at the time the book came out).

So I am very confused about why these additional types are presented as primitive.  My intuition is that a foundational theory should be as minimal as possible, and redefining a redundant Empty type as a primitive into the theory seems very arbitrary.

Was this choice made

for some some metatheoretic reasons that I am unaware of?
for historical reasons, to make the type theory look like
past type theories (which were not necessarily trying to be
foundational)?
for "usability" of computer interfaces?
for some advantage in proof search that I am unaware of?

Similar to: Minimal specification of Martin-Löf type theory , https://cs.stackexchange.com/questions/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

You are asking several questions which are similar but distinct.

Why doesn't the HoTT book use Church encodings for data types?

Church encodings do not work in Martin-Löf type theory, for two reasons.

First, MLTT is predicative. There is a universe hierarchy, and each type lives at a particular universe level, and a type at level $n$ can only quantify over types at smaller universe levels $k < n$. Church encodings like in System F or the CoC require impredicative quantification, where you can instantiate quantifiers with types which are the same size, or even bigger.

Second, even if you defined datatypes like the natural numbers with Church encodings, to do proofs with these types, you need induction principles to prove things about them. To derive induction principles for Church encodings, you need to use an argument based on Reynolds' parametricity, and the question of how to internalize parametricity principles into type theory is still not fully settled. (The state of the art is Nuyts, Vezzosi, and Devriese's ICFP 2017 paper Parametric Quantifiers for Dependent Type Theory -- note that this is well after the HoTT book was written!)
Next, you are asking why the foundation is not minimal. This is actually one of the distinctive sociological features of type-theoretic foundations -- type theorists regard having a small set of rules as a technical convenience, without much foundational significance. It's far, far more important to have the right set of rules, rather than the smallest set of rules.

We develop type theories to be used by mathematicians and programmers, and it's very, very important that the proofs done within type theory are the ones that mathematicians and programmers regard as being done in the right way. This is because the arguments mathematicians typically regard as having good style typically are structured using the key algebraic and geometrical principles of the domain of study. If you have to use complicated encodings then much structure is lost or obscured.

This is why even type-theoretic presentations of propositional classical logic invariably give all the logical connectives, even though it is formally equivalent to a logic with just NAND. Sure, all the boolean connectives can be encoded with NAND, but that encoding obscures the structure of the logic.


Mathematics degree for Theoretical Computer Science? I want to go to grad school in theoretical computer science.
I don't like programming.
I am in France.

Should I pursue a bachelors in math or in computer science?

I would say there is no "one best/most appropriate route" to becoming a theoretical computer scientist, so it is more a matter of your personal tastes, and even what part of theoretical computer science you are most interested in, which you may not even know yet. I know of great TCS researchers who started out in pure math, and great TCS researchers who started out in CS or (even!) EE.

(And by the way, to the commenters: I know plenty of good TCS researchers who more or less abhor programming, and I also know plenty who are not only great programmers, but great software engineers.)

Whatever route you take, if you think you are really interested in TCS then you should immerse yourself in it, especially to try to find out which parts of it you are really interested in. Introductory classes on algorithms (many of which are purely theoretical and involve no programming, if you so desire) or the theory of computation are good places to start, and beyond that it is a matter of reading, asking professors for references and pointers, sitting in on introductory TCS grad classes if you have the opportunity, etc. From that point of view, your particular degree doesn't matter so much (unless e.g. if you do a mathematics degree your university would perversely prevent you from taking a course on algorithms or theory of computation).

However, it also sounds like it is still so early in your potential research career that it would be healthy to question why you are interested in TCS (even asking this question can lead you on a path to discovering exactly what parts of TCS you are really interested in, and give you better motivation for your future work), and to expose yourself to plenty of other topics to see if your true interests end up being elsewhere.


Is there an efficient algorithm for finding edges that are part of all hamiltonian paths? I'm wondering if there is any algorithm known for finding edges in a graph that are part of all hamiltonian paths (operating under the assumption that the graph has at least one such path). Failing that, is there an algorithm for finding as many of these edges as possible, relaxing the requirement that all such edges are found?

One could find all hamiltonian paths in the graph, and then look at all the edges in those paths, but is there a better way?

One type of edge in this class obvious even to me is edges that are directed to vertices with in-degree 1 (or similarly edges from vertices that have out-degree 1). I'm particularly interested in directed graphs but the insight into the undirected version would also be helpful.

My apologies if this question is overly naive - I ran across this problem while doing microbial genomics, and any help would be greatly appreciated.

Thanks in advance,
ben

A polytime algorithm that can find such a collection of edges even in the promise version of this problem can be used as a blackbox to solve the Hamiltonian Path problem in polynomial time, and thus this promise problem is NP-Hard under Cook reductions. The idea here is to use the algorithm for solving the promise problem on a sequence of graphs, many (but not all) of which potentially violate the promise given in the problem statement. Importantly, nothing is assumed of the output of the algorithm when it is fed a promise-violating graph as input, just that it outputs something (perhaps even adversarially). We can, of course, always cut the algorithm off and return the empty set as its solution if its execution is taking longer than some provided time bound (a bound only proven to hold only in promise-satisfying instances) and satisfy this requirement. It is the nature of the change in the algorithm's output (or lack thereof) on the sequence of instances that interests us.

Suppose you have a graph $G=(V,E)$ in which you wish to determine the existence of a Hamiltonian path, and oracle access to a function $\varphi$ such that $\varphi(G) = h(G)$ (where $h$ is defined as in David's post) whenever $G$ contains a Hamiltonian path (and returns an arbitrary answer otherwise). Intuitively, the algorithm searches for a supergraph $H$ of $G$ on which $\varphi(H) = h(H)$ is violated. If such a graph can be found, it must be the case that $H$ (and all of its subgraphs, including $G$) is not Hamiltonian. Conversely, not violating the inequality on any graph in the sequence shows that the original $G$ is Hamiltonian.

Now construct a sequence of graphs $G_0 \cdots G_{n-1}$ as follows:

Let $G_0 = G$
Pick a permutation $\pi$ of $V$ such that no $(\pi_i, \pi_{i+1})$ is an edge of $\varphi(G_0)$.*
For $i = 1$ to $n-1$

Let $e_i = (\pi_i, \pi_{i+1})$
Let $G_i = G_{i-1}$ with edge $e_i$ added (if it did not already exist in $G_{i-1}$)

Note that $h(G_x) \supseteq h(G_y)$ when $x < y$ (i.e. containment of some fixed edge in $h$ is hereditary among the $\{G_i\}$). Thus, if $e_i \in \varphi(G_i)$ for some $i \geq 1$, it must be the case that $G$ does not contain a Hamiltonian Path, since $\varphi(\cdot)$ is not hereditary on this graph family (recall that $e_i$ is not in $\varphi(G_0)$) and thus $\varphi(G_i) \neq h(G_i)$ for some $G_i$.

However, if $e_i \not \in \varphi(G_i)$ for all $i$, no single addition of an edge was necessary in the construction of the first (set of) Hamiltonian Path(s) in the sequence in which we constructed $\{G_i\}$. Since $G_{n-1}$ contains a Hamiltonian path by construction, a simple inductive argument implies $G_0$ must contain one as well.

Thus, Hamiltonian Path can be solved via $O(n)$ queries to an oracle solving this promise problem (assuming they produce an arbitrary output on promise-violating graphs), meaning that any time bound $f(n)$ for an algorithm solving this problem implies a time bound of $O(n f(n))$ for solving Hamiltonian Path, and thus $f(n)$ (and any provable upper bound on the running time for a TM solving this problem) cannot be a polynomial unless $P = NP$.

*This is easy to do because $|h(G_0)| \leq n$ by definition, and we could always of course prematurely determine the nonexistance of a Hamiltonian path if $|\varphi(G_0)|$ is any larger than that.


Feel dissatisfied after each submission I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly productive over the last year or so and have 3 accepted papers and two submitted papers. All of this to say that I am a fairly experienced graduate student and what I am about to describe is not anecdotal.

Every submission brings me more dissatisfaction than satisfaction. Just before I start working on a problem, me and my advisor identify a list of concrete questions that need to be answered. After lots of thinking, we have some very nice non-trivial results which gives me a lot of happiness and satisfaction. As we start to write down all of the results, inevitably, there are some more interesting variants that pop up but are much harder to make progress on. After the initial euphoria point, I feel everything seems to go downhill. There are so many variants that also need to be answered, are clearly in the purview of the problem at hand but I am not able to. By the time we submit the paper, I am so dismayed that results in the paper seem almost trivial. Perhaps this is simply tunnel vision, but I can't overcome the sadness about not being able to answer peripheral questions (although these make for a terrific conclusion section).

This has happened every single time and I am wondering if this is a common feeling. Do other people in theory community feel the same way? I am not sure if this is an academia wide feeling. My fellow graduate students from other areas are over the moon after every submission (but this is just anecdotal).

Edit - I see that there is another soft-question on the front page. I apologize for adding another one. Its holiday season and (only?) after a few drinks, one starts to ponder over these things!

Yes, it is very common. Once we spent months thinking about a problem we start to see relations so well that the solution looks trivial to us. It is not specific to academia, once we have a solution for a problem it makes the problem look easier that it really was, all the clouds that prevented us from seeing it have disappeared.

How to deal with this feeling? I haven't figured out myself but a few observations that might help:

Remind yourself what seems obvious to you is not for many others. How many people in your broad area saw the solution beforehand?

For most results (and most results are not break through results) I think it is the case that someone else in our field who is smart enough could have figured it out as well. This also has an effect that we feel we are not so special after all. Well, we are not! Once we accept that there are others who are smart enough and deal with our ego and become humbler we tend to have higher satisfaction from our contributions. Yes, X, Y, and Z could have done it as well. But we were the person who put the effort to actually do it.

Another one is to pay more attention to what problem we decide to work on. Be very clear with yourself why you want to work on a problem. Don't do so just because it looks interesting or difficult or others say it is interesting. How would knowing the solution to the problem affect our understanding and world? If we are clear about that then the fact that the solution to the problem looks simple wouldn't bother us, it would delight us instead. This might be difficult though for a student, you have to pick a problem that is meaningful and solvable. It is harder in more pure areas than applied sides. And often we don't end up solving the real meaningful problem but make some meaningful advance towards it. Keep in mind that is also valuable. Even our failures can be valuable if we can share the insights we obtained from them with others.

There is also how others judge our contribution. It is will known some areas of theory have a problem of valuing technical heavy lifting more than some meaningful contributions. Don't let them discourage you. In the long term, most of those technical heavy liftings will be forgotten, don't allow the facade to discourage you from working on meaningful problems.

Lots of young researchers focus on proving themselves. Focus instead on building good and meaningful collaborations with others to work on meaningful problems. That is much more important in the long term. With some luck you will end up with some significant meaningful contribution.


Is $ALL\setminus(RE \cup co-RE)$ empty? Possible Duplicate:
  Are there languages that are not in RE nor CO-RE?

Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or complement-recognizable? If such a language exists, I believe it would be very interesting to study it (if it is possible!).

I'm posting my comment as an answer, at the request of the OP.

Arithmetic Hierarchy AH is a class of decision problems defined as below:

Let $Δ_0 = \Sigma_0 = \Pi_0 = R$. Then for $i>0$, let

$Δ_i = R^ {\Sigma_{i-1}}$.
$\Sigma_i = RE ^{\Sigma_{i-1}}$.
$\Pi_i = coRE ^{\Sigma_{i-1}}$.

Obviously, AH $\subseteq$ ALL. On the other hand, "each level of AH strictly contains the levels below it." (As pointed by Robin Kothari in a comment above). Therefore, $ALL\setminus(RE \cup coRE)$ is nonempty.


Turing Machines as Coalgebras I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations of DFA, NFA, Mealy machines, Moore machines, context-free grammars, and even simple quantum systems. I have not found a good source for representing a Turing Machine as a coalgebra.

Any sources/thoughts?

Thanks!

Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and $\rhd$ represent thereby the tape moves.

Bart Jacobs has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He present a Turing machine with $n$ states as a coalgebra for functor $\mathcal{P}_{\mathrm{fin}}[n]$ on sets. Alternatively, consider the type $\mathbb{T} = 2^\mathbb{Z} \times \mathbb{Z}$ that represents the tape and the position of the head on the tape. A Turing machine with $n$ states is then also an endomorphism   on $2^n \otimes \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$ in the category of join-semilattices, or an $n \times n$-matrix of coalgebras $\mathbb{T} \to \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$.

The most advanced approach to Turing machines (and also push-down automata) is given by Goncharov et al. The authors give presentations of monads for these types of machines by generators and equations, they show how represent rational behaviour by means of fixed point expressions and prove various other properties. In particular, they also study the language semantics of such machines.

I hope this helps.


Surprising algorithms for counting problems There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples include:

Counting perfect matchings in a planar graph (the FKT algorithm), which is the basis for how holographic algorithms work.
 Counting spanning trees in a graph (via Kirchhoff's matrix tree theorem).

A key step in both of these examples is reducing the counting problem to computing the determinant of a certain matrix. A determinant is itself, of course, a sum of exponentially many things, yet can surprisingly be computed in polynomial time.

My question is: are there any "surprisingly efficient" exact and deterministic algorithms known for counting problems which do not reduce to computing a determinant?

I don't know if the following problems reduce or not to computing the determinant, but I will list anyway:

1) Counting the number of paths in a DAG from a node $v_0$ to a node $v_f$.
But this is not surprising. Simply determining whether $v_f$ is reachable from $v_0$ is in NL, and thus in DET. I have no idea about the counting version.

2) Counting the number of solutions of problems definable in MSO-logic in structures of bounded Tree width.  See for example the paper which buids on works of Courcelle, Arnborg and others.

3) If you have a function $f:\{0,1\}^{n}\rightarrow \{0,1\}$, that can be expressed by a bolean circuit of logarithmic tree width, than you can
count the number of inputs $x$ such that $f(x)=1$ by devising a quantum
circuit $U_f$ which sends $|x\rangle|0\rangle$ to $|x\rangle|f(x)\rangle$,
and classically simulating the probability of measuring $|1\rangle$ in the
second register after the application of $U_fH^{\otimes n}|0\rangle|0\rangle$ using these results.


off-policy and offline policy reinforcement learning What's the difference between

  off-policy reinforcement learning
  algorithms

and

  offline policy reinforcement learning
  algorithms ?

Or do they mean the same thing ?
thanks

I assume that you know what "policy evaluation" means. Briefly speaking, it refers to the task of estimating the value of a given policy.

In the RL literature, the off-policy scenario refers to the situation that the policy you want to evaluate is different from the data generating policy. In other words, you behave in one way, but you want to evaluate the value of another policy. This should be contrasted with the on-policy scenario that the policy you want to evaluate is the same policy that generates (or generated) data.

The offline sampling scenario (and not "offline policy") is the scenario that you already have some samples and now you want to perform tasks like policy evaluation. In this scenario, the agent cannot have any further interaction with the environment. In other words, the data are given and fixed. This should be contrasted with the online sampling scenario that the agent actually interacts with the environment.

These two are orthogonal. So it is possible to have a on-policy/off-policy offline/online scenario.

Hope my short discussion has helped. You may also take a look at Sutton and Barto's textbook.

Amir massoud


Is abelian group isomorphism in $\mathsf{AC^0}$? An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time  to $O(n \log n)$. In 2007, Kavitha showed that abelian group isomorphism can be done in linear time i.e. $O(n)$ time.

I know that abelian group isomorphism when groups are given by table representation is in $\mathsf{TC^0}$. Is there any research paper or article which shows that it is in $\mathsf{AC^0}$? I tried to google but get only the result that it is in $\mathsf{TC^0}$.

  Question : Is abelian group isomorphism ( groups given in table representation ) in $\mathsf{AC^0}$

Contrary to what is stated in the question, abelian group isomorphism is not known to be in $\mathrm{TC^0}$. Needless to say, this also means it is not known to be in $\mathrm{AC^0}$.
What is known is the following observation from [1]. Let $\mathrm{pow}$ denote the following problem: given a multiplication table of an abelian group $(A,{\cdot})$, elements $a,b\in A$, and $m$ in unary, determine if $b=a^m$. The structure theorem for finite abelian groups easily implies that if $A,B$ are two such groups of size $n$, then
$$\tag{$*$}A\simeq B\iff\forall m\le n\:\bigl|\{a\in A:a^m=1\}\bigr|=\bigl|\{b\in B:b^m=1\}\bigr|.$$
Since we can count polynomial-size sets in $\mathrm{TC^0}$, we obtain

Proposition 1: Abelian group isomorphism is computable in $\mathrm{TC^0(pow)}$.

Now, $\mathrm{pow}$ is clearly computable in L, and as shown in [2], also in the class FOLL. Thus,

Corollary 2: Abelian group isomorphism is computable in $\mathrm{L}$ and in $\mathrm{TC^0(FOLL)}$.

It is not known if $\mathrm{pow}$ is computable in $\mathrm{TC^0}$.
It seems that Corollary 2 is the best known result when it comes to the usual, “polynomial-size”, circuit classes. However, I observe that the problem is in the quasipolynomial version of $\mathrm{AC^0}$:

Proposition 3: Abelian group isomorphism is computable by a uniform sequence of quasipolynomial-size constant-depth Boolean circuits; more specifically, it is in $\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$.

(This translates into a uniform family of depth-3 circuits of size $2^{O((\log n)^2)}$, where the bottom disjunctions have fan-in only $O\bigl((\log n)^2\bigr)$; this is often called “depth $2\frac12$”.)
Proposition 3 is again a consequence of the structure theorem for finite abelian groups: any such group can be written as a direct sum of $O(\log n)$ cyclic subgroups, thus groups $A$ and $B$ are isomorphic iff they can be written as direct sums of cyclic subgroups with matching orders: that is, if $|A|=|B|=n$, then $A\simeq B$ iff

there exist

a sequence $\{m_i:i<k\}$ of $k\le\log n$ integers $m_i\le n$

sequences $\{a_i:i<k\}\subseteq A$ and $\{b_i:i<k\}\subseteq B$

such that

$\prod_{i<k}m_i=n$

$a_i^{m_i}=1$ and $b_i^{m_i}=1$ for each $i<k$

for all sequences $\{r_i:i<k\}$ of integers $0\le r_i<m_i$, not all zero:
$\prod_{i<k}a_i^{r_i}\ne1$ and $\prod_{i<k}b_i^{r_i}\ne 1$

The two main quantifiers are highlighted. To see that the stated bounds are not exceeded, we need to show that the identities $\prod_{i<k}a_i^{r_i}=1$ can be checked in $\mathrm{NTIME}\bigl((\log n)^2\bigr)$. This can be done by successively guessing and verifying values of the partial products $\prod_{i<l}a_i^{r_i}$ for $l=0,\dots,k$; moreover, for each $i$, we similarly guess and verify $O(\log r_i)$ partial results of the computation of $a_i^{r_i}$ by repeated squaring. In total, this makes $O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$ guesses, each of which takes $O(\log n)$ time to verify.
There is another way to prove Proposition 3: namely, note that in $(*)$, we only need to consider $m$ that are prime powers: $m=p^e$. In that case, the two offending sets that we need to count also have sizes that are powers of $p$; in particular, if they are unequal, they differ by a factor of at least $p$. Thus, it is enough to count the sizes of the two sets approximately. This can be done in quasipolynomial $\mathrm{AC^0}$ using Sipser’s coding lemma. And as I’ve already shown, $\mathrm{pow}$ can be computed in quasipolynomial $\mathrm{AC^0}$ by repeated squaring.
One consequence of Proposition 3 is that if the abelian isomorphism problem turns out not to be in $\mathrm{AC^0}$, this might be rather difficult to prove: in particular, one cannot just reduce PARITY or MAJORITY to the problem, as these require exponential-size bounded-depth circuits, not quasipolynomial. Even if we attempt to reduce PARITY on $m\ll n$ bits to the problem, there is not much room for the parameters: specifically, PARITY of super-polylogarithmically many bits is not computable by quasipolynomial-size constant-depth circuits, and PARITY of polylogarithmically many bits is already computable in $\mathrm{AC^0}$ by divide and conquer.
References:
[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph isomorphism is not $\mathrm{AC^0}$-reducible to group isomorphism, ACM Transactions on Computation Theory 5 (2013), no. 4, article no. 13, doi: 10.1145/2540088.
[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: On the complexity of some problems on groups input as multiplication tables, Journal of Computer and System Sciences 63 (2001), no. 2, pp. 186–200, doi: 10.1006/jcss.2001.1764.


Properties expressible in 2-CNF or 2-SAT How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)?  Are there any games, such as pebble games?  It seems that the classical black pebble game and the black-white pebble game are unsuitable for this (they are PSPACE complete, according to Hertel and Pitassi, SIAM J of Computing, 2010).

Or any techniques other than games?

Edit:  I was thinking of properties that involve counting (or cardinality) of an unknown predicate (SO predicate, as finite model theorists would say).  For example, as in Clique or unweighted Matching.
(a) Clique: Is there a clique $C$ in the given graph $G$ such that $|C| \ge$ some given number $K$? $~$ (b) Matching: Is there a matching $M$ in $G$ such that $|M| \ge K$?

Can 2-SAT count?  Does it have a counting mechanism?  Seems doubtful.

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


(How) Could we discover/analyze NP problems in the absence of the Turing model of computation? From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to reason about them in any meaningful way with just the functional point of view? Would it even be possible?

I've been mulling on this question purely from a point of self inquiry as part of learning the lambda calculus model of computation. I understand that it's "non-intuitive" and that's why Godel favored the Turing model. However, I just wish to know what are the known theoretical limitations of this functional style of computation and how much of a hindrance would it be for analyzing the NP class of problems?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM machine, etc. A good place to start looking is this Lambda the Ultimate post, which has some good further references.

Section 7.4 of Bob Harper's Practical Foundations for Programming Languages explains the costs semantics.

The paper On the relative usefulness of fireballs by Accattoli and Coen shows that $\lambda$-calculus has at most linear blowup with respect to RAM machine model.

In summary, on this other planet things would be pretty much the same with regards to NP, but there would be fewer buffer overflows, and there wouldn't be as much garbage lying around.


Worlds Relative to Which "Invulnerable Generators" Do Not Exist Invulnerable generators are defined as follows:

Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it produces instance-witness pairs $(x, w) \in R$, with $|x| = n$, according to a distribution under which any polynomial-time adversary who is given $x$ fails to find a witness that $x \in S$, with noticeable probability, for infinitely many lengths $n$.

Invulnerable generators, first defined by Abadi et al., found many applications in cryptography.

Existence of the invulnerable generators is based on the assumption that $\mathbf{P} \neq \mathbf{NP}$, yet this is possibly not sufficient (see also the related topic).

Theorem 3 of Abadi et al. paper, cited above, shows that any proof of the existence of invulnerable generators does not relativize:

Theorem 3. There is an oracle $B$ such that $\mathbf{P}^B \neq \mathbf{NP}^B$, and invulnerable generators do not exist relative to B.

I don't understand a part of the proof of this theorem.
Let $\sqcup$ denote the disjoint union operation.
Let $QBF$ be the PSPACE-complete language of satisfiable quantified Boolean formulas, and let $K$ be an extremely sparse
set of strings of maximum Kolmogorov complexity. Specifically, $K$ contains one string of each length $n_i$, where the sequence $n_1, n_2, \ldots$ is defined by: $n_1 = 2$, $n_i$ is triply exponential in $n_{i-1}$, for $i > 1$; if $x \in K$ and $|x| = n$, then $x$ has Kolmogorov complexity $n$.

  The paper states that relative to $B = QBF \sqcup K$, it holds that $\mathbf{P} \neq \mathbf{NP}$. Can you explain? (Also, please clarify whether $B$ is recursive.)

If they were simply talking about (non-resource-bounded) Kolmogorov complexity, then $K$ would be uncomputable (otherwise you could use a machine computing $K$ to give short descriptions of the strings $x \in K$, since all you need to do is describe the machine and the length $n$ of $x$, and we have $K(x) = n$ yet $K(n) \leq \log n$), hence $B$ would be uncomputable as well.

However, the paper Abadi et al. reference (Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. FOCS 1983.) uses a resource-bounded version Kolmogorov complexity.  Let $U$ be an efficient universal Turing machine. Define $K_U[f(n), g(n)]$ to be the sets of strings $x$ such that there is a string $d$ of length $|d| \leq f(|x|)$ such that $x = U(d)$ and the computation of $U(d)$ takes at most $g(|x|)$ time. At the top of the second column on p. 444 of that paper, Hartmanis describes how to use this concept to construct a (computable) oracle relative to which $P \neq NP$.

Here is Hartmanis' idea, adapted to the Abadi et al. result.  Let $tow_3(1)=2$ and $tow_3(n+1)=2^{2^{2^{n}}}$ (which I believe is the function you described). By standard diagonalization (e.g. as in the time hierarchy theorem), construct a tally set $C$ such that $C \subseteq \{1^{tow_3(n)} : n \geq 1\}$ and $C \in TIME[n^{\log n}] - P$. Now place the first string of length $tow_3(n)$ from $K[\log n, n^{\log n}] - K[\log n, n^{\log \log n}]$ into $K$ iff $1^{tow_3(n)} \in C$. Since $C = \{1^n : (\exists x)[|x|=n \text{ and } x \in K]\}$, we have $C \in NP^{K}$.

We also have $C \notin P^{K}$, hence $P^K \neq NP^K$. Suppose for the sake of contradiction that $C \in P^{K}$. Then there is a poly-time oracle machine $M$ such that $C = L(M^K)$. I claim that this implies $C \in P$ (without the oracle!), contradicting the construction of $C$. Here's the poly-time algorithm: on input $x = 1^{tow_3(n_0)}$:

Compute all strings in $K$ of length strictly less than $|x|$. This can be done in polynomial time because all such strings have length at most $\log \log \log |x|$, and we just need to test the computation of $U(d)$ on even smaller strings $d$, for amounts of time that are still very small compared to $|x|$.
Run $M(x)$, simulating oracle queries to smaller strings with the results of (1). If $M(x)$ ever queries a string of length $|x|$, simulate that query with a "NO" answer.

The reason step (2) works it that, for sufficiently large input lengths, if there is a string $y \in K$ of that length, $M^K$ cannot query $y$, so we can simulate all such queries with a NO answer.  If it did query $y$, then we would have $y \in K[\log n, n^k]$ (where $n^k$ bounds the run-time of $M$), contradicting the fact that we chose $y$ to be not in $K[\log n, n^{\log \log n}]$.


How do database aggregations form a monoid? On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package.

The github page has some clues:

  Implementations of Monoids for interesting approximation algorithms,
  such as Bloom filter, HyperLogLog and CountMinSketch. These allow you
  to think of these sophisticated operations like you might numbers, and
  add them up in hadoop or online to produce powerful statistics and
  analytics.

and in another part of the GitHub page:

  It was originally developed as part of Scalding's Matrix API, where
  Matrices had values which are elements of Monoids, Groups, or Rings.
  Subsequently, it was clear that the code had broader application
  within Scalding and on other projects within Twitter.

Even Oskar Boykin of Twitter chimed in:

  The main answer is that by exploiting semi-group structure, we can
  build systems that parallelize correctly without knowing the
  underlying operation (the user is promising associativity).

  By using Monoids, we can take advantage of sparsity (we deal with a
  lot of sparse matrices, where almost all values are a zero in some
  Monoid).

  By using Rings, we can do matrix multiplication over things other than
  numbers (which on occasion we have done).

  The algebird project itself (as well as the issue history) pretty
  clearly explains what is going on here: we are building a lot of
  algorithms for aggregation of large data sets, and leveraging the
  structure of the operations gives us a win on the systems side (which
  is usually the pain point when trying to productionize algorithms on
  1000s of nodes).

  Solve the systems problems once for any Semigroup/Monoid/Group/Ring,
  and then you can plug in any algorithm without having to think about
  Memcache, Hadoop, Storm, etc...

How are Bloom filters / hyperloglog / countminsketch like numbers?

How is it that database aggregations have a monoidal structure?
What does this monoid look like?  Do they ever have group structure?

Literature references would be helpful.

You ask why database aggregations have monoidal structure.

Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, vectors, matrices, probability distributions, sets, or anything else we want to store and manipulate.  So we denote the "aggregation" of $a$ and $b$ by $a.b$.

The operation $.$ is usually associative, since we don't want the order in which it is applied to affect the result: we want $(a.b).c = a.(b.c)$.  So we have a semigroup.

Almost always there is some kind of identity, whether it is the number 0 or 1, the empty string, an identity matrix, a uniform distribution, or the empty set, which depends on the operation.  So in fact data usually forms a monoid.

The practical point about thinking of data as forming a monoid is that it provides a way to discuss operations on different kinds of data using a common algebraic language.  This then translates into generic code libraries that can deal with any monoids, by simply passing an appropriate aggregation operation as an argument.

Note that many kinds of data do not have inverses, so a group structure is too much to hope for.  If you have group structure then some additional ways of manipulating the data become possible, but since neither matrices with multiplication, nor the positive integers with addition have inverses, non-group-structured data is quite common.

We don't usually want to just store data, but to run queries over the database.  So we need some notion of what to do when a query generates many answers.  Often this requires a combining operation $+$ (which may be the same as $.$), and which should be compatible with $.$ in the way they interact.  So some kind of distributivity is needed.  Commutativity of $+$ and sometimes also of $.$ is also often natural.  We then have a semiring or a commutative semiring.  Again inverses are usually too much to hope for, so semirings are a better fit than rings.

A semiring model of data aggregation has been around in the constraint satisfaction community for some time.  Note that a constraint satisfaction problem instance is a conjunctive query over a particular database of facts, so this is pretty general: most practical queries over data are conjunctive.

Stefano Bistarelli, Ugo Montanari, and Francesca Rossi,
Semiring-based constraint satisfaction and optimization,
JACM
44(2),
1997,
201–236.
doi:10.1145/256303.256306

The current spurt of theoretical analysis of the semiring model of data aggregation was kick-started in 2007, in the context of provenance.  Provenance is a fancy term for annotating data.  Since any database tuple can be seen as annotations applied to some unique tuple identifier, aggregation of data can be seen as just combination of annotations.  Provenance is therefore a generalization of the idea of aggregating data, and it has explicitly been argued that the right theoretical model of combining annotations is a semiring.  The most general semiring, of provenance polynomials, actually allows one to keep track of the entire history of how a piece of data was obtained from constituent parts.  As an example, a p-value in the analysis of a clinical trial can keep track of how it was calculated from each of the individual trial results.  If some of them turn out to be wrong (or fake) then one can simply recalculate without the bad data.

Todd J. Green, Grigoris Karvounarakis, and Val Tannen, Provenance semirings, PODS 2007, 31–40.
doi:10.1145/1265530.1265535

There has been a lot of further work using semirings to aggregate data, see the papers citing this one.

From the more immediately practical perspective that you cite, see for instance the GDL framework for how one can effectively parallelise a computation by grouping the underlying semiring expression appropriately.

Srinivas M. Aji and Robert J. McEliece,
The generalized distributive law,
IEEE Transactions on Information Theory
46(2),
2000,
325–343.
doi:10.1109/18.825794


An optimization problem I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\Vert^2=1, \hat{x}\in \mathbb{R}^d$.
Without the absolute value inside the summand, the solution is easy, the optimal solution is achived by the unit vector along the vector $\sum_{p\in P}\Vert p\Vert p$. But with the absolute value in the picture, I failed to find a solution. Can this problem be solved by techniques of optimization literature?
Thanks
p.s.
This problem has some superficial similarities with Chebyshev approximation problem:
$minimize \max_i \vert a_i^Tx-b_i\vert$. The aforementioned problem involves $l_\infty$ norm, whereas the original problem deals with $l_1$ norm.

The problem as described is not convex, due to the nonconvexity of the constraint set. However, if you were to permit a relaxation, we could write your problem as
$\begin{array}{ll}
\max & \sum_{p\in P} t_p\\
\text{subject to }& t_p \geq \langle x, \|p\| p \rangle\\
& t_p \geq -\langle x, \|p\| p\rangle ,\\
&  \|x\|_2 \leq 1.
\end{array}$
This is a second-order cone program, which can be solved by standard methods.
It is probably not trivial to recover a solution to your original problem from this relaxation (for instance, Goemans-Williamson wrote a breakthrough paper describing the rounding algorithm for a similar relaxation). But maybe this is helpful in some way.
edit -- As pointed out by Neal Young, there is an error in the above answer. The question in the original post is a maximization of absolute value function, which isn't a convex objective; so, my reduction is incorrect. I am leaving the incorrect answer here in case someone finds any information in it useful, but please see Neal Young's comments below for more comprehensive (and correct) observations about the problem.


Initial conditions for universal Rule 110 In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer.

I was wondering what specific initial conditions are used to model basic computations.  For the sake of specificity, my question is--what initial conditions do I have to give Rule 110 if I want to simulate $1 + 1$?

Note:  On page 681, Wolfram provides pictures of "black elements" and "white elements" in Rule 110, but it is hard to tell which initial conditions created them.  On page 1116 (in the "Notes" section), he gives Mathematica code to set up the cyclic tag system.  But I want to know specifically which initial conditions will simulate the computation $1 + 1$.

the rule 110 initial condition constructions are extremely intricate even for simple computations and generally cannot be constructed by hand. one would generally start with a real/concrete TM [turing machine] built to compute your problem, ie the complete state table (TMs are of course alluded to in thousands of TCS papers but rarely actually built directly).

generally the papers build initial conditions using complex algorithmic conversions to tag systems. the cook paper cited by DE in comments above[1] does improve the simulation time by a polynomial instead of exponential construction. in other words, theres more than one way to create suitable initial conditions. another recent construction with emphasis on regular languages by martinez et al can be found[2]. the authors of the papers generally do not seem to release code they used to construct their paper results [scanning the two papers below], a legitimate complaint that could be made of much research papers in TCS which tend to give short shrift to experimental approaches[3] even as they seem to focus on them.

so once you have the TM alphabet and state table one runs the conversion algorithms described but not really explicitly/manifestly implemented in the papers [because no code is given, only a prose description of the algorithm(s)] which take the TM alphabet and state table as input and then output a tag-system setup and 110 initial tape conditions that simulates the TM. my understanding is that in some cases, an infinite periodic starting "tape" pattern may be required.

in their papers they do not even seem to mention what coding languages they use for their simulations/experiments. they might release code if you contact them directly. therefore wolframs release/publishing of some mathematica code you mention above [nice but now rather dated based on later developments in the area] seems to be an exception in this area. therefore to actually independently construct concrete machines built using these techniques a researcher might have to reimplement the algorithms described in the papers.

footnote: the exact TM problem must be defined with some care because in your case, does a TM that simply erases and outputs 2 to its tape compute 1+1? you probably want a TM that computes $a+b$ and starts with input 1,1 on the tape.

[1] A concrete view of rule 110 computation by matthew cook

[2] Reproducing the cyclic tag system
developed by Matthew Cook with
Rule 110 using the phases fi_1 by Martinez et al

[3] Is "Experimental Complexity Theory" being used to solve open problems?


Is this optimum travelling problem under deadlines NP-hard on trees? One of my friends asks me the following scheduling problem on tree. I find it is very clean and interesting. Is there any reference for it?

Problem:
There is a tree $T(V,E)$, each edge has symmetric traveling cost of 1. For each vertex $v_i$, there is a task which needs to be done before its deadline $d_i$. The task is also denoted as $v_i$. Each task has the uniform value 1. The processing time is 0 for each task, i.e., visiting a task before its deadline equals finishing it. Without loss of generality, let $v_0$ denote the root and assuming there is no task located at $v_0$. There is a vehicle at $v_0$ at time 0. Besides, we assume that $d_i \ge dep_i$ for every vertex, $dep_i$ stands for the depth of $v_i$. This is self-evident, the vertex with deadline less than its depth should be taken as outlier. The problem asks to find a scheduling which finishes as many tasks as possible.

Progress:

If the tree is restricted to a path, then it is in $\mathsf{P}$ via dynamic programming.
If the tree is generalized to a graph, then it is in $\mathsf{NP}$-complete.
I have a very simple greedy algorithm which is believed 3-factor apporoximation. I have not proved it completely. Rightnow, I am more interested about the NP-hard results. :-)

Thanks for your advice.

For this to be true, we have to make some assumptions. See comments below

For the tree case, I believe that there is a polynomial time recursive dynamic programming algorithm parameterized by the maximum deadline time. The sub-problems are: if we enter a sub-tree by time $t_a$ and exit the sub-tree by time $t_b$, what is the maximum number of tasks we can finish in the sub-tree? The base cases at the leaves are easy and we memoize from the bottom up.

If we truly parameterized by the maximum deadline time, then the algorithm would not really be polynomial in the size of the tree. However, the length of the longest path that visits every node in the tree is only polynomial in $|V|$, and we never need to check deadline times later than that.


Enumeration given a product of primes Given a list of (small) primes $ (p_0, p_1, \dots, p_{n-1})$, is there an (efficient) algorithm to enumerate, in order, all numbers that can be expressed as $ \prod_{k=0}^{n-1} p_k^{e_k} $, where $e_k \in \mathbb{Z}, e_k \ge 0 $?  What about in a certain interval, potentially at an exponential starting point?

For example, if we had the set $(2,3,5)$, the first few numbers would be $(2, 3, 2^2, 5, 2 \cdot 3, 2^3, 3^2, 2 \cdot 5, \dots )$.

Is there an algorithm to efficiently enumerate all the numbers not expressible as a product of powers of primes from the set?  How about in an interval?

Note:  I just saw the Polymath paper on deterministic prime finding in an interval ( Deterministic methods to find primes ) and thats what inspired this question.  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.

EDIT: I was unclear by what I meant by 'efficient' .  Let me try making it more precise:

Given a list of $n$ primes $(p_0, p_1, \dots p_{n-1})$ and a bound, $B$, is it possible to find in polynomial time with respect to $lg(B)$ and $n$, the next integer, $x$, such that $x > B$ and is expressible as a product of powers of primes from the list?

You can generalize the standard algorithm for enumerating Hamming numbers in increasing order by merging with a min-heap. The Hamming numbers are the numbers expressible with primes 2, 3 and 5.

If you can enumerate the expressible numbers in order, the non-expressible numbers are easily found in the successive gaps. To solve the problem for an interval [i, j], find the greatest expressible number less than i and the least expressible number greater than j, and use that to initialize and terminate the algorithm.

Edit: I forgot to mention how you might efficiently find the bounds for the interval problem. Modified bisection should work. You have an exponent sequence as your current guess. For each individual exponent split the difference as in bisection, yielding n variants, and then find the numerically smallest of the variants (or the largest, depending on whether you're searching for lower or upper bounds), and use that as your next guess.

  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.

No, it doesn't matter. If you use the algorithm I suggested, the effect of allowing composites is that you generate duplicates when unique factorization fails; this happens when two or more numbers in the generating set aren't relatively prime. For generators 2 and 4, the sequence goes

1 = 2^0 4^0, 2 = 2^1 4^0, 4 = 2^2 4^0, 4 = 2^0 4^1, ...

Any duplicates will occur in contiguous runs, so they are easily filtered out without keeping a black list. You could also kill them upon insertion in the min-heap.


Spectral techniques for genus of a graph A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.

It is NP-hard to approximate the genus of a graph to within an additive error of $O(n^\epsilon)$.  There are polynomial-time algorithms that compute an embeddings of genus $O(g\sqrt{n})$ or  $\max\{4g, g+4n\}$, where $g$ is the true genus and $n$ is the number of vertices.  A significantly better approximation algorithm, spectral or otherwise, would be a significant breakthrough!

See: Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. A note on approximating graph genus.  Information Processing Letters 61(6):317–322, 1997.


Sufficient conditions for the collapse of Polynomial Hierarchy (PH) What are some (not well-known) assertions that if true, the PH must collapse?

Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much luck.

There are a (growing) number of parameterized complexity results where the existence of a polynomial-sized kernelization implies the collapse of the PH to the third level. The central technique is given in [1], building on prior work (referenced in [1]).

As a simple example, the $k$-Path problem is the parameterized version of the Longest Path problem:

  $k$-Path
  Instance: A graph $G$ and integer $k$.
  Parameter: $k$.
  Question: Does $G$ contain a path of length $k$?

This problem is in FPT (with somewhat practical algorithms), but in [2] they show that if it has a polynomially sized kernel (in $k$), then the PH collapses to $\Sigma^{P}_{3}$. (The current presentation is typically phrased as a negative kernalization result unless NP $\subseteq$ coNP/poly or coNP $\subseteq$ NP/poly, so searching for something like "no polynomial kernel unless" nets a lot of results.)

References

H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, "Kernelization lower bounds by cross-composition", SIAM J. Discrete Math., 28 (2014), pp. 277–305. [arXiv version]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, D. Hermelin, "On problems without polynomial kernels", Journal of Computer and System Sciences, 75(8):423-434. 2009. [Stanford hosted version]


Is the following optimization problem (a variant to a previous problem) NP-hard? This problem is a following up question on  this one. The only difference is the newly added constraint in the bold font.

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$

Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.

This is easy to solve in polynomial time.

To see this, it may be easiest to interpret $S$ as a preorder $\le$ on $N$:

$i \le j$ iff $(i,j) \in S$ or $i = j$.

Then we define the equivalence relation $\sim$:

$i \sim j$ iff $i \le j$ and $j \le i$.

Now let $W$ consist of all equivalence classes of $\sim$; for each $i \in N$ let $[i] \in W$ be its equivalence class. Put otherwise, $[i]$ consists of all $j \in N$ such that $(j,i) \in S$ and $(i,j) \in S$. Now we can define the natural partial order $\le'$ on $W$:

$[i] \le' [j]$ iff $i \le j$ for each $i,j \in N$.

We say that $[i] \in W$ is maximal if $[i] \le' [j]$ implies $[i] = [j]$. We have the following property that is easy to verify:

If $[i]$ is maximal, we cannot get the benefit $c(j)$ for all $j \in [i]$.

Hence in any solution, for every maximal class $[i]$, we have to choose at least one node $j \in [i]$ such that we do not get the benefit of $c(j)$.

We now construct a solution as follows: For each maximal class $[i]$, choose a node $j \in [i]$ that minimises $c(j)$; we say that $j$ is a sink node. Now assume that $k \in N$ is not a sink node. There are too cases:

$k \in [i]$, where $[i]$ is maximal. Now we can simply choose the edge $(k,j) \in S$, where $j \in [i]$ is a sink node, and collect the benefit of $c(k)$.
$k \in [i]$, where $[i]$ is not maximal. Then there is a maximal set $[\ell]$ with $[i] \le [\ell]$. Let $j \in [\ell]$ be the sink node, choose the edge $(k,j) \in S$, and collect the benefit of $c(k)$.

That is, we can get the benefit of $c(k)$ for all nodes $k \in N$ that are not sink nodes; the solution is optimal.


"forward-secure" zero knowledge protocols Has anything been done on the modification of the zero knowledge condition

where the distinguisher has access to the witness used by the prover and

the random bits used by the algorithm that generated the auxiliary input?

(Or is that, in fact, how the zero knowledge condition is usually defined?)

This seems like it would be important for using ZK protocols as pieces of larger protocols,

since whether or not an adversary succeeds could depend on that information.

Regarding the prover's witness, the standard zero-knowledge (ZK) definitions already imply that ZK holds even if the distinguisher is given this witness.

I'm not sure what you mean by "the random bits used by the algorithm that generated the auxiliary input". Please clarify.


Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$? Quasi-polynomial time, or QP for short, is a complexity class on deterministic Turing machine. Here is the precise definition:https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

While βP is a complexity class of limited nondeterminism. Here is the precise definition: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

It is easy to see that any machine of βP can be simulated by a machine of QP, namely, βP $\subseteq$ QP.

But do we have an example, a problem that is in QP but not in βP, even if we just have no precise proof that the problem is not in βP?

While I don't know a specific (conjectured) example in $QP-\beta P$, there is still rather compelling evidence that $\beta P$ is a proper subset of $QP$. Namely, these classes behave very differently in their relationship to $NP$:

$\bullet$ It is obvious from the definition that $\beta P\subseteq NP$.

$\bullet$ On the other hand, $QP\subseteq NP$ is not known, and it would be very hard to prove, since it implies $P\neq NP$. (In fact, it is an even stronger statement than $P\neq NP$.)

Such a very different behavior relative to $NP$ seems to provide a fairly strong reason to believe that $\beta P\neq QP$.


Consequences of faster parameterized integer programming Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.

Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)$ under the assumption the integer programming problem we have had at most $1$ solution?

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.

Hence if integer programming in $k$ variables can be solved in time $k^{O(k^\alpha)}$ for some $\alpha < 1$, then CNF-SAT with arbitrarily long clauses can be solved in $k^{O(k^\alpha)} = 2^{O(k^\alpha \cdot \log k)}$, which would contradict the Strong Exponential Time Hypothesis since $c \cdot k^\alpha \cdot \log k < k$ for any constant $c$, $\alpha < 1$, and sufficiently large $k$.


Shortest formula for an n-term monotone CNF A monotone CNF formula with m terms on n variables ($x_1,\ldots,x_n$) is a formula of the form $f(x_1,\ldots,x_n) = \bigwedge C_i$, where each $C_i$ is an OR of some subset of the variables $x_1,\ldots,x_n$, and $i$ ranges from $1$ to $m$.

For example, $(x_1 \vee x_3 \vee x_4) \wedge (x_2 \vee x_4)$ is a monotone CNF formula with 2 terms on 4 variables.

I'm looking for the shortest formula (not necessarily monotone, not necessarily CNF, any formula will do!) on the same set of variables that represents the same function as a given monotone CNF formula on n variables with n terms. (Note that the number of terms and variables is the same.)

One obvious way to construct a formula is to expand out the given CNF definition, which will give us a formula of size $O(n^2)$. (Let's define the size of a formula to be the length of the formula when it is written down as a string.) I want to know if this is the most efficient general construction or if for every n-term monotone CNF there exists a formula of size $o(n^2)$.

I just want to know whether this is possible, I'm not really interested in an algorithm. If this is not possible, a function that serves as a counterexample would be great. Pointers to where I can find an answer in the literature are also appreciated.

EDIT: I'm adding an example to make thins clearer.

Say the input formula is $f = (x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge \ldots \wedge (x_1 \vee x_n)$. This is a monotone CNF formula. A shorter formula which represents the same function is the following: $x_1 \vee (x_2 \wedge x_3 \wedge \ldots \wedge x_n)$.

You can get an $\Omega(n^2/\log n)$ lower bound using a counting argument: there are $exp(n^2)$ $n$-term CNFs on $n$ variables (this is easy but requires just a little care as to make sure that there is no over-counting), but there are $exp(s \log s)$ formulae (or even circuits) of size at most $s$.

It seems that winning the last $\log n$ factor will be hard since it would require proving a quadratic lower bound on formula size, and my guess is that the few existing techniques for this don't suffice.  $O(n^2/\log n)$ may even be the right answer -- at least for circuit size -- using some four-Russian-like technique.


Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm? In their paper (p. 503) Garey and Johnson remark:

  ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ...

Does anyone know some candidate problems with the properties the mentioned above?

I think the possible answer to this question can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.

I do not know if you are interested in hearing more detail of my comment on your question, but here is more detail anyway.

If P=NP, every problem in NP can be solved in polynomial time and therefore in pseudo-polynomial time, which means that no problem satisfies your requirement, as Magnus noted in his answer.  So assume P≠NP in the rest of this answer.

Because P≠NP, there exists a language L∈NP∖P which is not NP-complete (Ladner’s theorem).  Consider the following problem:

Direct product of Partition and L
Instance: m positive integers a1, …, am and k integers b1, …, bk∈{0,1}.
Question: Do both of the following hold?
(1) The m integers a1, …, am form a yes-instance of the Partition problem.
(2) The k-bit string b1…bk belongs to L.

Following the paper by Garey and Johnson, define the Length function as m+⌈log maxi ai⌉+k and the Max function as maxi ai.

It is a routine to check (i) that it is NP-complete in the weak sense, (ii) that it does not have a pseudo-polynomial-time algorithm, and (iii) that it is not NP-complete in the strong sense.

(Hints: (i) Membership to NP follows from the fact that both the Partition problem and L are in NP.  For NP-hardness, reduce Partition to this problem.  (ii) Construct a pseudo-polynomial transformation from L to this problem.  (iii) Construct a pseudo-polynomial transformation from this problem to L by using the fact that Partition has a pseudo-polynomial-time algorithm.)

There is nothing special about the Partition problem in this construction: you can use your favorite weakly NP-complete problem with a pseudo-polynomial-time algorithm.


Best $\Pi_k \text{SAT}$ running time? Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$,
where $\phi(y_1, \dots, y_k)$ is boolean predicate with each $y_i$ a vector of variables, $Q_{2j-1} = \forall$ and $Q_{2j} = \exists$ at every $j\in\mathbb N$, is $\varphi$ valid?' (page $99$ in Arora book).

$ETH$ says $\text{SAT}$ and so $\Pi_1\text{SAT}=\overline{\text{SAT}}$ needs $\Omega(2^{c\cdot n_1})$ time at some $c>0$ where $n_1$ is number of variables in $y_1$.

If there are $n=n_1+\dots+n_k$ variables where each $y_i$ has $n_i$ variables then

what is the best known algorithm for $\Pi_k \text{SAT}$ at each fixed $k$?
Is there a generalized $ETH$ that applies to $\Pi_k\text{SAT}$?

These questions are discussed in detail in the paper

  Rahul Santhanam, Ryan Williams:
  "Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity"
  Electronic Colloquium on Computational Complexity (ECCC) 2013, #108
  https://eccc.weizmann.ac.il/report/2013/108/


Proof theory of biproducts? A category has biproducts when the same objects are both the products and coproducts. Has anyone investigated the proof theory of categories with biproducts?

Perhaps the best-known example is the category of vector spaces, in which the direct sum and direct product constructions give the same vector space. This means vector spaces and linear maps are a slightly degenerate model of linear logic, and I am curious what a type theory which accepts this degeneracy would look like.

Samson Abramsky and I wrote a paper about the proof theory of compact categories with biproducts.

  Abramsky, S. and Duncan, R. (2006) "A Categorical Quantum Logic",
  Mathematical Structures in Computer Science 16 (3).
  10.1017/S0960129506005275

The ideas were later developed a bit further in this book chapter:

  Duncan, Ross (2010) "Generalised Proof-Nets for Compact Categories
  with Biproducts" in Semantic Techniques in Quantum Computation,
  Cambridge University Press, pp70--134 arXiv:0903.5154v1

The full details are there, but the short version is that your logic is inconsistent, because you have a zero proof for every implication, and the rest of your proofs are equivalent to "matrices", where the matrix entries are the proofs in the biproduct-free part of the logic.  Speaking without the caveats required to make this precise, the resulting category of proofs is the free biproduct category on some category of axioms.


Finding number of cycles of length $k$ in a graph We have $f(k) n^3$ time algorithm to determine whether a graph $G$ has a cycle of length exactly $k$.
How can we find how many such $k$-cycles are present in $G$ using the same or any other algorithm.

When $k$ is part of the input, the problem of deciding if $G$ contains a simple cycle of length $k$ is NP-complete. For every fixed $k$, the problem can be solved in either $O(VE)$ time, or $O(V^\omega \log V)$ time. Flum and Grohe [1] showed that counting cycles and paths of length $k$ in both directed and undirected graphs, parameterized by $k$, is #W[1]-complete.

For $3 \leq k \leq 7$, one can count the $k$-cycles in $O(V^\omega)$ time, where $\omega < 2.376$ is the exponent of matrix multiplication. This is the result of Alon, Yuster and Zwick [2]. The paper also contains methods for finding simple cycles of length exactly $k$, where $k \geq 3$.

[1] Flum, Jörg, and Martin Grohe. "The parameterized complexity of counting problems." SIAM Journal on Computing 33.4 (2004): 892-922.

[2] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.


Maximum subset of words with Hamming distance ≥ D For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D.
(The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)

Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?

Thank you very much.

In coding theory, the quantity you are looking for is called $A_q(n, d)$, where $n$ is the length of vectors, $d$ is the minimum distance between them, and $q$ is the alphabet size (omitted when $q=2$). Characterizing $A_q(n,d)$ is a challenging open problem (with many basic questions remaining unanswered) but various asymptotic and non-asymptotic upper and lower bounds are known. See Chapter 17 of the book "The Theory of Error-Correcting Codes" by MacWilliams and Sloane for a summary of the most important ones.


Nonstandard dual parametrization of graph problems One fundamental result in parameterized complexity of graph problems is that VERTEX COVER parameterized by the solution size $k$ is fixed-parameter-tractable (FPT). On the other hand, when parameterized by the "dual parameter" $|V(G)|-k$, it becomes equivalent to INDEPENDENT SET parameterized by solution size (because any vertex cover is the complement of an independent set), and thus it is W[1]-hard.

Although this seems less natural, I am interested in the parameterized complexity of VERTEX COVER for the parameter $|E(G)|-k$. This is a larger parameter than $|V(G)|-k$. Is VERTEX COVER FPT for this parameter?

Note: I am also interested in similar parameterizations for other graph problems (e.g. DOMINATING SET). The only place where I have seen both kinds of dual parameters studied is for the hypergraph problem TEST COVER in the 2012 paper "Parameterized Study of the Test Cover Problem" by Crowston, Gutin, Jones, Saurabh and Yeo. (also on arXiv)

Edit (04/12/2016): This parameterization is also studied for the other hypergraph problem HITTING SET in the 2011 paper Kernels for below-upper-bound parameterizations of the hitting set and
directed dominating set problems by Gutin, Mones and Yeo (arXiv link).

I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution and remove them from the graph. We now have a graph $G'$ with $|E(G')|\le |E(G)|-2k$. It is easy to find a vertex cover of $G'$ with size at most $|E(G')|$. Together with the removed vertices this gives a vertex cover of size at most $|E(G)|-k$ for $G$.

If the graph does not contain a path on $2k+1$ vertices, then a DFS tree of the graph has height at most $2k+1$, and hence can be used to construct a tree decomposition of width at most $2k$. We can then solve Vertex Cover optimally with the standard algorithm for treewidth.


Efficient enumeration of the reachable leaves of nodes in a polytree A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart.

Given a polytree $T$ and a node $n \in T$, the set of reachable leaves $L(n)$ of $n$ is the set of nodes $n' \in T$ that have no child in $n'$ and such that $n'$ is reachable from $n$.

I would like intuitively to know an efficient algorithm to preprocess a polytree to be able to answer queries where I am given an arbitrary $n \in T$ and I must enumerate the contents of $L(n)$.

Specifically, a preprocessing algorithm takes as input the polytree $T$ and computes some data structure $D$ in some amount of time. An enumeration algorithm takes as input $T$, $D$, the query node $n \in T$, and the previous state $S_{i-1}$ of the enumeration (initially $S_0$ is empty), and outputs the $i$-th element $n' \in L(n)$ and a next state $S_i$ (with a special value used to signal termination of the enumeration). The enumeration, when called successively, must output exactly the elements of $L(n)$ in some arbitrary order, without outputting the same element multiple times.

What are the most efficient algorithms for this problem, in terms of preprocessing time and enumeration time? Specifically, I am looking for a linear-time preprocessing and for constant-delay enumeration, i.e., the preprocessing should take time $O(|T|)$ and, for any query node $n \in T$, each enumeration step should take $O(1)$ time. If this is known to be impossible, I am also interested in a lower bound.

[Note that we can just precompute the answer for all nodes with quadratic preprocessing time, or compute each answer on the fly with linear-time enumeration for each answer (to traverse the relevant part of $T$), hence my focus on linear-preprocessing and constant-delay.]

[Further note that, if $T$ is a directed tree, we can achieve what I request by precomputing in linear time, for each node, its first and last reachable leaf in pre-order traversal, and for each leaf, its next leaf in post-order traversal. Then we can do constant-delay enumeration by jumping to the first reachable leaf of the vertex, and go through the leaves in order until we reach the last reachable leaf of the vertex. But the extension to polytrees does not seem straightforward.]

It turns out that it is possible to do what I want with linear preprocessing and constant delay, by an argument suggested by my friend Louis. Here is my summary of his idea.

Edit: The scheme below, in a much more concise and understandable form, appears as Theorem C.1 in our recent preprint. I'm leaving the messy sketch below in case it's useful, but you should probably look at the preprint instead (the theorem and proof are independent from the surrounding material). The proof is generalized to multitrees and also refines the scheme slightly to show a logarithmic bound on memory usage.

Let's consider a polytree $P$. The linear preprocessing can insert
intermediate nodes and collapse nodes with
only one child to get a polytree which we can use to answer queries on the original polytree, so that we can assume
without loss of generality that all internal nodes of $P$ have degree exactly
2.

We will do the linear-time preprocessing bottom-up following any
topological order. For every node of $P$ that we process (whose children have
all already been processed), we will construct an index structure for
the node, which we call an "infix tree", and which may also include
pointers to other previously defined such structures (but not modify
them, of course: one can think of this as a purely functional
data structure supporting constant-delay enumeration and constant-time
union.)

The construction will work in linear time, and for any node we will be
able to enumerate its descendants in constant delay by considering its
infix tree.

There are three kinds of nodes in infix trees:

leaves, which are labeled with an explicit set of at least one and at
most four elements (which are leaves of the original polytree);
small internal nodes, which are labeled with one explicit element
and with pointers to one or two infix tree nodes;
large internal nodes, which are labeled with two explicit elements and
with pointers to one or two infix tree nodes.

We further require that there are no duplicate elements in the infix
tree, i.e., for every node $x$ of the infix tree, each leaf of $P$ appears
at most once in the labels of $x$ and its descendants. A node $x$ in
an infix tree codes a set $S(x)$ of leaves of $P$,
namely, those which appear in the node's label and its descendants (and
as we just assumed it is always duplicate-free). The idea of the infix
tree is that, by keeping around some explicit elements, we can both use
them when enumerating to make progress when visiting the nodes, and use
them when unioning two sets of descendants to have sufficiently many
elements to annotate the newly created nodes in the infix tree.

Our indexing data structure will map each node $n$ of the polytree to an
infix tree node $N(n)$ capturing exactly its reachable leaves, i.e.,
$S(N(n))$ is the set of leaves that are reachable from $n$ in $P$.
There are two claims:

we can actually do this in linear time;
when we have done this, we can enumerate in constant delay.

Let's first see why claim 2 is true. From the infix tree $N(n)$ of a node $n$ of
$P$, we can enumerate its contents in constant delay with the
following algorithm. Maintain a working list $W$ of nodes of the infix
tree to be enumerated, initially it is $\{N(n)\}$. Now, until $W$ is empty,
take its first element $x$ and do the following:

if $x$ is a leaf of the infix tree, enumerate its elements and
discard $x$
if $x$ is an internal node (small or large), enumerate its explicit
elements and add its child nodes to $W$.

It is clear that this correctly enumerates $S(N(n))$, and that it is constant
delay because at each step we enumerate something

So now let's turn to the proof of claim 1. To do this, we will proceed
bottom-up as I pointed out above, further maintaining the following
invariant: for any node $n$ of $P$, $N(n)$ is never a small internal node, so it is
either a large internal node or a leaf. In other words, small internal
nodes will only be used as an intermediate tool in the construction, but
no node of $P$ directly points to such a node in the result of the indexing.

The base case is for a leaf $n$ of $P$, where we set $N(n)$ to be a
fresh leaf node of the infix tree whose contents are $\{n\}$.

The inductive case is for an internal node $n$ of $P$ with
children $n_1$ and $n_2$, for which $N_1 := N(n_1)$ and $N_2 := N(n_2)$ have
already been prepared (and are not small internal nodes). We set $N(n)$ as
follows depending on the types of $N_1$ and $N_2$. Note that, by design, in
the nodes that we add, we will be pointing to $N_1$ and $N_2$ (and also to
their children in some cases), but that's fine provided that we don't
modify them.

If $N_1$ and $N_2$ are leaves and their explicit lists contain at most
four elements total, set $N(n)$ to be a fresh leaf node with an
explicit list which is the union of the labels of $N_1$ and $N_2$.
If $N_1$ and $N_2$ are leaves and their explicit lists contain five or
more elements total, set $N(n)$ to be a fresh large internal node
labeled with the first two elements of the union of the labels, and
whose two children are two fresh leaves with the missing elements
(the two lists can be made non-empty because there are at least two
elements left).
If $N_1$ is a large internal node and $N_2$ is a leaf, we make $N$ a fresh
large internal node labeled with the elements of $N_1$, and having one
child which is a fresh small internal node labeled with the first
element of $N_2$ and whose children are (pointers to) the children of
$N_1$. If $N_2$ has strictly more than one element, we create a fresh leaf
node containing the remaining elements of $N_2$, that we add as a second
child of $N$.
The case where $N_1$ is a leaf and $N_2$ is a large internal node is
symmetric to the case above.
If $N_1$ and $N_2$ are large internal nodes, we create a fresh large
internal node $N$ containing the elements of $N_1$, and whose children are
two fresh small internal nodes, the first one containing the first
element of $N_2$ and pointers to the children of $N_1$, the second one
containing the second element of $N_2$ and pointers to the children of
$N_2$.

This is clearly in constant time, and one can verify that the semantics
is correct, i.e., $S(N)$ is the set of reachable leaves, with no dupes:
this is obvious for leaves and proved in the inductive case from the
contents of $N_1$, $N_2$ and their children. This concludes the proof of claim 2 and the proof of the overall scheme.


Generating $k$ random bits from a pdf with entropy $H(p) = k$ All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it.
So can we formalize this as follows? Suppose I can only sample from my distribution, is there an algorithm or procedure to generate a uniform $k$ bit binary string?
Thanks for your help.

The relevance of Shannon entropy is to repeated sampling: Given $n$ independent samples from a source with binary Shannon Entropy $k$, you can extract $nk(1+o(1)$ i.i.d. uniform bits as $n$ tends to infinity with probability tending to 1. This follows e.g. from the Keane-Smorodinsky [1] finitary isomorphism theorem. See also [2]-[5] below.
[1] M. Keane and M. Smorodinsky (1979), Bernoulli schemes of the same
entropy are finitarily isomorphic. Annals of Math. 109, 397–406.
[2] P. Elias (1972), The efficient construction of an unbiased random sequence. Ann. Math. Statist. 43, 865–870.
[3] D. E. Knuth and A. C. Yao (1976), The complexity of nonuniform
random number generation. Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), 357–428. Academic Press, New York.
[4] Y. Peres (1992), Iterating von Neumann’s procedure for extracting random bits. Ann. Stat. 20, 590–597.
[5] Harvey, Nate, Alexander E. Holroyd, Yuval Peres, and Dan Romik. "Universal finitary codes with exponential tails." Proceedings of the London Mathematical Society 94, no. 2 (2007): 475-496.


Problems Between P and NPC Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete.  What are some other (sufficiently different) natural problems that share this property?  Artificial examples coming directly from the proof of Ladner's theorem do not count.

Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?

Here's a collection of some of the responses of problems between P and NPC:

Factoring
Isomorphism problems: Graph Isomorphism [not NPC unless $\sum_2^p=\prod_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, Ring Isomorphism and Automorphism (via @Joshua Grochow)
Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
The Turnpike Problem of reconstructing points on line from distances (via @Suresh Venkat)
Problems arising from the Unique Games Conjecture (via @Moritz)
Discrete Log Problem and others related to cryptographic assumptions (via @Joe Fitzsimons)
Determining winner in parity games (via @mashca)
Determining who has the highest chance of winning a stochastic game (via @Peter Shor on MO)
Numbers in boxes problems (via @Joshua Grochow)
Agenda control for balanced single-elimination tournaments (via @virgi)
Knot triviality (via @JeffE)
(Assuming NEXP≠EXP) padded versions of NEXP-complete problems (via @Joshua Grochow)
Problems in TFNP (via @Marcos Villagra)
Intersecting Monotone SAT (via @András Salamon)
Minimum Circuit Size Problem (via @Eric Allender)
Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
The Cutting Stock Problem with a constant number of object lengths (via @Suresh Venkat)
Monotone Self-Duality (via @Danu)
Planar Minimum Bisection (via @turkistany)
Pigeonhole Subset Sum (via @user834)
Square Root Sums (via @JeffE)
Deciding Whether a Graph Admits a Graceful Labeling (via @Oleksandr Bondarenko)
Gap version of the closest vector in lattice problem GapCVP$(\sqrt{n})$ (via @MCH)
The linear divisibility problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
Finding the VC dimension (via @Mohammad al Turkistany)
Finding the minimum dominating set in a tournament (via @Mohammad al Turkistany)


Career in Theoretical Computer Science I am currently a high school student, interested in theoretical computer science and applied mathematics. I have self taught myself linear algebra and calculus and concrete mathematics. I have a naive notion that for one to write better algorithms, one must know as much mathematics as one can because you can learn about new structures and then use those structures to form more complex and faster algorithms, now, I am not understanding what to do next. I have still an year to go to college, and in that time, I would like study some mathematics that may help me in my career. What should I start with ? Can someone please provide me with probably a list of topics that I should study now and in future.

Also are things like abstract algebra (it is too formal of a subject) and algebraic topology useful in computer science?

My name is Mike.  I'm a PhD student in the area of TCS.  I am self taught in many areas of Mathematics and Computer Science.  Many people would tell you NOT to do this, but when I was your age I bought a book on Analysis (Formal Version of Calculus) and read it cover to cover.  It took about 9 months to read with a continued supply of effort and motivation, but it helped transform my way of thought and gave me the skills to formally express concepts and create proofs on my own.  It also helped me to finally understand the concept of real numbers.

Here's a problem that you would face if you did this.  One, it's hard and you would likely be reading it on your own.  You can talk about it with your friends and parents, but most of them won't really understand.  Secondly, once you finish it, you will be much better at math, but you don't get any college credit and later on you may have to retake a simpler version of the class and be bored out of your mind.  I was able to avoid this by doing a summer program at a local university and afterwards enrolling there as a part-time student.  It took some confidence, effort, and luck to organize such an education, but it paid off.  It allowed me to continue to learn and get credit so that I could take the classes I should be taking when I got to college.

After telling that little story I decided to write up some options that I'd recommend:
(1) Get a good math book and read it
(2) Enroll in a college course at a local university (or summer program locally or not locally)
(3) Work on programing projects
(4) ** Participate in USAMTS ** - http://www.usamts.org/
(5) But, whatever you do, try not to do it all alone

Options for what you could be learning:
(a) Intro to Formal Mathematics: any book that includes proofs, sets and functions, basic number theory, inequalities, basic counting problems, and fun/interesting/challenging problems.
(b) Number Theory - I did well starting out with a few number theory books early on.
(c) Intro to Analysis - Formal version of Calculus and a study of real numbers.
(d) I myself didn't learn much graph theory until later on, but I don't think that would be an unreasonable subject to learn about especially since it's important for Computer Science and Computation in general.

You should know this as well.  For all those who are self teachers, be aware that communication with others is key.  It's important to develop the flexibility to take on new terminology, to be capable of verbally expressing complex concepts, and to take the time and energy to really focus and listen to others.

I wish you the best of luck with everything.  If you ever would like to talk further, please respond.  I am more than willing to chat with you every now and then.  :D

Ps. I would have started out by saying hi, but it didn't let me.


Minimum maximal solutions of LPs Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the strong duality, poly-time algorithms, etc.

But what is known about minimum maximal solutions of LPs? Or, equivalently, maximum minimal solutions?

(This is not really a research question, but maybe we can have something less technical for the holidays. I'm just being curious, and after some googling I got the feeling that I must be missing the right keywords. It feels like an obvious problem to study, but I only found some sporadic papers that mention the problem.)

To keep things simple, let's focus on packing and covering LPs. In a packing LP we are given a non-negative matrix $A$. A vector $x$ is feasible if $x \ge 0$ and $Ax \le 1$. We say that $x$ is maximal if it is feasible and we can't greedily increase any component. That is, if $y \ge 0$ and $y \ne 0$, then $x + y$ is not feasible. And finally, $x$ is a minimum maximal solution, if it minimises the objective function $\sum_i x_i$ among all maximal solutions.

(You can define a maximum minimal solution of a covering LP in an analogous manner.)

What does the space of minimum maximal solutions look like? How can we find such solutions? How difficult it is to find such solutions? How can we approximate such solutions? Who studies such things, and what is the right term for it?

These questions were originally motivated by edge dominating sets and minimum maximal matchings. It is well known (and fairly easy to see) that a minimum maximal matching is a minimum edge dominating set; conversely, given a minimum edge dominating set, it is easy to construct a minimum maximal matching.

So they are, in essence, the same problem. Both problems are NP-hard and APX-hard. There is a trivial 2-approximation algorithm: any maximal matching.

However, their "natural" LP relaxations look very different. If you take the edge dominating set problem and form a natural LP relaxation, you get a covering LP. However, if you take the problem of finding a minimum maximal matching and try to come up with an LP relaxation, then what do you get? Well, of course fractional matchings are feasible solutions of a packing LP; then maximal fractional matchings are maximal solutions of such LPs, and minimum maximal fractional matchings are therefore minimum maximal solutions of such LPs. :)

Maximality and minimality: They are kinds of Pareto optimality.
Complexity: I think finding a minimum maximal solution is NP-hard.  I would reduce the independence domination problem (aka the minimum maximal independent set problem) in bipartite graphs.  This problem (more precisely its decision version) is known to be NP-complete (D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs.  Discrete Applied Mathematics 9 (1984) 27-39).  Since a bipartite graph is perfect, its independent set polytope is determined by the clique inequalities, and the number of cliques in a bipartite graph is polynomial.  Therefore, we can explicitly write down a system of linear inequalities Ax <= 1, x >= 0 for the independent set polytope.  The extreme solutions correspond to the independent sets, and the extreme maximal solutions correspond to the maximal independent sets.


Examples of $\Sigma_2^p$ complete problems? I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely:

Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of literals?
Shortest implicant. Given a formula F and integer k, is there a conjunction of k or fewer literals that implies F?

Another basic $\Sigma_2^p$ complete problem:

$\Sigma_i \text{SAT}$. Given a quantified boolean formula $\varphi$ of the form $\varphi = \exists \vec{u} \forall \vec{v}\, \phi(\vec{u}, \vec{v})$, is $\varphi$ valid?

However, I am hopefully looking for a problem which makes use of graphs (e.g. a clique related problem).

Marcus Schaefer and Chris Umans have a nice Garey-and-Johnson-esque survey of complete problems in the polynomial hierarchy.


Algorithms with multiple right answers --- complexity theory terminology In standard complexity theory terminology, one wants to find Turing machines which decide membership in a language. For any given string, there is only one right answer --- either "yes" or "no."

But suppose we want a Turing machine $f$, which computes a function of its input $x$. We want to ensure that, for any $x$, we satisfy $A(x, f(x))$ where $A$ is some predicate. For example, given a graph $G$, we want to find some proper vertex-coloring of $G$. We don't care which one.

Many of the standard complexity theory notions have analogues in this model. For example, we may want $f$ to be a deterministic polytime algorithm succeeding with certainty (corresponding to complexity class $P$), we may want $f$ to run in expected polynomial time and succeed with probability $1$ (corresponding to class $ZPP$), we may want $f$ to run polynomial time and succeed with high probability (corresponding to $BPP$), or we may want $f$ to run in deterministic polylog time on polynomial-many parallel processors (corresponding to $NC$). And so forth.

What is the terminology for this type of algorithm? In many cases, we know that there exists some $y$ satisfying $A(x,y)$, so $f$ can't really be said to decide anything. I could just refer to saying that $f$ is an "NC algorithm", which is really an analogy and not proper nomenclature.

Thanks!

I think algorithm is the right word. An algorithm doesn't need to decide or compute a function.

The type of problems you want is called search problems in complexity theory. For example, see the definition of the complexity class FNP. But we still refer to the algorithms solving them simply as algorithms.

There is also the notion of multifunction which is used in computability, but again it is for problems not algorithms.


Undecidability of program optimization A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:

  On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is equivalent to $M$.

If size-optimization is not computable, the above $M_1$ shouldn't exist.

How do we prove this?
Does this also mean a size-optimality decider can't exist?
How does this generalize to other kinds of optimization (speed-optimization, for example)?

In your example, you consider a size optimizer, that is a program that

  takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.

With such a perfect size optimizer, you could build a decision procedure for this question

  Is an input program $P$ equivalent to any program of at most $33$ characters?

But this is a non trivial property of program semantics. Rice Theorem says that such properties are undecidable.


Resource for LTL formulae? I would like to practice on some problems for using LTL formulae but besides the foundations and theory there are only every few examples. I know that having understood theory is not enough. Where can I go looking for interesting applications, examples including discussions about it. Is it possible to open a thread with examples here?

E.g.

$(P\to \Diamond Q)$ is intriguing. One would think "On a path $\pi$ starting at state $s$ when P holds, eventually Q will hold." But of course given LTL formula does also hold for any other path which does not satisfy $P$ but $\Diamond Q$ (def. $\rightarrow$ or $\neg P \vee  Q$).

Now, this is not covered in theory in general. It is experience knowledge. I want to practice LTL formulae, where can I go looking for them?

I am not sure what you are referring to when you say "this is not covered in theory in general." The specific example that you give has been studied and is called antecedent failure.

  Formally verifying a microprocessor using a simulation methodology., D. L. Beatty and R. L. Bryant, 1994

  One of the principal dangers of formal verification is what we have called antecedent failure. Formally, implications have an extensional meaning: they are also true if the antecedent condition is not true. Antecedent failure means that we can speak nonsense and not realise it.

The problem of detecting more general forms of such logical pitfalls is called vacuity detection. The introduction of the paper below has an excellent overview. You will also find examples of formulae.

  Enhanced Vacuity Detection in Linear Temporal Logic, Roy Armoni, Limor Fix, Alon Flaisher, Orna Grumberg, Nir Piterman, Andreas Tiemeyer, and Moshe Y. Vardi, 2003

There are lots of courses where people teach temporal logic and those notes and exercises have lots of examples. I would also suggest Manna and Pnueli's book for examples.


Journals with quick reviewing Background: The motivation for this question is two-fold. First, I would like to get some hard facts to better understand the ongoing conferences vs. journals debate. Second, if this information was somewhere available, I could make a more informed decision when submitting papers for review; I would be happy to favour journals whose editors do a good job at selecting and shepherding referees.

Question: Are there any TCS journals that have consistently fast reviewing?

The rules:

I am not looking for any anecdotal evidence; I would like to see hard facts, such as "according to our statistics, during the last 3 years, 98% of our submissions were reviewed in at most 4 months".
Only time from the initial submission to the first decision counts. I do not care how long it takes to actually print a physical journal; it is beyond our control anyway.
A journal that is just a series of conference proceedings does not count. We all know that conference reviewing is quick.
Open-access on-line journals are perfectly fine.

(And if a journal is so questionable that you would be embarrassed if your name was somehow associated with it, let's skip it entirely.)

Glencora Borradaile has an interactive graph with turnover time (among other information) for several journals from several sources.

However, not included is the first journal I think of with a fast turnaround time: Information Processing Letters (IPL).  I couldn't find any statistics, but rapid dissemination is their first goal.  When refereeing for a similar Elsevier journal with the same goal of rapid dissemination but with a slightly different scope, they requested my report within about 5 weeks.