texts: Storing a bit vector in uninitialized memory and minimal space

texts:
A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of memory and initializing only $\lceil \lg n \rceil$ of them. This representation supports setting and unsetting any bit in constant time.

This dates back to "Alfred Aho, John Hopcroft, and Jeffrey Ullman's 1974 book The Design and Analysis of Computer Algorithms . . . Chapter 2, exercise 2.12", "Jon Bentley's 1986 book Programming Pearls . . .Column 1, exercise 8; exercise 9 in the Second Edition", and "Preston Briggs and Linda Torczon's 1993 paper, 'An Efficient Representation for Sparse Sets'".

Dodis et al.'s "Changing Base without Losing Space" brings the space requirement down slightly to $\lceil (2 n + 1) \lg n \rceil + 1$ bits, though this algorithm requires the precomputation of $\Theta(\lg n)$ constants with $\Theta(\lg n)$ bits each.

How much space can be saved? Is there a representation of bit vectors in which

Bits can be set or unset in $O(1)$ time
Initializing a new bit vector of $0$s uses $o(n \lg n)$ bits of uninitialized memory and $O(\lg n)$ initialized memory


texts: Is the complexity of this path problem known?

texts:
Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$.

Question: Does there exist an $s-t$ path in $G$, such that the path intersects at most $k$ triangles? (For this problem a path is said to intersect a triangle if the path contains at least one edge from the triangle.)


texts:
I'm in search for a data structure which efficiently operates over closed intervals with the following properties:

dynamically add or remove an interval
set, and anytime change, a number ("depth") for each interval. no two depths are ever the same
find all intervals that overlap with any given interval, sorted by "depth"

The closest structure I found is Interval tree but it lists the found intervals in arbitrary order with respect to their depths. I could collect all the "unsorted" intervals as reported and sort them afterwards but I was hopping it was possible to avoid to sort the result for every query.

Please, does anyone know of such data structure or have any suggestion how (if at all possible) to enhance the Interval tree to support such sorting?

Example:

add [1,2] to the empty structure and set its depth to 1
add [10,100], depth = 2
add [5,55], depth = 3
query for [5,50] reports [10,100] and [5,55]
set depth of [10,100] to 3, and of [5,55] to 2
query for [5,50] reports [5,55] and [10,100]

Edit

I'm more interested in fast adds/removes and queries, than in updating of depths. A depth can take as much as O(n), if that helps speed-up the other operations.


texts: test if a polygon-surface is closed (+ additional nice-to-have requirements)

texts:
I have a 3D object bounded by Polygons. Is there a standard algorithm that tests if the volume is closed e.g. no polygon is missing?

Example: I have a cube bounded by six squares. The algorithm should detect if one of those squares is missing.

It would be perfect, if also the minimal surface could be calculated to complement an existing (open) surface to a closed one.

It would be even more perfect if that minimal surface could be returned in terms of a minimal set of convex polygons.


texts: Monotone circuit complexity of computing functions on sparse inputs

texts:
The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones?

We know that deciding if a graph has a $k$-clique is hard for monotone circuits (see among others Alon Boppana, 1987), but if a graph has for example at most $k^3$ edges it possible to find a monotone bounded depth circuit of size $f(k)\cdot n^{O(1)}$  which decides $k$-clique.

My question: is there any function which is hard to compute by a monotone circuit even on inputs of weight less than $k$? Here hard means circuit size  $n^{{k}^{\Omega(1)}}$.

Even better: is there an explicit monotone function which is hard to compute even if we only care about inputs of weight $k_1$ and $k_2$?

Emil Jeřábek already observed that known lower bounds hold  for monotone circuits that separate two classes of inputs ($a$-cliques vs maximal $(a-1)$-colorable graphs), thus at cost of some independence in the probabilistic argument it is possible to make it work for two classes of input of fixed weight.  This would cause $k_2$ to be a function of $n$ which I want to avoid.

What is would really like is an explicit hard function for $k_1$ and $k_2$ much smaller than $n$ (as in the parameterized complexity framework).  Even better if $k_1=k_2+1$.

Notice that a positive answer for $k_1=k_2$ would imply an exponential lower bound for arbitrary circuits.

Update: This question may be partially relevant.


texts: Abilities of Restricted Relativization in Proving Conjectures

texts:
Though everyone seems to say that P vs NP cannot be solved using relativization because there are oracles both $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \neq \text{NP}^B$, why is it that oracles cannot quantified in terms of power much like how time and space are very strictly limited in reductions?

An example would be that one cannot say that a problem is in L because there is a reduction from the given problem to an L-Complete.  They would clearly have to be more specific and be using a reduction that is log space or less as the problem would not necessarily be in L if it was polynomial time reducible to an L-Complete problem.

I guess my question ends up being, is there any way to quantify the power of given oracles in a manner such that they can be used for proving results that would not otherwise be provable using relativization?


texts: Relation between automorphism group of a linear code and its dual code

texts:
Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc.

In general are there any instances where charcterization of automorphism groups of code or its dual code lead to showing something of interest for a code?


texts: What are the main sub-areas of theoretical computer science?

texts:
I often want to give students a broad view of theoretical computer science, in the beginning of algorithms class or when advising a new student. It is hard for me to decide which sub-areas to talk about and how much emphasis to put on each of them.

Therefore, my question is: What are the main sub-areas of theoretical computer science and what is their relative "size"? Let's say the size is the number of researchers who work mostly in that area.

Of course the division into sub-areas is a clustering problem with no unique answer. I also don't expect people to have precise statistics for the size of each area, but some feeling of the relative sizes is already helpful.


texts: Existing implementation of Scott's reduction?

texts:
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the fact that any sentence in $\mathrm{FO^2}$ can be reduced to Scott's Normal form in polynomial time. The Scott's Normal form is given as
$$\forall x \forall y \alpha(x,y) \land \bigwedge_{i=1}^{m} \forall x \exists y \beta_{i}(x,y) $$
Does anyone know of existing code base where scott's reduction is implemented, i.e I input an arbitrary $\mathrm{FO^2}$ sentence and get it's Scott's Normal Form?


texts: Offline multidimensional RMQ/RSQ in query model

texts:
Problem: In the multidimensional range Max/Sum query problem (RMQ/RSQ)
  you are given a $d$-dimensional array
  with $n$ elements, and given a
  $d$-dimensional box, you wish to
  determine the max/sum of all elements
  in the range (if the elements are from
  semigroup, they have no inverses).

What is the state-of-art best algorithm for offline multidimensional RMQ/RSQ in query model (preprocessing of data allowed in offline, queries asked online)? Is there any gap between RMQ and RSQ in multidimensional case? What theoretical/practical interest does this problem have, if any?

I'm interested in it because looks like the best asymptotics for both RMQ and RSQ was achieved in this paper by Chazelle and Rosenberg in 1989, which was not cited a lot, though the problem looks very natural and interesting. By best asymptotics I mean $O(\alpha^d(m,n))$ query time, where $m$ is the amount of storage available per element, $d$ --- number of dimensions of the array, $\alpha$ --- inverse Ackerman function, $n$ --- number of entries in the array. I suspect that this is mainly because this paper is not very readable in the part where it describes the construction, so implementation of this approach is complicated. So a simpler description of a data structure with the same asymptotics is also very welcome.


texts:
Are we able to prove a free parametricity theorems about functions like $f : \forall A . [A] ⊸ [A]$?
It is supposed to state that $f$ takes a list and always returns a permutation of it.

Another example: prove that function $f : \forall A . (A ⊸ (A, A)) ⊸ [A] ⊸ [A]$ will always return a permuted list with exactly one element copied.


texts: Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?


texts: List the $k$-faces of an $n$-dimensional simplex

texts:
Suppose you are given an $n$-dimensional simplex

S = [ 0 1 ... n ]

which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $1 \leq k \leq n$, how can we enumerate the $k$-faces of S, i.e. the $k$-dimensional subsimplices? - In less geometric words, we want a complete and multiples-free list of all $k$-sized strictly ascending sequences of numbers between in $\{ 0, \dots , n \}$.

The straight-forward algorithm is to create the list of all $k$-sized tuples of numbers between $0$ and $n$, and pop out those that are not strictly ascending or contain duplicates. This can be done in space and time $O(n^3)$.

But can we do better? We do not impose restrictions on a particular ordering of the output.


texts: Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?

texts:
I have the following problem:

Given a set of path existence/absence constraints C (not necessarily for all pairs of vertices) and a (fixed) set of vertices V, generate a random DAG, s.t.

it is acyclic (by definition),
it contains all vertices of V,
all constraints in C hold,
each possible DAG (given the specific constraints) should be generated with equal probability.

The type of the constraints should be self-explanatory, but in case it is not I can edit the question to provide additional information.

Intuitively I would say that the problem should be NP-hard.

The question is:

  Are there any known results on this problem?

Thanks in advance,

George

Edit: added "(not necessarily for all pairs of vertices)" in the problem definition.


texts: Reference for the number of samples needed to distinguish two probability distributions

texts:
I am looking for a reference (and/or a full proof) for this statement:

  $O(1/\epsilon^2)$ samples suffice to distinguish any two probability
  distributions with variation distance $\epsilon$.

I would be very grateful for any pointers.


texts: What class of languages is recognized by finite-state automata with $k$ heads?

texts:
A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the input from left-to-right, but not necessarily at the same place in the input as the others.
Let us define a finite state machine with $k$ heads as follows:

A k-head NFA is a tuple $(Q, \Sigma, \Delta, q_0, F)$, where:

As usual, $Q$ is a finite set of states, $\Sigma$ is a finite alphabet, $q_0$ is an initial state, and $F$ is a set of accepting states. Let $\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$ denote the set of characters including the empty string.

