Fast algorithm to find a maximum connected subgraph of k vertices Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)$ is maximum.

This problem is a generalization of the maximum connected subgraph of size $k$, which can be solved by means of integer linear programming. Unfortunately, my objective function $f$ is nonlinear. One can enumerate all connected subgraphs of size $k$ and take one with the largest objective value. However, I think this approach is very slow. I also tried the color-coding technique but it is slow too. Does anyone know any best/fast algorithms to solve this problem in a such general scheme? Thank you in advance!

This is a self-plug but in the paper An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems we consider exactly problems such as the one that you describe. The running time of the algorithm is $O((e\cdot (\Delta-1))^k\cdot (\Delta+k)\cdot n)\cdot T(n,k)$ where $T(n,k)$ is the time needed for evaluating the objective function $f$. Here, $\Delta$ is the maximum degree in the input graph. The algorithm is based on enumeration of connected subgraphs of order $k$. Observe that a graph may have $\Omega((e\cdot (\Delta-1))^k\cdot n/k)$ such induced subgraphs. The bounds for the number of connected induced subgraphs are based on a result of Bollobás in The Art of Mathematics - Coffe Time in Memphis.

Thus, to further improve on the running time above, one either needs to consider other structural properties of the input graph or to exploit some properties of $f$ that make it possible to avoid enumerating all connected induced subgraphs.


Inspirational talk for final year high school pupils I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire their interest (which mostly involves something to do with the Halting problem) but would love hear other people's ideas/successes/failures.

The remit is that these are pupils who are considering applying for a CS undergraduate degree at a decent university but may be more attracted by maths or another one of the sciences.  I find that the usual topics of shortest path algorithms or faster sorting methods don't really work any more to pique their interest.

There is a neat way to introduce zero-knowledge proofs to students, which I think is originally due to Oded Goldreich (please correct me if I'm wrong).

You have a red ball and a green ball, which poor colorblind Charlie believes are the same color. You want to convince Charlie that you can tell the difference between the red ball and green ball, and you want to do this in a way that Charlie does not learn which is red and which is green. (You want to prove something is true, in such a way that no one else can turn around and claim a proof of that something as their own.) How can you do this? Or is it impossible?

One protocol is the following. Charlie puts a ball in each hand, then chooses to either switch the two balls behind him, or not. Then he presents the two balls again. If you can always detect whether he switched the two balls or not, then Charlie is increasingly convinced that you can tell the difference between them. If Charlie does this shuffle at random and you really can't tell the difference between the colors, then you will only guess correctly with probability $1/2$. After $k$ trials, Charlie should be convinced that you can tell the difference with probability at least $1-1/2^k$.

Now while Charlie becomes increasingly convinced that you can tell the difference, he frustratingly never learns which ball is red and which one is green.


Computability Theory prerequisites What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?

Theory of computation and automata theory are not really needed for pure computability theory (but they are a very nice complement to computability theory and certainly help put it in perspective and relate it to the real world!).

Rather, a senior undergraduate level course in mathematical logic is the typical prerequisite.

Traditionally since Gödel, mathematical logic is considered to have four parts (in no particular order):

Set theory
Model theory
Computability theory
Proof theory

In computability theory you will learn things like the correspondence between $\Sigma^0_n$ sets in arithmetic and the Turing degree $0^{(n)}$, and of the Turing degrees of complete extensions of Peano Arithmetic.

Both culturally and scientifically, computability theorists are, and consider themselves to be, part of the mathematical logic community and often study things like computable model theory or higher computability theory (which borders on set theory). Some mathematical maturity is also very helpful.


Among an infinite variety of n x n board games, why are some interesting? Suitably generalized to $n \times n$ boards,
Checkers, Chess, and Go are each EXPTIME-Complete.
(See the Wikipedia
Game Complexity table.)
Each of these two-person games of perfect information
has a simple, finite set of move / capture / promotion / win rules.
Presumably there are an infinite number of sets of rules that lead
to games of complexity (at least) EXPTIME-Complete.

  Q. Are the rules of
  {Checkers, Chess, Go} historical accidents among
  an infinite variety of similarly difficult but potentially interesting games
  that just haven't been explored or 'caught on'?
  Or do the rule sets of popular games have special properties that make them
  especially attractive for human play?

I realize this is not a sharp cstheory question, and perhaps has no definitive answer.

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game attractive and fun:

simple rules;
simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is meaningless if the game can be played on a computer;
a clear ending/winning condition;
a well balanced (usually short) duration;
as game proceeds the "current position" should get simpler and should soon or later clearly reflect a draw or winning/losing condition;
the game contains tactical aspects (usually short term) or long term strategic aspects (usually long-term);
many games are played using dice, so a random component can make the game more balanced and attractive;
it abstracts an aspect of reality (war, conquer, destroy, survive, escape, build, ...);
the difficulty should be balanced and the players must have the sensation that if they play more games they can improve their playing skills and/or discover new (tactical/strategical) aspects of the game;
the game offers many strategies that can be chosen to win (a human player should not be able to learn a perfect winning strategy) and each match can lead to completely different positions and "situations";
errors are "scaled": if a player makes small error then he can recover if he plays well or the other player makes a similar error.

Two-players games usually share some basic settings or meta-rules (some of them also apply to one-player puzzles):

the board is finite and (usually) doesn't change during the game;
a move is well defined; and it is (usually) local;
player A and player B alternate during the game and a turn is usually a single move;
there is usually an initial position (if the elements of the game are not placed on th eboard during the game);
during the game there are some elements on the board (they are placed on the board at the beginning or during the game) and there is a clear distinction between elements owned by player A and elements owned by player B, i.e. both players have their avatars on the board :-)). A move can change the ownership of an element or kick it out of the baord;
there is a winner;
initially both players have allmost the same winning chances.

There are a lot of classic and popular two player games (that were invented before the computer age); and most of them have very different rules and settings: e.g. chess, go, card games, mancala, othello, hex, risk, master mind, scrabble, and so on. Many of them have been proved to be at least PSPACE-complete (the generalized version).

So, returning to your question, I think that there are enough evidences that:

there are no "special rules" (exept for some common meta-rules), but there is a mix of elements involved (the  list above can probably be further extended);
there is a a clear connection between the (underlaying) computational complexity and the addictiviness/fun of a game;

Though point 2. is also related to the age of the players (or how much a player "want to think" while playing); e.g. simpler games like "game of the goose" (which is purely random) or the $O(n^2)$ "connect the dots" are funny for children.

Oldest games like chess, checkers and go satisfy many of the (orthogonal) aspects underlined above, but each in a different way: e.g. chess has harder rules than checkers, but it is deeper from a tactical/strategical viewpoint.

I'm not an expert of their history, but I'm sure that initially there were many variations of them, and their rules/settings have "slowly been tuned" to better satisfy the above aspects. For example, in order to shorten the duration of a chess game and enter the middle game faster, rules were changed (see history of chess or History of chess variants). Go rules in ancient times were always passed on by word of mouth, and were usually not clear; and even nowadays there are many variants (two main variations are about scoring, i.e. winning conditions) (see for example The History of Go rules). Even draughts has many national variants.

As a further confirmation of point 1. and 2. you can examine how many addictive  video games (most of them are single player puzzles) have been created in the last years and have become "classics": candy crush, sokoban, snake, minesweeper, atomix, tetris, portal, ... they have completely different rules and settings, but they share a common point: they are theoretically hard :-)

From a theoretical point of view; a game is simply a path on a state graph (or state space) in which each node is a valid position and many of the above aspects are closely related to the structure of such a graph. We could write pages about such relation, but I think that a key concept is:

the players don't play (theoretical) perfect strategies, so a game is addictive if they can perceive the state space in a strategical/tactical way exactly like on a battlefield with hills, valleys, hidden parts that will be discovered later, positions that look good, positions that look bad, one or more target to reach, temporary disadvantages that will lead to future advantages, different ways to reach a target, the possibility of hindering the opponent's strategy, and so on ...


What is logic programming and does it really add anything new to the logic? I am acquinted with the basics of such notions as logic programming, monotonic and non-monotonic reasoning, modal logic (especially dynamic logic) and now I am wondering - does logic programming provides anything new to any logic?

As far as I understand, then (at least in dynamic logic) the logic programming refers to the formalization of state transitions (by actions, i.e. - logic programing can be understood just as logic about actions). But the same notion "logic programing" seems to be in use even in domains, where there is not state transition, just exploration of one state (or set of states - in case then the initial set of premises are vague enough to describe more than one state). It seems to me that some authors simply use  the notions "logic programming" for describing the procedure how to evaluate the query (I am reading currently about defeasible logic programming). But such procedure (although practical indeed) does not add anything new to the underlying logic. E.g. there is notion of "rational closure" (e.g. used for adaptive logics; just the consequence set for some set of premises) which should contain all the possible knowledge about state and therefore all the possible results of "logic programing" (if it is indeed perceived just as state exploration, derivation).

So - the question is - does logic programming provides anything new to the logic and does every logic (to be completely understood and readied for applications) need to have its own logic programming?

Maybe I am just missing the point...

Just for reference I find the following works interesting about this subject, if there are more along this line, then it would be great to hear!

Mathematical Aspects of Logic Programming Semantics by Pascal
Hitzler, Anthony Seda
Dynamic Logic (Foundations of Computing) by
David Harel, Dexter Kozen, Jerzy Tiuryn
Adaptive Logics for
Defeasible Reasoning: Applications in Argumentation, Normative
Reasoning and Default Reasoning (Trends in Logic) by Christian
Straßer

