texts: Are there Petri net models with "checking" rather than "taking" transitions?

texts:
Is there a studied model of Petri nets where each transition only has one normal in-edge (which removes a marker from a place), but can also have "checking" edges, which only check whether there is a marker in a place?

Alternatively, each transition has at least one out-edge to each of its input places, except for one.

Such a net would model a random-permitting context grammar, but a Google Scholar search for "random permitting context" and "petri net" doesn't yield any likely candidates.

EDIT: it seems my question is not very clear, but I'm unsure exactly of how to improve it.

I'm looking for a restricted class of Petri nets: these nets can indeed be simulated by ordinary Petri nets, so I'm definitely not looking for a generalisation of Petri nets.

Unless I'm more-than-usually confused, there are Petri nets which cannot be simulated by these nets.

Perhaps my motivation and what I mean by my definition can be clarified by a further restriction: we keep the restriction of each transition having only one normal in-edge, but further disallow checking edges.
In this case, we get a model (the Parikh vectors of) the context-free languages: each transition represents a production and places represent symbols, with a production deleting one symbol and adding any number of others.

Marek and Češka have shown that Petri nets can simulate any random-context language; the random-permitting context languages are a strictly smaller class (even when we ignore the order of symbols). For example $\{a^{2^n} : n \in \mathbb{N}\}$ is a random-context language but is not random-permitting context language (these languages satisfy a pumping lemma).

The Petri nets here correspond to these languages: the production $A \rightarrow XYZ$ with permitting set $\{C,D\}$ corresponds to a transition with an in-edge from $A$, out-edges to $X$, $Y$ and $Z$, and checking edges from $C$ and $D$.


texts: Is there a list of NPC or harder problems for specific real world problem domains?

texts:
The domains of interest to me are:
1. Robotics
2. Search
3. NLP
4. Image feature extraction
5. Network optimization
6. Network security


texts: Bipartite formula complexity lower bound

texts:
I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 from that page.

The approach is to construct an polynomial approximation $p$ for the function $f$, and then show that the matrix $M_f$ is equal to the matrix consisting of sign$(p(x,y))$ for each entry $x,y$.

My question is regarding the following sentence, found on the very last paragraph of the page:

  Each summand on the right-hand side corresponds to a matrix of rank 1 over the reals.

I do understand why this must be true. If I construct a matrix with coordinates corresponding to, say, the first summand evaluated at $x,y$ for each row/column $x,y$, I don't see why it must be rank-one.


texts: Speedup from algorithmic advances vs. hardware

texts: I recall seeing a study or article a while ago claiming that most of the speedup seen in computer programs over the last several decades is from better algorithms rather than faster hardware. Does anyone know the study or article?


texts: NP-hard problems with very fast exponential-time algorithms

texts:
NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.

Is any fact like

"For any constant $\epsilon>0$ there is an NP-hard 'natural' problem $\Pi_{\epsilon}$ that is not solvable in subexponential time $O(2^{o(n)})$
(assuming ETH) but can be solved in $O\left((1+\epsilon)^n\right)$ time by an exact algorithm."

in the literature somewhere?

(Actually, I am not able to find such an NP-hard problem that can be solved in time near $O(1.01^n)$.)

I do not have a formal definition for natural problems. (but I think each of us has an idea what a natural problem should be?)
Searching the literature I found the following paper which is very close to my question.
The informal discussion on page 2 of this paper is perhaps what I mean
by natural (graph)problems. On page 15, the authors also ask for (sporadic)
problems not solvable in subexponential time but have very fast exponential-time
algorithms. (My question goes a step further by expressing 'very fast' in $\epsilon$:
Given $\epsilon$, is there such a problem, depending on $\epsilon$, that can solved in
$O((1+\epsilon)^n)$ time?)


texts: The significance of state complexity in automata and regular languages?

texts:
I'm reading "Concatenation of Regular Languages and Descriptional Complexity" by Galina Jiraskova, 2009 on the state complexity resulting from concatenation of two regular languages ( by Galina Jiraskova), but I can't understand what the practical implications of state complexity would be. The first trivial thought that struck me was that higher complexity would require more time and space by the machine. Is this correct? Also are there any other places where state complexity is relevant and signinficant?

Edit:
The state complexity of a regular language is the smallest number of states in any
deterministic finite automaton (dfa) accepting the language. The nondeterministic
state complexity of a regular language is defined as the smallest number of states in any nondeterministic finite automaton (nfa) for the language.


texts: Looking for information about a problem of a least subset of vectors modulo 2 summing to another vector

texts:
I'm quite interested in the following algorithmic problem, on which I can't find any information. Phrased as a decision problem:

Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ in $\text{GF}(2)^n$, and an integer $k$, decide whether there exists a subset $S \subseteq V$ such that $|S|\leq k$ and  $\sum_{\mathbf v\in S} \mathbf v = \mathbf u$.

Note that despite sounding similar to the subset sum problem, it's actually quite different – in particular without the $|S|\leq k$ restriction it's basic linear algebra. My attempts to google the problem have failed so far. Is this a problem already explored in some papers? Is it equivalent to another well-known problem? Is it solvable by a practical algorithm? Is it NP-complete? I would be surprised if there was no literature about this problem at all given the short formulation.
What I figured out by myself is that this problem could be polynomially reduced to the problem of

Given a set of vectors $V$ in $\text{GF}(2)^n$, a vector $\mathbf u$ in $\text{GF}(2)^n$, and an integer $k$, decide whether there exists a subset $S \subseteq V$ such that the vector $\mathbf u+\sum_{\mathbf v\in S} \mathbf v$ consists of at most $k$ ones.

Maybe this one is better-known?


texts:
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine where the input comes "padded" with endmarkers on both ends which can never be overwritten, and so that the head can never move out of the input region, "outside" the endmarkers.

The LBA is bounded-visit if there is a number $k$ such that all runs on all inputs terminate and visit every cell of the tape at most $k$ times.

Does such a machine recognize only regular languages? Hennie's result seems to say this only for deterministic machines, if I'm reading it right. Does the result hold for nondeterministic machines too? If yes, a reference would be appreciated.


texts:
In the pebble game on a line there are N+1 nodes labelled 0 through N. The game starts with a pebble on node 0. If there is a pebble on node i, you can add or remove a pebble from node i+1. The goal is to place a pebble on node N, without placing many pebbles on the board at the same time and without taking too many steps.

The naive solution is to place a pebble on 1, then 2, then 3, and so forth. This is optimal in terms of the number of steps. It's not optimal in the maximum number of pebbles on the board at the same time: during the last step there are N pebbles on the board (not counting the one on 0).

A strategy that places fewer pebbles on the board at the same time is in this paper. They reach node N without exceeding $\Theta(\lg N)$ pebbles at a time, but at the cost of increasing the number of steps to $\Theta(n^{\lg_2 3})$. They toggle whether there's a pebble at position $N$ without leaving any other pebbles around by recursively toggling $N/2$, using that as a starting point to toggle $N$ with another recursive step, then toggling $N/2$ with a third half-sized recursive step to clear it.

I'm interested in the tradeoff between the maximum number of pebbles and the number of steps, under the assumption that pebble additions and removals can be done in parallel. By "parallel" I mean that each step can add or remove as many pebbles as desired, as long as each individual addition/removal is allowed and doesn't interact with the other moves being made. Specifically, if $A$ is the set of nodes we want to add or remove pebbles from, and $P$ is the set of nodes that had a pebble at the start of the step, then we can do all those additions and removals in a single step as long as $\{a-1 | a \in A \} \subseteq P - A$.

For example, consider the strategy that places a pebble at $i$ on step $i$, but marks the pebbles that are multiples of $\sqrt{N}$ as "checkpoints" and removes the highest-index pebble behind a pebbled checkpoint whenever possible. This strategy still reaches node N after $N$ steps, like the naive strategy, but reduces the maximum number of pebbles from $N$ to $2 \sqrt{N}$.

Are there parrallel-line-pebbling strategies that finish in $N$ steps with even lower asymptotic max-pebble complexity? What if we're willing to allow $O(N \lg N)$ steps? What are the "interesting" points, where the tradeoff between max-pebble and time is particularly good?


texts:
Let $S$ be a collection of sets of binary vectors (in $\{0,1\}^m$) $S_1, S_2, \dotsc, S_t$ (say $t = O(m^d)$) each of VC dimension $d$. What can be said about the size of a hitting set $S_\text{hit}$ which consists of binary vectors that intersect every set $S_1, \dotsc, S_t$?

Any relevant reference would be of great help.

Thanks!


texts: Deterministic dynamic dictionary on a small universe

texts:
We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe has size $\{0,\ldots,n^c-1\}$ for some constant $c$.
How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to $O(n)$ space? How about $O(n \mathop{\mathrm{polylog}} n)$ space?
A few simple observations:

When $c=1$, an array of size $n$ support all operations in worst time $O(1)$.

It's not hard to come up with a $O(n^{1+\epsilon})$ space data structure so all queries can be done in $O(\frac{1}{\epsilon})$ worst case time for any $\epsilon>0$.

We can implement all operations in worst time $O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$ with $O(m)$ space using exponential tree.[1]

To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.


texts: What is the recommended software for drawing data structures such as graphs and trees?

texts: When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint.  What is the standard for drawing data structures?


texts: Nonterminal descriptional complexity of regular languages

texts:
Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.
I am aware of an old Grushka's article and a more recent paper by Dassow and Stiebe. I've also found Wolfsteiner's thesis.
What is the state of art of the study of grammar complexity? Could you explain simply the connection between grammar complexity and formal proof theory?


texts:
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.

You may recall that Hoffman and Singleton proved that the only Moore Graphs [: regular graphs achieving the Moore Bound for a given diameter $d$ and a degree $\Delta$] that exist for diameter $d=2$ are for degree $\Delta=2,3,7$ and possibly 57, but for no other degrees.

Little is really known about the 57-Moore Graph. I will attempt to make a complete list of all facts known about it here and hopefully start a conversation or discover more of them that I may have missed.

The 57-Moore Graph will have:

Diameter $d=2$, [definition]
Degree $\Delta=57$, [definition]
Girth $g=5$, [MS10]
Number of vertices $|V| = 3250$, [definition]
Number of edges $|E| = 92625$, [definition]
At most 375 automorphisms, [MS10]
Independent Number at most 400, and [reference missing, take it with a grain of salt]
It will be regular, [definition]
It will not be vertex-transitive. [Ca83]