$\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ is the transition relation: a transition $(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$ means that, if the machine is in state $p$, it may read in $(\sigma_1, \sigma_2, \ldots, \sigma_k)$ such that $\sigma_i$ is the next character for head $i$ (or $\varepsilon$ if that head does not move), and then move to state $q$.

A run of this kind of machine (any path starting from the start state and ending in an accepting state) results in not one string, but $k$ different strings (formed by concatenating the characters along the run). Then we say that the run is valid if the $k$ strings are identical.
The language of the machine is the set of strings $w$ such that there exists a valid run of the machine where the $k$ strings produced along that run are all equal to $w$.

Question: What is the class of languages recognized by such machines? Has it been studied?

A first observation is that such machines produce a class larger than the regular languages. For example, the language
$$
\{a^n b^n \mid n \in \mathbb{N}\}
$$
is recognized by the following $2$-head NFA with $3$ states:

(Here, an edge labeled with $\sigma_1 / \sigma_2$ denotes a transition of the form $(p, (\sigma_1, \sigma_2), q)$.)
However, a second observation is that not all context-free languages are recognized; for example, it seems that the Dyck language cannot be recognized by these $k$-head machines.


texts: Is there a standard format for Dependent QBF?

texts: I know there is a standard input format DIMACS for a formula is in conjunctive normal form (CNF) and QDIMACS for quantified Boolean formulas. Is there a similar standard format for the Dependent-QBF (DQBF)?


texts:
I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ states) in software and operate with them. May someone suggest me data structures with reasonable performance and a good book with algorithms for automata theory (minimization, determinization, extraction of regular languages, automata equivalence, ...)?

PS: This is my first question and my English is very poor but I expect everyone to understand. Thanks in advance


texts: Does PSPACE-completeness imply approximation hardness?

texts:
It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?

Is this "tight"? (i.e., are there PSPACE-complete problems whose optimization problem admits constant factor approximation in poly time?)

What about completeness for some level of PH? Does it imply any approximation hardness?


texts: Order of drawing colored balls from a bag

texts:
We're looking for an upper bound on (or a method to compute) probabilities of the following type:  Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag.  Then I start withdrawing random balls one by one. What is the probability that I draw at least one red ball and at least one yellow ball before I draw the first green ball?

More generally, I have a set $A$ of $m$ colors, a set $B \subset A$ of colors, a color $c \in A \setminus B$ and a set of $n$ balls with colors from $A$ where the number of balls of each color is known. Whats the probability that I draw at least one ball of each color in $B$ before I draw a ball of color $c$?

Peter Shor points out that this is related to the coupon collector's problem (thanks!), the main difference being that we want to know the probability of a particular color being last (not the number of steps required to collect every coupon).  The literature we've searched on the coupon collector's problem (in the last few hours) doesn't seem to address this question.  (A minor difference is that we're sampling without replacement, though a solution for sampling with replacement would be welcome too.)  Ideally we'd like a closed-form upper bound (an asymptotic upper bound would probably do), but a polynomial-time algorithm to compute an upper bound would be useful too.

We seek this bound to help us analyze a randomized geometric algorithm.


texts:
I am studying algorithm construction and weaknesses to resource consumption.  One vulnerability that really caught my eye was the Apache Range Header DoS Vulnerability.  The following quote was taken from Apache developers discussing the flaw:

  From looking at the code, I think the problem is the bucket structs.
  With N the number of requested ranges, the initial brigade is
  partitioned into 2*N buckets at the maximum. Then those buckets are
  copied into the output brigade N times, which means that O(N^2)
  buckets are created. The data is not copied, and only N "A-B" strings
  are allocated from the pool.

Does anyone else know of other resources about building algorithms that are resistant to resource exhaustion attacks?   Does anyone of interesting papers related to Algorithmic analysis and susceptibility to resource exhaustion?  Do you know of other resource consumption vulnerabilities that where caused by flawed algorithms?


texts: Algebraic (or numeric) invariants of complexity classes

texts:
I hope this question isn't too naive for this site.

In mathematics (topology, geometry, algebra) it is common for one to distinguish between two objects by coming up with an algebraic or numerical invariant, and proving the two objects have different values. I'm wondering to what extent this has been tried with complexity classes (or if it has, why I haven't ever heard about it). Algebraic structures show up a lot in theoretical computer science as a whole (cf Uses of algebraic structures in theoretical computer science), so why not in complexity theory?

In my naivete I can imagine a notion of equivalence of two languages: the existence of a polynomial-time reduction which is also reversible (or a bijection on the strings). I can also imagine that this notion is unsuitable: no finite languages of differing cardinality could be considered equivalent, even though we're more often interested in infinite languages.

Are there any other, weaker notions of isomorphism of languages that have yielded interesting results? Are there other kinds of numerically-flavored invariants that have been used to distinguish complexity classes?


texts: What is known about the complexity of finding minimum circuits for SAT?

texts:
What is known about the complexity of finding minimal circuits that compute SAT up to length $n$?

More formally: what is the complexity of a function which, given $1^{n}$ as input outputs a minimal circuit $C$ such that for any formula $\varphi$ with $|\varphi| \leq n$, $C(\varphi) = SAT(\varphi)$?

(I'm specifically interested in lower bounds.)

The naive deterministic algorithm (compute SAT by brute force up to length $n$, then try all circuits in order of size until you find one that correctly computes SAT up to length $n$) takes $\leq 2^{O(n)}$ time to compute SAT, and then an additional $O(2^n 2^M)$ time to find a minimal circuit, where $M$ is the size of the minimal circuit.

  Is there a deterministic algorithm that finds minimal circuits for SAT whose running time is $o(2^n 2^M)$, where $M$ is the size of the minimal circuit?  Or does this imply some complexity collapse?

Here are two things that, although related to my question, are definitely not what I'm asking about (which is, I think, why I found it a little difficult to search for):

The circuit minimization problem: given a circuit $C$ (or a function $f$ given by its truth table, or several other variants) find a minimal circuit $C'$ computing the same function as $C$.  Even if circuit minimization were easy, it would not necessarily imply that the above task is easy, as even computing the function we want to minimize (SAT up to length $n$) is believed to be hard, whereas in the circuit minimization problem the function we want to minimize is free (it's given as the input).
$NP$ versus $P/poly$.  My question is not merely about what size the minimal circuit has; it is about the complexity of finding a minimal circuit, regardless of its size.  Obviously if we can compute minimal circuits in polynomial time then $NP \subseteq P/poly$ (and in fact $NP \subseteq P$, since then the circuit family is $P$-uniform), but the converse need not be true.  Indeed, I believe Immerman and Mahaney were the first to construct an oracle where $NP \subseteq P/poly$ but $P \neq NP$ -- that is, $NP$ has polynomial-size circuits but they cannot be found in polynomial time.


texts: What's the difference between proving weak normalization and implementing evaluator?

texts:
Implementing an normalization (cut elimination) procedure for a type system A in a language with a total type system B, automatically proves cut elimination for type system A since the implementation will be total.

What's the difference between proving weak normalization and implementing the evaluator?

If there is none, is that effect also present in proving consistency of all the mathematical proof systems?

The same question in a strong normalization setting:
If the host language is strongly normalizing does strong normalization of client language follows?


texts: Literature for Generalized Load Balancing

texts:
i am looking for literature on this kind of problem.
$$
\begin{align}
\min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\
\text{subject to}&\\
&\sum_j x_{ij}=1,&& \forall i\in\mathcal J\\
&x_{ij}\in\{0,1\},&& \forall i\in\mathcal J, j\in\mathcal M
\end{align}
$$

$\mathcal J$ is a set of Jobs and $\mathcal M$ is a set of Machines.
$c_{ij}$ is a vector and describes the cost of the job $i$ on the machine $j$.
So the cost has multiple dimension.

The Aim of the programm is to find a schedule so that each job is scheduled on a machine and the biggest dimension of the add up cost vector is minimized.

The problem is described here:

http://arxiv.org/pdf/1211.5729v2.pdf (Page 2 left column bottom) as Generalized load balancing

and here:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&rep=rep1&type=pdf (Page 4 left column) as  generalized AP association
problem

EDIT

load balancing can be generalized in several ways, i.e. restrict that each job can only run on a specific set of machines.
This is also a generalization of the scheduling problem.

I'm interested in the case where the scheduling is restricted and multidimensional.
I'm looking for more literature for this problem.

Thank you


texts: Getting to local/global minima with (stochastic) gradient descent on non-convex objectives

texts: Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that the spectral norm of the Hessian is bounded by some epsilon..)


texts: Generalization of locally bounded treewidth graphs

texts:
Is the following graph class known in the literature?

The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance at most $d$ from $v$ in $G$ has treewidth at most $t$.

It generalizes the concept of locally bounded treewidth, and it seems useful when searching for local structures in graphs.


texts: Can we design our own `if` clause in Normal Order evaluation

texts:
I have been reading SICP and have been thinking over a thing for quite some time related to evaluation using Substitution with Applicative-order vs Normal-Order.

Suppose, I have defined my own if-new clause which is supposed to behave exactly as if

(define (if-new predicate a b)
        (cond (predicate a)(else b)))

This is not same as if in a runtime that evaluates in Applicative-Order. Example:

(define (p) (p))
(if (= 0 0) 0 (p)) ; This evaluates to 0.

; In case of 'if-new`
(if-new (= 0 0) 0 (p)) ; Infinite self-recursive iterative loop

But say it was evaluated in Normal-order then it will evaluate to 0.

So can I say, for a runtime which evaluates in Normal-Order, is if-new same as if?

PS: I could not think of any counter examples. I tried to solve it mathematically by proof of contradiction but I am not sure of its correctness.

Proof by Contradiction: Hypothesis: A runtime which evaluates in Normal-Order, (if-new p a b) is not same as (if p a b)
               where p,a,b are deterministic expressions and pure procedures. (i.e. when evaluated they return the same value always)