The answer to such question can have practical applications as well - e.g. it can help to define some kind of formal semantics of the "business rules" (declarative programming paradigm that is used more and more in business applications, e.g. IBM ILOG, JBoss Drools, Oracle Business Rules, PHP and Python also have their own rules engined) and going further - this can be useful for cognitive robotics as well.

I will just write what Frank Pfenning taught me (all mistakes go on my account).

A traditional formal system in logic, such as natural deduction, is descriptive in the sense that it tells us what valid deductions are, but it does not tell us how we are supposed to look for them.

The starting point of logic programming is to take the rules of deduction and reformulate them in such a way that they can be read both as rules of deduction and an evaluation strategy for a computation. This way a strong connection between deduction and computation is created. Both logic and theory of computation benefit from it, and it is perhaps a bit pointless to ask whether logic programming "really adds" anything new to logic. Logic and computation are not separate entities anyway.


Winning strategy in the game of triplets The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements.
Two players take turns picking elements from $X$ until all elements are taken. Then, the score of each player is the number of triplets from $T$ in which he has at least 2 elements.

A standard strategy-stealing argument shows that the first player can always score at least $|T|/2$. Suppose by contradiction that it is false. Then the second player can score more than $|T|/2$. But then the first player, copying the second player's winning strategy, can score more than $|T|/2$ too. This is a contradiction since the sum of scores is $|T|$.

  QUESTION: what is an explicit strategy for the first player to get a score of at least $|T|/2$?

EDIT: Here is an explicit strategy for the first player to get at least $3|T|/8$. To each triplet in $T$, assign a potential $P(a,b)$ based on the number of its elements taken by the (first,second) player:

\begin{matrix}
\bf a \downarrow b \rightarrow & \bf 0 & \bf 1 & \bf 2 & \bf 3 \\
\bf 0    &3/8&0& 0 & 0 \\
\bf 1    &3/4&1/2& 0 &   \\
\bf 2    & 1 & 1 &   &   \\
\bf 3    & 1 &   &   &   \\
\end{matrix}
Initially, every triplet has potential $3/8$, so the potential-sum is $3|T|/8$.

Player 1's strategy is: pick an element that maximizes the potential-sum.
Suppose that element is $x$ and the element picked next by player 2 is $y$. I claim that the potential-sum after these two moves weakly increases:

The potential of a triplet that contains neither $x$ nor $y$ does not change.
The potential of a triplet that contains both $x$ and $y$ changes from $P(a,b)$ to $P(a+1,b+1)$, which is always at least as large.
The potential of a triplet that contains $x$ and not $y$ increases by $P(a+1,b)-P(a,b)$;
The potential of a triplet that contains $y$ and not $x$ decreases by $P(a,b)-P(a,b+1)$; it is easy to check in the table that $P(a,b)-P(a,b+1)\leq P(a+1,b)-P(a,b)$ (the decrease when going right is at most the increase when going down).

All in all, the potential-sum increases by the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $x$, and decreases by (at most) the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $y$. By the choice of $x$, the first sum is weakly larger. So the potential-sum weakly increases.

So the final potential-sum is at least $3|T|/8$. At the end, a triplet has potential $1$ ($0$) iff it is won by player 1 (2), so the final potential-sum equals player 1's score.

This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first move is already probably tricky.

As a first step, we argue that the triplets game is harder (in the appropriate sense) than the $\textrm{Denser Induced Subgraph}$ game defined as follows.

Two players, A and B, alternate picking vertices on a common graph G. Vertices can only be picked once. When no more vertices remain to be picked, the subgraphs induced by each player's choices are compared.  The player with the larger number of induced edges is declared the winner.

Proof outline:
Given an instance of the $\textrm{Denser Induced Subgraph}$ game with graph $G = (V,E)$, we construct a $\textrm{Triplets}$ instance as follows. Without loss of generality, assume $G$ has no isolated vertices. The set of elements in our instance will be $V \cup (E \times \{0,1\})$. For each edge $e \in E$ between vertices $u$ and $v$, we have two triplets of the form $(u, v, (e, 0))$ and $(u, v, (e, 1))$. Additionally, for each vertex $v \in V$, we throw in four additional triplets of the form $(v,v,v)$. This completes the reduction.
Now imagine the proceedings of the $\mathrm{Triplets}$ game. As long as some vertex from $V$ has not been picked, the choice of such a vertex strictly dominates that of any element from $E$. Indeed, picking an element from $E \times \{0,1\}$ only ever gives a potential score increase of $1$ (and also blocks the opponent from at most $1$ point), while picking an element from $V$ automatically gives a score increase of $4$, with potential for more.
Therefore, under optimal play, the first $|V|$ rounds will correspond to both players picking elements from $V$. After these rounds, the players alternate picking up the even-sized collection of triples that have not yet been claimed, which correspond to exactly the edges whose endpoints have been picked once by each player. Any reasonable strategy here, for either player, ends up picking up exactly half of those available triplets. The game ends with a sequence of NOOP moves on the already-picked-up triplets.
Let $V_A$ be the vertices chosen by player A, and $V_B$ those chosen by B. The score for player A is the sum of (i) four points per vertex chosen from the $(v,v,v)$ triplets (ii) two points per induced edge created from these vertices, and (iii) one point for each split edge. Therefore, the score is $4|V|/2 + 2|E[V_A]| + (|E| - |E[V_A]| - |E[V_B]|)$, where $E[S]$ is the set of edges induced by $S$. Since the first and last terms are ultimately equal for both players, the player with the larger induced subgraph wins. $\square$

With this in mind, we can appeal to some of the work in the literature of detecting dense subgraphs. There's a ton of relevant work out there on this that one can appeal to, but for simplicity of analysis I'll appeal to a particular conjecture on the difficulty of finding dense random graphs in sparse random graphs (I believe that this dependence can be removed with just a little more thought, but this is not meant to be a formal proof).

The Planted Dense Subgraph Problem (informal). Let $G = (V,E)$ be a random graph sampled from the Erdos-Renyi distribution $G(n, 1/\sqrt{n})$. With probability $1/2$, we return $G$ as is. Otherwise, we let $V'$ be a uniformly random subset of $V$ of size $\sqrt{n}$. For each $u,v$ pair in $V'$, we add an edge $(u,v)$ to $E$ independently with probability $n^{-1/4}$. Only then do we return $G$. The problem is to, given only the output of the above, correctly identify whether or not the Erdos-Renyi graph was augmented.
The Planted Dense Subgraph Conjecture (informal). No polynomial-time algorithm can solve the Planted Dense Subgraph problem with probability at least $51\%$.

Suppose that the graph was augmented, and there is an unusually dense component. Since no poly-time algorithm can reliably detect this dense subgraph's presence, it also cannot reliably sample a vertex from this dense component (e.g. due to self-reducibility). Therefore, since (from Player A's perspective) it is selecting a random vertex from a pure Erdos-Renyi graph, it does not matter much which vertex A picks (up to a small change in its scoring that will end up not mattering1). However, if Player B is omniscient, it can reliably sample a vertex from the dense component on its first shot. This process repeats a superconstant number of times before B's choices begin unveiling the dense component to A (otherwise, a polynomial-time algorithm can traverse every path in this game tree to constant depth in order to solve the Planted Dense Subgraph problem). If the process repeated $r$ times before A catches on, then the first $r-1$ rounds can be seen as "freebie" rounds for B, while the $r$th round is the beginning of A and B fighting over the dense component, with B getting the first move and (by your strategy stealing argument) a winning subset.
Once the dense component is exhausted, the two players resume fighting over the rest of the graph. While A has chosen $r$ more vertices here than B has, B's first $r$ vertices are worth $\Omega(n^{1/4})$ times as much, and thus B is ultimately the winner.
1. By some type of concentration and pigeonhole argument, the difference between making the first choice and the second choice should not be more than $O(1)$ in the final score.

Therefore, despite the game being very weakly solved for player A, it's unlikely that it's computationally feasible for A to play out even the first move of the winning strategy.
An approach based on the hardness of the "normal" densest subgraph problem should not be difficult to attain here, either, and composing the reduction with a hardness of approximation result likely can be used to get some kind of hardness based on more mainstream conjectures (eg ETH). I'm not sure what the difficulty of moving up to NP-hardness (or beyond) may be.


What is the difference between propositions and judgments? I get confused by the subtle difference between propositions and judgments when exposed to intuitionistic type theory. Can any one explain to me what is the point to distinguish them and what distinguishes them? Especially in view of the Curry-Howard Isomorphsim.

First, you should know that, in general, there is not consensus about these terms and their definitions depend on the system in which one is working.Since you asked about intuitionist type theory, I'll quote Pfenning:

  A judgment is something we may know, that is, an object of knowledge. A judgment is evident if we in fact know it.

Propositions on the other hand, according to Martin-Löf are sets of proofs. In this interpretation, if the set of proofs for a proposition is empty then it is false and otherwise true.

  A proposition is interpreted as a set whose elements represent the proofs of the proposition

says Nordström et al.  On the other hand, in classical logic and in general, propositions are objects expressed in a language which can be either "true" or "false".

To give you some extra intuition; from my point of view, judgments are metalogical and propositions logical.

I suggest "Constructive Logic" by Frank Pfenning, "Proofs and Types" by Jean-Yves Girard and "Programming in Martin-Löf's Type Theory" by Bengt Nordström et al. All three are freely available on the Internet. The last one is probably the closest to what you want as it is oriented to programming and goes into great detail, at length, about the meanings of these terms and many more.