Some more results from combinations of the above:

Proposition 1. [MS10] It's Adjacency Matrix $A$ will satisfy $$A^2 +A - 56I = J,$$ where $I$ is the identity matrix and $J$ the all one matrix. Consequently, it's eigenvalues will be 57, 7, and −8, with multiplicities 1, 1729, and 1520, respectively.

This, to the best of my knowledge, is all we know about the existence of this graph. Have I missed something? Is there something more that we can say about this graph?

Moreover, assuming that this graph exists, is there any hope in pruning down the search space enough to at least try to find it with a semi-brute force approach using supercomputers? Clearly, the search space is too large to brute force even if knew the exact edge count. But can we make other observations towards this or do you think that it is hopeless and that the existence (or not) of this graph would have to be proved some other way?

Thank you.

[Ca83] P.J. Cameron, Automorphism groups of graphs, Selected Topics in Graph Theory II (ed. L. W. Beineke and R. J. Wilson), 89-127, Academic Press, London, 1983.

[MS10] M. Mačaj, J. Širáň, Search for properties of the missing Moore graph, Linear Algebra and its Applications, Volume 432, Issue 9, 15 April 2010, Pages 2381-2398, ISSN 0024-3795 (http://www.sciencedirect.com/science/article/pii/S0024379509003735#)


texts: Shouldn't relativisation contain consistency proof ?

texts:
My question may be stupid, but let's take the Baker-Gill-Soloway theorem as an example :

There exists an oracle A such as $P^A = NP^A$ and an oracle B such as $P^B \neq NP^B$.

If we take both oracles A and B, I suppose we have $P^{A,B} = NP^{A,B}$ and $P^{A,B} \neq NP^{A,B}$, and then, theory wouldn't be consistent.

What says us that the theory with only oracle A is consistent ? If such theory isn't consistent, then there could be non-relativizing proofs of $P \neq NP$.


texts: How to prove fooling set problem to be NP-hard

texts:
I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself.

Thank you.

Edit: The fooling set technique is defined by the following theorem:


texts: An example of a totally computable function that is not definable in system T?

texts: Could you give me an example of a totally computable function of type N × N → N that is not definable in System T? Thanks.


texts:
Consider the following game on a directed weighted graph $G$ with a chip at some node.

All nodes of $G$ are marked by A or B.

There are two players Alice and Bob. The goal of Alice (Bob) is to shift the chip to a node that marked by A (B).

Initially Alice and Bob have $m_A$ and $m_B$ dollars respectively.

If a player is in a losing position (i.e., current position of the chip is marked by opposite letter) he or she can move the chip to a neighboring node. Such move costs some dollars (the weight of the corresponding edge).

The player loses if he or she is in a losing position and has not money to fix it.

Now consider the language GAME that consists of all directed weighted graphs $G$ (all weights are positive integers), initial position of the chip, and capitals of Alice and Bob that are given in the unary representation

such that Alice has a wining strategy at this game.

The language GAME belongs to P. Indeed, the current position of the game is defined by the position of the chip and the current capitals of Alice and Bob, so dynamic programming works (here it is important that initial capitals are given in the unary representation).

Now consider the following generalization of this game. Consider several directed weighted graphs $G_1, \ldots G_n$ with a chip at each graph. All nodes of all graphs are marked by A and B. Now Bob wins if all chips are marked by B and Alice wins  if at least one chip marked by A.

Consider the language MULTI-GAME that consists of all graphs $G_1, \ldots, G_n$, initial positions and capitals $m_A$ and $m_B$ (in the unary representation) such that Alice wins at the corresponding game.  Here it is important that capitals are common for all graphs so, it is not just several independent GAMEs.

Question What is the complexity of the language MULTI-GAMES? (Is it also belongs to P or there are some reasons to thing that this problem is hard?)

UPD1 Neal Young suggested to use Conway's theory. However I do not know is it possible to use this theory for several games with common capital.

UPD2 I want to show an example that shows that MULTI-GAME is not very simple.  Let Alice split her capital $m_A$ to some $n$ terms $m_A = a_1 + a_2 + \ldots a_n$ (She is going to use $a_i$ dollars for $i$-th graph). Define $b_i$ as the minimal number such that in $i$-th game Bob wins if Alice and Bob have $a_i$ and $b_i$ dollars respectively. If $b_1 + \ldots b_n > m_B$ (for  some spliting $m_A = a_1 + a_2 + \ldots a_n$) then Alice wins. However, the opposite is not true. Consider two copies of the following graph (initially the chip is at the left up A):

For one graph Bob wins if $m_A=0$ and $m_B=2$ or if $m_A=1$ and $m_B=3$.
However for the game with two copies of this graph Bob loses if $m_A=1$ and $m_B=5$. Indeed, Bob have to spend $4$ or $5$ dollars to shift both chips to a node marked by $B$. Then Alice can shift at least one chip to a node marked by A. After that Bob have not money to save his position.

UPD3 Since the question for arbitrary graphs seems difficult consider specific graphs. Denote the nodes of some graph $G_i$ as $1, \ldots k$. My restriction is the following: for every pair $i<j$ there exists edge from $i$ to $j$ and there is no the reverse edge. Also there exists a restriction for the costs of edges: for $i<j<k$ the edge $j$ to $k$ is not greater than from $i$ to $k$.


texts:
Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (some arbitrary, some not)

It should be a well defined method without numerous parameters, and with a concrete running time (maybe per iteration)
It should have some known theoretical results associated with it (rate of convergence, approximation bounds if any, stationary properties, and so on)
It should have wide applicability and at least one flagship application where it's either the method of choice or one of a few.
it should not be inspired by nature (while this seems like a frivolous objection, I'm trying to exclude genetic algorithms, ant colony optimization and the like).

Answers should ideally be in the following format: here's an example.

Name: Alternating optimizaton

Goal: Minimize a (generally nonconvex) function $f(x,y)$

Conditions: The associated functions $g(x) = \min_y f(x,y)$ and $h(y) = \min_x f(x,y)$ are convex

Algorithm: $i^{\text{th}}$ iteration starts with $x_i, y_i$.

$x_{i+1} \leftarrow \arg \min_x f(x, y_i)$
$y_{i+1} \leftarrow \arg\min_y f(x_{i+1}, y)$

Best known app: $k$-means, iterated closest pair.

Theory: Known results on $k$-means, general sufficient conditions for global optimality of framework

p.s You might find that your answer ends up as a lecture in an algorithms seminar I'm planning :)


texts: Surveys on Algorithmic Problems in Coding Theory

texts:
Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. I'm aware of the NP-completeness of Maximum likelihood decoding problem.

Are there recent surveys and tutorials of computationally hard problems in coding theory?

I'm more interested in surveys that do not assume strong background in coding theory.


texts: Set optimization problem - is it np-complete?

texts:
Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective function:
$$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$$.

Is the problem NP-hard?

Since the objective function seems weird, it is helpful to explain an application of the objective function.

Suppose we have n items $e_1$ to $e_n$ and there are $c_i$ copies of each object $e_i$ in our inventory. We have some customers and they are interested in these objects in proportion with their weight $w_i$, which means the object with greater $w_i$ is more popular. We have an online sale system and we need to answer our customer's requests correctly. We cannot recognize objects by their shapes (They all look the same!). But we have some classifier to find them. Each classifier can be used for detecting copies of an object. We aim to run k classifier in order to maximize our customer's satisfaction.

P.S: It may be useful to think about the case that $w_i c_i=p$ for all $i\leq n$; however, I'm not sure.[I was wrong about this! It is in P by this assumption]


texts: Why REFL rule is primitive in HOL Light?

texts:
HOL Light
assumed REFL as a primitive.
Why does it need to do so?
Can't REFL rule be deduced in this way using ASSUME twice and DEDUCT_ANTISYM_RULE once?

$$\frac{\overline{\{p\}\vdash p} \quad \overline{\{p\}\vdash p}}{\vdash p = p}$$


texts: Are there other proofs for Barrington's theorem?

texts:
I know that you can use other non-solvable groups, but is there a proof that uses a completely different approach?

In case someone would not know the theorem:
http://en.wikipedia.org/wiki/NC_(complexity)#Barrington.27s_theorem


texts:
Long/Servedio showed AdaBoost/etc doesn't perform well under noisy environments, but that branching forms of boosting do.  Can any point me to a list of branching boosting algorithms, or a reference for the current best-of-breed alternatives?

Much appreciated!


texts: k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?

texts:
It is well known that bounded diameter planar graphs have bounded treewidth (e.g. see this). Does the converse hold? That is, is every planar bounded treewidth graph the (induced?) subgraph of a bounded diameter planar graph?

I am interested in a proof sketch/reference if this is true or a counterexample if this is false.

Note1: David's correct answer below is in the negative. In its light can we modify the question to read: Are k-outerplanar graphs subgraphs of simultaneously bounded diameter and bounded genus graphs?

Note2: David further indicates (correctly) that the nested triangles graph cannot be made bounded tree-width even at the expense of increasing the genus to a constant.


texts: Complexity class for quantum computer with commutative gates

texts:
BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be represented by unitary matrices. In general, unitary matrices do not commute with each other.

My question is what would be BQP analog for a quantum computer where only unitary matrices that commute with each other are allowed?


texts:
Background
A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs are labeled by outputs in $\{A,B\}$, and each edge is labeled by $0$ for the left child and $1$ for the right child. To apply a tree to an input $x$:

Start at the root
if you are at leaf, you output the leaf label $A$ or $B$ and terminate
Read the label $j$ of your current node, if $x_j = 0$ then move to the left child and if $x_j = 1$ then move to the right child.
jump to step (2)

The tree is used as a way to evaluate a functions, in particular we say a tree $T$ represents a total function $f$ if for each $x \in \{0,1\}^n$ we have $T(x) = f(x)$. The query complexity of a tree is its depth, and the query complexity of a function is the depth of the smallest tree that represents it.

Problem
Given a binary decision tree T output a binary decision tree T' of minimal depth such that T and T' represent the same function.
Question
What is the best known algorithm for this? Are any lower bounds known? What if we know that the $\text{depth}(T') = O(\log \text{depth}(T))$? What about if we only require $T'$ to be of approximately minimal depth?

Naive approach
The naive approach is given $d = \text{depth}(T)$ to recursively enumerate all binary decision trees of depth $d - 1$ while testing if they evaluate to the same thing as $T$. This seems to require $O(\frac{d 2^n n!}{(n - d)!})$ steps (assuming that it takes $d$ steps to check what $T(x)$ evaluates to for an arbitrary $x$). Is there a better approach?
Motivation
This question is motivated by a previous question on the trade off between query complexity and time complexity. In particular, the goal is to bound the time separation for total functions. We can make a tree $T$ from a time optimal algorithm with runtime $t$, and then we would like to convert it to a tree $T'$ for a query optimal algorithm. Unfortunately, if $t \in O(n!/(n - d)!)$ (and often $d \in \Theta(n)$) the bottleneck is the conversion. It would be nice if we could replace $n!/(n - d)!$ by something like $2^d$.


texts: Two-player zero-sum games in extensive form represented as directed acyclic graphs

texts:
The following is a way to represent two-player zero-sum games in extensive form. Consider a directed acyclic graph $G$ where each non-terminal vertex is one of 3 types: player 1 vertex, player 2 vertex or chance vertex. There is a designated initial vertex $v_0$. The vertices of each player are divided into information sets. The edges outcoming from player nodes are labeled by actions, s.t. vertices in the same information set have the same set of actions and vertices in different information sets have disjoint sets of actions. The edges outcoming from chance nodes are labeled by transition probabilities. The terminal vertices are labeled by payoffs.

We say that such a game has "perfect recall" when knowing the sequence of actions that player $i \in \{1,2\}$ took before reaching a given information set $U$ of player $i$ tells us nothing about which particular vertex $v \in U$ we reached, i.e. all vertices in $U$ have the same possible histories from the perspective of the given player.

Koller and Megiddo have established that zero-sum two-player games in extensive form with perfect recall can be solved in polynomial time (i.e. we can find a Nash equilibrium in behavioral strategies). This assumes the game is given as an explicit tree. Now, unpacking the DAG into a tree can obviously increase its size exponentially. The question is thus:

  What is the complexity of computing the value of a two-player zero-sum DAG game with perfect recall?

Note that, as opposed to the tree case, I don't even know whether there is a Nash equilibrium in behavioral strategies.

As another variant, instead of labeling the terminal nodes by payoffs we can label every edge by a payoff so that the total payoff is a sum over traversed edges (this is similar to the games defined by McMahan and Gordon). For trees this doesn't matter but for DAGs separating vertices in order to remember accumulated payoff can again cause an exponential expansion (although if we're willing to settle on approximating with $\frac{1}{poly(n)}$, this expansion can probably be contained).

If the problems above are likely to require superpolynomial time, I am also interested in the special cases in which one of the players has perfect information (the case where both players have perfect information is solvable by backward induction).


texts: Storage requirements for median selection (two passes algorithms)

texts:
In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array.  In particular they focus on the following model:

the input is read from left to right for a number P of times.

It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1.  I haven't seen any result for P>1.  Is anyone aware of such lower bounds?

Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.


texts: Fano's inequality in the high error regime

texts:
Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More formally, given two random variables $X,Y$ that take values from some alphabet $\Sigma$ such that $\Pr[X = Y]=p$, we can lower bound the mutual information $I(X:Y)$ in terms of $p$ and $|\Sigma|$. However, this inequality is useful only if $p > 0.5$.

My question is whether there is a similar theorem that allows lower bounding the mutual information $I(X:Y)$ when $p$ is small, but non-trivial, i.e., $p > \frac{1}{|\Sigma|}$.In such a case, $Y$ is still a non-trivial guess of $X$, so it should still give some information on $X$.

To be more concrete, suppose that $X$ is uniform over $\Sigma$, and that $p = \frac{1}{|\Sigma|} + \varepsilon$. Can we say anything about the mutual information $I(X:Y)$? What if $p = \frac{1}{\log|\Sigma|}$?

Thanks!


texts: Can every undecidability proof be converted into diagonalization proof?

texts:
Possible Duplicate:
  Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

As is stated, can every undecidability proof can be stated in form of diagonalization?

Also, can halting problem be reduced to every undecidable problem? (we all know that every undecidable problem can be reduced to halting problem)

Thanks.


texts: MLTT/MiniTT: why do normal forms of sum types carry environments?

texts:
I am learning how to implement MiniTT: a simple type theoretic language, which is a dependently typed language with sum types, mutual recursive/inductive definitions and a universe of small types.
A sum type in this language is created using Sum(c1 A1, ..., cn An), which contains objects of the form ci E : Sum(c1 A1, ..., cn An), where E: Ai. For example, booleans are encoded as Sum(true 1, false 1) where 1 is the unit type. The type of naturals is encoded as rec Nat : U = Sum (zero | succ Nat). Sum types are eliminated using case-analysis, written as fun(c1 M1, ..., cn Mn), where each constructor is ci and the associated handler is Mi. For example, the elimination rule for booleans can be encoded as:
Bool : U = Sum (true | false)
elimBool : Π C:Bool → U. C false → C true → Π b:Bool. C b
= λ C.λ h0.λ h1.fun (true → h1 | false → h0)

The evaluator for type-checking using a normalization-by-evaluation strategy, where it first converts Exp into Val (values), and then reads back Val into NExp (normal-form-read-back-expressions). This NExp contains for sum-type related expressions, extra information that was not present in the Exp syntax. For example, the value NFun (normal form of sum-type eliminator) holds on to the entire environment, as does NSum (normal form of sum type). These environments are compared when checking for equality of normal forms! The precise Haskell code is:
-- | Values
data Val =
  Lam Clos -- has closure
  | Fun SClos -- has sum-closure
  | Sum SClos -- has sum-closure

-- | Normal form expressions
data NExp =
...
| NLam Int NExp -- no closure
| NFun NSClos -- holds onto closure!
| NSum NSClos -- holds onto closure!

Why does the read back versions of sum types (NSum) and sum eliminators (NFun) need to compare the entire environment, while the same is not necessary for lambda (NExp)?
Can I have a counterexample of terms that get incorrectly considered as equal if we forget their environments?

For completion, here are all the types:
type Branch = [(Name,Exp)]
data Rho = RNil | UpVar Rho Patt Val | UpDec Rho Decl
type SClos = (Branch, Rho)
data Clos = Cl Patt Exp Rho | ClCmp Clos Name

data NRho = NRNil | NUpVar NRho Patt NExp | NUpDec NRho Decl
type NSClos = (Branch, NRho)
```


texts: Approximation schemes for P-complete problems?

texts: What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\mathsf{NC}$ approximation schemes", analogous to $\mathsf{FPTAS}$ for $\mathsf{NP}$ optimization problems?


texts: Is infinitary Böhm-reduction wrt. root-active terms for $\lambda$-calculus transitive?

texts:
I expect the answer to be "obviously yes", but to my inexperienced eye, that's not directly obvious, because the definition of infinite Böhm-reduction does not include a transitivity rule (it wouldn't work), and because I couldn't find a relevant lemma in the papers themselves.

I'm referring in particular to the definition by Czajka [1] of the relation $\rightarrow^\infty_{\beta\bot}$, called infinitary Böhm-reduction. I've looked at [2], which however does not include Böhm-reduction (such that the defined relation isn't confluent IIUC, which is a problem for me).

Rationale: Defining reduction for infinitary $\lambda$-calculus is tricky. In particular, you cannot create an "infinite transitive closure" which allows an infinite number of transitivity steps, but you need to be more careful. In particular, if you define multi-step reduction coinductively, you cannot include a transitive rule, lest your relation becomes total and thus degenerate. So one ends up doing transitivity elimination, which is not always trivial; and given how unintuitive coinduction is, I'm afraid I'd fool myself when attempting a proof.

[1] Łukasz Czajka, 2014. A Coinductive Confluence Proof for Infinitary Lambda-Calculus. Proc. of Rewriting and Typed Lambda Calculi, Springer. http://www.mimuw.edu.pl/~lukaszcz/coind.pdf

[2] Jorg Endrullis and Andrew Polonsky, 2011. Infinitary Rewriting Coinductively. In Proc. of TYPES, volume 19 of LIPIcs, pages 16–27. Schloss Dagstuhl. http://drops.dagstuhl.de/opus/volltexte/2013/3897/

[3] Richard Kennaway, Jan Willem Klop, M. Ronan Sleep, and Fer-Jan de Vries, 1997. Infinitary lambda calculus. Theoretical Computer Science, 175(1):93–125. http://www.sciencedirect.com/science/article/pii/S0304397596001715


texts: Does bisimulation or the approximation lemma work for monadic streams?

texts:
For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on streams defined like this:
$s_1 \sim s_2 \iff \operatorname{head} s_1 = \operatorname{head} s_2 \wedge \operatorname{tail} s_1 \sim \operatorname{tail} s_2$.

Now, let $M$ be a monad. We'll define the type of "monadic streams" $S^M_A := \nu X. M (A \times X)$. Intuitively, if $M$ corresponds to a side effect, every time I retrieve the head from the stream I have to perform the side effect. I can define $\operatorname{head}^M: S^M_A \to M A$ and $\operatorname{tail}^M: S^M_A \to M S^M_A$ (using functoriality of $M$).

My question is now: Is there anything similar to bisimulation for monadic streams? Can I prove equality of monadic streams in the same way, using $\operatorname{head}^M$ and $\operatorname{tail}^M$? If not, what are proof methods that work on this coinductive type? Maybe the approximation lemma?

Edit: Maybe there has to be a restriction on the monad, like being completely positive?


texts: How powerful are nondeterministic constant-depth circuits?

texts:
A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ on input string $x\in \{0,1\}^{n}$ outputs $1$ if and only if there exists some witness string $w\in \{0,1\}^{\mbox{poly}(n)}$ such that the output of $C$ on input $(x,w)$ is $1$.

M.J. Wolf introduced nondeterministic circuits in 1987 and showed that $\mathsf{NC}$ circuits with a polynomial amount of nondeterministic gates are equivalent to $\mathsf{NP}$, and that $\mathsf{NC}$ circuits with $O(\log n)$ nondeterministic gates are equivalent to $\mathsf{NC}$ itself.

How much more power does a polynomial amount of nondeterministic add to constant-depth circuit classes, such as $\mathsf{AC}^{0}$, $\mathsf{ACC}^{0}$, and $\mathsf{TC}^{0}$? Do these classes then contain more powerful circuit classes like $\mathsf{NC}$ or $\mathsf{P/poly}$, or even $\mathsf{NP}$?


texts: Generating uniform integers in a range from a random generator with another range

texts:
Let $p$ and $q$ be two positive integers. I have an oracle that can generate a uniform integer in $\{1, \ldots, p\}$, the integers thus produced being independent across oracle calls. My goal is to generate a random number in $\{1, \ldots, q\}$ with uniform probability, and to do so in a way that minimizes the expected number of oracle calls required.

My question is: What is an optimal algorithm to solve this problem? I expect this to be a standard problem, so I'd be interested in pointers to the name of this problem in the literature. A special case of this problem ($p = 5$ and $q = 7$) is a standard puzzle or interview question (see here, but I was unable to find pointers to a generalization, and I don't see any optimality proof in those answers.

Of course, in general, the problem will not be solvable with a bounded number of oracle calls. Take for instance $p = 2$ and $q = 3$, or more generally, cases where some prime divisor of $q$ is not a divisor of $p$, and it is clear that for any bound $N$, the number of possible outcomes when doing $N$ calls, i.e,. $p^N$, cannot be divided evenly in $q$ buckets for each possible value.

One natural approach outlined here is to see the oracle calls as generating a uniform real number in [0, 1] from its $p$-ary writing, and terminate whenever the first decimal in the $q$-ary writing of that number is certain: think of it as using the oracle to select a subdivision of size $1/p^k$ in the interval $[0, 1]$, and concluding whenever the interval that you fall in is included in one of the $q$ intervals $[i/q, (i+1)/q]$ for $0 \leq i < q$. However, this approach does not seem optimal: for instance, for $p = q+1$, the approach only concludes in one call if the call returns 1, otherwise a second call is necessary. By contrast, a simpler rejection-based approach that calls the oracle, concludes if it falls in $\{1, \ldots, q\}$, and rejects and tries again if it falls in $q+1$, seems to have better performance.

One can try to generalize the rejection-based approach to the following: letting $k$ be minimal such that $p^k \geq q$, use $k$ oracle calls to get a uniform integer $n$ in $\{1, \ldots, p^k\}$. If $n$ falls in $\{1, \ldots, M\}$, for $M > 0$ the smallest multiple of $q$ which is $\leq p^k$, return $n \text{ mod } q$, otherwise try again. However it would seem that the additional information of which excess value in $\{M+1, \ldots, p^k\}$ was obtained could be also used in the next attempt. I can imagine how to do this (see here for a proposed algorithm, which I think is correct), but I have no idea of how to prove the optimality of such a scheme.

I am also curious about the natural variation of this problem where you want to generate not a single random number in $\{1, \ldots, q\}$, but a stream of such numbers. What's the expected number of calls per number, and an optimal method in this case?

[Note that an alternative vision of the problem that does not involve randomness at all is to think of the outcome trees: each node is either a leaf with label in $\{1, \ldots, q\}$ corresponding to a decision, or an internal node with $p$ children corresponding to an oracle call. An algorithm is a (generally infinite) such tree where, for each $1 \leq l \leq q$, the probability mass of all the leaves labeled $l$ (i.e., the sum of the mass over leaves, where the mass of each leaf is $1/p^h$, where $h$ is its height) is equal to $1/q$; and its expected performance is the sum, over all leaves, of $h/p^h$ (probability mass of this leaf, times the number of oracle calls performed in that case).]


texts: What is the enlightenment I'm supposed to attain after studying finite automata?

texts:
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)? So here are some answers I came up with after soliloquing  but still fail to see their overall contribution to the 'aha' moment:

To study what they are and aren't capable of i.e. limitations

Why?

Since they are the basic models of theoretical computation and would lay the foundation of other more capable models of computation.

What makes them 'basic'? Is it that they have only one bit of storage and state transitions?

Okay, so what? How does all this contribute to answer the question of computability? It seems Turing machines help understand this really well and there are 'lesser' models of computations like PDAs, DFA/NFAs/Regexes etc. But if one didn't know FAs what is it that they are missing out on?

So although I 'get it' to some extent, I am unable to answer this question to myself? How best would you explain 'why study D/N-FAs'? What's the question they seek to answer? How does it help and why is it the first thing taught in Automata Theory?

PS: I'm aware of the various lexicographic applications and pattern matchers that can be implemented as such. However, I don't wish to know what it can be used for practically but what was their reason for use/invention/design during the culmination of studying the theory of computation. Historically speaking what led one to start with this and what 'aha' understanding is it supposed to lead to? If you were to explain their importance to CS students just beginning to study Automata Theory, how'd you do it?


texts: Is infinitary logic a logic in the sense of Gurevich?

texts:
Gurevich provides an exact definition of what Logic capturing PTIME is.

An abstract logic $L$ consists of

a set of $L[\tau]$-sentences for each vocabulary $\tau$,
and a mapping that maps a property $\mathcal{P}_\varphi$ to each $L[\tau]$-sentence $\varphi$.

An abstract logic $L$ captures polynomial time on $\mathcal{C}$ if

for every $\tau$, $L[\tau]$ is decidable,
for every property $\mathcal{P}$ of $\tau$-structures that is decidable in polynomial time, there is a $\varphi \in L[\tau]$ which defines $\mathcal{P}$ on $\mathcal{C}$,
for every vocabulary $\tau$, we can compute an algorithm which decides $\mathcal{P}_\varphi$ for every $\varphi \in L[\tau]$.

  Infinitary logic $\mathcal{L}_{\infty \omega}$ is an extension of
  First-Order Logic s.t. if $X$ is set then  both

  $$ \bigvee_{\phi \in X} \phi \textrm{ and } \bigwedge_{\phi \in X} \phi$$

  are formulars. $\mathcal{L}^k_{\infty \omega}$ is infinitary logic
  with only $k$ distinct variables.

Apart from the question for which classes $\mathcal{C}$ of finite(!) structures, $\mathcal{L}_{\infty \omega}^k$ describes all polynomial time decidable properties, I want to know if $\mathcal{L}_{\infty \omega}^k$ is a logic in that sense.

First Question: Is $\mathcal{L}_{\infty \omega}^k[\tau]$ decidable for each $\tau$? We need an encoding for each $\varphi \in \mathcal{L}_{\infty \omega}^k[\tau]$ and a Turing Machine to decide whether $X$ is a set. Is it possible to provide a finite encoding for each $\varphi$?

Problem: If we want to define a Turing Machine which decides whether $\varphi \in \mathcal{L}_{\infty \omega}^k[\tau]$ we need a finite representation of $\varphi$. Approach: Let $\mathsf{FO}[\tau]$ be the set of all first order sentences over $\tau$. It is not possible to define a finite code for each $X \subset \mathsf{FO}[\tau]$ over a finite alphabet like $\{0,1\}$. $X$ is countable. However, $|\mathcal{P}(\mathsf{FO}[\tau])| > |\{0,1\}^*|$. Hence, there can be no bijective mapping from $\mathcal{P}(\mathsf{FO}[\tau])$ to $\{0,1\}^*$ (or any code with finite alphabet).

Second Question: The other thing is a model checking algorithm. Is there a model checking algorithm for $\mathcal{L}_{\infty \omega}^k[\tau]$ on each finite $\tau$ for classes $\mathcal{C}$ of finite structures? Can we make assertions regarding the run time? The basic ideas that on a finite structure it is sufficient to model check a finite $X' \subset X$ to decide.

Any ideas? Any references?


texts: Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

texts:
I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:

It uses O(1) space
It can be updated to reflect an insertion or deletion in O(1) time
Two identical collections (i.e., collections that have the same elements with the same multiplicities) should always hash to the same value, and two distinct collections should hash to different values with high probability (i.e., the function is independent or pairwise independent)

One initial attempt at this would be to store the product modulo a random prime of the hashes of the individual elements. This satisfies 1 and 2 but it's not clear whether it, or a close variation, would satisfy 3.

I originally posted this on StackOverflow.

*Properties 1 and 2 could be relaxed a little to, say, O(log n), or a small sublinear polynomial. The point is to see whether we can identify multi-sets and reliably test equality without storing the elements themselves.


texts: Complexity of counting the number of edge covers of a graph

texts:
An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: A Simple FPTAS for Counting Edge Covers and Generating Edge Covers of Path Graphs. However, unless I missed something, they do not provide a reference for this claim, or a proof. (Reference 3 of the first paper seemed promising, but I didn't find what I wanted there either.)

Where can I find a reference or proof of the fact that counting the number of edge covers of a graph is #P-complete?


texts:
I would like to ask you for a help about modified balls into bins problem.
Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a maximum capacity $W$.
We place $n$ balls into $m$ bins uniformly at random. That is,
there are $m^n$ different assignments of balls to bins and all of them are equally likely.

If a ball $i$ with the weight $w_i$ lands into a random bin $j$ that already contains balls of total weight $w'_j$, then two cases are possible:

$W \ge w'_j + w_i$: we put the ball into the bin and set $w'_j:= w'_j + w_i$
$W < w'_j + w_i$  : we split the ball $i$ putting $W-w'_j$ of its weight to $j$-th bin and proceed to insert the $i$-th ball with the new weight $w_i:=w_i-W+w'_j$ to the bin $j + 1 \mod{m}$.

If this helps its a modified linear probing algorithm, when we insert super keys into a hash table, where each super key consists of at most $W$ keys.

Now assume that we already have $n$ balls with weights $w_1, \dots, w_x$ in $m$ bins. The total weight of the balls is $\mathcal{W}$ and $\mathcal{W}$ is a multiple of $W$.
Let $E[T]$ is the average number of bins visited during the insertion of a new ball with the weight $W$.
I want to show that $E[T]$ is maximized when we insert $x = \mathcal{W}/W$
balls with the weight $W$ each.

Example: we have $\mathcal{W} = 8$, $W = 2$ and $m=16$.
We can insert $x=5$ balls: $\{1, 1, 2, 2, 2\}$
or $x=4$ balls:  $\{2, 2, 2, 2\}$ and so on.
The only condition is that the total weight of the balls is $8$ and the maximum weight
of each ball is $2$.
I want to show that $E[T]$ is maximized when we insert $x=4$ balls
with maximum weight $2$.

Could you please advise me some approaches or papers to tackle this problem.
Thank you very much.


texts: What kind of research can be considered publishable for undergraduate or graduate students (MSc level)

texts:
I'am currently doing a non-research Dipl.Eng (Engineering Diploma in French school system equivalent to MSc) in Computer Science.
The courses I am currently taking are software oriented, there's an absence of anything related to TCS except an Algorithm Design course I took in my first year.
However my personal interests are in TCS,in the last two years (prior to starting the program I finished a BSc in Applied Mathematics) I did a deep dive in TCS and Cryptography my goal was to understand zero-knowledge proofs so I read many books (Prof. Avi Wigderson's Mathematics and Computation, the first part of the Computational Complexity book by Arora and Barak, Scott's Aaronson book + lecture notes). I also started reading papers released on eprint.iacr.org website about zkSNARKs and zkSTARKs and I implemented some of the works.
I would like to pursue a PhD in TCS later on (I am graduating in June 2022) but there are no programs available in my country, I was told from a professor in a foreign university that the field is very competitive and because I have no published results I have very slim chances of getting accepted.
Is there an absolute necessity to publish at my level, if so what kind of research should I work on ? Improve some SNARK scheme ? Make a synthesis of previous results ? Publish in an adjacent field where I have some results (Machine Learning) ?


texts: Is the following optimization problem (a variant to a previous problem) NP-hard?

texts:
This problem is a following up question on  this one. The only difference is the newly added constraint in the bold font.

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

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

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


texts: Algorithmically compute a reasonable bound on the runtime of an algorithm

texts:
Possible Duplicate:
  Are runtime bounds in P decidable? (answer: no)

Originally asked on SO: https://stackoverflow.com/questions/13371025

I have seen many questions asking if this computation is possible, but they all ask about writing a program to compute the complexity of arbitrary algorithms (which is obviously undecideable). I am willing to make the following restrictions on the input:

The algorithm terminates
The algorithm is purely functional

The question is, can a program be written to compute the time complexity of such an algorithm through static analysis? If the input algorithm does not terminate, the program behaviour is undefined (it may crash, return a lie, or fail to terminate).


texts: Linear-time algorithm to test if clique number equals degeneracy bound?

texts:
Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique.
A well-known bound on the clique number is $\omega\le d+1$, which is helpful when solving the maximum clique problem or when enumerating all maximal cliques.
How fast can one test whether this bound is tight, $\omega=d+1$? An algorithm that runs in time $O(dm)=O(m^{1.5})$ is known.
Is there a faster algorithm, say, running in linear time?
Or, is $O(m^{1.5})$ best possible under something like SETH?


texts: Is it possible to find the median with a linear size sorting network?

texts:
Is there a sorting network that makes only $O(n)$ comparisons and finds the median?

The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of comparisons.
The median of medians algorithm finds the median with $O(n)$ comparisons, but it cannot be implemented as a sorting network.

Remark. In fact, in a recent work, we needed a version that is less powerful than pairwise comparison and resembles sorting networks. In our model one could input two elements, $a$ and $b$, and the output was either "a" or "b", such that the output is at least as big as the other number. (In case of equality, either one of them, and we are interested in worst case complexity.) In this variant we could prove that there is a solution with $O(n)$ comparisons. Of course I am also interested if anyone knows anything about this model ever being studied.


texts:
Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables.   My question is motivated by curiosity.  Less formally, I would like to know: "What is the 'most natural' reduction from SAT to 3-SAT?"

Now the reduction that I've always seen in text books goes something like this:

First take your instance of SAT and apply the Cook-Levin theorem to reduce it to circuit SAT.
Then you finish the job by the standard reduction of circuit SAT to 3-SAT by replacing gates with clauses.

While this works, the resulting 3-SAT clauses end up looking almost nothing like the SAT clauses you started with, due to the initial application of the Cook-Levin theorem.

Can anyone see how to do the reduction more directly, skipping the intermediate circuit step and going directly to 3-SAT?  I would even be happy with a direct reduction in the special case of n-SAT.

(I would guess that there are some trade-offs between computation time and the size of the output.  Clearly a degenerate -- though fortunately inadmissible unless P=NP -- solution would be to just solve the SAT problem, then emit a trivial 3-SAT instance...)

EDIT:  Based on ratchet's answer it is clear now that the reduction to n-SAT is somewhat trivial (and that I really should have thought that one through a bit more carefully before posting).  I'm leaving this question open for a bit in case someone knows the answer to the more general situation, otherwise I will simply accept ratchet's answer.


texts: Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

texts:
Usually, in Pure Type Systems, the type of a λ/∀-bound variable is only accessible on its body. That is, on λ (X : A) -> B, X is free inside A and bound in B. But what if X was also bound in A? The typing rules should be updated accordingly, i.e., instead of:

$$ \frac{Γ \vdash A : * \quad Γ, x : A \vdash B : *}{Γ \vdash ∀ (x : A) \rightarrow B : *}$$
$$ \frac{Γ \vdash f : ∀ (x : A) \rightarrow B \quad Γ \vdash a : A}{Γ \vdash f a : [a/x]B}$$

we'd have:

$$ \frac{Γ, x : A \vdash A : * \quad Γ, x : A \vdash B : *}{Γ \vdash ∀ (x : A) \rightarrow B : *}$$
$$ \frac{Γ \vdash f : ∀ (x : A) \rightarrow B \quad Γ \vdash a : [a/x]A}{Γ \vdash f a : [a/x]B}$$

In other words, on the ∀ (x : A) -> B case, in order to infer the type of A, we extend the context with x : A, which is possible, because we know the value of A. On the application case f a with f : ∀ (x : A) -> B, we substitute x by a in A before checking for equality. I have never seen such an approach, though. My question is: was this explored before? If so, is there a name for it so I can look up? If not, is there an obvious reason for it to be undesirable?

(The reason I initially asked this question is I've previously asked if it is possible to implement a halting definition of ind on the calculus of constructions with equi-recursion. I've noticed one can do so in a setting with mutually recursive definitions, as long as we also allow a λ/∀-bound variable to refer to itself on its type. Here is an example.)


texts:
This page asserts that

  many languages do not use implicit subtyping (structural equivalence), prefering explicit/declared subtyping (declaration equivalence)

I've mostly used programming languages which uses explicit subtyping. What are the advantages of implicit subtyping, as described in the notes above.


texts: States and Probability distributions that the 5-qubits IBM computer can produce

texts:
Update (January 2018) A new very interesting paper with various experiments on the IBM machine is Five Experimental Tests on the 5-Qubit IBM Quantum Computer by Diego García-Martín, Germán Sierra.

Update (July 2017) Extended question: Of course, the question extends to the newly built IBM 16-qubits quantum computer, and the 50-qubits quantum computers that IBM, Google and various other players expect to demonstrate in the near future. A natural conjecture is that all these computers can only approximate "noise-stable" pure states.  namely pure states that are stable under noise operator with exponential decay of high order Pauli terms, (see e.g. this paper by Montanaro and Osborne).

Original question:

IBM has recently built a 5-qubits quantum computers based on superconducting qubits. It is even possible to make experiments over the cloud.

The space of pure states for 5 qubits is the unit sphere in the 32-dimensional space over the complex number. When you measure the state of the computer you get a probability distribution on strings of 5 bits.

Give a "map" of the probability distributions and of the actual states that the IBM quantum computer can reach.

Of course, the boundary between what can be reached and what is beyond reach is of special interest. And also the case of 3 and 4 qubits.

My question is motivated by this comment over Lipton abd Reagan's blog by Alexander Vlasov.

I would expect that distributions that can actually be reached are characterized by "noise stability" which is equivalent to "low degree Fourier-type" expansion. The relevant "noise" here is independent depolarizing noise. The relevant "Fourier expansion" might be the one described by Ashley Montanaro and Tobias J. Osborne in the paper quantum Boolean function.

Vlasov referred to the paper by Daniel Alsina and  José Ignacio Latorre Experimental test of Mermin inequalities on a 5-qubit quantum computer. A sentence from the abstract reads "The experimental results obtained using the quantum computer show violation of all Mermin inequalitites, with a clear degradation of the results in the 5 qubit case."

Update: Andrew Morgan suggests in the comment below that the proposal for the threshold might be too naive. A specific question inspired by Andrew's comment is:

Can we well approximate with the IBM machine the state

$$\frac 14 |11111\rangle+\frac 14 |11100\rangle+ \frac 14 |11010\rangle+\frac 14 |11001\rangle+
\frac 14 |10110\rangle+\frac 14 |10101\rangle+ \frac 14 |01110\rangle+\frac 14 |01101\rangle+
\frac 14 |10011\rangle+\frac 14 |01011\rangle+ \frac 14 |00111\rangle+\frac 14 |10000\rangle+
\frac 14 |01000\rangle+\frac 14 |00100\rangle+ \frac 14 |00010\rangle+\frac 14 |00001\rangle.$$
(Superposition of the computational basis elements with an odd numbers of 1's)

(Later update: In view of Peter Shor's comment below I suppose we need to look more carefully for "noise-sensitive" states that we would like to explore.)

Also of interest are the states $$\frac {1}{\sqrt {5}} |10000\rangle +
\frac {1}{\sqrt {5}} |01000\rangle +\frac {1}{\sqrt {5}} |00100\rangle + \frac {1}{\sqrt {5}} |00010\rangle +\frac {1}{\sqrt {5}} |00001\rangle $$ and the superposition of all basis elements with two 1's. (If somebody reading this question actually tried to program the IBM 5-qubit computers I'd love to hear about it.)


texts: Is scope extrusion necessary in the Pi-calculus?

texts:
What is the real benefit of scope extrusion in the Pi-calculus? I read that it adds more flexiblity to the overly restrictive prior process algebra where the scope of a newly created channel was limited. However, taking a first serious look into Pi-calculus, I came to think that this $\nu$-binder is a source of confusion between channel names and bound variables, which should be considered separately.

There are two binders in pi-calculus. One is a normal binder (just like the one in lambda calculus) in the receive $c(x).Q$ where $x$ is bound in $Q$. However, $(\nu x).P$ is a very strange binder because the scope of $x$ can extend over other parallel processes by an axiom, which is just strange, reminding me of dynamic scoping.

IMHO, this is all due to overloading variables and channel names. If we separate the notion of channel names from variables, we can make the $\nu$-binder a true binder where the variable following $\nu$ is a normal bound variable and we only need to add a reduction rule for it, which is just like the reference cell allocation in ML:
$$ (\nu x)P \longrightarrow P[c/x] $$
where $c$ is a globally fresh channel name. Then, everything made sense to me.

So, what is the benefit of having this strange axiom for scope extrusion when we can simply model it as new channel creation, which to me is much more intuitive and also closer to real implementations.


texts:
The book by Arora and Barak contains in chapter notes on PCP

  We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's deterministic logspace algorithm for undirected connectivity described in Chapter 20, which suggests that more connections are waiting to be made between these different areas of research. (pg 494)

What precisely is meant by this reminiscence? Is there a common property/lemma than can be "factored out" of these two proofs?


texts: CSPs with unbounded fractional hypertree width

texts:
At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional hypertree width, CSP($H$) $\in PTIME$.

Definitions, etc.

For a great survey of standard tree decompositions and treewidth, see here (Thanks ahead of time, JeffE!).

Let $H$ be a hypergraph.

Then for a hypergraph $H$ and a mapping $\gamma : E(H) \rightarrow [0,\infty)$,

$B(\gamma) = ${$v \in V(H) : \sum_{e \in V(H), v \in e} \gamma(e) \ge 1$}.

Additionally, let weight($\gamma$) = $\sum_{e \in E}\gamma(e)$.

Then a fractional hypertree decomposition of $H$ is a triple $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$, where:

 $(T, (B_t)_{t \in V(T)})$ is a tree decomposition of $H$, and
 $(\gamma_t)_{t \in V(T)}$ is a family of mappings from $E(H)$ to $[0, \infty)$ s.t. for every $t \in V(T), B_t \subseteq B(\gamma_t)$.

Then we say the width of $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ is $\max${weight$(\gamma_t), t \in V(T)$}.

Finally, the fractional hypertree width of $H$, fhw($H$), is the minimum of the widths over all possible fractional hypertree decompositions of $H$.

Question

As stated above, if the fractional hypertree width of the underlying graph of a CSP is bounded by a constant, then there is a polynomial time algorithm to solve the CSP. However, it was left as an open problem at the end of the linked paper whether there were any polynomial-time solvable families of CSP instances having unbounded hypertree width.
(I should also point out, this question is completely resolved in the case of bounded vs. unbounded treewidth (ACM citation) under the assumption that $FPT \ne W[1]$.) Since there's been some time since the first-linked paper, plus I'm relatively unaware of the general state of this sub-field, my question is:

Is anything known about the (in)tractability of CSPs over graphs with unbounded fractional hypertree width?


texts: Areas of research and open problems in functional programming

texts: What are the major areas of functional programming that require more research and development? For example, I know a lot of people are asking for dependent types in Haskell, and someone at my uni is doing a PhD in algebraic effects.


texts: Minimal clique edge cover vs minimalist (assignment-minimum) ones

texts:
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \bigcup_{c\in C} c\times c$).
The cover is said to be minimal if $|C|$ is minimal, i.e. the number of cliques used to cover the graph is minimal.
Let us say that the cover is minimalist if $\sum_{c\in C} |c|$, i.e. the sum of clique sizes, is minimal.
(Is there a better term than minimalist here? Does it appear in the literature?)
There exists minimal covers that are not minimalist covers.
Consider for instance, the graph where $V=\{a,b,c,d,e\}$ and $E$ is covered by $C = \{\{a,b,c\}, \{b,c,d\}, \{c,d,e\}\}$. This is a minimal covering of the graph, but not a minimalist one, since it is also covered by $\{\{a,b,c\}, \{b,d\}, \{c,d,e\}\}$.
Question:
Is the converse true? Is there any graph having a minimalist cover that contains more than the minimal number of cliques needed to cover it?


texts:
I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively.

The fact is as follows:

Given a line segment and two points p,q in the plane, which conditions need to hold such that the point on the segment that is closest to p,q (i.e., sum of the distances to p and q) is one of the extreme points of the segment?

This is easy enough if the metric is l1 (Manhattan) and the segment is horizontal (or vertical). In this case, it is sufficient that at least one among p and q is outside the vertical "stripe" defined by the extreme points of the segment.

The metrics I am most interested in are fixed orientation metrics. I guess that something similar to what happens for l1 would be true also for fixed-orientations, but I am not sure where to start for proving it.

I am reading through the papers of Widmayer, Sarrafzadeh, and others trying to get the hang of it. I was hoping some of you could refer me to other readings.

This is probably not the right place to ask, since it is more related to topology rather than computer science. However, being a computer scientist myself, I would find it more comfortable to read something written by a computer scientist.

Thanks for your help!


texts: Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

texts:
I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is semicomputable if the probability it assigns to a given string can be computed to arbitratry precision from above or below by a Turing machine. If it can be computed from above and below, it's computable. (formal description here)

Now, I prefer to think of the space of distributions that can be sampled by a probabilistic Turing machine (PTM). That is the distributions $p$ for which a PTM with no input outputs the string $x$ with probability $p(x)$.

I have a (rough) proof that the two classes of distributions the class of lower semicomputable semimeasures and the class of semimeasures samplable by PTM are equivalent: every lower semicomputable semimeasure can be sampled by a PTM and vice versa. However, this seems like the sort of thing that has been worked out ages ago, and is well known to everybody. Can anybody help me with a reference that asserts and proves this equivalence?

edited after @domothorp's comments


texts: Though there have been many questions asked in this forum on complexity of integer operation, I could not find an answer to the following question: What implications are there to complexity theory if integer addition and multiplication of two integers have the same asymptotic complexity in the worst case?


texts: Another weird $O(N \log{N})$ Turing machine

texts:
This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial solution, so I will delete it).

Idea: build a TM that sweeps the input tape from left to right, and right to left "adding" to each symbol an incremental value (and trying to use all available symbols).

Let $\Sigma_4 = \{.,0,1,2\}$ be a 4 symbols alphabet.

We map each pair of symbols to an integer according to the following table:

00->0    10->4    20->8    .0->12
01->1    11->5    21->9    .1->13
02->2    12->6    22->10   .2->14
0.->3    1.->7    2.->11

Informally, the dot "." is used like the symbol "$3$". So, we can encode an integer in [0..14] using two symbols. The pair "$..$" will be used as a separator.

We informally define a function that "sweeps" the input from left to right - processing 2 symbols at once - and adds the last integer written on the tape to the current one modulo 15. For example (left-right sweep):

>01  00  11  01  10  11   Decoded: >1  0  5  1   4  5
 01 >00  11  01  10  11            [1  0] 5  1   4  5
 01  01 >11  01  10  11             1 [1  5] 1   4  5
 01  01  12 >01  10  11             1  1 [6  1]  4  5
 01  01  12  13 >10  11             1  1  6 [7   4] 5
 01  01  12  13  2. >11             1  1  6  7 [11  5]
 01  01  12  13  2.  11             1  1  6  7  11  1

Then it do the same thing from right to left (right-left sweep):

 01  01  12  13  2.  11<   Decoded: 1  1   6  7  11  1<
 01  01  12  13  2.< 11             1  1   6  7 [11  1]
 01  01  12  13< .0  11             1  1   6 [7  12] 1
 01  01  12< 10  .0  11             1  1  [6  4] 12  1
 01  01< 22  10  .0  11             1 [1  10] 4  12  1
 01< 2.  22  10  .0  11            [1 11] 10  4  12  1
 .0  2.  22  10  .0  11            12 11  10  4  12  1

Now we define:

$\displaylines{ L = \{ x \in \{0,1\}^* \, s.t. \, |x| = 2^k \text{ and after } k \text{ left-right + right-left sweeps} \cr \text{ the tape contains the same number of 1s and 2s } \} } $

$L$ can be recognized by a TM using alphabet $\Sigma_4$ in $O(N \log{N})$ :

check the length of the input string ($|x|=2^k$) and store $k$ in unary format on the left,
make $k$ left-right, right-left sweeps
compare the number of 1s and 2s using the usual $O(N \log{N})$ technique

Can we build a Turing machine TM3 that uses only 3 symbols $\Sigma_3 = \{.,1,2\}$ and recognizes $L$ in $O(N \log{N})$ ?

Steps 1 and 3 can be performed by a 3-symbols TM (see my previous question for details).

But step 2 seems to add "more information" and the extra symbol $2$ cannot be stored by TM3, so it must expand the input (and the resulting time complexity is $O(N^2)$).

I say "more information" because the value of each pair of symbols (at the end of the sweeps) depends on $k$ and on the number of 1s in the original input tape (at both sides).

Furthermore the bookkeeping tecnique (using the "." symbol) seems not to work in this case because the symbol itself is used in the encoding during the sweeps.


texts:
In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?

A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ imply any difficult lower bounds? Does the resolution of this problem hit against a known barrier in complexity theory?

My motivation for this question is to understand the relative difficulty (with respect to other major open problems in complexity theory) of showing a hierarchy for $\mathsf{BPTIME}$. I am assuming that everyone believes that such a hierarchy exists, but please correct me if you think otherwise.

Some background: $\mathsf{BPTIME}(f(n))$ contains those languages whose membership can be decided by a probabilistic Turning machine in time $f(n)$ with bounded probability of error. More precisely, a language $L \in \mathsf{BPTIME}(f(n))$ if there exists a probabilistic Turing machine $T$ such that for any $x \in L$ the machine $T$ runs in time $O(f(|x|))$ and accepts with probability at least $2/3$, and for any $x \not \in L$, $T$ runs in time $O(f(|x|))$ and rejects with probability at least $2/3$.

Unconditionally, it is open whether $\mathsf{BPTIME}(n^c) \subseteq \mathsf{BPTIME}(n)$ for all $c > 1$. Barak showed that there exists a strict hierarchy for $\mathsf{BPTIME}$ for machines with $O(\log n)$ advice. Fortnow and Santhanam improved this to 1 bit of advice. This leads me to think that a proving the existence of a probabilistic time hierarchy is not that far off. On the other hand, the result is still open and I cannot find any progress after 2004. References, as usual, can be found in the Zoo.

The relation to derandomization comes from Impagliazzo and Wigderson's results: they showed that under a plausible complexity assumption, $\mathsf{BPTIME}(n^d) \subseteq \mathsf{DTIME}(n^c)$ for any constant $d$ and some constant $c$. By the classical time-hierarchy theorems for deterministic time, this implies a time hierarchy for probabilistic time. I am asking the converse question: does a probabilistic hiearchy hit against a barrier related to proving derandomization results?

EDIT: I am accepting Ryan's answer as a more complete solution.

If anyone has observations about what stands between us and proving the existence of a hierarchy for probabilistic time, feel free to answer/comment. Of course, the obvious answer is that $\mathsf{BPTIME}$ has a semantic definition that defies classical techniques. I am interested in less obvious observations.


texts: The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment with a smaller computer than Summit/OLCF-$4$ in a reasonable time and if not why not?


texts: Computing the Cheeger constant: feasible for which classes?

texts:
Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated.  I am interested to learn if exact polynomial algorithms
are known for special classes of graphs.
For example, is it still NP-complete for regular graphs?
For distance-regular graphs?
(I have not studied the existing NP-completeness proofs to examine their assumptions.)
Literature pointers appreciated—thanks!


texts: Is this a proof that diophantine equation solutions can't be bounded by power towers?

texts:
From this 2017 paper on upper bounds for solutions to diophantine equations:

  Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution
  in positive integers x1, . . . , xn , then x1, . . . , xn ≤ g(2n). In
  other words, ξ (n) ≤ g(2n) for every positive integer n.

And following this:

  Theorem 2. Conjecture 1 implies that there exists an algorithm which
  takes as input a Diophantine equation D(x1, . . . , xp) = 0 and
  returns a positive integer d with the following property: for every
  positive integers a1, . . . , ap, if the tuple (a1, . . . , ap) solely
  solves the equation D(x1, . . . , xp) = 0 in positive integers, then
  a1, . . . , ap ≤ d.

This means that given a diophantine equation, we can first compute $d$, and then check the finitely many tuples less than or equal to $d$ to find a solution. If we don't find a solution, this means the diophantine equation does not have exactly one solution - it has none or more than one.

Now from Hilbert's 10th problem is unsolvable:

  Let #(P) be the number of solutions of the Diophantinequation P = 0.
  Thus O ≤ #(P) ≤ N_0. Hilbert's tenth problem seeks an algorithm for
  deciding of a given P whether or not #(P) = 0. But there are many
  related questions: Is there an algorithm for testing whether #(P) = N,
  or #(P) = 1, or #(P) is even? I was able to show easily (beginning
  with the unsolvability of Hilbert's tenth problem) that all of these
  problems are unsolvable. In fact if A = {0,1,2,3,.. N_0} and B subset of
  A, B not null set, B not equal to A, then one can readily show that
  there is no algorithm for determining whether or not #(P) is an
  element of B

Does that mean conjecture 1 and hence theorem 2 (and to be frank atleast half of the rest of the paper) is false? Or am I missing something?


texts: Finding a matching whose contraction minimizes the number of arcs in a graph

texts:
Given a mixed graph $G=(V,E,A)$ with edges $E$ and arcs $A$, find a matching in $E$ that minimizes the number of arcs in $G/M$, where $G/M$ is obtained from $G$ by contracting matched vertices and removing parallel arcs.

Is (the decision version of) this problem NP-complete? Has it been studied in the literature?


texts: Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

texts:
We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.

The problem is defined as follows:

Instance: A directed graph $G=(V,E)$, a cost function $w : E \to \mathbb{R_0^+}$, two vertices $s,t \in V$ and an integer $k$.

Solution: An $s$-$t$-cut, i.e. a partition of $V$ into two sets $V_1, V_2$ such that $s \in V_1$, $t \in V_2$ and the number of edges that cross the cut is at most $k$, i.e. $|\{ (u,v) \in E: u \in V_1, v \in V_2 \}| \le k$.

Measure (to minimize): The cost of the cut: $$ \sum_{ (u,v) \in E : u \in V_1, v \in V_2 } w(u,v) $$

In "Cardinality constrained and multicriteria (multi)cut problems" the autors prove that this problem is strongly NP-Hard even for undirected graphs.

We are mainly interested in approximation algorithms for directed graphs, but approximation results for the undirected case might also be useful.

Thank you for any insights.


texts: Catalog of NP-complete problems, more up-to-date than Garey&Johnson?

texts: Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&Johnson's book? I don't want to cite web sites, even though I know there are some excellent compendiums om the web.


texts: Is this permutation-sum problem NP-complete?

texts:
A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular, we were not able either to find a polynomial-time algorithm to compute this bound, or to prove that the problem is NP-hard. In this respect, a sufficient condition for the problem to be NP-hard, is that the following sub-problem is NP-complete.

Given:

a set $\tau$ of $N$ pairs $(C_i, U_i) \in \mathbb{Q}^2$, with
$C_i > 0$ and $0 < U_i \le 1$ for all
$i \in \{1, 2, \ldots, N\}$,
the smallest natural number $M$ such that
$\sum_{i=1}^{N} U_i \le M$ (which implies $M \le N$, because
$U_i \le 1$),
an integer $M'$ with $1 \le M' \le M$,
a strictly positive value $b \in \mathbb{Q}$;

does a permutation
$\tau' = ( (C_{i_1},U_{i_1}), (C_{i_2},U_{i_2}), \ldots,
(C_{i_{M'-1}}, U_{i_{M'-1}}))$
of $M' - 1$ pairs in $\tau$ exist, such that
$$
  \sum_{g = 1}^{M'-1}\frac{C_{i_g}}{M - \sum_{v=1}^{g-1}U_{i_v}} \ge b
  \quad ?
 $$

Any suggestion for proving that this is problem is NP-hard, or, on the other hand, for finding a way to solve the problem in polynomial time?


texts: Wide and shallow circuits for $\mathrm P$

texts:
The $\mathrm{NC} \stackrel?= \mathrm P$ question is not as famous as the $\mathrm P$ versus $\mathrm{NP}$ problem, but still a deep and interesting question. It is generally accepted that there are unlikely to be polylog-depth, polynomial size circuits for all problems in $\mathrm P$ — especially in the poly-time uniform setting (where we require the circuit to be specified by a polynomial-time algorithm).
However, if you have gates with unbounded fan-in and fan-out, one might still have exponential-size, polylog-depth circuits for $\mathrm P$, which are uniform in the sense of having a (logspace) succinct representation.

Definition (succinct circuits). Given a circuit with $n$ inputs, $k$ outputs, and $m$ gates, we represent the circuit by a directed acyclic graph with node labels $\{1,2,\ldots,n{\:\!+\:\!}m{\:\!+\:\!}k\}$, where the wires connecting the output of one gate to the input of another are represented by directed edges between the corresponding nodes. A succinct representation for the circuit is

a deterministic logspace algorithm which assigns the type (e.g. input, output, AND, OR, NOT, PARITY, etc.) to each node,

accompanied by a deterministic logspace algorithm for deciding the input/output relation (i.e. the adjacency relation in the digraph) for pairs of gates,

from binary encodings of the gate labels.

For instance, $3\textrm{-SAT}$ can be solved using a succinct AND-OR tree of depth 4, by using exponentially many sub-circuits, each of which tests a 3-CNF formula presented as input against a possible assignment to its variables: this gives rise to a circuit of constant depth. By considering log-space reductions of arbitrary problems in $\mathrm{P}$ to $3\textrm{-SAT}$ and using $\mathrm L \subseteq \mathrm{NC^2}$, it seems to me that we can obtain succinct $O(\log^2 n)$-depth circuits of size $2^{O(\mathrm{poly}\,n)}$ for any problem in $\mathrm P$ — where the polynomial in the exponent will be related to the deterministic run-time of the polynomial time algorithm for the problem in $\mathrm P$.
What exponential upper bounds are known for the size of succinct $O(\log^d n)$-depth circuits — boolean or arithmetic, with unbounded fan-in — for arbitrary problems in $\mathrm P$, for instance for $d \leqslant 4$?


texts: Partitioning a set of 2d polygons into intersection-connected subsets

texts:
My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them.

In other words I have a set of polygons. I want to group them into subsets where each polygon has at least one intersection with (one or more) other polygon(s) of the subset and no intersections with any other polygon in a different subset.
So if I have S = {A, B, C, D} and A intersects C and C intersects D the resulting partitions are: P1 = {A, C, D} and P2 = {B}.

I don't have any problems with an good approximate solution if its fast and doesn't generate false negatives (i.e. no (potential) intersection is lost).

I don't need to actually calculate the intersections just determine if they intersect.

In my case the polygons are complex but if a known answer only works for concave or simple polygons I would still like to know about  it!

I am actually not sure how to phrase this question which may account for my lack of findings of relevant papers.


texts: Are there simple core languages which are consistent and expressive?

texts:
The Calculus of Constructions is a very simple core functional language with dependent types. Per curry-howard isomorphism, it could, potentially, be very useful for writing programs and proofs. It, though, has a few problems: induction isn't derivable, it isn't possible to prove 0 != 1, and pattern matching on algebraic data structures take linear time. In order to solve those issues, practical languages such as Coq are based on the Calculus of Inductive Constructions instead, which add a layer of primitive datatypes on top of CoC. That, unfortunately, makes the core language very complex.

An alternative solution to those problems is a new primitive, self, which is a construction that allows a type to reference its typed term. This construct, together with the Parigot encoding, and a slightly weakened but still useful notion of contradiction, is sufficient to solve the problems above. The proposed language, though, is still somewhat complex. In particular, it has different Pi types, complex kind machinery and requires a restricted form of recursion (for the Parigot encoding).

Is it possible to be simpler? I.e., can the calculus of constructions with only self types and nothing else from this paper still be able to derive induction and employ the parigot encoding?


texts: What limits the performance of evolutionary computing techniques?

texts:
What limits the current performance of genetic algorithms and neural networks?
The principles underlying these techniques, at least the popular science presentation of these principles, suggests that with enough training they could be improved
as much as desired. It seems that this is not the case though.

What are the causes for this? Why can't better results be achieved simply with
more computing power? Are there fundamental theoretical reasons for this?

I realize this is a very broad question, but I'm sure some of the people here
push against these bounds in their work, and I'd like to hear what they have to say.


texts: Methods for proving deterministic communication complexity lower bounds

texts:
I am familiar with the classic techniques for proving deterministic communication complexity lower bounds for boolean functions in the 2-party model: To the best of my knowledge, these are

fooling sets,
the rank method, and
the "tiling method", which refers to determining the minimal number of monochromatic rectangles needed to cover all possible outputs.

It is known that (3) gives almost tight bounds but is difficult to apply. On the other hand, fooling sets are easier to find in general, but the obtained bounds can be exponentially smaller than the actual deterministic communication complexity, whereas the rank method yields lower bounds that can be polynomially smaller.

These are the only techniques that I am aware of and they were invented in the early 90s.

Are there any newer techniques for finding deterministic lower bounds?

Related question:
Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?


texts: I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.


texts: Is this tree minimization problem NP-complete?

texts:
I'm totally new to complexity theory, hence don't know much about how reductions work. So, I'm not sure how hard the following problem is. Please let me know what kind of problems I should look at to attempt for a reduction to my problem (if it is NP-hard or complete). Even reduction from that problem to my problem (yielding this is NP-hard) would be a good result to have.

The problem is the following. Suppose, we have the set of all possible 'single rooted' trees with $n$ nodes, denoted by ${\cal T}$. The set of nodes is denoted by $N$. Each node has some intrinsic values $\gamma_i$ (these are given beforehand). The function $\mu : 2^N \to \mathbb{R}$ maps the children of each node to real numbers, and this function is also given beforehand. Another function $f: {\cal T} \to \mathbb{R}$ maps the subtree of a given node to reals. Now the problem is,

$$ \min_{T \in {\cal T}} \sum_{i \in N} f(T_i) \mu (C_{p(i)}) (\gamma_{p(i)} - \gamma_i).  $$

Where $T_i$ is the subtree rooted at $i$, $p(i)$ is the unique parent of $i$, $C_{p(i)}$ is the children set of $p(i)$. Given a tree $T$, both $f$ and $\mu$ are computable in linear time. The problem basically is to find the right connection of nodes over a tree.

Thanks in advance.

%%% Editing after getting the answer from Yuval %%%

Maybe I was unclear. For single rooted trees with $n$ nodes, one can have $(n-1)!$ possible trees (this can be enumerated using the incidence matrix of the tree and considering the placements of 1 in the upper triangular part), and in each of those trees, there are $n!$ ways to place the nodes (remember $\gamma_i$s are node identity specific). And so, in each of the $n! \times (n-1)!$ possible configurations, you'll get a value for the sum. The problem is to find the minimum over such a huge space. My question is: do there exist efficient algorithms to compute this min? Or, is the problem hard, i.e., no efficient algorithm exists?


texts:
What is known about the following problem?

  Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-Dimension$(S) \leq k$ for some integer $k$.

Are there approximation algorithms or hardness results for this problem?


texts: What does PAC-learnability say about the learner runtime?

texts:
I am new to PAC-learnability. Assume a class $\mathcal{H}$ of hypotheses is PAC-learnable. Then all we know that if we draw polynomial number of examples (in $\delta$ and $\epsilon$), we can return a hypothesis with high accuracy.

But how this related to the complexity of the learner $L$?. Because I often read $\mathcal{H}$ is PAC-learnable if there exist an algorithm $L$ runs in time polynomial (in $\delta$ and $\epsilon$).


texts: Size complexity of probabilistic two-way automata for a Boolean function

texts:
I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the minimal automaton computing this function.
Automaton $A$ computes $f$ if it recognizes the language $L_f=\left\{ x \in \{ 0, 1 \} ^n | f(x)=1 \right\}$.

The result that I want to get is that there exist hard Boolean functions - requiring superpolynomial number of states for any probabilistic (with arbitrary rational probabilities) two-way automaton that computes the function.

This result can be proven for deterministic automata:

Theorem. There exists an infinite sequence of Boolean functions $f_1, f_2, \ldots$ of $n_1, n_2, \ldots$ ($n_1 < n_2 < \ldots$) variables such that for every sequence of 2DFAs $A_{f_1}, A_{f_2}, \ldots$ such that $A_{f_i}$ computes $f_i$ the number of states grows superpolynomially - for every polynomial $p$ there exists $i$ such that the number of states $\left| P_{f_i} \right| > p(n_i)$.

  Sketch of proof. We will use counting argument.
  The alphabet including the endmarkers is $\Sigma = \left\{ 0, 1, \vdash, \dashv \right\}$.
  The number of determinstic two-way automata with $k$ states is no more than $(3 \cdot k)^{ \left| \Sigma \right| \cdot k } = 2^{4 \cdot k \cdot \log_{2}{3k} }$ - for every state and every symbol (hence the $\left| \Sigma \right| \cdot k$ part) there is a transition to some state and the transition itself can be one of 3 types - moving the head left, right or not moving (hence the $(3 \cdot k)$ part).
  The number of Boolean functions on $n$ variables is $2^{2^n}$.
  If $k = p(n)$ then the number of automata is no more than $2^{p'(n)}$ (where $p(n)$ and $p'(n)$ are polynomials) which is less than $2^{2^n}$ therefore there are more Boolean functions than automata of polynomial size. So there must be a Boolean function without a polynomial size automata $\blacksquare$

This result can also be extended to nondeterministic automata.
The number of 2NFAs with $k$ states is no more than $ 2^{3 \cdot k \cdot k \cdot \left| \Sigma \right|} = 2^{12 \cdot k^2}$ (because every transition from a state to a state with a given symbol and head movement can either be there or not be) which for $k$ polynomialy related to $n$ is still $2^{p(n)}$.

Now let's consider probabilistic automata. That is, for each transition from a state to a state with given input symbol and head movement there is a probability from a set $S \subseteq [0,1]$ assigned to it. Of course the probabilities for all transitions from a given state and input symbol must sum to 1. We will consider bounded-error computation - the automaton has to give the correct answer with probability $\geq \frac{2}{3}$.

If $S = \left\{ 0, \frac{1}{2}, 1 \right\}$ (these are sometimes called coin-flipping automata) then the result still holds - there are no more than $3^{3 \cdot k^2 \cdot \left| \Sigma \right|} = 2^{12 \cdot \log_{2}{3} \cdot k^2}$ such automata.

The result also holds for any other set $S$ ($S$ is allowed to depend on $n$) that is considerably smaller than $2^{2^n}$. The number of such automata is no more than $\left| S \right|^{12 \cdot k^2}$. For example $\left| S \right| = 2^{1.99^n}$ would be fine.

The question: What happens if we allow all rational probabilities? Does there exist a hard Boolean function for such probabilistic two-way automata?
Intuitively, going from probabilities from a quite large set $S$ to arbitrary rational probabilities shouldn't make a big difference, however the problem is that this counting argument doesn't work anymore.

This question for logical circuits was answered here (and the proof also extends to automata that works polynomial time, but not if the working time is unbounded).


texts: Are there any classes of functions which require provably different resources to compute versus computing their inverse?

texts:
Apologies in advance if this question is too simple.

Basically, what I want to know is if there are any functions $f(x)$ with the following properties:

Take $f_n(x)$ to be $f(x)$ when the domain and codomain are restricted to $n$-bit strings. Then

$f_n(x)$ is injective
$f_n(x)$ is surjective
$f_n(x)$ takes strictly less resources (either space/time/circuit depth/number of gates) to compute under some reasonable model than $f^{-1}_n(y)$, where $y=f_n(x)$.
The resource difference for $f_n(x)$ vs $f^{-1}(y)$ scales as some strictly increasing function of $n$.

I can come up with examples where the function is either surjective or injective, but not both unless I resort to a contrived computational model. If I choose a computational model which allows left shifts in unit time on some ring, but not right shifts, then it is of course possible to come up with a linear over head (or higher if you consider some more complicated permutation as a primitive). For this reason I am interested only in reasonable models, by which I mostly mean Turing machines or NAND circuits or similar.

Obviously this must be true if $P\neq NP$, but it would seem that this is also possible if $P=NP$, and so should not amount to deciding that question.

It is entirely possible that this question has an obvious answer or an obvious obstacle to answering which I have missed.


texts: Is there such a thing as a state-based programming language?

texts:
As anyone knows who has read Alan Turing's paper describing the Turing Machine (On Computable Numbers, With an Application to the Entscheidungsproblem), the syntax he uses is vastly different from that of modern languages (and closer to the densely symbolic mathematical writing of the time). This is not very surprising, since he wrote the paper about a decade before the first working electronic computer was finished and several decades before the first compiler was written. More interestingly, though, is the fact that the paradigm Turing uses seems pretty foreign as well. I would expect it to be procedural, but in fact it's what I would call "state-based": he describes a finite set of possible states in which the machine might find itself, and, given a particular state and an input value, he describes what actions the machine should take. In essence, then, the Turing machine is a finite state machine that has access to an infinite strip of rewritable memory locations. Since Turing proves that this machine is functionally equivalent to any other sufficiently powerful mechanical computational device, we can see that his state-based programming language can implement all the algorithms that other languages can implement.

As far as I know, however, there is no modern programming language that actually uses this paradigm. I suppose this is probably because it's a bit of a pain to wrap one's head around, and because it doesn't provide a very natural way of thinking about most algorithms, but I'd still be surprised if no one has at least tried something like this. And there may be some applications for which such a language would work extremely well. For instance, a processor can be represented quite directly as Turing's "universal" machine, which takes as input a coded representation of another machine and then performs the work that machine would perform; so might it be possible to design new processors by "compiling" something akin to Turing's language into a circuit layout for an FPGA? (True, the compiler might not come up with the optimal layout, and this approach might be too abstract to fully characterize the details of chip design, but this is just an example of something I think might work.)

So, my question is: does anyone know of any modern programming languages based on the original Turing machine language, or any languages that use a paradigm akin to this "state-based" paradigm?