Then ∃(p a b) such that (if-new p a b) => x1 and (if p a b) => x2. And x1 != x2 (=> represents evaluation)

a' represents that a has been evaluated.

Case-1: p whenever evaluated, returns true

   (if-new p a b) => (cond (p a)(else b)) => (cond (p' a)(else b)) => a'

   (if p a b) => p' => a'

Case-2: p whenever evaluated, returns false

   (if-new p a b) => (cond (p a)(else b)) => (cond (p' a)(else b)) => b'

   (if p a b) => p' => b'

In each of the case, both the expressions provide the same result. This is a contradiction as our assumption suggests they are different. Hence proved


texts: Strongly normalizing type theory beyond induction-recursion

texts: Are there known type theories in the literature, which have strong normalization proofs and their proof-theoretical strength goes beyond strength of type theories with induction-recursion?


texts: Finding a subset of a set in a collection of sets

texts:
What data structures would you recommend that represent a collections of subsets of $\{1, \dots, n\}$ and support the following operations?

$insert(S)$: inserts $S$ in the collection.
$query(S)$: returns true if there exists $S'$ in the collection such that $S' \subset S$, false otherwise.

My main criterion would be practical time efficiency.


texts: "Elements of Information Theory": Some (basic) help needed here

texts:
I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me)

I have one question that has been irking for me some time. It is regarding that achievability of the Capacity region for multiple access channels (p530-531):

$\mathbf{X_1, X_2}$ are two i.i.d. random $n-$sequences (codes) drawn from a joint distribution $p(x_1, x_2)=p_1(x_1)p_2(x_2)$. These sequences correspond to two indepepndent information sources. These sequences are mapped to an output sequence $\mathbf{Y}$ by a discrete memoryless channel have transition probability mass function $p(y|x_1, x_2)$. Let $A_\epsilon^{(n)}$ the set of jointly-typical $\mathbf{(x_1, x_2, y)}$ sequences. The senders map their input alphabet set $\{1,2,...,2^{nR_1}\}\times\{1,2,...,2^{nR_2}\}$ to the code sequence pair $\mathbf{X_1}(i),\mathbf{X_2}(j)$. The decoder selects that pair $(i, j)$ for which $$(\mathbf{x_1}(i), \mathbf{x_2}(j), \mathbf{y}) \in A_\epsilon^{(n)}.$$ The goal is to bound the probability of error $P_e^{(n)}$ using this typical decoding strategy and eventually to show that it goes to zero as the blocklength $n\rightarrow \infty$.

To this end, define the following event:$$E_{ij}=\{(\mathbf{X_1}(i), \mathbf{X_2}(j), \mathbf{Y}) \in A_\epsilon^{(n)}\}$$

Suppose that the index $(1,1)$ was transmitted. The probability of error in this event is union bounded as$$P_e^{(n)} \leq P(E_{11}^c) + \sum_{i\neq1, j=1}P(E_{i1}) +\sum_{i=1, j \neq 1}P(E_{1j}) + \sum_{i\neq1, j\neq1}P(E_{ij}) $$
Consider the second term, here is the problem:

  $$P(E_{i1})=P\{(\mathbf{X_1}(i), \mathbf{X_2}(1), \mathbf{Y}) \in A_\epsilon^{(n)}\}=\sum_{(\mathbf{x_1},\mathbf{x_2},\mathbf{y})\in A_\epsilon^{(n)}}p(\mathbf{x_1})p(\mathbf{x_2},\mathbf{y})$$

This last factorization of the joint PDF is something i do not understand. The fact that the sequences $\mathbf{X_1}(i)$ and $\mathbf{X_2}(1)$ are independent is certainly not enough to justify it. I would appreciate if someone can shed a little light on it.


texts: Subexponentially solvable hard graph problems

texts:
In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms but believed not to be polynomially solvable. A famous example is graph isomorphism which has subexponential algorithm of $2^{O(n^{1/2} \log n)}$ run-time. Another example is log-Clique problem which is solvable in quasi-polynomial time ($n^{O(\log n)}$).

  I'm looking for interesting examples and preferably a reference to surveys of subexponential hard graph problems (not necessarily $NP$-complete). Also, Are there any $NP$-complete graph problems with subexponential time algorithms?

Impagliazzo, Paturi and Zane showed that the Exponential Time Hypothesis implies that Clique, k-Colorability, and Vertex Cover need $2^{\Omega(n)}$ time.


texts: The halting problem in computational models weaker than Turing machines

texts:
What are the main results and/or literature on the (self) halting problem
for other machines than Turing machines? Alternatively, what would be
the right keywords or tags to search for it.

I am considering of course the ability to determine halting on given
input of automata in a family $F$ by one of the members of $F$,
i.e. the $F$-decidability of the halting problem for $F$-automata.

I am not here interested in hypercomputation, but rather in
"hypocomputation", i.e. computational models that are weaker than
Turing machines.

One problem I looked at is the definition of halting for
non-deterministic models of computation, since non-determinism can
make a difference for PDA and possibly for LBA. I asked a question on
that, Defining the halting problem for non-deterministic automata, but
was a bit disappointed by answers, and ended up answering it myself (how well, I do not know).

Other issues I have in mind are:

what would be a proper definition of a family of automata defining
a model of computation? Should it satisfy some closure property or other?

The reason is that one can contrive simple collections of automata such
that one of them will decide halting for the whole family. But it
does not seem very meaningful, if that is all the family has to offer.
when asking one automaton $H$ to decide on halting of automaton $A$ on
input $I$, is one free to encode $A$ and $I$ in whatever way
is deemed convenient?

I am not even sure whether stating that there is a standard
encoding has any meaning.

I realize the question is open. But I do not know how much may exist
as possible answer, possibly little. If it is too wide, suggestions to
tighten it would be welcome.


texts: Four color theorem and map pre-simplification of faces with less than 5 edges

texts:
It is already known that in searching for a solution of the four color problem, regular maps can be pre-simplified by removing all faces with less than four edges. This is described for example in the book "What is Mathematics? An Elementary Approach to Ideas and Methods" about the five color theorem.

I belive that all regular maps can be simplified by removing all faces with less than five edges (instead of less then four), without affecting the search and the validity of the four color theorem. This simplification is described here: http://4coloring.wordpress.com/t1/

In this case Euler’s identity gets really simplified: F5 = 12 + F7 + 2F8 + 3 F9 + ...

What is known about this? Has it already been studied before?


texts: Self Generating Grammars - Does it have to be infinite recursion?

texts:
For brevity, let's redefine a grammar to be just the three-tuple $(\Sigma_G, P_G, S_G)$.
As usual, $\Sigma_G$ is the alphabet, $P_G$ are the production rules and $S_G$ is the start rule of $G$.
For our "special" instance of a grammar, which we call $X$:
Let's define our alphabet $\Sigma_X$ to contain the metasymbols

or rather "symbols that are indistinguishable to whoever will be parsing the definition"

themselves used to define grammars in the first place:
$$\{\text{ }\pmb{\{},\text{ }\pmb{,}\text{ },\pmb{\}}, etc\}$$
Then, we can define $P_X$ as $\{S_X \to \pmb{(}\Sigma_X\pmb{,}P_X\pmb{,}S_X\pmb{)}\}$
Of course, $\Sigma_X$ actually expands to all the required metasymbols to define $X$ itself and any other alphabetic symbols used in the production rules of $X$.
As one can see, $P_X$ is not only a recursive definition, but it never meets an end.
Are there cleverer ways to construct a self-replicating grammar?
By self-replicating grammar, I mean a grammar whose only recognisable language is that which contains only the string which is used to define it in the first place.


texts:
Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ?

I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m>1$, is it true that $F$ has exactly $m$ models ?

Both problems look similar. So my questions are :

1- Is «Exactly $m$-SAT » polytime (many-one or Turing) reducible to Unique SAT?

2- Do you know any reference on the subject ?

Thank you for your answers.

Addendum, first articles about complexity of Exactly $m$ SAT :

1- Janos Simon, On the Difference Between One and Many, In Proceedings of the Fourth Colloquium on Automata, Languages and Programming, 480-491, 1977.

2- Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 23, 325-356, 1986.

In both articles, Exactly $m$ SAT ($m \geq 1$) is shown to be $C=$ complete (under many-one reductions), where the class $C$ is from the Counting Hierarchy (CH) of complexity classes. Informally, $C$ contains all problems which can be expressed as deciding whether a given
instance has at least $m$ many polynomial size proofs (the class $C$ is known to coincide with the class $PP$). The class $C=$ is a variant of $C$, where “exactly $m$” replaces “at least $m$".


texts: Efficient graph isomorphism for similar graph queries

texts:
Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one node from G2, and we have the result of F(G1,G2), can we compute F(G1,G3) without computing it from scratch by extending any existing state-of-the-art methods?

For example, if G2 is formed by nodes 2,3,4,5 and G3 is formed by nodes 3,4,5,6, can we make use of the result of F(G1,G2) to compute F(G1,G3) more efficiently?


texts: What does it mean that there are differing views on how computations are represented on the Turing Machine?

texts:
For a given algorithm (eg reverse the items in this list) and a given type of Turing machine (eg the 3-state 2-symbol busy beaver reduced to 5-tuples) - is there a single simplest way that this algorithm can be represented?

(This thread on LTU seems to suggest there are differences of opinion about what representing an algorithm on the Turing machine boils down to.)


texts: What are the limits of computation in this universe?

texts:
I understand that Turing completeness requires unbounded memory and unbounded time.
However there is a finite amount of atoms in this universe, thus making memory bounded. For example even though $\pi$ is irrational there is no way to store more than a certain number of digits even if all the atoms in the universe were used for this purpose.
What then are the limits of computability of an implemented Turing machine (which could use all the resources of the universe but no more) based on the limits of the universe? What is the maximum number of digits of $\pi$? Are there any papers on this subject that might be interesting to read?


texts: Linear Time Hierarchy and Circuit complexity

texts:
By Karp-Lipton Theorem we have:
$$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$
So this theorem suggest it is unlikely that $PH\subseteq P/poly$.
I want to know is there any similar conditional or unconditional theorems that study relationship between $LinH$ and $P/poly$?

Thanks!


texts: Choosing one number from each set so that the difference between maximum and minimum is minimized

texts:
Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}.

I need to choose exactly one number from each of these sets, so that the difference between the largest and smallest chosen numbers is as small as possible.

What type of problem is this?  Is there a graph algorithm that could be used to solve this problem?


texts: A proof that Partition into forests is NP-Complete

texts:
The partition a graph into forests problem is defined as:

Given a Graph $G=(V,A)$, and a positive integer $K \le |V|$, can the vertices $V$ be partitioned into disjoint sets $V_1$, ..., $V_k$, $k \le K$, such that, for $1 \le i \le k$, the subgraph induced by $V_i$ contains no circuits?

I am trying to prove it is NP-Complete the following way:

Given an instance of the clique problem consisting of a graph $G'=(V', A')$ and a number $m$, where $m$ is odd, I will build an instance for my problem in the following way: $G=G'$, and $k = \frac{m-1}{2}$. If there is a clique with size at least $m$ in $G$, then there will be no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits. And if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G'$.

Is this proof correct?

If not, how can I prove that the partition a graph into forests problem is NP-Complete?


texts: Select in union of sorted arrays: Already known?

texts:
I am looking for bibliographic references for the following algorithm/problem: I named it "BiSelect" or "t-ary Select" or "Select in Union of Sorted Arrays", but I guess it was introduced before under another name?

Problem

Consider the following problem:

  Given $k$ disjoint sorted arrays $A_1,\ldots, A_k$, of respective sizes $n_1,\ldots,n_k$, and an integer $t\in[1..\sum n_i]$, what is
  the $t$-th value of their sorted union $\cup_i A_i$?

Solutions

There is a very simple and elegant algorithm running in time $O(\lg\min\{n_1,n_2,t\})$ if $k=2$: if $k=2$, just compare $A_1[t/2]$ with $A_2[t/2]$ and recurse on $A_1[t/2..t]$ and $A_2[1..t/2]$ or $A_1[1..t/2]$ and $A_2[t/2..t]$ accordingly, in both cases with parameter $t/2$ (and some minor optimizations when $n_1$ or $n_2$ are smaller than $t$).

This generalizes to a slightly more sophisticated algorithm running in time $O(k\lg t)$ for larger values of $k$, based on computing the median of the values $A_i[t/k]$ for $i\in[1..k]$: the $t/k$  smallest elements can be further ignored in the $k/2$ arrays where $A_i[t/k]$ is smaller than the median, and the elements of ranks in $[t-t/k..]$ can be further ignored in the $k/2$ other arrays, resulting in a halving of $t$ in each recurrence (and a cost of $O(k)$ for the median).

References?

I am happy with my solution(s), but I suppose that the problem (and its solution) was already known. It is related to the linear time algorithm for computing the median (by sorting groups of size $5$, and recurse on the median of their middles), but is slightly more general. I asked several colleges at Madalgo in Aarhus (Denmark), and then some others at the workshop Stringology (Rouen), without success:  I am hoping that someone more knowledgeable might help on Stack Exchange...

Motivations

Solutions to this problem have applications to Deferred Data Structure on arrays (indeed, it can be seen as an operator in a deferred data structure for the union of sorted arrays); and in a more convoluted way, to the adaptive computation of optimal prefix free codes.


texts: Sublinear time algorithm for maximum degree node

texts:
Here is a quick algorithmic problem: given a graph $G=(V,E)$ such that for each two distinct nodes $u,v \in V$ there's exactly one directed edge between them, and a probability $p$, such that each node is available w.p. $p$, find the maximum in-degree node in the induced realized subgraph. The goal is to minimize the expected number of queries, where a query means checking whether a node is available or not. The existence of an edge can be verified only after querying both of its end-points, of course.

Now, I am interested in proving lower bounds for either adaptive or non-adaptive sublinear time algorithms (as a function of p and n), and the complexity of constructing a policy tree that in each node either makes a query or declares the answer.

Any thoughts? Potentially useful directions would be most welcome.

Thanks,
Joel.


texts: Automatic structures/functions: Is (Z,+) under a unary representation automatic?

texts:
The group $(\mathbb{Z}, +)$ is automatic (ala Khoussainov) when using the "standard" representation in a decimal base. But if I want to use a different representation of Z, encoding my integers with the alphabet $\Sigma = \{y, z\}$
$0 = z$
$1 = yz$
$-1 = zy$
$2 = yyz$
$-2 = zyy$...

however the representation of each integer is not unique... $ z = yzy = yyzyy = yyyzyyy$ (the standard construction in set theory) This leads to problems later.

If we define
$a + b :=$ match $a$ with
$|z \rightarrow b$
$|y^nzy^m \rightarrow y^{n-1}zy^m + yb$
$|zy^n \rightarrow zy^{n-1} + by$

Now, by some convolution function, I can accept equations such as "$z + z = z$" or "$yyyz + zyy = yyyzyy$" but not equations such as "$z + z = yzy$" and "$yyyz + zyy = yz$"

Should this (unary integral addition) count as an automatic function?


texts: Computational query complexity of SQ-learning

texts:
It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic learning by a computationally unbounded learner, and the sample complexity needed by a polynomial-time learner. (see, e.g. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE or http://portal.acm.org/citation.cfm?id=301437)

These results seem to depend on encoding a secret in particular examples, however, and so don't naturally translate into the SQ-model of learning, where the learner just gets to query statistical properties of the distribution.

Is it known whether there exist concept classes for which information-theoretic learning in the SQ model is possible with O(f(n)) queries, but computationally efficient learning is only possible with Omega(g(n)) queries for g(n) >> f(n)?


texts:
Does anyone knows of references that precisely spell out the connection between the unification algorithm and Gaussian elimination? I'm particularly interested in the relationship between triangular substitutions and LU decompositions.

Wayne Snyder and Jean Gallier mention this analogy in passing in their paper, Higher-Order Unification Revisited: Complete Sets of Transformations.


texts: Complexity of finding the largest induced subgraph with all even degrees

texts:
What is the complexity of the following problem?

Instance: Simple, undirected graph $G$, and a positive integer $k$.

Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that all vertices have even degree within the subgraph?

Remark. It is similar to the problem known as Maximum Eulerian Subgraph, which is is NP-complete. However, in Maximum Eulerian Subgraph, beyond the even degrees, it is also required that the subgraph is connected. It is not clear whether dropping the connectivity requirement makes the task easier, or it still remains NP-complete.


texts:
Suppose we have two stacks of cards on a table. On each turn, each of two players draws a card from the top of one of the stacks. The game ends when there are no cards left in either stack. The person with the greatest sum then wins. If this were a chess problem, for example, one could attempt to solve this game by starting from a winning final position, and then inducting backwards. However, in this game, the final card picked up has little bearing, as it is the overall sum that results in a winner. Is it possible to find a game plan for perfect play, assuming both players pursue this game plan?

EDIT: The values of all the cards are known by both players, i.e. the players are omniscient when it comes to information about the cards. The card deck need not be complete, just some random cards in two stacks on a table, and we only care about the values.

EDIT 2: I'm wondering whether this can be solved efficiently with an algorithm that does not have to go through all the potential decisions in a decision tree.


texts: $NP$-complete problem with quasi-polynomial bound on the number of solutions

texts:
FewP is the class of $NP$-problems with polynomial bound on the number of solutions (in the input size). There is no known $NP$-complete problem in $fewP$. I am interested in how far we can stretch this observation.

  Is there any natural $NP$-complete problem with quasi-polynomial upper bound on the number of solutions (witnesses)? Is there a widely accepted conjecture that would rule out such possibility?

Natural means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (as defined by Kaveh).

EDIT: The bounty will be awarded to such natural $NP$-complete problem or a reasonable argument ruling out the existence of such problems (using widely accepted complexity-theoretic conjectures).

Motivation: My intuition is that $NP$-completeness imposes super-polynomial (or even exponential) lower bound on the number of witnesses.


texts: Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

texts:
Sean Anderson published bit twiddling hacks containing the Eric Cole's algorithm to find the $\lceil\log_2 v \rceil$ of an $N$-bit integer $v$ in $O(\lg(N))$ operations with multiply and lookup.

The algorithm relies on a "magic" number from De Bruijn sequence.
Can anybody explain fundamental math properties of the sequence used here?

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];


texts: Understanding the definition of a "restriction of a resolution derivation"

texts:
I am reading the paper An Introduction to Lower Bounds on Resolution Proof Systems. In its subsection 2.3 the author gives an inductive definition of the restriction of a resolution refutation $\pi$.
My preoccupation resides on the second line of the definition :

$C'_i=C'_{j_1} \vee C'_{j_2}$ if $C_{j_1} \vee y$ and $C_{j_2}\vee \bar{y}$ derive $C_i$ via the resolution rule for $j_1 < j_2 < i;$.

I wonder how this induction can be apply on $C'_{j_1}$ and $C'_{j_2}$ since $C_{j_1}$ and  $C_{j_2}$ are not in $\pi$ but instead $C_{j_1}\vee y$ and  $C_{j_2}\vee \bar{y}$.

Furthermore, in example 2.12 the author computes the restrictions  $\pi[x_1=0]$ and $\pi[x_2=1]$ of the refutation $\pi$ as if they were just a restrictions of sets of clauses i.e. by using $\pi[x=a]=\{C[x=a]; C \in \pi\}$ instead of the inductive definition.

Is there anything that I'm missing?


texts: Inferring simplest method to convert bit array 1 to bit array 2

texts:
Consider the set of all bit arrays of length n. Now consider the set of all 1-to-1 functions that map from this set to this set.

Now select a single function out of the latter set. Is there any algorithm to find a "minimal" method of implementing this function? Assume that we only have access to fundamental bit array operators such as AND OR XOR NOT and left and right bitshifts.

In case you're wondering, the reason I want this is because I'm writing an algorithm to convert from z-curve ordering of bits to hilbert-curve ordering of bits. My current method is to make a lookup table, but I bet there's a better option.

As a simple example, let's say I have a truth table that looks like this:

00 -> 10
01 -> 01
10 -> 00
11 -> 11

Then I should be able to infer that, given an input bit string input, the output bit string output is (in java syntax)

output = ((~input) << 1) ^ input

Here's the proof in this case:

00 -> 11 -> 10 -> 10
01 -> 10 -> 00 -> 01
10 -> 01 -> 10 -> 00
11 -> 00 -> 00 -> 11


texts: Better lower bounds than 3n for non-boolean functions?

texts:
Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results.

What are the best known lower bounds if the range of $f$ is $\{0,1\}^m$?  In particular, do we get anything better for $m = n$, or for $m = 2$?


texts: Are there [good/optimal] parallel comparison sorts?

texts:
Comparing each pair of elements and sorting according to

[[number less than] minus [number greater than]] is a parallel comparison

sorting algorithm with a depth of $1$ comparison and $O\left(n^2\right)$ total comparisons.

By the AKS network, there is a parallel comparison sorting algorithm with

a depth of $O(\log(n))$ comparisons and $O(n\cdot \log(n))$ total comparisons.

1.
Are there any parallel comparsion sorts with a depth of

$o(\log(n))$ comparisons and $o\left(n^2\right)$ total comparisons?
2.
Are there any parallel comparison sorts with a depth

of $1$ comparison and $O(n\cdot \log(n))$ total comparisons?


texts: Time complexity of finding chain decomposition of partially ordered set

texts:
Given a partially ordered set $P$ with $n=|P|$ and width $w$:
-What is the best known complexity (in expectation) for finding a chain decomposition of $w$ chains?
-What is the best known complexity (in expectation) for finding a chain decomposition of $O(w)$ chains?
The paper "On the Decomposition of Posets" (2012) seems to provide an algorithm in worst-case $O(wn^2)$ time for the first question but is there better for either?
Another question, possibly naive: does the chain decomposition produced by topological sort have any guarantees on the number of chains it consists of?


texts: Compendium of the Best Approximation and Hardness Results for NP optimization problems

texts:
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?

Based on the feedback, it seems that it is safe to assume there is not such a resource (see the end of this question for two close options). -- added on Feb 8.

Since there is a huge body of results and problems introduced in the past two decades, existence of a dedicated wiki could be a great help for students and professionals working on subject of approximation algorithms and hardness of approximation.

I have been suggested to start a new wiki. I like the idea, but I need some feedback before starting:
Are you interested in a wiki devoted to the above subject and are you going to contribute something? What is your preferred format for this wiki (see my preferred format in comments)? Should we use a wiki farm or a wiki engine? In the latter case, what is your suggestion for a wiki engine? MediaWiki?

The two closest options that I am aware of, are:
1- "A compendium of NP optimization problems," edited by Pierluigi Crescenzi and Viggo Kann: This compendium seems to be out-of-date. I think the volume of current results cannot be managed by a few people and if we want an up-to-date list, we should have a wiki.
2- Wikipedia: This wiki is for general audience and you cannot have a short page just including problem description, and the best approximation and hardness result.


texts: Deciding bound on Tensor Rank for a fixed value

texts:
This question is related to a previous unanswered question of mine.  Please see that question for background.

When Håstad proved that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input.  Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.

What if we fix the bound on the rank to some constant?  For example...

  What is the complexity of deciding if a tensor has rank at most 3?

The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check).  Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best.  I am personally interested in this question using the complex numbers.


texts:
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be some string.

Consider the following Alice and Bob game. Initially, Alice and Bob have $m_A$ and $m_B$ dollars respectively. Alice wants $M^A(x)=1$ and Bob wants $M^A(x)=0$.

At every step of the game a player can add one string to $A$; this costs one dollar. Also a player can miss his or her step.

The play ends if both players spends all money or if some player missed step when he or she in a losing position (that defines by the current value of $M^A(x)$).

Question: is the problem of defining the winner of this game for given $M, x, m_A, m_B$ is an

EXPSPACE-complete task?

Note that $M$ can ask (for belonging to $A$) only strings of polynomial length so there is no  sense for Alice or Bob to add more longer strings to $A$. Hence, this problem is in EXPSPACE.


texts: Boundary between decidability and undecidability for small theories

texts:
There is a lot of research on the boundary between decidability and undecidability of the halting problem for small models of computation: Turing machines, tag systems, CAs, ... This boundary is clearly linked to the (non-)universality of such models.

I'm wondering if there are similar works on the "logic-side":

  What are the smallest theories for which the boundary between  decidability and undecidability (of valid formulas) is unknown ?
  Is there a survey paper on the subject ?

I realize that it is not easy to formalize the notion of "small theory" (or "simple" theory), but it should include the number of axioms of the theory and the size of the signature.

For example Andrzej Grzegorczyk in “Undecidability without arithmetization” (Studia Logica 79(2005))
proved that Tarski’s theory of concatenation (TC) is already undecidable; the axioms are:

TC1: $x*(y*z) = (x*y)*z$
TC2: $(x*y = u*v ) \to \exists w((x*w = u \land w*v = y)\lor(u*w = x \land w*y = v))$
TC3: $\neg (\alpha = x*y)$
TC4: $\neg (\beta = x*y)$
TC5: $\neg (\alpha = \beta)$


texts:
reading this paper on CPS-tranformation from the $\lambda\mu$-calculus, I'm a bit confused about the type system presented:

Why second-order formulas in the types?  Is this according to the Curry-Howard interpretation?
What kind of second-order formulas are permitted here, can $X$ be any arbitrary n-ary relational symbol?
Am  I reading this correctly, that the quantifier introduction / elimination rules only apply to non-indexed formulas?
Is there a relation between the $\lambda$-variables in the terms (resp. the indices of the formulas in $\Gamma$) and the variables in the formulas?
As far as I can see, the only way for a $\lambda\mu$-formula to have a type is that any occurence $[\alpha]$ is directly preceded by some $\mu\beta$ since $[\alpha]M$ has a type of the form $\Gamma\vdash\Delta$ and the only typing rule that can deal with this form (no non-indexed formula $A$) is $\mu$-introduction.  Is that correct?


texts: Structures admitting directed sums and directed products?

texts:
Some structures have a property of closure by a "sum" or "product" operation. Given a family of structures $(S_i)_{i \in I}$, we can then define a new structure denoted by $\sum_{i \in I} S_i$, resp. $\prod_{i \in I} S_i$; structures enjoying this property are vector spaces for instance. I consider these operations as "undirected" as the result does not depend on the order of the summands, up to isomorphism.

I am interested in structures for which we can define a "directed sum" / "directed product" operation, meaning that the definition of the sum / product could now depend on the structure of the index set $I$ (e.g. it could be a totally ordered set and we would compute non-commutative sums / products according to this order).

To illustrate this, consider the following definitions for posets. Let $I = (G,\leq)$ be a poset and for each $i \in G$ let $S_i = (U_i,\leq_i)$ be a poset.

we define $\sum_{i \in I} S_i$ as the poset $R = (V,\leq')$ with $V = \cup_{i \in G} \{i\} \times U_i$, and $(i,x) \leq' (j,y)$ iff either $i < j$ or ($i = j$ and $x \leq_i y$);
we define $\prod_{i \in I} S_i$ as the poset $T = (W,\leq'')$ with $W = \prod_{i \in G} U_i$, and $x \leq'' y$ iff there exists a maximal antichain $A$ of $I$ such that (i) for every $i \in G$ below $A$, $x_i = y_i$, (ii) for every $i \in A$, $x_i \leq_i y_i$.

Note that when the poset $I$ has no arcs, then we recover the usual constructions (disjoint union and function dominance).

In particular I would like to know whether (i) there could exist an axiomatic / category-theoretic definition of these "directed" operations, (ii) there are other examples of structures displaying this property.


texts: NP-hardness of approximation for unconstrained submodular maximization

texts:
The problem of unconstrained submodular maximization can be phrased as follows:

  Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$.

Here a submodular function is one satisfying
$$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$
for all $A,B \subseteq D$.

Buchbinder et al. gave a $1/2$-approximation algorithm for this problem. This is best possible in the value oracle model: Feige et al. showed that achieving a $(1/2+\epsilon)$-approximation requires exponentially many value oracle queries, for any $\epsilon > 0$.

What if the function $f$ is given explicitly? Dobzinsky and Vondrák gave a class of explicit functions for which no $(1/2+\epsilon)$-approximation can be achieved unless $\mathsf{NP} = \mathsf{RP}$.

My question is:

  Is there a natural class of explicit submodular functions that is NP-hard to $(1/2+\epsilon)$-approximate for all $\epsilon > 0$?

Compared to Dobzinsky and Vondrák's result, I want a result which holds under the assumption $\mathsf{NP} \neq \mathsf{P}$ rather than the stronger $\mathsf{NP} \neq \mathsf{RP}$, and moreover I want the class of explicit functions to be natural, in contrast to the ingenious but somewhat contrived functions used by Dobzinsky and Vondrák.

For the related problem of monotone submodular maximization subject to a matroid constraint, such a beast does exist: Feige famously showed that is it NP-hard to approximate Maximum Coverage any better than $1-1/e$, which matches both the value oracle hardness and the best approximation algorithms.


texts: Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

texts:
For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$.  This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) dynamic programming on a bounded tree-width decomposition of $G$ derived from the DFS traversal.

However, [2] does not contain explicit details on what information should be stored in the tables associated with each bag of the tree decomposition.

  When looking for long cycles using the dynamic programming method suggested by [2], are there any ideas or resources that specify what information needs to be stored at each bag and how to combine such tables?

References:

[1] Gabow & Nie, 2008
contains an overview of the above problem, from the perspective of directed and undirected graphs, and includes a review of research on the undirected case.

[2] Bodlaender, 1993 suggests an $O(k!2^kn)$-time algorithm based on depth-first search (DFS) and dynamic programming.


texts: Book/ Monograph on graph minor theory [Reference request]

texts:
I want to learn graph minor theory. Now i have read the very basic things and the overview from the book of R.Diestel but proceeding further is getting difficult. Currently, I am also following the video lectures by Jim Geelan on graph minor theory.

Please suggest more books/monographs/lecture notes on graph minor theory. In case there is none, please suggest a systematic way to learn the concepts.

I posted the same question here, but not sure if it reached the right community.


texts: Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

texts:
Let $G=(V,E)$ be graph. Recall that a  cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in E \mid a \in A, b \in B\} = E \cap (A \times B)$. Finally, let $E = E_1 \cup E_2$ be a given partitioning of the edges.