Inferring optimal utility values from a decision process I've been able to model a particular decision problem as a
Markov Decision Process, where the optimal policy (i.e. what decision should be taken at each step) is defined in order to optimize a given utility function. Hence, given the utility function and the probabilistic behaviour of the system, I can calculate what actions to take.

I'm interested in knowing if there exists some "reverse" process: if I know the probabilistic behaviour of the system and which action should be taken, can I calculate what the utility values should be in order to get the expected behaviour?

My first guess was to look at Monte-Carlo simulations, where I would set up some (more or less) random utility values, perform some simulations, see if it's consistent with what I would expect, and keep going until I find something satisfactory. But I'm not sure it's converging, and I have the feeling that I'm not the first one to want to do this.

If it helps, the context is security decision mechanisms, where we would know the actual policy for some base cases, the goal being to calculate the utility values for more complex cases.

EDIT: Give a bit more details following Markus' comment

Let us assume I have a set of states $\Sigma$, a set of actions $A$ and a probabilistic transition function $P : \Sigma \times A \times \Sigma \to [0, 1]$. I also have a boolean function that can tell me, given a trace $\sigma_0, a_0, \sigma_1, a_1, \dots, \sigma_n$, if this trace is "good" or not. Note that I assume here that the system is completely observable, i.e, after executing an action in a state, I know in which state the system is. I also consider working at a finite horizon $n$.

The question becomes: how can I calculate a reward function $W : \Sigma \times A \times \Sigma \to U$, where U is a utility domain (e.g. $\mathbb{R}$) such that the optimal policy (i.e. the  policy returning the maximum utility for a finite horizon $n$) only outputs "good" traces.

Refinement 1: What if I want to define the utility function only on the states and not on transitions, that is, if I just want to define a function $W : \Sigma \to U$?
Refinement 2: What if I consider that the state consists of some attributes $x_1, \cdots, x_k$, and I want to define a reward function only based on the attributes of the state?
Refinement 3: What if, instead of simply classifying the traces into the good ones, and the bad ones, I can define a partial order over them, can I calculate the reward function that always returns the "best" trace?

I hope this clarifies a bit the question, and although any general results is interesting, I'm also interested in practical approaches, that would provide only an approximation (since calculating the general solution is likely to be intractable in general).

You might want to have a look at Inverse Reinforcement Learning. IRL tries to infer a reward function given observed optimal behavior in some MDP. I believe the framework was originally described in the 1998 paper Learning agents for uncertain environments by Stuart Russel. This paper and and those that cite it should be a good place to start, assuming IRL is a good fit for your problem.


What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers? In particular, the genesis of this idea was the notion that you could minimize the number of passes through the list in a comb sort by using the primes as a way to guarantee that every element gets sorted while having the largest gap be only slightly larger than the square root of the size of the list rather than just below the size of the list. Some quick experimentation showed that this was very wrong and that starting with the largest prime possible as the gap is always more efficient (for comb sort; I confess I don't really get shell sort and so didn't test it, though I expect similar results) unless the list is already extremely well-ordered, so that part of the idea is a bust, but I'm still curious about the relative merits of using primes over other gap-choosing strategies.
I assume that this is obvious enough of an idea that it's been studied and found inefficient in some key way, but I don't have any idea why exactly this might be so beyond an aversion to having a lookup table of primes in one's code (or needing to calculate a significant number of primes every time the sort is run); I couldn't begin to speculate as to how costly that kind of overhead would be considered to be however.

Analyzing various gap sequences is very difficult, but it is easy to see that this would require at least approximately $n\cdot\pi(n)\sim n^2/\log(n)$ passes, since you are looping over the entire array once per prime. This makes it worse than some other simple gap sequences, such as $2^n\pm1$ or $(3^n-1)/2$, which are known to take only $\mathcal O(n^{3/2})$ passes. The other issue is the amount of time and space it would take to generate the gap sequence.
Generally a good gap sequence should grow exponentially. Intuitively we want to make $\mathcal O(\log(n))$ loops through the entire array, and with each loop involving as few swaps as possible overall. This would get you closer to $\mathcal O(n\log(n))$ complexity. There's more details on the linked Wikipedia concerning the complexity of shellsort and picking gap sequences.


How to minimize a FSM transducer? In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the following question.

  Given a FSM transducer, how does one find a "minimal" equivalent transducer?

Note that there are possibly multiple reasonable ways to define the minimal transducer. The literature maybe hasn't settled on one. Also, I'm looking for applications if some are known.

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

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

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

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

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

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

See also Thm XII.4.2 in

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

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

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

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


Formalizing a notion of machine Intelligence Turing test of Artificial intelligence relies on interaction between two parties with the goal that one party convinces the other party that it has the same computational abilities.

I'm trying to formalize a new notion of machine Intelligence: the ability of Turing machines (algorithms) to recognize their programmer and that they were not generated randomly.
This requires defining metrics to be used by Turing machines to measure the creative abilities of the programmer. We may allow interaction between the algorithm and the programmer.

  How can we formalize such notion of AI? Has any similar idea been investigated before in TCS?

EDIT1: programmer here is a program that is able to generate other algorithms runnable on some computing device.

One motivation is whether intelligence of an algorithm is dependent on programmer's intelligence.

EDIT2: I'd like to formalize a notion for the intelligence and creativity of programs. Not all programs created equal. My question is an attempt to model and formalize aspects of intelligence that are not captured by current definitions of AI. For instance, Does an evolutionary algorithm possess any intelligence? If yes, What is the source of this intelligence?

EDIT3: My goal is to remove the subjectivity from Turing test. If the programmer is able to convince a Turing machine that it was the product of creativity of the programmer then the Turing machine is intelligent. Furthermore, the programmer is far more intelligent than the code he created. So, the challenge is how to formally convince the Turing machine that the programmer has superior computational abilities. In addition, the programmer must convince the Turing machine that those superior computational abilities are required and critical to the creation of the Turing machine code.

Let me give a partial answer from a learning theory perspective.  As your question isn't well specified, this answer won't be either.  In my answer, I'm assuming your question was inspired by your blog post, linked from your profile.

Say that you are thinking about programs that are just functions (so they have to halt, etc.).  You can ask whether certain classes of such functions can appear randomly by, perhaps, looking at the probability a random program (from some distribution that you think is likely) lands in that class or not, with the hope that probability is polynomially large.  I haven't really thought this argument through.

You can also ask whether such a class is efficiently evolvable according to Valiant's model of evolution (also in @Artem's pointer in comments): luckily what is efficiently evolvable is known to be the class learnable by correlational statistical queries; taking "crossover" into account, you get parallel correlational statistical queries. One thing to note is that just because evolvability is characterized, it is still a separate and sometimes difficult task to determine whether a particular class is evolvable (learnable with CSQs) or not.

If you find a class of "programs" that is neither randomly occurring nor evolvable, perhaps you can conclue it has a "creator/programmer," though that conclusion may still take a leap of faith.


Locally-nameless normalization This paper on locally-nameless (Charguéraud, Arthur: The locally nameless representation, Journal of Automated Reasoning (2012): 1-46) describes how to perform beta-reduction by "opening", but it's unclear to me how to normalize under abstractions.
For example how would one normalize the following expression, with the locally-nameless operations:

$\lambda((\lambda\lambda(1 \; 0)) \; 0)$

A good rule of thumb with locally nameless is "pattern matching on a binder is opening". In particular, take a naive call-by-name normalization algorithm on terms with named binders that ignores variable capture (in OCaml syntax):

 let rec norm t = match t with
     | Var v -> Var v
     | Lambda (v, t') -> Lambda (v, norm t')
     | App(t, u) -> let t' = norm t in
                    let u' = norm u in
                    match t' with
                       | Lambda (v, t'') -> norm (subst v u' t'')
                       | _               -> App (t', u')

The locally nameless version is exactly the same, except that you need to open the lambdas right after pattern matching on one, i.e. instantiate the top level deBruijn index with a name. What name do you want to open with? Well it probably needs to be a name you haven't opened with "above", aka a fresh variable.

Well darn. We were kind of hoping to not have to care about generating fresh variables with locally nameless. No such luck. In OCaml, you can cheat a little and create a statefull fresh : unit -> name function that always produces a never-seen-before name.

You don't actually need to do this with the second pattern match! When opening a term and immediately substituting, you can skip a step and call instantiate directly. This mentions no names (and works on a "scope", a non "opened term" with 1 deBruijn variable still in it).

But then you have the fresh names in the normal form! You need to abstract over the name again before applying the Lambda constructor. This gives

 let rec norm t = match t with
     | Var v -> Var v
     | Lambda t' -> let v = fresh () in
                    let t'' = instantiate (Var v) t' in
                    Lambda (abstract v (norm t'))
     | App(t, u) -> let t' = norm t in
                    let u' = norm u in
                    match t' with
                       | Lambda t'' -> norm (instantiate u' t'')
                       | _               -> App (t', u')

Easy peezy (except for the implementation of fresh, which can be tricky)!


Parallel algorithms to find the optimum of polynomials Are there any non-trivial parallel algorithms to find the optimum (local or global) of polynomials? By trivial, I mean something which is an obvious application of a serial algorithm. For example, one trivial way to parallelize the search for a global optimum would be to partition the space and then search for a global optimum amongst all the partitions in parallel.

To the best of my knowledge, parallelization of this problem is not done as you suggested, i.e., searching in parallel the whole space to determine extremal points. A much faster parallelization method for multi-variate polynomials (when appropriate) may be based on the use of parallel automatic differentiation, the (parallel) solution of the resulting system of equations and finally the study of the related Hessian.

However, you may consider non trivial the paper "Polynomial Optimization via Recursions and Parallel Computing", which deals with the problem of finding the global minimum for a special class of dominated real valued polynomials.

"A Parallel-Computing Solution for Optimization of Polynomials" provides a parallel algorithm for determining polynomial positivity.


Digital steganography re-encoding resistance I'm curious to know if any papers exist on the ability of steganographically-altered image data to retain its integrity after it has been re-encoded into a different format (e.g., from PNG to JPEG). Is this an inherent trait in good steganography implementations, or is this an issue that needs to be treated separately?

I'm not sure what policy here is on reviving dead questions. I'll answer in case anyone else needs this question answered. I'm sorry, but I know of no papers on the subject (likely due to ignorance rather than non-existence, however).

As with most lossy methods of compression, JPEG aims to remove the image features that are not important or differentiable to the human eye. Unfortunately, those parts of the image are precisely where Steganography would occur (for example, in the least significant bits) - so if you had embedded data in an image, JPEG encoding would almost certainly destroy the stego data. Re-encoding image files is actually considered a good way of protecting against steganography. Since steganography is concerned with making the data as un-noticeable as possible (and in the process making it as indistinguishable to the human eye as possible) it is an entirely natural conclusion that steganography would be at odds with format changes (at least, lossy format changes. Lossless changes would not destroy any embedded steganography, unless they relied on some part of the format rather than the pixels themselves).


Are there good implementations for easy subclasses of NP-hard graph problems Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource on graph classes http://www.graphclasses.org).
How can I know if G belong to some of these classes? Do I need to read and code algorithms from each paper to check it? Or there exists already an implementation for most of these algorithms?

Thanks in advance.

Edit: Maybe it is too broad my question but in some sense I want to know if someone is trying to code all these theoretic algorithms.
As a reformulation of my question: Does exist some project with the goal of unify all this theoretical knowledge in practical application (real code implementation)?

I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of classes... For example chordal graphs (easy to recognise), or treewidth-bounded graphs (much harder.. hopefully the algorithms given for these classes are almost useless in practice), planar graphs, ...

In Sage (http://www.sagemath.org/), we are trying to build a large graph library, with recognition algorithms and methods to solve NP-Hard problems. For instance, we have the following methods :

g.is_bipartite
g.is_chordal
g.is_circular_planar
g.is_clique
g.is_drawn_free_of_edge_crossings
g.is_equitable
g.is_eulerian
g.is_even_hole_free
g.is_forest
g.is_gallai_tree
g.is_hamiltonian
g.is_interval
g.is_line_graph
g.is_odd_hole_free
g.is_overfull
g.is_perfect
g.is_planar
g.is_prime
g.is_regular
g.is_split
g.is_transitively_reduced
g.is_tree
g.is_triangle_free
g.is_vertex_transitive

The best is probably to read the (unfortunately) long list of methods related to graphs...

http://www.sagemath.org/doc/reference/graphs.html

(I wrote a short tutorial there : http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/ )

Nathann


A theorem regarding statistically-hiding commitment schemes Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends $C_n(m ; r)$ to the receiver. To decommit, he simply reveals $m$ and $r$. We let $C_n(m)$ denote the random variable obtained by uniformly and independently picking $r$ (of proper length) and computing $C_n(m ; r)$.

Finally, let $U_n$, $U_n'$, and $U_n''$ be i.i.d. random variables with uniform distribution over $\{0,1\}^n$. We assume that repeated use of a random variable results in the same sample. For example, $\langle U_n, U_n+1 \rangle$ means a pair, where we first sample $U_n$ to obtain an $n$-bit string $m$, and then let the pair be $\langle m, m+1 \rangle$.

I want to prove that the following distribution ensembles are statistically indistinguishable:
$$\mathcal {X} = \{\langle U_n, C_n(U_n) \rangle\}_{n \in \mathbb{N}} \enspace,$$
$$\mathcal {Y} = \{\langle U_n', C_n(U_n'') \rangle\}_{n \in \mathbb{N}} \enspace.$$

This certainly follows for $n=1$.

Fix any algorithm $A$ that attempts to distinguish, and let $p_{a,b} = \Pr[A(\langle a, C(b) \rangle)=1]$, where $a,b\in \{0,1\}$.  Now by the assumption that $C$ is statistically hiding, we have $p_{0,0} \approx p_{0,1}$ (for otherwise you could prepend the fixed constant 0 to any commitment and then use $A$ to break the hiding property) and we have $p_{1,0} \approx p_{1,1}$ (for a similar reason).

Expanding out the definitions, we have $\Pr[A(X)=1]=(p_{0,0}+p_{1,1})/2$ and $\Pr[A(Y)=1]=(p_{0,0}+p_{0,1}+p_{1,0}+p_{1,1})/4$ (where $X,Y$ are samples from your distributions ${\cal X},{\cal Y}$).  But from the facts above, we have $2p_{0,0} + 2p_{1,1} \approx p_{0,0} + p_{0,1} + p_{1,1} + p_{1,0}$, i.e., $\Pr[A(X)=1]\approx \Pr[A(Y)=1]$, and thus $X,Y$ are statistically indistinguishable.

I think from this you should be able to see how this generalizes to $n>1$ as well. Basically, you note that

$$\Pr[A(X)=1]=1/2^n\sum_b \Pr[A(\langle b,C(b)\rangle)=1]\approx 1/2^{2n}\sum_{a,b} \Pr[A(\langle a,C(b)\rangle)=1] = \Pr[A(Y)=1],$$

using the fact that $\Pr[A(\langle a,C(b))\rangle)=1] \approx \Pr[A(\langle a,C(b')\rangle)=1]$ for all fixed $a,b,b'$ (otherwise you could distinguish $C(b)$ from $C(b')$ by simply prepending $a$ and then running $A$).


NEXP-complete problems There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one available? As I assume there isn't, I open this question (is this supposed to be a community wiki? I don't know about this stuff).

Ideally the list should cover the different "types" of NEXP-complete problems, perhaps with some healthy redundancy to get the big picture, but without repeating itself too much. For example, it is good to have two or three different succinct versions of the same NP-complete problem as examples, if the succinct encodings come in slightly different forms. Not a dozen. A clean way to add the redundancy is by adding clauses of the form "Also NEXP-complete if BLAH". Clauses of the form "Remains NEXP-complete if the input graph has degree at most BLAH" are also welcome.

Finally, let me add a personal preference. I am most of all interested in complete problems of "algebraic" flavor, if there are any. For example, my favorite #P-complete problem is the permanent for its algebraic flavor. I hope the equality NEXP = MIP can also provide some nice algebraic NEXP-complete problem that I am not aware of.

For some NP-complete problems, there's a SUCCINCT variant that's NEXP-complete.

An example is SUCCINCT HAMILTON PATH:

A Boolean circuit with 2n inputs and one output represents a graph on 2n vertices. To determine if there is an edge between vertices i and j, encode i and j in n bits each, and feed their concatenation to the circuit: there is an edge between these vertices iff the output of the circuit is true. Given such a circuit, is there a Hamilton path in the graph represented by the circuit?

Similarly, there's SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Reference

Hana Galperin, and Avi Wigderson (1983), "Succinct representations of graphs", Information and Control 56:3, pp. 183–198.


What would you advise someone who wants to do research as a hobby? I love doing TCS in my spare time. Lately I have been trying to do some research as a hobby.
I'm looking for some extra input from people who do this full-time:

Do you think it is possible to do this "just for fun"? I have no intention to ever get a PhD.
What resources would you recommend?

If you intend to publish it is essential that you learn how to write academic papers. Even if you can already write well, it still takes effort to get the style, focus, and, in particular, the quality right. Academic writing is highly compressed, rather formal, and precise. Theorems and so forth must be written in a particular way. Writing proofs is an art. There are even (implicit) standards for referencing the literature. Get any of these wrong and your article looks amateurish, which lends itself to rejection irrespective of the quality of the contents.

Here are some general tips that will help in this direction:

Use LaTeX. Papers, especially formal papers, written with Word look like crap.
Read a book on academic writing (and do the exercises). We use Academic Writing: A Handbook for International Students, mostly because our students are non-native English speakers.
Read Writing for Computer Science: The Art of Effective Communication  by Justin Zobel.
Learn how to write theorems and proofs correctly. One way of doing this is to find a high quality book in the area and mimic its style, even if it comes down to copying the text word for word to get the feel for how things are written. Then when you write your own results, consult the book regularly so that you can mimic the style. I know people who have used Relation Algebras by Games by Hisrch and Hodkinson as an exemplary model of mathematical writing. Undoubtedly there is such a text in your area.
Learn the conventions of the venues/communities where you plan to publish. Most papers have an abstract and introduction, body, discussion, related work, conclusions and future work sections, but different venues/communities may vary the ordering or have different expectations about how much attention goes into which part of the document. Issues such as how much background information is added to your paper depend very much on the expected audience, and it always pays to know the background of the average reader in the community. Critically reading many papers from the target community and trying to comprehend the stylistic expectations, is the only way to address this issue (without a supervisor in the area).


The theory of definitions in first order logic I'm looking for a clear and thorough treatment of the theory of definitions in first order predicate logic from a syntactic/proof theoretic point of view (as opposed to semantic/model theoretic point of view). Ideally, the covered material should include at least what is covered in sections 2.3-2.5 of Anil Gupta's Stanford Encyclopedia of Philosophy article titled Definitions, namely conservativeness and eliminability, definitions in normal form, and implicit definitions. It doesn't have to be all in a single resource.

I don't have the books handy at the moment, but I think Shoenfield's "Mathematical Logic" and Hinman's "Fundamentals of Mathemtical Logic" would contain much if not all of what you're looking for.

Probably not what you want but perhaps worth mentioning anyway is A. P. Morse's book "A Theory of Sets". This is a development of (a rather idiosyncratic version of) what is usually called Morse-Kelley set theory, but Morse also pays a great deal of attention to the formulation of definitions. His goal is to make the formal language close to normal mathematical English, while avoiding ambiguities. There's a long chapter, early in the book, spelling out what is allowed in definitions.

Another logician who paid close attention to definitions was S. Lesniewski. He developed a system of foundations of mathematics in which definitions played a crucial role. In contrast to most systems, definitions are not conservative in Lesniewski; some definitions play the role of comprehension axioms. Because of their importance in his framework, Lesniewski gave very careful rules for what constitutes a legitimate (in his sense) definition. Some of his work is very hard to find (and it's mostly in Polish, though a little of it is in German), but there's a book, "The Logical Systems of Lesniewski" by Luschei, that describes it well. (There should be an acute accent on the first s in "Lesniewski" but the best my keyboard and browser can do here is Le´sniewski.)


Approximation algorithms for min vector subset-sum over GF(2) In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.

  Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to $y$?

In the answers, comments, and referenced papers I noted

The decision problem is in P.
The natural minimization problem (finding the smallest subset) is NP-hard.
It's related to the problem of finding sparse codewords in a linear code.

My question is: are there any known polynomial-time approximation algorithms for the minimization problem in (2)? I know very little about coding theory, so there may be some obvious or well-known approximation-preserving reductions to (3) that I have not seen.

Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum distance problem is the same as your problem if the $v_i$'s form the columns of the parity check matrix and $y = 0$.


Approximating convex sets In the Haussdorf approximation of a convex object $C$ (and in much core-set work), the standard approach is to take an $\epsilon$-net on the enclosing hyper-sphere, then project it down to $C*(1 + \epsilon)$, where $C*(1+ \epsilon)$ is defined as $C$ projected outwards normally by an $\epsilon$ factor. I have a basic understanding of the proofs, but I'm trying to visualize why the hypersphere is really necessary. If you take an $\epsilon$-net on the surface of $C*(1+\epsilon)$ itself, would that not suffice? If there is an immediately obvious reason it would not work, I'd appreciate the clarification :).

Note: The $\epsilon$-net here is defined as a collection of equally spaced points on given surface.

The construction you suggest does work, but it is not optimal. The reason why people use the sphere with a constant expansion is that then a $\sqrt{\epsilon}$-net is enough. That reduces the size of the coreset from $O(1/\epsilon^{d-1})$ to $O(1/\epsilon^{(d-1)/2})$. To see that replacing $\epsilon$ by $\sqrt{\epsilon}$ in your construction does not work, consider the case of a regular triangle (or simplex) where only points within distance roughly $\sqrt{\epsilon}$ of the vertices are sampled.


Reordering data (set of strings) to optimize for compression? Are there any algorithms for reordering data to optimize for compression?  I understand this is specific to the data and the compression algorithm, but is there a word for this topic?  Where can I find research in this area?

Specifically, I have a json list of 1.5 million strings, and I want to reorder the strings so that gzip (for HTTP) compression is optimized.  Sorting the strings does pretty well, but I don't really know if that is optimal.

This is an addition to the Navin Goyal's answer.

Since a JSON file can be regarded as a tree data structure, you can use the XBW-transform for trees, which is an extension of the Burrows-Wheeler transform for strings.


Dissecting tetrahedra into similar tetrahedra (i) Does anybody know what is the smallest number $k$ such that there
  is a tetrahedron T that can be subdivided into $k$ tetrahedra that are
  similar to T ?

I know $k$ is at most 8 (I know a tetrahedron that can be subdivided into 8 similar tetrahedra), and at least 3 (I can prove no tetrahedron can be subdivided into 2 tetrahedra that are similar to the whole). Does anybody know better lower or upper bounds?

  (ii) What if we require the tetrahedra in the subdivision to have the
  same size? (Again, I know $3 \leq k \leq 8$)

Hi Herman — since you asked me this at GD, I've found an answer to version (ii) of your question. Jiří Matoušek and Zuzana Safernová have shown that subdivision of a tetrahedron into $k$ tetrahedra that are similar to the original and congruent to each other is possible only when $k$ is a cube (and it is conjectured more strongly that this is possible exactly when $k$ is a power of eight, the case you already know about). See their paper "On the nonexistence of k-reptile tetrahedra", arXiv:1006.1807.


Reachability Query for Tree What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $O(n\log n)$ which supports $O(1)$ query time for planar graphs. Do trees have better complexity?

Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the $n-1$ edges).

[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar reachability in linear space and constant time." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.


Is this partition problem strongly NP-complete? Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the fixed-point free GA problem is NP-complete.

Partition problem is weakly NP-complete problem since it has pseudo-polynomial time algorithm. I am interested in variants that are strongly NP-complete.

Here is a variant of partition problem:

Restricted partition problem

Input: Set $S$ of $2N$ integers, and a collection $P$ of pairs from $S$, $0 \lt |P| \lt N$

Query: Is there a partition of $S$ into two equal cardinality parts $A$ and $S-A$ such that both parts have the same sum and no pair in $P$ has both elements in one side of the partition?

  Is this variant of partition problem NP-complete in the strong sense?

This was posted first on Math overflow (I believe the posted answer is incorrect since the proposed dynamic programming algorithm does not take into consideration the cardinality of $P$).

Your problem can be reduced to the Partition problem (which is weakly NP-complete) without an exponential blowup of the numeric values; so your problem is weakly NP-complete, too.

This is the idea: you can view the $2N$ integers as nodes of a graph $G$, the pairs in $P$ indentify the edges between the nodes.

Clearly $G$ cannot contain cycles of odd length (checkable in polynomial time); otherwise there would be a conflict and at least one element should be excluded from the partition $A$ vs $S \setminus A$.

Each connected part $H_i$ of $G$ is bipartite $H_i = H_i' \cup H_i''$, and you can treat it like a single integer $h_i = | \sum  H_i' - \sum H_i''|$

Let $w_i$ be the difference between the number of elements in the greatest side and the number of elements in the smallest side of the bipartite component $H_i$ plus $N$:

$w_i = N + |H_i'| - |H_i''|$ if $\sum  H_i' > \sum H_i''$;

$w_i = N + |H_i''| - |H_i'|$ otherwise.

Let $a_1,a_2,...,a_m$ be the "isolated" integers.

Let $k$ be the minimum value such that $2^k > \sum h_i + \sum a_j$.

We finally build a Partition problem with the elements:

$B = \{ a_j + 2^k (N + 1) \} \cup \{ h_i + 2^k w_i \}$

It is not hard to show that $B$ has a partition $B = B_1 \cup B_2$, $\sum \{B_1\} = \sum \{B_2\}$ if and only if the original $S$ can be split into two equal size halves having the same sum and such that no pair in $P$ have both elements in the same side.

Very informally: if $h_i$ is placed on one side, it also carries the $w_i$ (positive) "weight" that keeps track of the (absolute) difference between the number of elements of $H_i'$ and $H_i''$; so on the opposite side both the sum and the weight must be "balanced" and this ensures that a solution leads to a valid equal size partition also on the original problem. In the original problem we can derive $A$ from $B_1$: if $h_i$ (or $a_j$) is placed on $B_1$ then the integer nodes of the bipartite component $H_i$ must be arranged in such  a way that $A$ recieves the elements from $H_i'$ or $H_i''$ according to which have the greater sum.

A simple example: given the integers: $1,1,2,3,4,7$ and the pairs $(7,2), (7,3)$, we build the following graph $G$:

We then reduce the connected component to a single number $(2,-1)$ (for better clarity we use the notation $(x,y)$ instead of $x + 2^k (N + y ))$; and solve the corresponding partition problem.

You can also apply the Partition problem pseudo-polynomial time dynamic programming algorithm  to the set $B$ to find the solution.


Hidden constant in eps-sample size computation Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\delta}\right)\right)$ points with replacement from $X$.

Löffler and Phillips [1] showed experimentally that the constant hidden in the Big-Oh notation is at most 0.5.
I was wondering whether there is any known theoretical, rather than experimental, upper bound to this constant.

Thanks in advance for any reference

[1] Löffler, M and Phillips, J.M. "Shape fitting on point sets with probability distributions". ESA'09

I discovered after this publication that there is older work by
Dvoretzky-Kiefer-Wolfowitz in 1956 that looks specifically at this one-dimensional case for sampling.  There is also follow up by just Kiefer and Wolfowitz a year or two later that handles the (anchored) rectangle case.

For these specific settings, there has been some much more refined work looking at the actual constants.  Here is a reference that might help:

P. Massart, "The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality", 1990.

I don't know off-hand any other work on the constants other than the 1-d or "anchored" rectangle cases

Jeff


Correcting a conference paper error in the journal version In a conference paper, in order to prove the $\mathsf{NP}$-completeness of a problem, I wrote the stupid sentence "It is clear that the problem is in $\mathsf{NP}$. So we will prove that it is $\mathsf{NP}$-hard". In fact, it was not clear at all. It even seems to be an open problem. For the targeted audience, it's not a big deal because the main result is the $\mathsf{NP}$-hardness, and thus the impossibility "difficulty" to design a polynomial algorithm.

But, of course, I want to correct the mistake in the journal version.

  My question is: In a journal paper, how to point a mistake in the conference version and correct it?

Should I write: "There is a mistake in the conference version: ..."? Or should I  state the correct result without saying that the conference version was wrong? Any advise is welcome.

I think it is very helpful to point out if and where previous results are erroneous. I've done this myself (more times than I would have liked to). My style is to state the correct result, and in immediate proximity (above, below, footnote) a remark to the effect that "In the conference version [citation], Theorem X incorrectly stated that...".


Number of rounds of iterative one-round distributed color reduction We are talking about one-round coloring algorithms for distributed graphs.

In "On the complexity of distributed graph coloring" (theorem 5.1) Kuhn and Wattenhoffer presented a one-round algorithm to transform an $m$-coloring to a $q$-coloring, where $q = m(d+1)/(d+2)$ ($d$ is the max degree).
We can show that if $m >= d+2$, then $q <= m-1$. [Therefore the algorithm returns a smaller coloring, as long as $m >= d+2$]

They mention that by applying this one-round algorithm over and over, we can transform an $m$-coloring to a $(d+1)$-coloring in $O(d \log(m/d))$ rounds.
I don't understand how they reached this number.

I thought that the number of rounds n needed to fulfill the equation:

$m((d+1)/(d+2))^n = d+1$

Because $m$ is the starting coloring, and each round we get a lower coloring by a factor of $(d+1)/(d+2)$.
But this doesn't yield the proper result for $n$. Why is it wrong? We want to get $n = O(d\log(m/d))$.

The algorithm itself isn't very complicated and I don't think will contribute to the question; basically for every color that is larger than $q$, we choose for him a color from $\{ 1,\ldots,q \}$ in a way that ensures it is a legal coloring.

Anybody has any insights about the number of rounds needed to achieve a $(d+1)$-coloring?

A friend helped me, the equation I wrote was correct. I simply didn't develop the result enough to bring it to the desired form. I will post more details when I have time.
Edit: what I needed to achieve the desired result is:

$log(a/b)/log(c/d) = log(b/a)/log(d/c)$

And that we should use Taylor expansion to say $log(1+1/d+1) =~ d+1$ as 1/x+1 -> 0.

If anybody needs help contact me.


Constraint types (IBM/X10) compared to dependent types Constraint types have been proposed by IBM in their X10 programming language (it's a commercial programming language, not open source software).

Nystrom, Nathaniel, et al. "Constrained types for object-oriented languages." ACM Sigplan Notices. Vol. 43. No. 10. ACM, 2008.
http://www.model.in.tum.de/um/reading-group/Grothoff.oopsla08.pdf

How do “constraint types” compare to dependent types? Or do they resemble more one of the haskell extensions that simulate dependent types?

Can say the vector append from Agda be typed as say Lists in X10?

_++_ : ∀ {m n} {A : Set} → Vec A m → Vec A n → Vec A (m + n)

Further references on constraint types:

Saraswat, Vijay, et al. "Constrained Types-Future Directions." CP-18th International Conference on Principles and Practice of Constraint Programming-2012. 2012.
http://www.cs.nyu.edu/~lianah/files/CP-2012.pdf

Nystrom, Nathaniel, et al. "Genericity through Constrained Types.
http://www.nanocow.com/nystrom/papers/generics.pdf

Tardieu, Olivier, et al. "Constrained kinds." Proceedings of the ACM international conference on Object oriented programming systems languages and applications. ACM, 2012.
http://www.inf.usi.ch/faculty/nystrom/papers/res0179-tardieu.pdf

As they explain in the related work section of the 2008 paper, the constraint types they describe are most closely related to refinement types. I wont give references, as there are plenty in the bibliography of the aforementioned paper, but I can give a quick overview.

Refinement types are a language that allow the expression of refinements of the values of a given type $C$: if $C$ is identified with the expressions of that type, then a refinement $R$ of $C$ is simply a subset $R\subseteq C$.

This is extremely helpful, as may allow the expression of invariants that the code needs to satisfy: say you have a type Rectangle with three fields, width, height and area. You are interested in the type in which area = width*height, which you might write:

{ x :: Rectangle | x.area == x.width*x.height)

This is useful for expressing pre and post-conditions on your code. Again, a trivial example would be the head function, which only makes sense on non-empty lists.

head :: NonEmptyList<A> -> A

In this respect, refinement types capture the notion of contracts, and are also related to axiomatic semantics or Hoare logic.

So here's the real issue: what is the language for expressing refinements? Say we authorize linear constraints, in wich we can have

n :: { x : Int | x < 2 }

and on the other hand we have a function of type

f :: { x : Int | x <= 1+1 } -> Bool

It is clear that f can safely be applied to n. However, for this to be statically verified, we need to prove the statement:
$$ x < 2 \Rightarrow x \leq 1+1$$
So this imposes a restriction on the expressivity of the refinement language: either the statements that need to be proven to verify type-safety are decidable (linear arithmetic and the theory of equality is a common choice in this case), or there need to be dynamic casts that are verified at runtime.

The traditional approach to dependent types, however, allows for arbitrarily complex constraints on types, with the following caveat: the onus of verification is placed on the programmer rather than on the compiler.

In this setting, an element of { x : Int | x < 2 } is not an integer less than 2, but a pair (n, e) where n is an integer and e is evidence that n<2 holds. Therefore the compiler only has to check the evidence at compile time, rather than building it herself.

Note however that some computational inferences can be performed, typically $1+1$ can be seen to be identical to $2$ (but $x<2$ can not be seen to imply $x\leq 2$ without some contribution from the user).

The obvious advantage is that arbitrarily complex constraints on the code can be verified, and the programmer may have access to automatic tools to assist the production of the required evidence (the famous "tactic language" of Coq is an example of this).

This is the main difference between refinement types and dependent types. The Haskell extensions tend to be in the second category, where evidence has to be provided by the programmer.

I do need to qualify all this: there is no hard line which differentiates refinement types from dependent types; in dependent types there may be a significant amount of information inferred by the compiler, and systems with refinement types may require information to be supplied by the developer. In fact the interaction between the communities contains IMHO some of the most interesting developments of type theory applied to practical software engineering.


When was co-NP introduced for the first time? My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space". The class $\Pi_1^P$ in there is of course coNP. Stockmeyer wrote a full paper on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.


Complexity lower bound of finding the factorial of a number I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read.

Two similar problems, Matrix Multiplication and Factorization are in, almost, all discussions about $\mathrm{P}$ and $\mathrm{NP}$. The complexity of the first is a major research field, see here, and we are trying to put Factorization inside $\mathrm{P}$.

But for the, seemingly, close problem of Factorial nothing is being said. Almost no result at all. The only one I could find is the one mentioned here and the wiki article from the far away 1983.

Why there is no interest in it? Can it have any implications in Complexity Theory like Factoring? Can Factorial be in $\mathrm{P}$ ?

Lastly one thought, Factorial must be in $\mathrm{NP}$ (or better in $\mathrm{FNP}$?) the certificate would be the actual number? that is $n!$ ?

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over some field. Their model of computation is the straight-line programs: The goal is to compute $n!$ from the constant $1$, using only additions, subtractions and multiplications. That $n!$ is ultimately hard means that the number of operations needed is asymptotically not bounded by some polynomial in $\log n$.

For more recent results in this direction (and pointers to the relevant literature), you can read a paper of Cheng [2]. The paper contains also a very brief remark about the standard complexity of the problem, that has to be exponential in $\log n$ (because of the output size), and of the modular variant of it (computing $n! \bmod m$) and its relations with integer factoring.

[1] Mike Shub and Stephen Smale. On the intractability of Hilbert’s nullstellensatz and an algebraic version of “P=NP?”. Duke Math. J., 81:47–54, 1995.

[2]  Qi Cheng, On the Ultimate Complexity of Factorials, Theoretical Computer Science, Volume 326, Issues 1-3, Pages 419-429.


Is there a backup/replacement for the Complexity Zoo? This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close.

The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/Complexity_Zoo) has certainly been of great service to the TCS community over the years. Apparently it is down since quite a while. I was wondering, if someone is still maintaining it, if it has moved, if there is a backup server, or if there are other plans to preserve this wonderful database of complexity classes, their relationships and citations to relevant publications. If not, are there comparable webpages that could be used as a replacement?

UPDATE (Aug 1, 2012): The Zoo is back online, and Scott is looking for people volunteering to mirror it to avoid any future outages.

I cannot remark on whether the Zoo has a continuous existence on the web or elsewhere. However, there are still some proto-Zoo and Zoo-derived resources available on the web.

There seems to be a copy of at least an earlier incarnation of the Zoo on Greg Kuperburg's UC Davis website.
A Latex/PDF version of some state of the Zoo written by Chris Bourke seems still to be available on his webspace at the University of Nebraska–Lincoln.

Other sources on the net seem to be links to the first (or to the URL to the stanford.edu subsite), or pieces of the second.

It is worth noting that the entire qwiki.stanford.edu subsite seems to have disappeared, and that google searches for "qwiki", with or without specifying "stanford", either yields references to a multimedia product launched in January of last year, or produces the typical spoor of SEO companies trying to leach off of online resources.


Sum-of-square-roots-hard problems? The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater than the sum $\sum_i \sqrt{b_i}$.  The complexity status of this problem is open; see this post for further details.  This problem arises naturally in computational geometry, especially in problems involving Euclidean shortest paths, and is a significant stumbling block in transferring algorithms for those problems from the real RAM to the standard integer RAM.

Call a problem Π sum-of-square-roots-hard (abbreviated Σ√-hard?) if there is a polynomial-time reduction from the sum of square roots problem to Π.  It is not hard to prove that the following problem is sum-of-square-roots-hard:

  Shortest paths in 4d Euclidean geometric graphs

  Instance: A graph $G=(V,E)$ whose vertices are points in $\mathbb{Z}^4$, with edges weighted by Euclidean distane; two vertices $s$ and $t$

  Output: The shortest path from $s$ to $t$ in $G$.

Of course this problem can be solved in polynomial-time on the real RAM using Dijkstra's algorithm, but each comparison in that algorithm requires solving a sum-of-square-roots problem.  The reduction uses the fact that any integer can be written as the sum of four perfect squares; the output of the reduction is actually a cycle on $2n+2$ vertices.

What other problems are sum-of-square-roots-hard?  I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM.  See
my previous question for one possibility.

As Robin suggests, boring answers are boring.  For any complexity class X that contains sum-of-square-roots (for example, PSPACE or EXPTIME), every X-hard problem is boringly  sum-of-square-roots-hard.

This should be a comment, as it is a mostly boring answer, but I don´t have enough reputation.

The sum of square roots problem is in $P^{PP^{PP^{PP}}}$ from [ABKM98], so any problem hard for this class has the required property. This is done by reducing the sum-of-square-roots problem to a problem called $PosSLP$, defined as deciding whether a straight-line problem represents a positive integer, so that problem is sum-of-square-roots hard.

[ABKM98]: On the Complexity of Numerical analysis, by Allender, Burgisser, Kjeldgaard-Pedersen and Miltersen.


Agnostic learning over arbitrary distributions Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:
$$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$$
and let:
$$OPT(C,D) = \min_{f \in C}\ err(f,D)$$
Say that an algorithm $A$ agnostically learns $C$ over any distribution, if for any $D$ it can with probability $2/3$ find a function $f$ such that $err(f,D) \leq OPT(C,D) + \epsilon$, given time and a number of samples from $D$ that is bounded by a polynomial in $d$ and $1/\epsilon$.

  Question: What classes of functions $C$ are known to be agnostically learnable over arbitrary distributions?

No class is too simple! I know that even monotone conjunctions are not known to be agnostically learnable over arbitrary distributions, so I'm just looking for nontrivial classes of functions.

If no class is too simple, then here are some agnostically PAC learnable classes.  In response to the comments, the classes with polynomially many hypotheses are crossed out:

constant depth decision trees (and other classes having only poly many hypotheses)
hyperplanes in $R^2$ (only $O(n^2)$ hypotheses producing distinct labelings)
unions of intervals (dynamic programming)
parity on some of the first $\log(k)\log\log(k)$ of $n$ bits (see this and this)
other hypothesis classes in low dimensional settings.

Pretty much everything else is NP-Hard to (at least properly) agnostically PAC learn.

Adam Kalai's tutorial on agnostic learning may also interest you.


Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's QF_LIA optimizer have fallen flat, which leads me to wonder if perhaps there is an alternative formulation of the problem, and a solver that might have better performance characteristics. Any advice is appreciated.

I have:

A set $V$ of Boolean variables: $V = \{v_i\}$. For a "large" instance, $|V| \approx 6,000$.
A set $P \subseteq V \times V$. For the same "large" instance, $|P| \approx 140,000$.
A set of constraints $C \subseteq V \times V$: if $(x,y) \in C$, then $x \wedge y \neq 1$. For the same "large" instance, $|C| \approx 4,000$.
A weight function $w_1 : V \mapsto \mathbb{N}$ (i.e., a total function on $V$).
A weight function $w_2 : P \mapsto \mathbb{N}$, which is mostly unrelated to $w_1$, except that $\forall v_i,v_j. w_2(v_i,v_j) \leq min(w_1(v_i),w_1(v_j))$. $w_2$ can be thought of as either:

A total function on $P$
A partial function on $V \times V$
A total function on $V \times V$, where $w_2(x,y) = 0$ if $(x,y) \notin P$.

I want: an assignment $Asg : V \mapsto \mathbb{B}$ such that:

Satisfies all constraints: $\forall (v_i,v_j) \in C$, $Asg(v_i) \wedge Asg(v_j) \neq 1$.
Maximizes $\sum_{v_i \in V} Asg(v_i)*w_1(v_i) + \sum_{(v_i,v_j) \in P} Asg(v_i)*Asg(v_j)*w_2(v_i,v_j)$

I.e., maximizes $w_1$ on $V$ and $w_2$ on $P$ simultaneously.

Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room):

We are looking at a random graph $G$ with 6000 weighted nodes, a subgraph $G'$ induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to.

A satisfying assignment for $C$ induces a bipartite subgraph of $G'$ (all nodes with assignment 1 plus their immediate neighbors with assignment 0). So you are looking to optimize over the set of bipartite subgraphs of $G'$?

A few random thoughts:

How structured are $G$ and $G'$? I presume a random graph model is not a very good model? What is the distribution of degrees of nodes?
Are all nodes in $G'$?

Is there a way we can bound the sum of all $w_2$-induced weights for given node? We know that the node weight $w_1(v)$ is bigger than the edge weight $w_2(v, \centerdot)$, is there something to be said for $\sum_{v_2 \in V} w_2(v, v_2)$? That could give some information about whether "switching a node on" is worth it...

If nodes have a tendency to outweigh the sum of their edges, would that hint at a bigger bipartite subgraph being always better than a smaller one, and at the problem becoming one of maximizing the size of the bipartite subgraph?


Lower bound for determinant and permanent In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the following questions :
Grigoriev and Karpinski proved an $2^{\Omega{(n)}}$ lower bound for any depth-3 arithmetic circuit computing the Determinant of $n \times n$ matrices over finite fields (which I guess, also holds for the Permanent). Ryser's formula for computing the Permanent gives a depth-3 arithmetic circuit of size $O(n^2 2^n) = 2^{O(n)}$. This shows that the result is essentially tight for depth-3 circuits for the Permanent over finite fields. I have two questions:

1) Is there a depth-3 formula for the determinant analogous to Ryser's formula for the Permanent?

2) Does a lower bound on the size of arithmetic circuits computing the Determinant polynomial \textit{always} yield a lower bound for the Permanent polynomial?(Over $\mathbb{F}_2$ they are the same polynomials).

Though my question currenly is regarding these polynomials over finite fields, I would also like to know the status of these questions over arbitrary fields.

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open.

In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $perm_{q(n)}(Y)$, i.e. there is a certain substitution sending each variable $y_{ij}$ either to a variable $x_{k\ell}$ or a constant such that after this substitution the $q(n) \times q(n)$ permanent is computing the $n \times n$ determinant.

1) Thus Ryser's formula yields a depth 3 formula (depth does not increase under projections because the substitutions can be done on the input gates) of size $2^{O(q(n))}$ for determinant.   UPDATE: As @Ramprasad points out in the comments, this only gives something nontrivial if $q(n) = o(n \log n)$, since there is a trivial depth 2 formula of size $n \cdot n! = 2^{O(n \log n)}$ for det. I am with Ramprasad in that the best I know is the reduction through ABPs, which yields $q(n)=O(n^3)$.

2) If the $m \times m$ permanent can be computed - again, over some field of characteristic not 2 - by a circuit of size $s(m)$, then $n \times n$ determinant can be computed by a circuit of size $s(q(n))$. So a lower bound of $b(n)$ on circuit-size for $det_n$ yields a lower bound of $b(q^{-1}(n))$ on circuit-size for the permanent (that's $q$ inverse, not $1/q(n)$). The above-mentioned $q(n)=O(n^3)$ yields a $b(n^{1/3})$ perm lower bound from a $b(n)$ det lower bound.


Capacity planning algorithm resources Let's say I have a machine with many boxes of different sizes. I want to put packages inside those boxes. Packages arrive at different time and then stay in the box for specific period of time. I need to be able to tell if there is be an appropriate box available in the future for the package (will there be small size box for package in five days?).

I'm sure there are many papers about this kind of problem. Unfortunately I cannot find one, wrong keywords probably.

Thank you for your answers.

I am still unclear about the precise objective you want to optimise over, but you could look at

Peter Brucker,
Andreas Drexl,
Rolf Möhring,
Klaus Neumann, and
Erwin Pesch,
Resource-constrained project scheduling: Notation, classification, models, and methods,
European Journal of Operational Research
112
3–41,
1999.
doi:10.1016/S0377-2217(98)00204-5

for a comprehensive interdisciplinary overview of related terminology for many such problems.  These kinds of problems are studied in operational research, management science, computer science, and statistics.  There is an extensive literature about nearly every kind of such problem, but it can be hard to find the right terms and to translate between the different styles of exposition.  Good luck!


L1 - embeddability of metrics supported on the Hypercube I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.

Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge of the boolean hypercube has a non negative distance associated with it and the metric is defined by the length of the shortest path according to the distance function between any two vertices. Can we put upper bounds/lower bounds on the distortion when we embed such a metric into $l_1$ ?

Any references would be highly appreciated.

In general there are all kinds of lower bounds for embedding an arbitrary metric on the hypercube into $\ell_1$. For example, the edit distance cannot be embedded with better than $\log n$ distortion. Note that the Hamming distance itself embeds isometrically in $\ell_1$, so you can't expect to prove any nontrivial lower bound over all metrics on the hypercube.

p.s I don't think the boolean-ness matters at all.


Recognizing line graphs of hypergraphs The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection.
A hypergraph is an $r$-hypergraph if each of its edges has at most $r$ vertices.

What is the complexity of the following problem: Given a graph $G$, does there exist a $3$-hypergraph $H$ such that $G$ is the line graph of $H$?

It is well-known that recognizing line graphs of $2$-hypergraph is polynomial, and it is known (by Poljak et al., Discrete Appl. Math. 3(1981)301-312) that recognizing line graphs of $r$-hypergraphs is NP-complete for any fixed $r \ge 4$.

Note: In case of simple hypergraphs, i.e. all hyperedges are distinct,
the problem is NP-complete as proved in the paper by Poljak et al.

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

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

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


Large classes which contain LOGSPACE for which strict inclusions are unknown The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references).

Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these known to be strict?

Q2: If no, is there an established class $C$ which contains $P^{\#P}$ and for which it is not known if the inclusion $L\subset C$ is strict?

Q3: Are such inclusions discussed in literature?

This is a favorite question of mine.

Fortnow showed, in his paper "Time-Space Tradeoffs for Satisfiability", that $NL$ is properly contained in $\Sigma_{a(n)} P$, where $a(n)$ is any unbounded function. That is, nondeterministic logspace is properly contained in alternating polynomial time with $a(n)$ alternations.

Showing that $NL$ is not in $\Sigma_k P$ for a fixed constant $k$ would imply that $NL \neq NP$. (To see this, consider the contrapositive.)

It is open whether $NL = P^{\#P}$. The last time I seriously attempted to prove this, it resulted in the paper "Time-Space Tradeoffs for Counting NP Solutions Modulo Integers". I was trying to find some simulation of every language in logspace that would take $n^k$ time for some fixed $k$ when one has access to an oracle for counting satisfying assignments to a given formula. (This would imply $LOGSPACE \neq P^{\#P}$.) My approach didn't work, but I ended up using the same approach to prove time-space lower bounds for solving $Mod_6 SAT$ and other related results.

Uniform-$TC^0$ is properly contained in $P^{\#P}$. The proof is in Allender, "The Permanent Requires Large Uniform Threshold Circuits". Any improvement on this separation is open. (For example, proving uniform-$NC^1 \neq P^{\#P}$ is open, and proving uniform-$TC^0 \neq NP$ is also open.)


How can algorithms with nested combinatorial searches be quasi-linear? I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without stating any relaxing conditions. Since I haven't encountered any proofs that specifically target this issue, I wonder if there is something obvious I'm missing in algorithm analysis.

The example comes from this paper by Spielman and Teng, more specifically section 2.1, algorithm Nibble. The algorithm is a for-loop (with the number iterations defined approximately by $log_2(n) ln(n)$, where $n$ is the number of vertices in the graph). However, step 3.c states that the algorithm will exit, if a suitable set of $j$ vertices exists that satisfies some conditions. This set is in the paper's terminology designated as $S_j(q_t)$ and is defined as "the set of $j$ vertices $u$ that maximize $\frac{q_t(u)}{d(u)}$", where $d(u)$ is the degree of vertex $u$.

Note that the focus here is on the general problem of generating a subset of elements that fulfills some conditions and is subject to a constrained number of elements. Other aspects of the algorithm were covered in the proof.

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set. Also, I found no mention of it in the proof section. That, the reputability of the authors and the prominence of the paper makes me think that it's something obvious.

My question is what factors would make such an algorithm quasi-linear? Citing a paper where a similar algorithm's complexity is proven and the proof focuses this issue is most welcome.

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set.

No, it's just a selection problem, for which there are well-known linear algorithms.


Translation of Counter-free automata into Linear Temporal Logic There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a counter-free automaton.
Is there any reference that shows such a translation?
[1] Wolfgang Thomas, Safety- and Liveness-properties in Propositional Temporal Logic: Characterisation and Decidability, Mathematical Problems in Computation Theory, Volume 21, 1988

As mentioned in the comments, the translation is shown in:
Diekert, Volker, and Paul Gastin. "First-order definable languages." (2008)
http://www.lsv.fr/Publis/PAPERS/PDF/DG-WT08.pdf
And it goes via a characterization of $LTL$ as $FO[<]$.


Is there an efficient construction for a trilinear pairing that has been used in theory or practice A trilinear pairing is defined a function $e:G_1^3 \rightarrow G_2$, such that it satisfies the property $e(k_1^a, k_2^b, k_3^c) = e(k_1,k_2,k_3)^{abc}$

In general I am trying to solve the following problem,
given a tuple $$(g, g^s, g^{r_1}, g^{r_2}, k_1, k_2, k_1^{r_1s},k_2^{r_2s'} )$$
where $g, k_1,k_2 ∈ G_1$ and $r_1, r_2, s,s' ∈ {Z_q}$

Is it possible to predict if $s = s'$?

One of the easy ways is to use trilinear mapping function $e$ to evaluate
$$e(g^{r_2}, k_1^{r_1s}, k_2 ) = e(g^{r_1}, k_1, k_2^{r_2s'})$$

However this can only be true if there exists an efficient construction of a trilinear pairing...
Is there a feasible construction available for a trilinear mapping or at least is it/has it been used in theory and in proofs?
Is there any other way to examine the same?

This question has been open for long now, and after some research I think I have the following answer

There has been two candidate schemes proposed for multilinear pairing by Garg, Gentry,  Halevi and Coron, Lepoint, Tibouchi.

However either do not have a security proof and their security is given by extensive cryptanalysis.

So, to sum it up, although it is possible to implement a "trilinear" map, these maps are NOT (provably) cryptographically secure.


Complexity of finding the maximal number of pair-wise disjoint sets Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-complete or not:

Problem A. Are there $M$ ($1 \le M \le P$) distinct sets within the $P$ sets (i.e., their pair-wise intersection is empty)?

Problem B. Now $k$ ($k<n$) elements can be chosen from each set. Are there $L$ ($1 \le L \le P$) distinct sets of size $k$ each within the $P$ sets? Note that only one set of $k$ elements can be taken from each set of $n$ elements.

Remark: I am mainly interested in the case where $k,n$ are fixed ($n \ge 2, k \ge 2$).

I think that Problem A can be thought as an $n$-uniform $r$-partite hyper-graph matching problem. That is, we have the elements of $r$ as vertices, and each hyper-edge contains a subset of $n$ vertices of the graph.

In the $n$-uniform $r$-partite hyper-graph matching problem NP-complete?
I think that Problem B is equivalent to finding the number of distinct hyper-edges of cardinality $k$ taken from hyper-edges of cardinality $n$. Is this restricted version (in the sense that each $k$-cardinality set is taken from a pre-chosen set of $n$ elements rather than taken arbitrarily from $r$ elements) of Problem A NP-complete?

Example ($n=3,r=5, P=3$):

$A=\{1,2,3\}$, $B=\{2,3,4\}$, $C=\{3,4,5\}$

If $k=n=3$, there is only $M=1$ one distinct set, which is $A$ or $B$ or $C$, since each of the pairs $(A,B)$, $(A,C)$, $(B,C)$ has non-empty intersection.

If $k=2$, we have $L=2$ distinct sets: one solution is $\{1,2\}$, $\{3,4\}$ (subsets of $A$ and $B$).

This is a special case of the Maximum Set Packing Problem and both problem A and B are NP-Complete. Note that the problem is simply a matching problem if $n=2$ and is also easy if $n=1$. So I'll assume $n \ge 3$.

Instead of asking the question,

  Are there $M$ disjoint sets among the $P$ sets?

Let's ask the following question

  What is the maximum number of disjoint sets we can obtain from the $P$ sets?

It is clear that if the second question is answerable in polynomial time, then so is the first since all we have to do is compare this maximum value to $M$ and output YES if $M$ is less than or equal to this maximum and NO otherwise.

Also, if the first question is answerable in polynomial time, then the second is too since we can use binary search on $M$ and obtain the answer to the second question and only add a factor of $O(\log{M})$

So we can conclude that both questions are equivalent. i.e. Question 1 is polylomial time solvable if and only if Question 2 is too.

It is also clear that the problems are in NP since we can easily verify that the $M$ sets outputed are disjoint.

So the question now is how do we reduce a known NP-Hard problem to this? To do this we reduce from the maximum set packing problem. I'll simply focus on problem A since problem B can easily be shown to be hard by setting $k=n-1$

Consider an arbitrary instance of the maximum set packing problem $T$. Note that the only difference between problem A and the original maximum set packing problem is that in problem A, the size of the sets have to be equal. Let $t$ be the maximum cardinality among all sets in $T$. If every set in $T$ have the same cardinality, we are done and the set cover problem is exactlly problem A. Now suppose that for some set $S_i \in T$, we have $|S_i| < t$. We simply add $(t-|S_i|)$ elements to $S_i$ which are not elements of any set in $T$. We repeat this process until all sets $S_i \in T$ have the same size. It is clear that adding new elements in this way does not change the size of the maximum number of disjoint sets.

So, if we can solve problem $A$ in polynomial time, we can solve the maximum set packing problem in polynomial time since all we have to do is remove the extra elements that we have added, and doing this doesn't change the size of the maximum number of disjoint sets in $T$.

EDIT - Some Additional information about problem B

Suppose problem B has a polynomial time solution, now consider an arbitrary instance $T$ of problem A with $n$ elements per set. Now we add a dummy element $d$ to each set in $T$. We now ask the following question.

  What is the maximum number of disjoint sets we can obtain by taking
  $n$ elements from each set?

Now we know that among the sets in the maximum, at most one of them can contain the dummy element, hence if the answer we get as the maximum is $M$, then the actual maximum number of sets in instance $T$ (our original problem A) is either $M$ or $(M-1)$, but this gives a constant factor approximation for maximum set packing. And such an approximation is only possible if $P=NP$. So problem B is also hard.