Question. What is an efficient way to generate a cut $(A,B)$ of $G$ such that $|E_1(A,B)| > |E_2(A,B)|$ ?

Note. I'm fine with randomized algorithms. Also, in case one has the choice, I'd prefer a cut with minimal $|E(A,B)|$.


texts: Is there a known automatic proof of the independence of the continuum hypothesis?

texts:
In 2002, L.C. Paulson gave a mechanized proof of the consistency of the axiom of choice by formalizing $V=L$ and its consistency. We could ask whether there is a formalized proof of the independence of the continumm hypothesis (abbr. CH).

I have read the article mentioned above, and I know that he does not provide  a full metatheory, but only some instantiations required to achieve his goal; for example, he does not prove the fact that every $\Delta_0$-formula is absolute w.r.t. transitive models. Instead, he only proves the absoluteness of some useful concepts.

In the entire article, the author avoids metatheoretic arguments as much as possible. I didn't understand the reason why he did that, though it was very difficult in that time. We cannot hope, however, to formalize forcing arguments because it heavily relies on metatheory. For example, a forcing relation $p\Vdash \phi$ is defined for every formula $\phi$, so the definition of a forcing relation is in fact a metadefinition for each formula $\phi$.

Is the difficulty to handle metatheory the reason why nobody has tried to formalize the forcing arguments and the independence proof of the continuum hypothesis?
15 years have passed from when that article appeared, so I hope someone has found a way to formalize meta-arguments.

In short, my question is:

Is there any attempt to mechanize an independence proof of CH?
If not, what makes it so difficult? I guess handling metamathematics causes a problem. Is that right?


texts: EXP-Complete Problems vs Subexponential Algorithms

texts:
Does the fact that a problem $A$ is EXP-time complete implies that $A$ is
not in $DTIME(2^{o(n)})$?

I'm aware that by the time hierarchy theorem, $EXP=DTIME(2^{n^{O(1)}})$ is not
included in $E=DTIME(2^{O(n)})$. Nevertheless this does not seem to exclude immediately the existence of sub-exponential time algorithms for every EXP-complete problem $A$, since when reducing an instance $x$ of a problem $B\in EXP$ to an instance y of problem $A$, we may have a polynomial blow up in size. In other words, $|y|=|x|^{O(1)}$.

So my question is whether there exists some argument that rules out, unconditionally, the existence of sub-exponential time algorithms for EXP-complete problems.


texts:
Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.

For example, the “regular expression”

/^1?$|^(11+?)\1+$/

created by noted Perl personality Abigail (and part of Perl's test suite since 2002) describes a machine that accepts only composite unary numbers, but exercise 4.5 (b) in the third edition of Peter Linz's An Introduction to Formal Languages and Automata has the reader use the pumping lemma to prove that

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

is not a regular language.

In contexts where the distinction is important, what should we call the strictly more powerful expressions?


texts: Graph labelling where vertices with a common neighbour get different labels

texts:
Is the following notion of graph labeling (let me call it special labeling) ever studied in the literature?
A special labelling of a (simple undirected) graph $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $u$ and $v$ have a common neighbour (i.e., $N(u)\cap N(v)\neq \emptyset$).
The closest I  could find in the literature is strong subcoloring introduced in [1]. A strong subcoloring of $G$ is a function $f:V(G)\to\mathbb{N}$ such that $f(u)\neq f(v)$ whenever $d(u,v)=2$ (i.e. distance between $u$ and $v$ in $G$ is two). The difference between the two notions is that special labelling does not allow two adjacent vertices to have the same label if they have a common neighbour. Both notions are the same for triangle-free graphs.
Reference
[1] Shalu, M. A.; Vijayakumar, S.; Yamini, S. Devi; Sandhya, T. P., On the algorithmic aspects of strong subcoloring, J. Comb. Optim. 35, No. 4, 1312-1329 (2018). ZBL1400.90266.


texts: Is the Witness Size of Membership for Every NP Language Already Known?

texts:
The question occurred to me when I get Dana Moshkovitz answer to another topic.

Let $L$ be an NP Language, and let $R_L$ be the respective NP relation. We know that there exists some polynomial $p$ such that:

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

The above statement only requires the existence of such $p$, but it does not force it to be explicitly determined. In contrast, for every NP language I know, $p$ is already known:

For SAT, the size of witness is equal to the number of atoms appearing in the formula.
For Hamiltonicity, the size of witness is $O(|V|)$, where $V$ is the vertex set.
For Graph 3-Coloring, the size of witness is $O(|V|)$, where $V$ is the vertex set.

  Does there exist an NP language (even an artificial one), for which we know there exist some polynomial $p$ bounding the size of witness, yet we cannot explicitly determine $p$?


texts: generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

texts: In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their Theorem 1 that every language in NP has a perfect zero-knowledge protocol in the two-prover model.  The protocol is presented as a bit commitment scheme, which generalizes to a commitment scheme for arbitrary data by the well-known fact that all we are is 0s and 1s. My question is about the existence of more "direct" generalizations.  Specifically, it seems to me that the protocol is based on some simple facts about the finite fields ${\bf Z}_2$ and ${\bf Z}_3$, and I was wondering whether anyone has worked out how to abstract away these facts and generalize the commitment scheme to values over larger finite fields?


texts: Can an oracle allowing errors be non-relativizing?

texts: I am experimenting with k-SAT.  I'm using an oracle that returns the total number of satisfiable truth assignments, which is in #P.  The interest here is that this total is returned modulo a natural number, say N.  There is therefore a 1/N probability that the oracle mistakes a satisfiable problem for one with zero satisfiable truth assignments.  I'm wondering if this oracle could be non-relativizing.  I'm also wondering if there has been research concerning oracles with similar types of "errors".


texts: Have there been any practical applications of domain theory to formal methods?

texts:
By Domain Theory, I mean the use of CPOs (or related topological/order-theoretic structures) to study the denotational semantics of programming languages.

Compared to the two other common approaches to formal methods (operational and axiomatic semantics), where one might point to things like formal proof assistants, dependently-typed programming languages, refinement types, I have yet to meet a practical tool which has been developed using the tools of denotational semantics designed to formally verify real-world programs. Or, at least it seems that way on the surface.

So are they any practical formal verification tools which have benefited, either directly or indirectly, from the research into domain theory/deonotational semantics? If not, have there at least been particular software projects where the use of domain theory has helped with the process of formal verification, even if it didn't result in a general software development tool?


texts: Objective function for stochastic optimization

texts:
Stochastic Optimization problems in general deals with random variables in the 'loss function'.

Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we usually have,

\begin{equation}
\min_{x} \parallel Ax-b \parallel_2^2
\end{equation}

With some uncertainty or possible variations in the data matrix A, it is natural to use the expected value of the objective function $\parallel Ax-b \parallel_2^2$:

\begin{equation}
\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)
\end{equation}

How is the above objective function different from the following objective function-
\begin{equation}
E\left( \min_{x} \parallel Ax-b \parallel_2^2 \right)
\end{equation}

Certainly, for the basic objective function, first objective has a closed form compared the second objective. But, why aren't we dealing with the second objective in general ?

Which is more precise ?


texts: k-center 2.0: A stronger k-center condition

texts:
Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.

Note that this procedure often selects fewer than $k$ centers since it only needs to cover everything with a radius of 2, while OPT covers everything (with $k$ centers) with a radius of 1.

I am considering a stronger version of the $k$-center problem:

Is there a way to select $k$ centers in a graph such that there is an OPTIMAL set of centers $S^*$ with every node in $S^*$ adjacent to a node we select?

I suspect that an algorithm for this problem should use the Hochbaum-Shmoys procedure to select some $k'$ centers, then place the extra centers in some clever way to ensure the stronger condition.


texts: Polynomial time solvable instances of Max-Sat

texts:
The problem Max-Sat ask you to find an assignment of a CNF formula which satisfy as many clauses as possible.

For the simpler problem SAT there are many known special cases which can be solved in polynomial time, e.g. we can solve 2-SAT in polynomial time.

For Max-Sat the situation is different since Max-Sat is NP-hard even for 2-CNF formulas (each clause contains only 2 variables).

Is there any interesting special inputs for which Max-Sat is polynomial?

In particular I would be interested in a standard reference for solving Max-Sat when the incedence graph has bounded treewidth.


texts: Bi-criteria combinatorial approximation algorithms for min k-vertex cover

texts:
Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.

It is easy to see that this problem is inapproximable unless studied in a bi-criteria setting. We know a very simple LP-rounding algorithm for this problem that is a $(3,3)$ bi-criteria approximation.

Q. Has this problem been studied in the literature elsewhere, perhaps with a different name? Are there any known combinatorial approximation algorithms for this problem?

Clarification: The objective of this problem is to output a set of vertices $S$ that minimize the number of uncovered edges in $G = (V,E)$. The number of uncovered edges is equal to the number of edges in $E$ that have neither end point in $S$.


texts: Are all turing machines paths predictable?

texts:
I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has a certain path in terms of its movement on the tape. A positive answer to the below would give a complete characterization of the paths for which the decision problem of whether a given turing machine has said path is computable.

Define the path of a turing machine to be the sequence of left and right movements it makes on an empty input. For example, this turing machine has a path which looks like LRRRLLRRRLLLRR...

Define a turing machine $M$ to be predictable if there exists another turing machine $N$ (not necessarily computable from $M$) with the following properties:

$N$ has the same path as $M$. That is, when $M$ turns left, so does $N$. When $M$ turns right, so does $N$. Although this seems like a strong restriction at first, $N$ is not required to have the same states or even the same tape alphabet as $M$ so using both of these it may still be able to do some pretty complicated stuff relative to what $M$ does.
There is a subset of $N$'s states, $Q'\subset Q$ such that whenever $N$'s head reads from a square for the last time, it must also be in a state in $Q'$. Also, we require $N$ to only enter a state from $Q'$ if it is reading from a square for the last time. Thus, in a way, $N$ is able to predict the path $M$ and $N$ are simultaneously taking.

My question is: Are all turing machines predictable?

Any help or pointers to reference materials would be appreciated, especially since the terminology here is my own and I don't know what to search to get information on this subject.


texts: What are the root difficulties in going from graphs to hypergraphs?

texts:
There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking.  Why do you think problems often become much harder over 3-uniform hypergraphs than over 2-uniform graphs?  What are the root difficulties?

One issue is that we don't, as of yet, have a satisfactory understanding of spectral hypergraph theory.  Please feel free to shed more light on this issue.  But I'm also looking for other reasons which make hypergraphs more difficult objects.


texts: Simulator Efficiency versus Algorithm Efficiency

texts:
I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses some kind of oracle called non-information oracle (which is provided for countering the adaptive adversary). This oracle is simply the proposed algorithm itself except the signing operations. The simulator must invoke $n$ copies of these oracles to simulate the interactions, and thus it is quite an inefficient simulator; because it is doing the same algorithm $n$ times for all dummy parties (each party in the ideal world of UC is called a dummy party, because it only relays or generates some inputs and gets the required output from functionality).

  Question 1: If I improve the simulator, does it mean that I have achieved a better result? If the current inefficient simulator suffices, does it have any meaning to redefine the simulator in a more modular way to reduce the simulation time?

BTW, I am partially aware of meaning of the Knowledge Tightness, but I am not sure of my understanding.

  Question 2: If I change some parts of the proposed algorithm to make my simulator more efficient and the proof of security more modular, but add (some) slight communication complexity to the resulting algorithm, how can I determine that my changes are an enhancement to the protocol? (I mean, how can I assume this trade off as an advantage?)


texts: Early references for discrete optimization

texts:
(Apologies if this is misplaced or too broad.  I'm open to suggestions on how to reformulate it.)

I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete optimization algorithms in general.  Ford-Fulkerson is my straw-man of a starting point.  What were the significant advances prior to that?  How far back can we go while still being able to make a reasonable argument that somebody was working on max-flow?  How about graph algorithms?  How about discrete optimization in general?

I'd also be happy to get references to places where this is discussed.


texts: Recursively enumerable, non-recursive language without using Gödel's number

texts:
I am trying to find out if there exists a language, which is recursively enumerable but not recursive, but which wouldn't also use Gödel's number or any other kind of Turing machine description in its definition. The language should be possible to somehow "easily" describe. ("Easily" being purely subjective, I know.)

But each one I try to construct is either recursive or not recursively enumerable.


texts:
I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one.  The unweighted version of the problem can be defined as follows.

We are given a graph $G = (V, E)$ and a set of integers $B(v)$ associated to each vertex.  The goal is to find a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph (V, F) is one of the integers in the associated set $B(v)$.

The problem is known to be solvable in polynomial time if $B(v)$ does not have gaps of length greater than one for any $v$.  For example the set $B(v) = \{5, 7, 8\}$ is OK (the gap between 5 and 7 is of length 1) but the set $B(v) = \{5, 8\}$ is not OK (the gap between 5 and 8 is of length 2).

My question is whether there are any known results for the weighted version of this problem.  So far I found a 1995 survey (Pulleyblank, "Matchings and Extensions") saying that the weighted version has not been solved: "Recently Cornuejols(1988) developed a polynomially bounded extension of the blossom algorithm for this problem when no gap of size greater than one is permitted. However, the corresponding weighted problem has not yet been solved." (p. 212 of "Handbook of combinatorics" vol. 1)

Has this problem been solved since?


texts: VC dimension for ellipsoidal classifiers

texts:
What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as

$$ g( x, (P_1,p_2,p_3),  ) := \text{sgn} \left( x^\top P_1 x + p_2^\top x + p_3 \right) $$

(where $P_1$ is positive definite)?

Do you think that $(n^2 + 3n)/2$ from [http://arxiv.org/pdf/1109.4347.pdf] is correct?

In the book [Auger, Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments], on pag. 342, I found that $(n^2 + 3n)/2$ is an upper bound.


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

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

The rules:

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

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


texts: Partition refinement in transition state systems (bisimulation contraction)

texts:
I am trying to understand bisimulation contraction of Kripke models.

I have read these lecture slides and this Wikipedia page, but I still don't fully understand it.

I can understand that the two models below are bisimilar

In the lecture slides, the partition refinement algorithm is given as

I do understand that from the graph on the left in the first picture, the initial partition becomes

initial_partition = {
  'p': ['n1', 'n2'],
  'q': ['n3', 'n4']
}

because two of the nodes have $p$ and the two remaining nodes have $q$.

But now I need to understand the second step in the algorithm. It seems to me that I should first loop through each of the two blocks in the initial partition, and for each node check its relations to nodes in the other blocks in the initial partition.

Can someone give me an example of a larger model (more nodes), and show me the steps in reducing the larger model to a smaller model, or give me a hint on where to find literature about it where it is described more easy?

Edit

What I mean is that the model in the middle of this picture

shows the first partition, but I don't know what the next partition look like, and why I can suddenly remove two of the nodes.


texts:
[Edit 21 July 2011: I edited the question to ask for more examples]

This question is asking for documented discussion of or more examples of a heuristic observation.

Some mathematical problems that admit efficient algorithms appear to be convex in nature. I'm thinking of linear and semi-definite programs and various combinatorial problems that reduce to these.

First, are there other families of problems that admit efficient algorithms for the convex/conjunctive case? (I would be particularly grateful for examples of  decision procedures for logical theories) Second, I would appreciate pointers to articles or sections of articles that discuss an opinion such as "lurking under a lot of efficient algorithms is a convex structure."

[Edit, 21 July 2011: Added the following.]

I would like to add some clarifications. I'm sorry I didn't include them earlier. I am interested in logical decision problems. It appears to me that efficient decision procedures exist for the conjunctive fragment of several logical problems. Here are two examples.

Efficient solvers for quantifier-free first order theories (such as SMT solvers for equality, equality with uninterpreted functions, difference arithmetic, etc.) typically have an efficient solver for the conjunctive fragment and use various techniques to cope with disjunction and negation. In static analysis of programs, the commonly used (and efficient) abstractions are based on integer intervals, affine equalities, octagons or polyhedra. In predicate-based abstraction and program verification, there is something called the Cartesian abstraction, which is intuitively about having conjunctions of predicates rather than arbitrary Boolean combinations. All these cases appear to me to be about gaining efficiency by exploiting the conjunctive fragment of the problem.

The conjunctive fragment of the first order theory of linear, real arithmetic can express convex polyhedra. This is why I originally asked about convex programming.

I am interested to know of other problems or examples where efficient solutions (in the theoretical or practical sense) are based on a convex or conjunctive sub-problem. If there is another general condition (Suresh mentioned sub-modularity) please mention it and problems whose solutions exploit that condition.


texts:
If we want to pick a solution $S$ from a collection of items $C$ to maximize some function $f(S)$.

The constraint that we pick at most $k$ item, i.e., $|S| \leq k$, is called  the cardinality constraint.

If the items in $C$ belongs to different groups and we are allowed to picked at most $k_i$ items from group $i$, what is the right terminology for this constraint? I think some paper used to call it the group cardinality constraint but I'm not sure if it's still the popular terminology.


texts: Grid $k$-coloring without monochromatic rectangles

texts:
Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.

Anyone feel up to trying 5-colorings? ;)

The following question arises out of Ramsey Theory.

Consider a $k$-coloring of the $n$-by-$m$ grid graph. A monochromatic rectangle exists whenever four cells with the same color are arranged as the corners of some rectangle. For example, $(0,0), (0,1), (1,1),$ and $(1,0)$ form a monochromatic rectangle if they have the same color. Similarly, $(2,2), (2,6), (3,6),$ and $(3,2)$ form a monochromatic rectangle, if colored with the same color.

Question: Does there exist a $4$-coloring of the $17$-by-$17$ grid graph that does not contain a monochromatic rectangle? If so, provide the explicit coloring.

Some known facts:

$16$-by-$17$ is $4$-colorable without a monochromatic rectangle, but the known coloring scheme does not appear to extend to the $17$-by-$17$ case. (I'm omitting the known $16$-by-$17$ coloring because it would very likely be a red herring for deciding $17$-by-$17$.)
$18$-by-$19$ is NOT $4$-colorable without a monochromatic rectangle.
$17$-by-$18$ and $18$-by-$18$ are also unknown cases; an answer to these would be interesting as well.

Disclaimer: Bill Gasarch has a $289 (USD) bounty on a positive answer to this question; you can reach him through his blog. A note on etiquette: I'll make sure he knows the source of any correct answer (should one arise).

He brought it up again during a rump session at Barriers II, and I find it interesting, so I'm forwarding the question here (without his knowledge; though I highly doubt he would mind).


texts: How do you encode Lamping's abstract algorithm using interaction combinators?

texts:
Interaction combinators have been proposed as a compile target for the λ-calculus before. That paper implements the full λ-calculus. It is also known that it is possible to optimize interaction-net encodings of the λ-calculus for the subset of λ-terms that is EAL-typeable. That paper implements that subset of the λ-calculus by translating EAL-typeable λ-terms to interaction nets that are arguably more complex than interaction combinators, since they use an infinite alphabet of labels to group duplicators.

I wonder if it is possible to combine both proposals. That is, is there any encoding for the abstract algorithm - that is, λ-terms that are EAL-typeable - as interaction combinators?


texts: (How) can you model broadcasts in the pi-calculus?

texts:
Can you model reliable broadcasts in the pi-calculus?

If so: How?

If not: Are there any similar process algebras where you can?

What I have tried:

If sender $S$ wants to send a message $y$ to all $P_1$ to $P_n$, you could write
!($\overline{x}y).S$ and $x(z).P_1$ to $x(z).P_n$. But how do you guarantee that $(\overline{x}y)$ is replicated $n$ times, i.e. no messages get lost?
I do not know $n$ in advance. Is it (only) possible with sending several messages back and forth between all processes involved?

...or do I misunderstand the nondeterministic behavior of replication?


texts: Probabilistic and quantum analog of $FP$ and $FNP$?

texts: Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?


texts: Linear diophantine equation in non-negative integers

texts:
There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2, ... , x_n$ to the equation $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$, where all the constants are positive? The only noteworthy mention of this problem that I know of is in Schrijver's Theory of Linear and Integer Programming. And even then, it's a rather terse discussion.

So I would greatly appreciate any information or reference you could provide on this problem.

There are two questions I mostly care about:

Is it strongly NP-Complete?
Is the related problem of counting the number of solutions #P-hard, or even #P-complete?


texts: Is the collapse of $PH$ known to extend downward to classes in-between its levels?

texts:
Contained in-between each level of the polynomial hierarchy are various complexity classes, including $\Delta_i^{\text{P}}$, $\text{DP}$, $\text{BH}_k$, and $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$. For lack of better terminology, I will refer to these and any others as intermediate classes between levels $i$ and $i+1$ in the polynomial hierarchy. For the purposes of this question, assume they are the classes contained in $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$ but contain $\Sigma_i^\text{P}$ and/or $\Pi_i^\text{P}$. We want to avoid including $\Sigma_{i+1}^\text{P} \cap \Pi_{i+1}^\text{P}$, if possible, as it is trivially equivalent to $\text{PH}$ if it collapses to the ${i+1}^{th}$ level.

In addition, define the following:
$\text{DP}_i = \left \{ L \cap L' : L \in \Sigma_i^\text{P} \text{ and } L' \in \Pi_i^{\text{P}} \right \}$

The above is a generalization of the class $\text{DP}$ (also written $\text{D}^\text{P}$). In this definition, $\text{DP}$ is equivalent to $\text{DP}_1$. It is considered in another cstheory.se question. It is easy to see that $\text{DP}_i \subseteq \Delta_{i+1}^{\text{P}}$ and contains both $\Sigma_i^\text{P}$ and $\Pi_i^\text{P}$.

Reference Diagram:

Question:
Suppose that the polynomial hierachy collapses to the ${i+1}^{th}$ level, but does not collapse to the $i^{th}$ level.  That is, $\Sigma_{i+1}^\text{P}=\Pi_{i+1}^\text{P}$ and $\Sigma_{i}^\text{P}\neq\Pi_{i}^\text{P}$.

Can we say anything more about the relationships between these intermediate classes themselves and others in any level below $i+1$? Is there a schema for a collection of complexity classes where, for every collection, the classes are equivalent if and only if the $\text{PH}$ collapses exactly to an arbitrarily chosen level?

Just as a followup, suppose that the hierarchy collapsed to any particular one of these intermediate classes (such as $\Delta_{i+1}^{\text{P}}$). Depending on the class selected, do we know if this collapse must continue to extend downwards, perhaps even to the $i^{th}$ level?

The above question was partially explored and answered in a paper by Hemaspaandra et. al:
A Downward Collapse within the Polynomial Hierarchy
Does someone happen to know of additional examples not mentioned in this paper or have further intuition as to what needs to happen in order for a class to accomplish this?


texts:
In the "last paragraph" of the "first page" of the following paper:

Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical Computer Science, 1995.

I encountered a somewhat counter-intuitive claim:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

I think the identity above is deduced from the following:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

and

$(\Pi^P_2)^{NP} = \Pi^P_3$

The former is more simply written as $(NP^{NP})^{NP} = NP^{NP^{NP}}$, which is quite odd!

Edit: In light of Kristoffer's comment below, I'd like to add the following inspiring remark from Goldreich's complexity book (pp. 118-119):

  It should be clear that the class $C_1^{C_2}$ can be defined for two complexity classes $C_1$ and $C_2$, provided that $C_1$ is associated with a class of standard machines that generalizes naturally to a class of oracle machines. Actually, the class $C_1^{C_2}$ is not defined based on the class $C_1$ but rather by analogy to it. Specifically, suppose that $C_1$ is the class of sets that are recognizable (or rather accepted) by machines of a certain type (e.g., deterministic or non-deterministic) with certain resource bounds (e.g., time and/or space bounds). Then, we consider analogous oracle machines (i.e., of the same type and with the same resource bounds), and say that $S \in C_1^{C_2}$ if there exists an adequate oracle machine $M_1$ (i.e., of this type and resource bounds) and a set $S_2 \in C_2$ such that $M_1^{S_2}$ accepts the set $S$.


texts: Translating typed functional language to untyped lambda calculus

texts:
Defining a typed function in haskell,

double::Integer->Integer
double a = a + a

And we can get an untyped version of double and let's call it double' to distinguish from the typed one.
Then, we can't prevent someone from passing a non-integer value to double' and luckily retrieving a meaningless(?) value, or being stuck in infinite loop. However, we can denote a constraint that 'if a is an integer, double' a is also an integer'.

Using Church encoding, it would be 'if the normal form of a is λf.λx.f(f...f(x)), then the one of double' a is also λf.λx.f(f...f(x))'. I agree that this is not strict enough, and that's the point my questions begin.

Is there any strict and general way to describe that kind of constraints?
If so, how powerful is it compared to type systems?

I'm sorry that my question is so ambigious. But I think that there could have been some similar approaches, and only links to them would be very helpful.


texts:
How is DHT different than regular hash tables in context to data/node lookup?

This (introduction, 3rd paragraph) paper says:

  First, in addition to the insertion
  and deletion of items, DHTs must support the insertion and deletion of
  buckets: as machines join and leave
  the network, items must be migrated to
  other machines and the hash function
  revised to reflect their new location.

This problem is also in Hashtables (for example, if you implement a hashtable in C using LinkedList and Array, then if the size of the array increased (new node added) then the data needs to be redistributed to achieve good load factor)

  Second, some kind of routing protocol
  is usually necessary: since it is not
  feasible in a P2P system for every
  node to maintain up-to-date knowledge
  of all other nodes in the system, an
  item is looked up (or inserted) by
  following a sequence of routing hops
  through the peer-to-peer network.

Is this point talking about routing mechanism, if yes, then is this done is normal hashtable?


texts: Can generalized twenty questions be solved by a greedy algorithm?

texts:
The game of twenty questions can be generalized in the following way.

Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ is chosen unknown to the player, who then has the ability to iteratively choose a set $Q\in\mathcal Q$ and be told whether or not $x\in Q$. The player's goal is to determine $x$.
In order for the game to be solvable, $\mathcal Q$ is assumed to have the property that every $x\in\Omega$ can be realized as the intersection of some collection of elements of $\mathcal Q$ or their complements.

What we want is a strategy to solve this game with optimal worst-case running time.
At any point in the game, we can assign to each question a pair of integers - the number of possibilities that will remain depending on whether the answer is yes or no. Assign to each question a score which is the larger of these two integers, and always pick the question with minimal score. This is the "greedy" strategy.
Does the greedy strategy always have optimal worst-case running time?


texts: Courcelle's theorem for bounded clique-width graphs

texts:
Courcelle's theorem states that  "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded clique-width graphs [CMR99].

The theorem also holds with linear time replaced by logarithmic space [EJT10] for bounded tree-width graphs.
My question is: Does this theorem still hold for bounded clique-width graphs if we replace linear time with logarithmic space? Let me know of the recent progress in this direction.


texts: Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

texts:
I heard of a result in approximate graph coloring, but cannot find the source. The result is:

For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph with $hk$ colors is NP-hard.

Could someone please point me to the relevant paper?


texts:
I asked this question in cross validated Q&A but seems that it is related to CS much more than Statistics.

Can you give me examples of machine learning algorithms which learn from the statistical properties of the dataset not the individual observations themselves i.e. employ the statistical query model?


texts: What does one mean by heuristic statistical physics arguments?

texts:
I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a simple toy example of such a phenomenon?

It would be good if the answer assumed little background in statistical physics and could explain what these mysterious heuristics are and how they can be informally justified.  Also, perhaps someone can indicate the broad picture of how much of these heuristics can be rigorously justified and how the program of Lawler, Schramm and Werner fits into this.