texts: Should the Schedule of ``High-level Operations'' Respect the Linearizability of ``Low-level Operations'' in Proof of Simulation Algorithm?

texts:
Backgroud

I am reading Chapter 10 ``Fault-Tolerant Simulations of Read/Write Objects'' of the Book Distributed Computing (by Hagit Attiya & Jennifer Welch). Specifically, in section 10.2.3, it simulates a multi-writer multi-reader read/write register from single-writer multi-reader registers.

Simulation Algorithm

  The idea of the algorithm is to have each writer announce each value it desires to write to all the readers, by writing it in its own (single-writer multi-reader) registers; each reader reads all the values written by the writers and picks the most recent one among them.

The algorithm uses vector clock to compare the values written by the writers and find the most recent one among them. The pseudocode appears in Figure , where

  $TS[i]:$ The vector timestamp of writer $p_i$, $0 \le i \le m - 1$. It is written by $p_i$ and read by all writers.
  $Val[i]:$ The latest value written by writer $p_i$, $0 \le i \le m - 1$, together with the vector timestamp associated with that value. It is written by $p_i$ and read by all readers.

Correctness Proof

There are two types of operations in the algorithm:

high-level operation: operation on simulated object $R$ (i.e., $read_r(R)$ and $write_w(R,v)$ in the pseudocode).
low-level operation: operation on $TS[i]$ and $Val[i]$.

  To prove that the simulation is correct we have to show that every admissible execution is linearizable. Consider any admissible execution $\alpha$. To show that $\alpha$ is linearizable, we have to show that there is a permutation $\pi$ of the high-level operations in $\alpha$ that preserves the order of non-overlapping operations, and in which every read operation returns the value of the latest preceding write.

My Problem

As the last paragraph indicated, we consider the schedule of high-level operations. So my problem is:

  Should the schedule of high-level operations also respect the linearizability of low-level operations?

To illustrate, consider the following admissible (according to the simulation algorithm) execution:

  Assume $TS[i][i] = 0, \forall 0 \le i \le m - 1$ initially. $m$ writers write concurrently. They all first execute Line 10 - Line 11 in procedure $NewCTS_w()$ and thus obtain $TS[i][i] = 0, \forall 0 \le i \le m - 1$. Then, they execute Line 12 in some order (for example, in the order of pid). In this scenario, when all writers finish, the system state can be stated as
  $$S = \left\{ \begin{array}{ll}
\langle 1, 0 , 0, \ldots, 0 \rangle \\
\langle 0, 1 , 0, \ldots, 0 \rangle \\
\langle 0, 0 , 1, \ldots, 0 \rangle \\
\langle 0, 0 , 0, \ldots, 1 \rangle
\end{array} \right.$$

In the linearizability proof, the $m$ high-level writes will be put in an order, for example, according to their pids. However, if we consider the low-level operations in such order, the second writer cannot obtain $\langle 0, 1, 0, \ldots, 0 \rangle$. Instead, it should obtain $\langle 1, 1, 0, \ldots, 0 \rangle$, because it is put after the first writer's high-level write operation.

  Problem: I am confused about the situation. What is wrong of my argument? Should the schedule respect the linearizability of low-level operations in simulation algorithm? Or, what does it mean to respect it?


texts: Interesting functions on graphs that can be efficiently maximized.

texts:
Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed.

Say that $f:2^V\rightarrow \mathbb{R}$ defines a property of any subset of the vertices $S \subset V$.

  Question: What are some interesting examples of
  $f$s for which the maximization
  problem: $\arg\max_{S \subseteq
  V}f(S)$ can be performed in polynomial
  time?

For example, the graph cut function
$$f(S) = \sum_{(u,v) \in E : u \in S, v \not\in S}w((u,v))$$
 is an interesting property of subsets of vertices, but cannot be efficiently maximized. The edge density function is another example of an interesting property that alas, cannot be efficiently maximized. I'm looking for functions that are equally interesting, but can be efficiently maximized.

I'll let the definition of "interesting" be somewhat vague, but I want the maximization problem to be non-trivial. For example it should not be that you can determine the answer without examining the edges of the graph (so constant functions, and the cardinality function are not interesting). It should also not be the case that $f$ is really just encoding some other function with a polynomially sized domain by padding it into the domain $2^V$ (i.e. I don't want there to be some small domain $X$, and some function $m:2^S\rightarrow X$ known before looking at the graph, such that the function of interest is really $g:X\rightarrow \mathbb{R}$, and $f(S) = g(m(S))$ If this is the case, then the "maximization" problem is really just a question of evaluating the function on all inputs.)

Edit: Its true that sometimes minimization problems are easy if you ignore the edge weights (although not minimizing the cut function, since I allow negative edge weights). But I'm explicitly interested in maximization problems. It does not become an issue in natural weighted problems in this setting though.


texts:
Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.

Has any further progress on this problem been made since then?


texts: Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies

texts:
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the Boolean hierarchy $\textsf{BH} = \bigcup_k \textsf{BH}_2(k)$, just below $\Delta_2^P$. So we have $\Theta_2^{\textsf{P}} = \textsf{P}^{\parallel\textsf{NP}} = \textsf{P}^{\textsf{NP}[\log]} = \textsf{BH}$.
I've seen in an answer to this question (and in the cited papers) that Boolean Hierarchies have been defined over $\Sigma_2^{\textsf{P}}$ instead of $\textsf{NP}$. So now I am wondering if we have the same relationships higher up as well. Is the following equality known?
$P^{\parallel\Sigma_i^{\textsf{P}}} = P^{\Sigma_i^{\textsf{P}}[\log]} = \textsf{BH}_{i+1}$
Where I used the following notation:

$\textsf{BH}_i = \bigcup_k \textsf{BH}_{i}(k)$ where $\textsf{BH}_{i+1}(1) = \Sigma_i^{\textsf{P}}$ and $\textsf{BH}_{i+1}(k+1) =\{L_1 - L_2 \mid L_1 \in \Sigma_i^{\textsf{P}} \text{ and } L_2 \in \textsf{BH}_{i+1}(k)\}$.
$P^{\Sigma_i^{\textsf{P}}[\log]}$ to be the class of problems that can be solved in polynomial time by a deterministic Turing machine making no more than logarithmic oracle queries to a $\Sigma_i^{\textsf{P}}$ solver.
$\textsf{P}^{\parallel\Sigma_i^{\textsf{P}}}$ is the class of problems that can be solved in $\textsf{P}$ with parallel (non-adaptive) queries to $\Sigma_i^{\textsf{P}}$.

Where can I find a definition of the notation $\Theta_i^{\textsf{P}}$ for $i \geq 3$?


texts: Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$

texts:
I'm reading a paper which shows the result:

$(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$
$(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$.

Both $(1)$ and $(2)$ are unproven Conjectures.

A proof system for a problem $Q \subseteq \Sigma^*$ is a surjective function $P: \Sigma^* \to Q$ computable in polynomial time (see my other question). A proof system is $p$-optimal if for every proof system $P'$ for Q there is polynomial computable $T: \Sigma^* \to \Sigma^*$ such that f.a. $w \in \Sigma^*$

$$P(T(w)) = P'(w).$$

My first question is an intuition of the  $p$-optimal property: Does it mean that $P$ is minimal in a way? How does that work? Is it similar to the polynomial reduction one uses to show that a problem is $\operatorname{NP}$-hard?

A Logic $L$ is $P$-bounded for $P$ if there is a algorithm which decides the model relation $\mathcal{A} \models_{L} \varphi$ polynomial in $|\mathbb{A}|$. $L_{\leq}$ is variant of least fixed point logic (LFP). A formula $\varphi$ is $m$-invariant if for all structures $\mathcal{A}$ of size at most $m$ we have for all orderings $<_1, <_2$

$$(\mathcal{A},<_1) \models_{LFP} \varphi \Leftrightarrow (\mathcal{A},<_2) \models_{LFP} \varphi.$$ A formula in $L_{\leq}$ is satisfied on a structure $\mathcal{A}$ if it is at least $|\mathcal{A}|$-invariant and $(\mathcal{A},<) \models_{LFP} \varphi$ for one $<$.

I am interested in the consequences if $(1)$ was true (or even consequences if it was false?). $\operatorname{TAUT}$ is in $\mathrm{co}-\mathrm{NP}$ and $\operatorname{SAT}$ is in $\mathrm{NP}$. Is $(1) \Rightarrow \operatorname{NP} =
co-\operatorname{NP}$ and why? Is okay to "mildly assume" that $\operatorname{NP} = co-\operatorname{NP}$ is not true?


texts: Showing that interval-sum queries on a binary array can not be done using linear space and constant time

texts:
You are given a $n$-sized binary array.

I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):

1) Pre-process the input array using unlimited time, but only using $O(n)$ bits.

2) Answer queries in constant time, where query $(x,y)$ asks for the number of set bits between index $x$ and index $y$ in the array.

It seems that constant time per query should not allow the algorithm to read enough information to compute the number of set bits.

  How can we prove that no such algorithm exists?

A more general question would be,

  given that the algorithm is allowed to use $f(n)$ space, what lower bound on the query time can we derive?

Obviously, if we have $f=\Omega(n\log n)$ space we can store the all partial sums and answer queries in $O(1)$, but what if $f$ is smaller?

You may assume that the size of a memory word is $\Theta(\log n)$ and we can read the $x,y$ indices in constant time.


texts: Complexity class that captures linear or nearly-linear functions

texts:
A particular model I am working with can only compute a function $f: \{0,1\}^n \rightarrow \{0,1\}$ iff $f(x_1,...,x_n)$ is a linear combination (over $\text{GF}(2)$) of the $x_i$'s or has at most a constant amount of non-linearity. What is the complexity class that most closely corresponds to my model?
Non-linearity
I am not sure if there is a standard definition so let $S,T \subseteq \{1,...,n\}$, and $x_S$ (or, $x_T$) mean the bitstring from only the bits of $x$ whose index is in $S$ (or, $T$). Then we can define a function as $k$-near linear as follows:

$f$ is $0$-near linear if it is linear.
$f$ is $k$-near linear if:

$f(x) = g(x_S) \oplus h(x_T)$  and $g$ is $i$-near linear and $h$ is $j$-linear and $i + j = k$.
$f(x)  = g(x_S) \wedge h(x_T)$ or $f(x)  = g(x_S) \vee h(x_T)$ and $g$ is $i$-near linear and $h$ is $j$-near linear and $i + j = k - 1$.

for some $S$, $T$, $g$, and $h$.

If a function is $k$-linear on any input size (where $k$ is a constant) then I say the function has a constant amount of non-linearity. If this is not a standard definition, could you point me in the comments to a standard definition? Is my definition obviously equivalent to some other standard definition?
Question

What is the complexity class associated with functions that are $k$-near linear? And how does it compare to other popular complexity classes?

I can obviously simulate $\mathsf{NC}_0$. However, I can also compute parity, and can't compute the $\text{OR}$ function on $n$ bits, and so the complexity class is incomparable to $AC_0$. I have also heard of width-$2$ OBDDs as 'the next step' after linear, however the characterizations of approximating width-$2$ OBDDs I have seen allow for a logarithmic amount of non-linearity (as far as I can tell).


texts: Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses

texts:
The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of binary classification with the 0-1 loss.
Does a result of this form hold in more general settings? For example: margin-based classification rules, regression, multi-class classification, ...?
Another statement of this question could be: under what circumstances does uniform convergence of the empirical risk imply PAC learning? (I am most interested in this direction of implication.)
Please provide references if you have them.


texts: What is the status of fuzzy logic for TCS in 2011?

texts:
I am reviewing the Handbook of Nature-Inspired and Innovative Computing for SIGACT News.  It's a very interesting read.  Each chapter, though, has the flavor, "This is my research area, and damn it's awesome!"  So part of what I am trying to do is to separate out the hype, and make a sober assessment of the book's contents.

One chapter is on fuzzy logic and fuzzy systems, and how frikkin awesome they are.  And maybe they are, I frankly don't know.  The intuitive sense I've gotten from hanging around computer scientists is that fuzzy logic and fuzzy modeling of control systems, etc., are "dead."  I don't know if that's true, though -- and, even if it is true, I don't know if it's true for a "good reason."

Would anyone like to weigh in here?  What's the current status of research into fuzzy systems?  Does fuzzification see real-world applications?  Did it used to and people moved away because of problems?  Or do people "in the trenches" use it all the time, and it's just that theorists have moved away from it?  Or... something else?  (I have no idea what is true.)

I will probably cite answers to this question in the book review, unless an answerer specifically asks me not to.

Thanks.


texts: Isomorphism notion between sets of triples

texts:
Graph Isomorphism is natural problem which is most widely believed to have intermediate complexity between $P$ and $NP$-complete. GI can be thought as deciding the existence of an isomorphism between two sets of node pairs. I'm trying to develop a notion of isomorphism between sets of triples.

We are given two hyper-graphs $G1$ and $G2$ such that the set of hyperedges ($E_1$ and $E_2$) consists of  triples of 3 nodes $\{t_1, t_2, t_3 \}$. We say that Hyper-graphs $G1$ and $G2$ are isomorphic if there is bijection $f$ from $V_1$ to $V_2$ such that pair $\{u,v\} \in E1 $ if and only if $\{f(u),f(v) \} \in E2 $. We say $\{u, v \} \in E $ if there is a triple (hyperedge) $\{ u, v, z\} \in E$ for some node $z$.

Is it $NP$-complete to decide the existence of such isomorphism between two hyper-graphs $G1$ and $G2$?


texts: The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n2-eps, for some constant eps>0? I would be interested in such a result even for the special case where the input DFAs are acyclic.


texts: One-Way Functions vs. perfectly binding commitments

texts:
If OWFs exist, then statistically binding bit commitment is possible.[1]

Is it known that if OWFs exist then perfectly binding bit commitment is possible?

If no, is there a known black-box separation between them?

[1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem and

http://en.wikipedia.org/wiki/Commitment_scheme#Bit-commitment_from_a_pseudo-random_generator


texts: A property of suffix-free regular languages of maximal state complexity for the reverse operation

texts:
Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and  that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of the minimal automaton of $L$ which are neither the initial state nor a sink state, then there exists a word $w \in X^*$ such that $\delta(q, w) = \delta(p, w)$ in the minimal automaton for $L$.

That such languages exist is shown in this paper. The above reasoning is used in a paper without any further explanation, and I do not see that it is true. If we denote by $Q = \{0,\ldots, n-1\}$ the states of the minimal automaton of $L$ and by $F$ its final states, where $0$ is the start state and $n-1$ the sink state (which a suffix-free language always has) then it just precedes with constructing a NFA for $L^R$, determinizing by the subset construction and showing that it must contain the $2^{n-2}+1$ sets $\{ \{ 0 \} \}\cup \{ S \subseteq \{1,\ldots, n-2\}\}$ as states. Hence for $p,q \in \{1,\ldots, n-2\}$ we have some $p,q \in S$ such that $\delta_R(F, w) = S$ in the constructed automaton for $L^R$, and then it concludes that $\delta(p, w^R) = r = \delta(q, w^R)$ for some state $r$.


texts: Largest rectangle not touching any rock in a square field

texts:
Following this mathematical question, I am interested in the algorithmic question:

  Given $n$ points in the unit square,
  find the largest area of an axis-parallel rectangle in the unit square
  that does not contain any of the given points in its interior.

What is known about this problem?


texts: D. Knuth definition of a computational method

texts:
I am new to the site and I hope after reading the guide lines i am in line with them.
I am reading The Art of Computer Programming by Donald E. Knuth. The question is addressed to those having a copy of Volume 1. At pages 27-28, Knuth formally defines a computational method to be a quadruple (Q, I, $\omega$, f). I am interested in the first computational method.

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

3/ How are the values of f deduced from the algorithm?

P.S. In case my question is vague please mention in comments where i need to make things clear.
And I am more after understanding the theory than any algorithm usefulness, hope that will be useful.


texts: What's the expressive/compressive power of strongly normalizing subset of untyped lambda calculus?

texts:
Let $\Lambda$ be a set of strongly normalizing lambda terms.
Let $\mathtt{NF} : \Lambda \rightarrow \Lambda$ be evaluation to the normal form.
Let $ \lvert x\rvert : \Lambda \rightarrow \mathbb{N}$ be
size of a term in number of symbols.
The following function seems to be well defined:

$$f_\Lambda:\mathbb{N} \rightarrow \mathbb{N}$$
$$ f_\Lambda(n) = \max_{t \in \Lambda, \lvert t \rvert \leq n} \lvert\mathtt{NF}(t)\rvert $$

What is the rate of growth of $f_\Lambda$?

Can we define some lower and upper bound in fast growing hierarchy?


texts: Is the half-filled magic square problem NP-complete?

texts:
Here is the problem:

We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square.

Examples:

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _
9 _ _  >>>  NO SOLUTION
8 _ _

Is this problem NP-complete? If yes, how can I prove it?

Crosspost on MS


texts: How do you get the Calculus of Constructions from the other points in the Lambda Cube?

texts:
The CoC is said to be the culmination of all three dimensions of the Lambda Cube. This isn't apparent to me at all. I think I understand the individual dimensions, and the combination of any two seems to result in a relatively straightforward union (maybe I'm missing something?). But when I look at the CoC, instead of looking like a combination of all three, it looks like a completely different thing. Which dimension do Type, Prop, and small/large types come from? Where did dependent products disappear to? And why is there a focus on propositions and proofs instead of types and programs? Is there something equivalent that does focus on types and programs?

Edit: In case it isn't clear, I'm asking for an explanation of how the CoC is equivalent to the straightforward union of the Lambda Cube dimensions. And is there an actual union of all three out there somewhere I can study (that is in terms of programs and types, not proofs and propositions)? This is in response to comments on the question, not to any current answers.


texts: Constaint Satisfaction problem with exponentially many solutions

texts: Say we have a constraint satisfaction problem parametrized by $n$ number of variables whose solution lies in a set of bounded non-negative integers of size $O(2^{n})$. Say we also know that we have $O(2^{an})$ satisfying solutions for the $n$ number of variables for some $a \in (0,1)$. Are there any known cases where such problems can be solved in polynomial in $n$ time?


texts: To what extent is "advanced mathematics" needed/useful in A.I. research?

texts:
I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in artificial intelligence. However, I am not sure how many mathematics courses I should follow. (And which CS theory courses I should follow.)

From Quora, I learned that the subjects Linear Algebra, Statistics and Convex Optimization are most relevant for Machine Learning (see this question). Someone else mentioned that learning Linear Algebra, Probability/Statistics, Calculus, Basic Algorithms and Logic are needed to study artificial intelligence (see  this  question).

I can learn about all of these subjects during my first 1.5 years of the mathematics Bachelor at our university.

I was wondering, though, if there are some upper-undergraduate of even graduate-level mathematics subjects that are useful or even needed to study artificial intelligence. What about ODEs, PDEs, Topology, Measure Theory, Linear Analysis, Fourier Analysis and Analysis on Manifolds?

One book that suggests that some quite advanced mathematics is useful in the study of artificial intelligence is Pattern Theory: The Stochastic Analysis of Real-World signals by David Mumford and Agnes Desolneux (see this page). It includes chapters on Markov Chains, Piecewise Gaussian Models, Gibbs Fields, Manifolds, Lie Groups and Lie Algebras and their applications to pattern theory. To what extend is this book useful in A.I. research?


texts: Complexity class for some group and graph homomorphism problems

texts:
Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs?

$$\mathsf{Is }|Hom(G_1,G_2)|>0$$

Given two graphs $H_1$ and $H_2$ what is the complexity class in which the following problem belongs (Answered by Ricky Demer in comment)?

$$\mathsf{Is }|Hom(H_1,H_2)|>0$$


texts: What is the complexity of this edge coloring problem?

texts:
Recently, I have encountered the following variant of edge coloring.

  Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.

My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!


texts:
Problem :

We are given a stick partitioned into n - equal parts. Each of these parts has a weight, let's say x. Number of times x appears as weight of some part is guaranteed to be even.

For example consider the following stick with 6 parts -

1 2 2 1 3 3

So the stick has n parts, with weight of first part being 1, of second being 2, and likewise. Note that each weight appears even number of times.

Now, we need to cut the stick across these n partitions, and divide the parts into two users, and those two should have same weight in the end.

We divide the parts as follows -

Let's say I made first cut at y1, then from starting till y1 - this part goes to user1. Now, we make another cut at y2. Then from y1 to y2 goes to user 2. And so on alternatively.

So we need to find the minimum number of cuts in which we can do this fair division.

I couldn't find a polynomial time algorithm. And, problem appears to be NP - Hard. So, any good approximation algorithm for this problem ?


texts:
I am a PhD student in Theoretical Computer Science I am finishing PhD this year and now I want to apply for post-doc positions. I want to know if there exists a source where can I read about how to apply for post-doc.

Here is the partial list of questions I am interested in:

1) What scholarships exists in my area?

2) What Universities have open post-doc positions? Beside Princeton/IAS I did not found organized information in other universities.

3) How can I chose the right people to ask recommendation letters from?

4) Assume that someone wants that I will come to his university to do a post-doc and this will require some effort to hire me(need to find money ...), but my first preference is other university which I still do not know if will want to hire me. What should I do in this case.

5) Any other advises and suggestions about what I should know about application for post-doc.


texts: Characterisation of P in terms of register machines

texts:
It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.

It is relatively straightforward to prove that indirect addressing and binary shift (or, equivalently, division by two) are actually redundant when working in polynomial time, i.e., that polynomial-time Turing machines are equivalent to polynomial-time Minsky-like register machines with a constant number of registers, augmented with constant-time addition and subtraction instruction (rather than just increment and decrement).

This can be showed by encoding the sequence of symbols on the tape of the Turing machine as a single large integer stored in one of the registers; the individual symbols can be accessed by performing multiplications and divisions (implemented via repeated doubling).

(Incidentally, register machines without constant-time addition and subtraction are provably slower than Turing machines on certain problems.)

I have the feeling that this result must have been published a long time ago, but I seem unable to find it in the literature. Does anyone know a reference (possibly the first published one) for it?


texts: Why do we use single tape Turing machines for time complexity?

texts:
As you know there are many anomolies for the single tape Turing machines when the time is $o(n^2)$: multi-tape TM simulation, simulation of larger tape alphabet with just $\{0,1,b\}$, time constructability, non-tightness of time hierarchy theorem, ...

Also results like $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$, and very model specific $O(n^2)$ time lowerbounds for simple problems (that don't translate to even superlinear lowerbounds on two tape TMs).

For space complexity, we use a model where we have a separate read only input tape, which is more natural and robust.

A TM model with multiple tapes (or at least 2 working tapes) would be much more robust and will not lead to anomalies like those I listed above. I once asked a prominent complexity theorist who has proven simulation results in the early years of complexity theory if he knows any improvements on one of these old results and the reply was that he doesn't think that "questions about the one tape model are that important".

If we change the standard model for time complexity to a two tape TMs, reasonable results in complexity theory will not change and we avoid these anomalies caused by particular model. So my question is:

  is there any reason why the time complexity is still defined in terms of single tape TMs?
  (other than historical reasons)


texts: Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

texts: I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for vertex weighted graphs? I have only seen examples for weighted edges or edge connectivity problems that use this paradigm. The nearest i have seen is degree bounded networks that use this paradigm. Also, i would like to get some intuition that when is this method probably applicable (or what could be the underlying difficulty that it is not yet applied to vertex weighted scenarios).


texts: Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

texts:
If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time computable function, that maps instances of each $B_{i}$ to instances of $A$.

Once you find the first NP hard problem, by using reductions you can then find that many other problems are either NP Complete or NP Hard. However I imagine that this depends. If you are unlucky, then maybe all $B_{i}$ problems reduce to $A$, but $A$ reduces nowhere else, so your proof is essentially useless.

My question is about the motivation that Stephen Cook behind showing that the SAT problem is NP hard. Did he see a lot of potential behind this problem? Did he know that if he showed that this problem is NP hard then a lot of other problems could be shown to be NP hard as well?

In short, what is the story behind this proof? Because after studying some basic complexity theory, it really seems like this proof was one of the most significant ones in this area.


texts: Reductions between languages of different densities?

texts:
The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ many-one logspace reduces to $B$, and $B$ is not in $\textsf{L} = \text{DSPACE}(\log n)$.
Functions $f,g \colon\mathbb{N} \to \mathbb{N}$ are polynomially related if there are polynomials $p$ and $q$ such that for all $n\in \mathbb{N}$, $f(n) \le p(g(n))$ and $g(n) \le q(f(n))$.

  If the density of $A$ is not polynomially related to the density of $B$, can there be a logspace reduction from $B$ to $A$?

Background

I expect the answer is no, but can't currently show this.

Clearly, if $A$ is in $\mathsf{L}$ then there is no logspace reduction from $B$ to $A$.
So there are some examples for which it is possible to provide a definite negative answer.

I first had in mind the case where $B$ is some hard language, and $A$ is obtained by blowing holes in $B$ by taking $A = B\cap G$, for some gap language $G$ which contains all words of length $n \in S_G$ for some set $S_G \subseteq \mathbb{N}$ (see Schmidt 1985 and also Regan and Vollmer 1997).
This guarantees a trivial reduction from $A$ to $B$.
Gap languages $G$ usually have exponentially increasing gaps between the intervals of sizes in $S_G$.
This ensures that the densities of $A$ and $B$ are not polynomially related.
However, there is no guarantee that blowing holes in a language always gives rise to a language that has too little structure to be the target of a reduction from $B$.
(The term blowing holes is from Downey and Fortnow 2003.)
The difference in densities might be enough to guarantee this, but I don't immediately see how.

Another example is when $B$ is a mixture of a hard language and $A$.
First create a gappy language $A\not\in\mathsf{L}$ by intersecting some language $C \not\in \textsf{L}$ with a gap language $G$.
$A$ will then only contain instances of sizes that are in the intervals of the set of sizes $S_G$ determining the gap language.
Now create $B$ by mixing $A$ with some hard language $D$ in the gaps, by taking the union of $A$ and the intersection of $D$ with the complement of $G$.
If $D$ is hard enough compared to $C$, such as $D$ being $\textsf{2EXPSPACE}$-hard while $C \in \textsf{PSPACE} \setminus \textsf{L}$, then by the space hierarchy theorem there can be no logspace reduction from $D$ to $A$.
It then seems possible to extend this to show that there is no logspace reduction from $B$ to $A$.

This still leaves the situation where $D$ is harder than $C$ but "not too much", for instance take $D$ to be SAT and $C$ to be STCON, or $D$ to be QBF-SAT and $C$ to be SAT.
To get a result, one might have to assume $\mathsf{L} \ne \mathsf{NP}$ for STCON/SAT or $\mathsf{NP} \ne \mathsf{PSPACE}$ for SAT/QBF-SAT, but it is not immediately clear to me how to use these assumptions.


texts:
Given a set $S$, its multiplicative closure is the set
$$
\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}
$$
of products of zero or more elements of $S$. So the multiplicative closure of $\{2,3\}$ is the set of integers of the form $2^m3^n,$ for example.

I'm looking for an efficient algorithm to compute the number of elements of $\mathcal{M}(S)$ up to a given bound $x,$ given a finite set $S$ of positive integers. You may assume (it is true in my case, and simplifies the problem) that each element of $\mathcal{M}(S)$ has a unique factorization in $S$. In my case $S$ is small (150-250 elements) and $x$ is large ($10^{35}$ to $10^{50}$ or more).

A naive algorithm would construct all of the numbers and count them. This is slow, and more importantly consumes a lot of memory.

A better approach (dynamic programming) is to split the set roughly in half, let's say into $S_1$ and $S_2$, and construct the multiplicative closures of both. Then each element of $\mathcal{M}(S)$ is a product of an element of $\mathcal{M}(S_1)$ and an element of $\mathcal{M}(S_2)$, and by the special property no other product is equal to this value. So you can iterate through one of these, let's say $\mathcal{M}(S_1)$, and for each $m$ in that set the number of products which are at most $x$ is the number of elements in $\mathcal{M}(S_2)$ which are at most $x/m.$ This can be determined with a binary search.

Is there a way to push this method further? Is there a completely different approach which is more efficient? Is there literature I can read?


texts: About the sign-rank of the Minsky-Pappert function

texts:
Apologies this might be a very trivial thing I am getting confused by!

Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have given a new proof of the apparently well-known fact that the Minsky-Pappert DNF has an exponentially high sign-rank. They claim that this was previously also proven in this paper by Razborov and Sherstov, http://people.cs.uchicago.edu/~razborov/files/sign.pdf.

But in the Razborov-Sherstov paper I am unable to locate any such claim or proof.
What am I missing? Is this somehow implicit?

The high sign-rank function that Razborov-Shertov display is in their theorem $1.1$ called the "Main Result" on page $2$. This is a depth $3$ $AC^0$ function and not a depth $2$ one like Minsky-Pappert is.
Also on page $2$ a few lines below the statement of Theorem $1.1$ Razborov-Sherstov seem to say that depth $1$ and $2$ $AC^0$ function can only have polynomial sign-rank. This if I am reading correctly implies that the Minsky-Pappert function does not have an exponentially large sign-rank since it is depth $2$ $AC^0$. What is going on?
If true, could anyone kindly link to any reference which gives a pedagogic exposition of the proof that the Minsky-Pappert function has a high sign-rank?

The Razborov-Sherstov paper does use the Minsky-Pappert function as a tool in their final proof on page $16$ whereby they use its pattern matrix to create another matrix which is a submatrix of high sign-rank sitting inside the pattern matrix of their hard function from the "Main Result" quoted above. Its not clear to me if this is somehow implicitly also proving a high sign-rank for the Minsky-Pappert function itself. Is it?


texts: Does univ : univ always lead to a contradiction in a dependently typed language?

texts:
I am currently following Checking Dependent Types with Normalization by Evaluation: A Tutorial by David Christiansen, where we consider the type of U (the universe of types) to be U itself [this can be seen section 7.4.1 in the implementation of synth where we have ['U (go '(the U U))]: That is, the untyped expression U is elaborated into the expression U of type U. Effectively, we have taken that Univ : Univ.
This cannot happen in ZFC due to the axiom of foundation. I suspect type-inferring U as having type U is inconsistent. I do not know how to prove this; I would attempt to encode a Russell-style paradox if I were pressed to produce a proof.

Is it really true that U : U is inconsistent?
Is it possible to write a term that produces a proof of False assuming U : U? Or is the encoding to large to write down easily "by hand", but can be believed to be done?
If U : U is not inconsistent (i.e., is consistent), then a couple of words on why the dependently typed world allows for U : U while ZFC cannot allow U ∈ U would be appreciated.

I understand that talking about "dependently typed languages" is broad enough to be senseless. As a beginner, I find it hard to restrict to one theory, because I don't know the trade-offs between the theories. For the sake of the answer, please feel free to restrict to, say, MLTT, or CoC, or LF.


texts: 3D Bin Packing with one bin with infinite/unknown size

texts:
Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size.

I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$.
The dimensions of the items are $w_k, l_k, h_k$ with $k=1...n$.

I need to find the smallest cuboid $B$ that can contain all the items with no overlap and the positions $(x_k, y_k, z_k)$ with $k=1...n$ of the items in container for the optimal solution found.

I'm looking at the Martello et al. approach for the single bin filling.
What should I use in the branch backtrack condition since I don't know the volume $B$ of the bin?

The original condition is: $\sum_{i \in I}{v_i + (B-V(I)) \le F}$ where $I$ is the subset of items currently placed in the bin, $v_i$ is the volume of the item $i$, $V(I)$ is the volume occupied by the current set of items placed in the bin and $F$ is the current minimum found solution.

Any help is appreciated


texts: Relation beween approximate degree of a function and its Fourier coefficient.

texts:
Consider a Boolean function $f:\{0,1\}^n\to\{0,1\}$.
The degree of the function $d$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than $d$, i.e. $\forall S\subseteq [1,n], \hat{f}(S) = 0$ if $|S| > d$.
[edit:add] The approximate degree $\tilde{d}$ of a function $f$ is the lowest degree of a polynomial $p$ such that $\max_{x\in\{0,1\}^n} |f(x) - p(x)| \leq 1/3$.  [/edit:add]
I was wondering if there is an interpretation of the approximate degree along those kind of lines. I have the intuition (maybe plain wrong) the Fourier coefficient of a function lower that its approximate degree should be small, but I cannot find any claim to sustain this intuition.
The only result I am aware of, is a paper by Sherstov, in STOC'08 (corollary 3.3.1):

Let $f:\{0,1\}^n \to \mathbb{R}$ with approximate degree $\tilde{d}$. Then there is a function $\psi:\{0,1\}^n\to\mathbb{R}$ such that
• $\hat{\psi}(S) = 0$ if $|S|<\tilde{d}$
• $\sum_{x\in\{0,1\}^n}|\psi(x)| = 1$
• $\sum_{x\in\{0,1\}^n} \psi(x) f(x) > 1/3$

But the interpretation is very not clear to me since $\psi$ is bounded in the $\ell_1$ norm and not the $\ell_2$ norm as usually used in Fourier analysis. Also how can we have a constant overlap between $\psi$ and $f$ when $f$ is unbounded?


texts: Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

texts:
I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of outgoing edges in fixed order and that order must be respected by the isomorphism. I don't know if there is a widely used name for such structures.
An equivalent problem is probably isomorphism of acyclic deterministic semiautomata (the ordering of the edges can be recovered by just fixing an order on the alphabet and listing the transitions for a state in that order).
If the DAG is restricted to have only one root, it is trivial (just order by left-to-right DFS). Or, for the automaton, if the automaton has a designated initial state and all other states must be reachable. But if that's not the case, I'm at a loss.
I don't see any obvious polynomial reductions from GI-complete problems that I am familiar with. My intuition tells me this looks like it should be in P.
The best algorithm I came up with so far tries to successively label the nodes with numbers from 1 to n in a canonical way by picking the ‘smallest’ root w.r.t. some suitable partial ordering (e.g. based on the number of children and the ordering numbers that have already been assigned), but when there are still several minimal roots, I don't see how to get around trying all permutations of them.
There is a paper on isomorphism of ‘ordered graphs’ that seems to be similar to my problem except that their graphs are undirected and their ‘ordering’ is not a list, but a cyclic list. My intuition would tell me that my problem can be reduced to this (e.g. by adding some conspicuous ‘list beginning marker’ to recover the list from the cyclic list) but I am not quite sure. I am also not sure if there is not something more direct than their approach for my case.
EDIT: I thought about it a bit more and I think their approach doesn't work for my case at all. In my setting, there is an ordering on the outgoing edges of each node, but not on the ingoing ones. That makes a huge difference.
For illustration, here are two instances of the problem:


texts: Hitting edges in graphs at random and let them die with honor

texts:
Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit the edge $e$ and we let it die (sorry about that).
At the end of the process, we consider the set of survived edges $S$ and we look at the graph $G[S]$ consisting of survived edges only. Let $C_1, \ldots, C_n$ be the connected components of $G[S]$ and let $e=(u,v)$ be a dead edge: we say that $e$ died with honor if there exists just a single component $C_i$ s.t. $u,v\in C_i$, that is $e$ dies with honor if it doesn't connect two different components of the survived edges graph.

What can we say about the probability $P_H$ of the event $H=$"all the bad edges $B$ are dead and at least one died with honor" ? Can we lower bound somehow this probability as a function of $k$ ? Can we find structural hypothesis over $G$ or particular distributions for random $G$ in order to do that ?


texts: Perfect matching of monotone Boolean function with null Euler characteristic

texts:
For a set $V = \{0,\ldots,k\}$ of variables, let $\mathbf{G}_V$ be the undirected graph with set of vertices $\{S \subseteq V\}$ and set of edges $\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+1\}$, in other words the underlying undirected graph of the Hasse diagram of the powerset of $V$. Let $\phi$ be a Boolean function on variables $V$, that we see as a set of subsets of $V$. Define the graph $\mathbf{G}_V[\phi]$ to be the subgraph of $\mathbf{G}_V$ induced by $\phi$.

I conjecture the following:

If $\phi$ is monotone and $\sum_{S \in \phi} (-1)^{|S|} = 0$, i.e., $\phi$ has as many satisfying valuations of even and odd size, then $\mathbf{G}_V[\phi]$ or $\mathbf{G}_V[\lnot\phi]$ has a perfect matching.

What I know:

For a Boolean function $\phi$, $\sum_{S \in \phi} (-1)^{|S|}$ is called the Euler characteristic of $\phi$.
Observe that $\sum_{S \in \phi} (-1)^{|S|} = - \sum_{S \in \lnot\phi} (-1)^{|S|}$ ($=0$ in our case).
Of course, if $\sum_{S \in \phi} (-1)^{|S|} \neq 0$, then neither $\mathbf{G}_V[\phi]$ nor $\mathbf{G}_V[\lnot\phi]$ can have a perfect matching.
My claim does not hold if we do not impose $\phi$ to be monotone. For example, consider the following Boolean function (the satisfying valuations of $\phi$ are colored):
$\sum_{S \in \phi} (-1)^{|S|} = 0$, but $\mathbf{G}_V[\phi]$ does not have a perfect matching since, for instance, $\{3,4\}$ is isolated. The same holds for $\mathbf{G}_V[\lnot\phi]$ by considering $\{0,3,4\}$.
There are examples where both have a perfect matching, and examples where only one does. Here is one such example (this is actually the smallest such example):
$\sum_{S \in \phi} (-1)^{|S|} = 0$, $\mathbf{G}_V[\phi]$ does not have a perfect matching, but $\mathbf{G}_V[\lnot\phi]$ does (trust me).
I suspect that, if the claim is true, what decides if $\mathbf{G}_V[\phi]$ or $\mathbf{G}_V[\lnot\phi]$ has a perfect matching is $\max(|\phi|,|\lnot\phi|)$.
There are no counterexamples to my claim for $k \leq 5$.
In the particuliar case where $\lnot \phi$ corresponds to a collapsible abstract simplicial complex (an abstract simplicial complex is just another word for the negation of a monotone Boolean function), then $\mathbf{G}_V[\lnot\phi]$ has a perfect matching.

What I have tried:

Since $\mathbf{G}_V[\phi]$ and $\mathbf{G}_V[\lnot\phi]$ are bipartite, I've tried using:

Kőnig's theorem. So here I would need to show that for $\mathbf{G}_V[\phi]$ (or $\mathbf{G}_V[\lnot\phi]$), there is no vertex cover of size less that $|\phi|/2$ (since the set of all subsets in $\phi$ of even size is obviously a vertex cover of $\mathbf{G}_V[\phi]$).
Hall's mariage theorem. Here I would need to show that, for every subset $B$ of $\phi$ containing only subsets of even size, the subsets of $B$ are (collectively) adgacent to at least $|B|$ vertices in $\mathbf{G}_V[\phi]$.

with no luck so far. I should add that I don't have any particular reason for why this should be true, but this came to me as an intriguing question while I was working on something else.


texts: Eliminating tautological axioms in tree-like $k$-DNF resolution

texts:
The propositional proof system $k$-DNF-resolution, a.k.a. $Res(k)$, is a generalization of propositional resolution, where the lines in a proof are $k$-DNF formulas, i.e., disjunctions of $k$-terms of the form $(a_1 \land \ldots \land a_m)$ with $m\leq k$ and literals $a_i$.

The rules are

Weakening: from $C$ infer $C\lor T$,
$\land$-introduction: from $C\lor T_1$ and $D\lor T_2$ infer $C\lor D \lor (T_1\land T_2)$,
cut: from $C \lor T$ and $D\lor \bar{T}$ infer $C\lor D$,

where $C$ and $D$ are $k$-DNF formulas, $T$ is a $k$-term, and $T_1$ and $T_2$ are $k$-terms such that $(T_1\land T_2)$ is still a $k$-term. $\bar{T}$ denotes the negation of $T$ written as a $k$-clause.

In tree-like resolution, the addition of tautological axioms $x\lor\bar{x}$ is easily seen to be redundant. If $Taut(F)$ denotes the set of these axioms for all variables $x$ in $F$, then this means more precisely:

  $F + Taut(F)$ has a tree-like resolution refutation of size $s$ iff $F$ has a  tree-like resolution refutation of size $s$.

Now let $Taut_k(F)$ denote the set of all tautologies of the form $T \lor   \bar{T}$, for $k$-terms $T$ over the variables of $F$. I think the analogous statement for tree-like $Res(k)$ also holds, and that I can prove it:

  $F + Taut_k(F)$ has a tree-like $Res(k)$-refutation of size $s$ iff $F$ has a tree-like $Res(k)$-refutation of size $s$.

Is this fact known, and if so, does it appear somewhere in the literature?


texts: Efficient representation of set of partial order

texts:
I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.

Let $r$ be an integer, let $P_r$ be the set of partial (pre)order over $[1,r]$ and $T_r$ the set of total (pre)order. I say that $P\in P_r$ is included in $T\in T_r$ if it is included as subset of $[1,r]^2$, or to state it another way, if for all $i,j$ with $i$ less than $j$ for $P$ then it is also less for $T$. Finally I say that $P$ and $P'$ are incompatible if there is $i,j$ with $i<j$ for $P$ and $i>j$ for $P'$ (or if $i=j$ for $P$  and $i<j$ for $P'$).

Let $P\in P_r$ with $i<j$ and no $k$ such that $i<k<j$, then $P_{i,j}$ is the same partial (pre)order, except that $i$ and $j$ are incomparable.

I would like to find an efficient data structure to store a subset of $P_r$. I can't imagine something better than a trie of depth $r(r-1)/2$, with one level for every pair $(i,j)$ with $i<j$. If possible I would want to be able to efficiently add and remove elements from the set, or at least to easily transform $P$ into $P_{i,j}$ as defined above.

I need to know if for a given subset $S$ of $P_r$ and $P\in P_r$, $P$ is incompatible with every $P'\in S$. Or an equivalent problem would be to figure out if a set $S$ is such that its element are one to one incomparable. I also need to know if for every total (pre)order $T$ it is a superset of a partial order $P\in S$.

Intuitively, to each $P\in P_r$ is associate its set $T_P=\{T\in T_r\mid T\supseteq P\}$ and I need to know if $(T_P)_{P\in S}$ form a partition of $T_r$.
Then let $T_S=\bigcup_{P\in S} T_P$, then I would also be interested by having a way to efficiently describe $T_S$. (That is, efficiently checking for a given $T\in T_r$ if $T\in T_S$.

Finally, I will introduce the real structure I'm interested in, which is more complicated and probably less usual.

A partial preorder $P$ can be seen as partial function from $[1,r]^2$ to $\{<,>,=\}$, where $i=_P j$  if $i<j$ and $j<i$ in $P$ and $f(i,j)$ is undefined if neither $i<j$ nor $i>j$ in $P$. We can associate to $P$ a subset of $\mathbb N^r$ called $\mathbb N_P$ defined by  $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$  $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$.

The real data structure I must study is the structure of partial function from $[1,r]^2$ to $\{<,\le,>,\ge,=,\not=\}$. I will call this structure "extended preorder". Let $P$ be an extended preorder,  where $(x_1,\dots,x_r)\in \mathbb N_P$ if for all $i<_Pj$  $x_i<x_j$ and for all $i=_Pj$, $x_i=x_j$, for all $i\le j$, $x_i\le x_j$, and for all $i\not_P=j$, $x_i\not=x_j$.

I say that a total preorder $T$ is included in an extended preorder $P$ if $i\le_Pj$ implies $i<_Tj$ or $i=_Tj$, and $i\not=_Pj$ imply $i<_Tj$ or $j<_Ti$.

The operation I must have are still the same, having a set $S$ of extended preorder, verify if an extended preorder is incompatible with every extended preorder of the set, and verify that every total preorder is included in an extended preorder of the set. Or to say it another way,  $(\mathbb N_P)_{P\in S}$ is a partition of $\mathbb N^r$.


texts: An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?

texts:
In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and no one else ever cited it. I've tried to read it and the basic idea is an $O(\log^c{n})$ computation for inner product where $c$ is an constant, which results in an $O(n^2\log^c{n})$ algorithm for matrix multiplication.
The details in this paper are too complicated to be fully understand, have anyone checked the correctness of this paper or read this paper?


texts:
Given a sequence of $n$ propositional formulas $\varphi_1, \cdots, \varphi_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$.

Define $K=\min\{k\mid \wedge_{i=k}^n \varphi_i\not\models \phi\}$, i.e., it is the minimal number $k$ such that the conjunction of $\varphi_k, \cdots, \varphi_n$ does not imply $\phi$.

Question: what's the complexity of deciding whether $K=\theta$?

What I have tried: Since deciding $\wedge_{i=k}^n\varphi_i\not\models \phi$ is NP-complete, this problem is in $P^{NP}$. Moreover, by binary search, this can be improved to $\Theta^p_2$, i.e., only logarithmic number of NP queries is enough. (Is this correct?) However, I am not clear about the lower bound. Maybe it is just in NP?


texts: NP-hard problem on planar unit disk graph

texts:
I am curious to know whether there are problems which are np-hard even on planar unit disk graphs.

A unit disk graph is the intersection graph of a collection of unit disks in the plane, where we draw a vertex for each unit disk.

Maybe some problem on a accordingly restricted grid graph?

alex


texts:
Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.

I am thinking about few related question:

Given a large data set (total data size is known), how to find top k frequent items? better to use less space.
Simple approach(count frequency of each item in data set, and sort) requires lots of space
What about finding top k frequent items in data stream?

Is there any near-optimal algorithms avaiable? or, can we prove relationship between space requirement and error ratio?


texts: Fast convergence of a contagion process in special graphs

texts:
The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira):
Define an indicator variable $x_i(t)$, which denotes the state of node $i \in \{1,\ldots,n\}$ at step $t$. We interpret $x_i(t)=1$ as "node $i$ is black (infected) at step $t$, and white (uninfected) otherwise."

Initially, $x_1(0)=1$, whereas $x_i(0)=0$ for all $i=2,\ldots,n$. At step $t>0$, each node $i$ picks a neighbour $j \in N(i)$ uniformly at random (we assume that $i \in N(i)$), and sets $x_i(t)=x_j(t-1)$. The process stops only when the nodes are either all-black or all-white. This process is Markovian.

My problem: I want to compute the following probability. For a given $t^*$, compute the probability that for every $i=1,\ldots,n$, $x_i(t^*)=0$. Specifically, I want to show that for $t^*=O(\log n)$, the above probability is $1-o(1)$. In words, I want to show that only after a logarithmic number of steps, the entire clique is all-white w.h.p.

This seems to be similar to the extinction problem in branching programs (wikipedia entry), but I'm not sure if the results for that problem carry over directly to mine.

Update: One can try to solve this problem "from scratch" (without using
any known related results), by looking at the following measure.

Let $d(t,j)$ denote the probability that the graph is all-white by step $t$, assuming that there are initially $j$ black nodes (e.g., $x_i(0)=1$ for $i=1,\ldots,j$, and $x_i(0)=0$ for $i=j+1,\ldots,n$). Clearly, we are interested in the value of $d(log n, 1)$. Also,
we have that $d(0,0)=1$ and $d(0,j)=0$ for $j>0$; and also $d(t,0)=1$ for $t \geq 0$.

For $t, j>0$, the recurrence can be expressed as follows:

$d(t,j)=\sum_{i=0}^{n-1}\binom{n}{i}\big(\frac{j}{n}\big)^i\big(\frac{n-j}{n}\big)^{n-i}d(t-1,i)$

But I'm not sure how to solve it.


texts: Being a theoretician at a business university?

texts:
I'm currently on the job market and I've seen some open faculty positions in computer science at a business university (which is quite reputable among its kind). While the job opening doesn't emphasize TCS, it's written in such a broad way that my current line of work could easily fit the profile.

That said, I'm having some concerns before applying:

Will it be difficult/impossible to get PhD students that are interested in TCS?
Should I expect a negative bias from funding agencies regarding grants, because of me being at a "non-technical/science"-oriented university?


texts: Combinatorial algorithm for optimization over semimetric polytope

texts:
This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.

Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More formally:

minimize $\sum_{ij = 1}^n c_{ij} d_{ij}$
where $d$ is a semimetric over $\{1, 2, \ldots, n\}$
and $\sum_{ij = 1}^n d_{ij} = 1$

Of course it is a linear program that can be solved in polynomial time using ellipsoid method. But what I would like to know is if there are any combinatorial algorithms for this optimization problem. I suspect that the answer is 'no' since the problem looks pretty general to be solved combinatorially, but who knows...


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

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

Thank you for your answers.


texts: Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

texts:
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is the preferred method. Modular exponentiation is also prominently featured in the quantum factoring algorithm, and it is expensive there as well.

So: why isn't Montgomery modular exponentiation apparently present in current detailed subroutines for quantum factoring?

The only thing I can imagine is that there's a high qubit overhead for some non-obvious reason.

Running montgomery quantum "modular exponentiation" through Google Scholar yields no useful results. I am aware of work by Van Meter and others on quantum addition and modular exponentiation, but examining their references (I have yet to read this work) shows no indication that Montgomery methods are considered there.

The single reference I have found that appears to discuss this is in Japanese, which lamentably I cannot read, though apparently it is from a 2002 conference proceedings. A machine translation yields nuggets appended below that indicate there might be something useful. However, I can't find any indication that this has been followed up, which makes me think that the idea has been a) considered and then b) discarded.

  Quantum circuit in performing
  arithmetic Noboru Kunihiro

  ...In this study, but requires
  relatively large qubit, we propose a
  modular exponentiation circuit quantum
  computation time is short. Montgomery
  Reduction [8] and right binary method
  [9] Combined, they constitute a
  circuit Ru. Reduction Montgomery is, m
  randomly chosen as a natural number,
  mod 2m by the operation, perform the
  remainder operation If, mod n
  operations in eliminating. This will
  lead to reduction of computation
  time...

  Application of 3.2 Montgomery
  Reduction Montgomery Reduction [8] is
  formulated as follows...This algorithm
  can return the correct values can be
  easily confirmed. M R (Y) he asks for
  a law 2m Polynomials with 2m points
  are important and only requires
  division by. In addition, Montgomery
  Reduction in, there are different
  calculation methods....In general,
  Reduction Montgomery is not one-to-one
  function...

  ...The proposed method uses a right
  binary method, Montgomery Reducton has
  a feature that is adopted. Than the
  conventional method, characterized by
  a small component of the circuit Have.
  qubit fault that is required to have a
  lot of expectations can be computed in
  less computational time Be. The
  future, Montgomery Reduction and
  control circuitry specifically NOT
  described by the qubit really needed
  Evaluate the number is expected to
  evaluate the computation time. In
  addition, each taking advantage of
  research findings, more than modular
  exponentiation Non-arithmetic (Euclid
  mutual division, etc.) also with
  respect to the planned configuration
  of an efficient quantum circuit.

  ...[8] PL Montgomery, "Modular
  Multiplication Without Trial
  Division," Mathematics of Computation, 44, 170, pp. 519-521, 1985...


texts: Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

texts:
If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root, and "satisfiable" if it is 1. (I use interpolating in a very loose sense here). It seems plausible that the degree/number of turning points of the resulting polynomial corresponds loosely to how "complex" the formula is.

To give a trivial example,

$a \oplus b$ is quardratic, $(1-ab)(1-(1-a)(1-b))$

while

$a \wedge b$ is $ab$, linear.

I believe an argument of this sort was used by Smolensky to show that PARITY is not in $AC^0$. I wonder, however, if there is there a more precise interpretation of

The Degree of the Polynomial
 The Number of Turning Points in the Polynomial?

Thanks!


texts: Introduction to Black-Box Separations in Cryptography

texts:
Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it.

A previous StackExchange entry gives a list of papers on the topic. But I wonder if the topic is covered by introductory-level notes. For example, the intuition behind a PRG is fairly popular. However the intuition behind separation wasn't clear to me from the papers. While I could understand some of the details, I didn't have a clear idea what the overall goal was. Or, for example, I couldn't get the technique of separating a construction from a given primitive compared to that of establishing a lower bound on certain parameters in the construction.

I believe one reason for lack of introductory resources could be that the topic is considered advanced, e.g., despite not being so recent, it's not covered in classical textbooks. Perhaps I'm missing some of these pointers. But otherwise it would be a good idea to compile such an introduction in the comments.


texts:
I am looking for a complexity class that relates to APX as BPP relates to P. I have already asked the same question here, but perhaps TCS would be a more fruitful location for answers.

The reason for the question is that in practical problems one often needs to find approximate answers (thus APX) with sufficiently high confidence (thus BPP), which would make the class of problems with bounded probabilistic approximation algorithms potentially a useful model of what's computable in practice.

A possible candidate of such class would be $APX^{BPP}$: problems that admit approximated solutions with bounded probabilistic subroutines; however, I'm not confident that such class would be the appropriate setting for the class probabilistically computable approximations.

Both BPP and APX have been extensively studied. Is that the case for $APX^{BPP}$, or whichever class would be the best to capture the above problems?


texts: Has this form of "kind-of-dual" homomorphisms been studied?

texts:
Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs and let $h:V_2\to V_1$ be a map such that, for every edge $(u_1,v_1)\in E_1$, there is an edge $(u_2,v_2)\in E_2$ such that $h(u_2)=u_1$ and $h(v_2)=v_1$.

This kind of maps has occurred in our recent research in Database Theory. We think that it looks like a natural "dual" to graph homomorphisms, where $h$ would be $V_1\to V_2$ and map each edge of $G_1$ to an edge of $G_2$. However, we could not find it in the literature, but, since we do not have a name for it, maybe we searched in the wrong places.

Some background: in Database Theory, homomorphisms play an important role in the context of the containment problem for conjunctive queries. The "kind-of-dual" form occurs in the context of parallel query evaluation.

In this slightly extended context, testing for existence of such a mapping is NP-complete, and I expect that also for graphs. However, I am not asking for complexity results, but I would be be grateful for pointers to the literature (or even a name, for that matter).


texts:
Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is:

  Is it possible to construct these sets such that the size of the maximum pairwise intersection between any two $t_i, t_j$ is $k$? Is this question $\mathsf{NP}$-complete? Or equivalently, is minimizing the maximum pairwise intersection between the sets $\mathsf{NP}$-hard?

There is a lower bound on the max pairwise intersection given by ceiling(number of identical value pairs / number of set pairs), meaning $\lceil (s \cdot {r \choose 2}) / {t \choose 2} \rceil$.

The problem seems related to, but slightly different from, the block design problem. In the block design problem, there is a parameter $\lambda$ that dictates in how many of the $t$ sets each pair of integers in $\{1, \ldots, s\}$ must appear, so if $\lambda$ is 1, the maximum pairwise intersection between sets is 1 (since each pair of values appears in at most 1 set together). I've seen claims that deciding the existence of a block design is $\mathsf{NP}$-complete, but no actual proof - would also appreciate any link to such a proof.


texts: Why semi-gradient is used instead of the true gradient in Q-learning?

texts:
In reinforcement learning, with function approximation, a popular cost function is the Mean value error.

This involves a target value V_pi and a current value estimate V_hat.
When deriving the update rule for gradient descent learning, people just ignore V_pi-s dependence on the parameters, using a semi-gradient instead of the true gradient.
Why is this? Is it difficult to calculate the true gradient?


texts: Exact nearest neighbor in $d$-dimensional Euclidean space

texts:
Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$.  We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \mathbb{R}^d$, the closest point (in terms of Euclidean distance) is returned.

What is the best known query time on this problem in terms of $n$ and $d$ for data structures with near-linear size (or at worst polynomial size)?  Note that solutions requiring space exponential in $d$ are not acceptable.

Perhaps I'm missing an obvious reference here, but is there anything of the form $O(2^{O(d)}\mbox{polylog}(n))$, given the space requirements?

For approximate NN, the best bounds are given by results of Arya, Mount, and colleagues.  For slightly different requirements, the best results are given by Andoni-Indyk's Locality Sensitive Hashing.

If the space has a bounded expansion constant $c$ (aka doubling measure), then results of Karger & Ruhl, Clarkson, and several follow-up works (Navigating nets, Cover trees) give a query time of $O(c^{12}\log{n})$ with linear space.  However, a pointset in $\mathbb{R}^d$ does not necessarily have a bounded expansion constant (in terms of $d$).  In particular, the set $\{2^i:\quad i=1,\ldots,n\}$ has $c=O(n)$, despite lying in $\mathbb{R}^1$.  The Assouad (doubling) dimension does not have this problem, but as far as I know, all results based on this dimension are for approximate NN.

Surely this must be known, but the older work on NN (eg by Clarkson or Meiser) generally requires exponential space, and newer work mostly focuses on the approximate NN problem or has some extra requirements on the space.


texts:
Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the weight function is non-negative (i.e. $w(e) \geq 0$ for all $e \in E$), then there are many extremely simple 2-approximations for max-cut. For example, we can:

Pick a random subset of vertices $S$.
Pick an ordering on the vertices, and greedily place each vertex $v$ in $S$ or $\bar{S}$ to maximize the edges cut so far
Make local improvements: If there is any vertex in $S$ that can be moved to $\bar{S}$ to increase the cut (or vice versa), make the move.

The standard analysis of all of these algorithms actually shows that the resulting cut is at least as large as $\frac{1}{2}\sum_{e \in E}w(e)$, which is an upper bound on $1/2$ the weight of the max-cut if $w$ is non-negative -- but if some edges are allowed to have negative weight, is not!

For example, algorithm 1 (pick a random subset of vertices) can clearly fail on graphs with negative edge weights.

My question is:

  Is there a simple combinatorial algorithm that gets an O(1) approximation to the max-cut problem on graphs that can have negative edge weights?

To avoid the possibly sticky issue of the max-cut taking value $0$, I will allow that $\sum_{e \in E}w(e) > 0$, and/or be satisfied with algorithms that result in small additive error in addition to a multiplicative factor approximation.


texts: How could one define a language based on the Calculus of Constructions, but with fixed points and EAL-style duplication restrictions?

texts:
Suppose that we take the Calculus of Constructions as a basis, but take away exponential functions (allowing only linear functions), and add the controlled duplication rules of EAL. That'd, I believe, give us a simple core with dependent types that can be reduced on the oracle-free fragment of Lamping's abstract algorithm.

Now, it has been shown [1] that adding type-level fixed points to EAL do not affect its complexity bounds. Doing so would make the language more interesting, as one would be able to define induction and inductive types. Problem is, the Calculus of Constructions makes no distinctions between types and values. As such, adding Fix would imply its existence on the value level (except if we make an exception of the rule, which looks inelegant), which may cause non-termination.

As such, it is not obvious to me how to add Fix to the language of the first paragraph without inhabiting all types. Perhaps a restricted version of it, with fix variables only occurring on non-application positions (i.e., only as arguments) would suffice, but I'm not sure 1. if that's true, 2. if that'd be the right way.

[1] J.-Y. Girard. Light linear logic. Information and Computation,
143:175–204, 1998.


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

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


texts: Complexity of computing the average distance of a graph

texts:
Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$

One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum appropriately.

If the output graph is a tree then it is known that the average distance can be computed in linear time (See B.Mohar, T.Pisanski  - How to compute the Wiener index of a graph). There appears to be fast algorithms for graphs with bounded tree width as well.

An interesting question therefore is, whether it helps to know $D(G).$ In other words

  Is it possible to compute $\rm{ad}(G)$ in sub-quadratic time?

What I am interested in knowing is if there is a theoretical lower bound as to why this would not be possible.


texts: Lengths of "all-accepted" words in Context Free languages

texts:
If $L$ is a Context Free language, it can happen that for some $n$, all words of length $n$ are in $L$. If we consider the
set $A_L$ of such lengths represented in unary, we may guess that such set is Context Free (and hence regular), but it is not the case.
More formally; if $L \in CF$ define:
$A_L = \{ 1^n \mid |w|=n \Rightarrow w \in L \}$
There are CF languages for which $A_L \notin REG$.
The example I have in mind uses the sequence of tape configurations (alternating straight/reverse order like in the proof of the undecidability of $L = \Sigma^*$) of a valid Turing machine computation that on input $x$ (in binary), writes $1^x$ on the tape and halts.
Before spending more time in formalizing it, I wonder if there is a simpler example, or if I can find it in some books/papers (I made some searches but probably I'm using the wrong terms).


texts: Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

texts:
I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:

1) It is hard to sample approximately uniformly at random from the set of all solutions

2) It is easy to approximately integrate any (polynomially computable) function over the solutions.

I would also be happy with replacing 2) by the weaker:

2') It is easy to approximate the expectation of any polynomially computable function over the uniform distribution on the solutions.

My thoughts:

If 2) holds, then by integrating the constant function $1$, one can approximately count the number of solutions to the problem.
If 2) holds but 1) does not, then the problem cannot be self-reducible, as otherwise by reductions in JVV86 there would be an efficient algorithm for approximate uniform sampling by using the observation of the previous bullet.
A reasonable candidate technique for accomplishing 2) without 1) is importance sampling.
I know of situations where sampling is easy and counting is hard (so integration is hard); the case of uniformly sampling solutions to a DNF equation is explained in JVV86 section 4.
A specific candidate problem I would be interested in is the problem of sampling directed simple cycles from a digraph. (It is shown in section 5. of JVV86 that this problem is hard.) However, I know that counting the number of directed simple cycles is NP-hard, by a similar argument to that presented in JVV, and therefore so is integrating over them. However, perhaps 2') can be solved in this case?

--

Any references that seem relevant would be very appreciated, even if they are not a direct answer to my question.


texts: Parallel algorithms to find the optimum of polynomials

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


texts: Truthful posted-price mechanism with optimal efficiency (social welfare)

texts:
I am interested in mechanism design. In the paper On Profit-Maximizing Envy-free Pricing, SODA, 2005, the authors provided a truthful competitive posted-price mechanism with $4\log h$ guarantee of revenue in the unit demand setting (see Theorem 4.1 in section 4). If I understood correctly, this mechanism does NOT have guarantee on social welfare.

Is that possible to derive a truthful (a.k.a. incentive-compatible) posted-price mechanism with (approximate) efficiency (a.k.a. social welfare guarantee) for some envy-free pricing problem? I am aware of some frameworks based on VCG or non-VCG (e.g. critical-payment by Nisan). However, I do not find any of them a good fit for this problem.

P.S. "posted-price" means that the price of any bundle $S$ is the sum of prices of items in $S$, i.e. $p(S)=\sum_{i\in S} p_i$ where $p_i$ is the price of one copy of item $i$. The utility of buyer $j$ when he receives bundle $S$ can be formulated as: $u_j(S)=v_j(S)-p(S)$ where $v_j(S)$ is the valuation of $j$.


texts:
Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:

$$
|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}
$$

Let us focus on $\Delta_{|V|}$.

Question

How hard is to compute $\Delta_{|V|}$?

Motivation

The quantity
$$\Delta_{|V|}\ \ mod\ \ 2$$
is the parity of the number of vertex covers of $G$. If such quantity is $0$ then $|\mathcal{C}|$ is even, otherwise $|\mathcal{C}|$ is odd.

Therefore (forgive me if I'm wrong):

Being able to compute $\Delta_{|V|}$ in polynomial time implies $\mathbin{\oplus}$P = P.
$\Delta_{|V|}$ being $\#$P-hard to compute implies $\mathbin{\oplus}$P = PP.

It seems that in both cases we would get an important result. Clearly there is a third option: computing $\Delta_{|V|}$ may be of intermediate counting complexity, strictly harder than FP but strictly easier than $\#$P-hard.

Update 08/01/2013 21:50

After reading again and more carefully T. Williams' answer to this question, my understanding is that such answer precisely proves that computing $\Delta_{|V|}$ is $\#$P-hard (because the constraint $[0,1,1,1]$ forces every node of $G$ to be present).

However, my second conclusion above does not hold: to conclude $\mathbin{\oplus}$P = PP, computing $\Delta_{|V|}\ \ mod\ \ 2$ should be $\#$P-hard. But the $\#$P-hardness of computing $\Delta_{|V|}$ is not known to imply that computing $\Delta_{|V|}\ \ mod\ \ 2$ is $\#$P-hard as well.

Only a more vague and harmless conclusion can be drawn, more or less along these lines: something which appear to be false from a practical point of view (i.e. Graph Isomorphism $\not\in$ P) would imply something already formally known to be true (i.e. computing $\Delta_{|V|}$ is $\#$P-hard).


texts:
Kearns and Vazirani (chapter 1) describe an efficient algorithm for PAC learning conjunctions of boolean variables $x_1, x_2, \ldots, x_n$, which starts with the hypothesis $$h=x_1\wedge\overline{x_1}\wedge x_2\wedge\overline{x_2}\cdots x_n\wedge\overline{x_n},$$
and, on each call to an oracle that returns a positive example $a$, removes literals from $h$ to make it consistent with $a$. That is, if $a_i=0$, then you remove $x_i$ from $h$, otherwise you remove $\overline{x_i}$ from $h$.

However, if we don't receive enough examples, $h$ will still be unsatisfiable -- as it was at the beginning. So what are we supposed to do in this case? Remove some "problematic" literals at random?

Thanks for your help!


texts: Are there variants of visibly pushdown automata that allow pushing of words onto the stack?

texts:
I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack.

Alternately, a construction which allowed for symbols to be pushed on $\epsilon$-transitions could achieve the same goal.

Obviously, such variations can be formed, but I'm wondering if it ruins the closure and decidability properties that make VPAs interesting.

I'm looking at a construction where use the stack as a counter, incrementing it by constants based on the initial symbols read, then counting down based on other symbols read.

For anyone who doesn't know, visibly pushdown automata are ones where the alphabet can be divided into pushing symbols, popping symbols, and symbols not affecting the stack at all. The choice of pushing versus popping is entirely determined by the current symbol being read. They're closed under intersection, union, concatenation, star and complement, giving them a wealth of decidable properties.  See this paper for more.


texts: Minimum shortest path cover of $n$ vertices in $R^m$

texts:
Informally, we define minimum shortest path cover to be the smallest number of shortest paths that cover all vertices of a graph. In other words, every vertex should belong to at least one of those shortest paths (there is no problem if one vertex belongs to more than one paths). Formally, we define the problem as follows. Assume the directed graph $G=(V,E)$ with vertices $V=\{v_1, ..., v_n\}$, with non-negative edge weights $w(v_i,v_j) \ge 0$. We have following definitions respectively:

weight of a path: if $P=u_1, ...,u_{|P|}$ then $w(P) = \sum w(u_i,u_{i+1})$
set of all path covers of $G$: $PC(G)=\{\{P_1, ..., P_k\} |\forall i \exists j: v_i \in P_j\}$.
Size of a path cover: if $PC=\{P_1, ..., P_k\}$ then $Size(PC)= k$
set of all paths of $G$ starting from $v$ and ending in $u$: $P(G, v, u)=\{v, v_{i_1},...,v_{i_l}, u | \forall j: v_{i_j}, u, v \in V, (v_{i_j},v_{i_{j+1}}), (v,v_{i_1}), (v_{i_{|P|}},u)\in E\}$
set of all shortest paths of $G$ by $SP(G) = \{P =
   v_{i_1}, ..., v_{i_{|P|}} | \forall Q \in P(G,v_{i_1},v_{i_{|P|}}), w(P) \le w(Q)\}$.
Set of shortest path covers of $G$: $SPC(G)=\{PC=\{P_1, ..., P_k\} | PC \in PC(G), \forall i: P_i \in SP(G)\}$
Minimum shortest path cover of G: if $PC \in SPC(G)$ and $\forall Q \in SPC(G): Size(P) \le Size(Q)$ then $MSPC(G) = PC$

To give a concrete example, suppose graph $G=(V,E)$, with vertices $ V=\{1,2,3,4\}$, and edges $E=\{1\rightarrow 2,1\rightarrow 5, 2\rightarrow 3,4\rightarrow 5\}$. It is clear that $G$ could be covered by two paths. The minimal set would be $MSPC(G)=\{1\rightarrow 2 \rightarrow 3,\ 4\rightarrow 5 \}$.

Now we informally construct the graph $G$ as follows. Its set of vertices ${v_1, v_2, ..., v_n}$ are points in $R^m$. Then we put the $k$ nearest vertices to $v_i$ (euclidean distance) in its adjacency list $Adj(n_i)$. Noting that $n_i \in Adj(n_j)$ does not imply $n_j \in Adj(n_i)$, the formed graph is directed and not necessarily symmetric. We can hold $k$ to be constant or $k \ll n$, in a way that the graph would become sparse.More formally we have following definitions:

vertices: $V={v_1, v_2, ..., v_n}, \forall i: v_i \in R^m$
distances: $d(u,v)$ denotes euclidean distance between $d(u,v)=||u-v||_2$
k-nearest neighbours: $N_k(u)=\{u_1, ..., u_k\}$ in that $\forall u_1 \in N_k(u), u_2 \notin N_k(u)$ implies $d(u,u_1) \le d(u,u_2)$.
edges: $E=\{(u,v) | u,v \in V, v \in N_k(u)\}$. Alternatively, $Adj(u)=N_k(u)$.
weights: if $(u,v) \in E$ then $w(u,v) = d(u,v)$.
Graph: $G=(V,E)$.

UPDATE: Some additional notes:

Shortest paths are unique.
k is chosen large enough to keep $G$ connected
A special case of interest is when nodes are dense $n \rightarrow \infty$ in a limited space (say unit hypercube $(0,1)^m$), and they follow a specific distribution (namely uniform).

Using the above definitions, the question is what is the asymptotic value of $Size(MSPC(G))$ or $E\{Size(MSPC(G))\}$ in the case of stochastic points? My intuition is that it is of the form $O(n^\frac{m-1}{m})$, which comes from the number of necessary paths to cover a $m$-dimensional regular grid in $R^m$. Suppose we have $l^m$ vertices $(a_1, ..., a_m), a_i \in \{1, ..., l\}$. You could cover this grid by $l^{m-1}$ paths like this: $Path-Cover = \{\{(1, P), (2, P), ..., (l, P)\}| P \in \{1,...,l\}^{m-1}\}$. Substituting $l^m$ by $n$ the $O(n^\frac{m-1}{m})$ bound could be achieved.


texts: Isolation in Turing-complete reversible cellular automata

texts:
I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought.

Consider Turing-complete reversible cellular automata.

For instance, Wolfram's Rule 110 cellular automaton is Turing-complete, but, if I understand correctly, it's not reversible. However, it can be made reversible by converting it into a second-order cellular automaton and then implementing the second-order CA as a first-order CA with a larger cell state space.

My question is whether it's possible to define a finite region of cells that is completely isolated from the outside.

More specifically: if there exist an initial state of a finite connected region of cells (let's call it Vault), which is composed of a connected region Interior surronded by another region Wall, such that the state of the Interior at any time t depends only on the previous state of Interior.

My conjecture is that such isolated regions are impossible.

My intuition stems from the fact that Turing-complete reversible CA can be considered very simple models of physical reality (and proponents of the digital physics hypothesis argue that the physical world is actually a cellular automaton). If I understand correctly, totally isolated physical systems can't exist, thus I conjecture by analogy that this should also apply to all Turing-complete reversible CA.
(Turing-incomplete or irreversible CA can have isolated regions, but they are probably not good models of fundamental physical reality)

Has anybody already proved or disproved this assertion? Or do you have any thoughts about it?

UPDATE:

As Shor pointed out in the comments, the conjecture as stated above is false, since it is possible to use some states which are not required for Turing-completeness to achieve isolation.

I will try to reformulate the question in a way that the conjecture may possibly hold by adding more requirements on the cellular automaton.

I'm thinking of two reformulations based on two different additional requirements:

Minimal universality: As noted by Grochow, we can define a Turing-complete CA to be "Minimally universal" iff the CA obtained by removing one cell state (and the corresponding rules) is no longer Turing-complete.Thus, the conjecture is: There does not exist a minimally universal reversible CA such that isolated regions can be defined.
Total harnessability: We may say that the computational power of a Turing-complete CA is totally harnessable iff there exist undecidable properties regarding all cell states.More specifically, we define a CA to be totally harnessable iff $\forall s \in CellStates \ \exists$ a computable initial configuration $x(t_0,\,i)$, a finite set of cell indexes $Q$, a vector of cell states $\bar{q}$ containing $s$ and predicate $p(x,\,t)\ \equiv\ \bigwedge_{i \in Q}x(t,\,i)=q_i $ such that the question "$\exists t:\ p(x,\,t)=True$" is undecidable, and the question obtained by removing from predicate $p$ the conditions on state $s$ is decidable.Thus the conjecture is: There does not exist a totally harnessable Turing-complete reversible CA such that isolated regions can be defined.


texts: Convolution products in partial semigroups

texts:
A partial semigroup (or PSG) consists of a set $X$ and of a partial composition law $*$ defined over $X$, that is to say:

(1) $x*y$ is not always defined,

(2) if $(x*y)*z$ is defined, so is $x*(y*z)$, and the two values are equal,

(3) if $x*(y*z)$ is defined, so is $(x*y)*z$, and the two values are equal.

Let $\mathbb{R}$ be a ring. We may then define a convolution product over $\mathbb{R}^X$ : given two functions $f,g$, we define a function $f*g$ such that

  for every $w \in X$, $f*g(w) = \sum_{x,y \in X : x*y = w} f(x) g(y)$.

By a graded PSG, we mean a pair $(S,r)$ consisting of a PSG $S = (X,*)$ and of a rank function $r : X \rightarrow \mathbb{N}$ such that whenever $x*y$ is defined, $r(x*y) = r(x)+r(y)$. This holds for instance for the interval algebra of an Eulerian poset (see On the Foundations of Combinatorial Theory I. Theory of Moebius Functions, by G.C. Rota).

By analogy with the situation in posets, we may define a 'triangular matrix' $\lambda \in \mathbb{R}^X$ by $\lambda(x) = 1$ for every $x \in X$, and a mapping $\zeta : \mathbb{R}^X \rightarrow \mathbb{R}^X$ by $\zeta(x) = \lambda * x$. It is known that for a partial semigroup obtained from the interval algebra of an Eulerian poset, the function $\lambda$ has an inverse $\mu \in \mathbb{R}^X$ given by $\mu([x,y]) = (-1)^{r(y)-r(x)}$. This suggests a possible extension to certain graded PSGs, which leads me to ask the following.

Question: for a graded PSG, under what conditions does $\lambda$ have an inverse $\mu$? When this holds, is it always true that $\mu(x) = (-1)^{r(x)}$?

(NOTE: I renamed the rank function $r$ instead of $l$ for greater consistency.)


texts: Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

texts:
Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.

One can see that inserting elements of an array into a binary search tree and reading them back out requires (on insertion) the same comparisons as running Quicksort on that array. The sequence of pivots that Quicksort uses is the sequence of insertions into the binary search tree.

This is also trivially true for Heapsort and heaps, since Heapsort is literally doing such a series of insertions and then reading the elements back out.

Does there exist an analog of this in the case of, say, Mergesort? Is there a deeper connection here, or is it an interesting coincidence between data structures and sorting algorithms?


texts: What do we know about checking real-stability of multivariate complex polynomials?

texts:
Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root have a positive imaginary part.

[..clearly if $n=1$ then the polynomial being real-stable is the same as the polynomial being real-rooted..]

Q1 Do we know of any method to check for real stability of a polynomial?

Q2 Even if not a general solution but can one at least be able to check this property on some specific polynomial via some commands on SAGE or Mathematica ?

Q3 Is any hardness result known about this when thought of as a decision question?

If necessary feel free to assume that the polynomial is homogeneous.  May be if thinking about the associated projective variety helps...
May be you can just choose some specific value of $n$ or the degree of the polynomial if you think that the questions are answerable easier for those values. (like $n=1$ and degree $\leq 5$ are the trivial cases)
A generic example of a real-stable polynomial is $p(z,t_1,..,t_n) = det(zI + \sum_{i=1}^{n} t_i B_i)$ where $B_i$ are positive-semi-definite matrices. Now we know that real-stability of a polynomial is preserved under operations like acting by differential operators like $(1+ a \frac{\partial }{\partial x})$ (where $x$ is one of the domain variables of the polynomial and $a \in \mathbb{R}$) or setting any of the variables to a real-number or taking a product of two real-stable polynomials.  Now one obvious way to try to decide if a polynomial is real-stable or not is to see if it can be obtained via doing any combination of these real-stability preserving operations on some other polynomial which is known to be real-stable.

But I am wondering if any direct method (algorithm) exists..


texts: Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

texts:
I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(2) languages in the streaming model. Quoting a sentence from the introduction section of the paper - "Using a straightforward one-way communication complexity argument for EQUALITY, we can deduce that DYCK(2) requires linear space for deterministic one-pass streaming algorithms." Can anyone see the straightforward argument? (I can't, but perhaps I am being blind.)

Some background -

DYCK(2) languages are basically sequences of two kinds of parantheses that are well-formed. For example, the sequence [()] is in DYCK(2), but the sequence [(]) is not.

One-way communication complexity of EQUALITY refers to the following problem. Alice and Bob both have one n-bit string each. Alice does some computation on her bits and sends some information to Bob. Bob can do computation on this information plus his bits and has to decide whether his n-bit string is exactly equal to Alice's bit string or not. It can be shown using simple communication complexity arguments that the number of bits that must be communicated is $\Omega(n)$.

Communication complexity lower bounds are often used for proving lower bounds for streaming algorithms. The usual scheme is the following. Suppose the problem you want to solve in streaming is P. Pick a communication complexity problem P' for which you know of a lower bound on the number of bits that need to be communicated. Then assume that the problem P can be solved in the streaming model using $o(f(n))$ space. Now in the communication complexity problem P', assume that Alice has as her input the first few bits of the input for P (or some mapping of the first few bits to something else). Then assume that the protocol they use for communication is that Alice runs the streaming algorithm on her input, sends the working space to Bob and then Bob finishes off using his input. In the end, prove that the solution to the streaming problem somehow gives a solution for the communication complexity problem. This will show that the communication complexity problem can be solved with $o(f(n))$ bits of complexity. The trick is to choose $f(n)$ in such a way that this leads to a contradiction.


texts: Monotone circuit representations of paths in a graph?

texts:
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every path $\pi$ from $s$ to $t$ gives a clause where we conjoin all edges of $\pi$, and $\phi_G$ is the disjunction of all these clauses. (It is obvious that it suffices to only consider simple paths: any path containing a vertex multiple times must use a set of edges that is not minimal under inclusion, so it defines a clause which is absorbed by another.)
If $G$ is required to be an acyclic graph, then I can easily construct in linear time from $G$ a representation of $\phi_G$ as a monotone Boolean circuit (using operators $\lor$ and $\land$). Specifically, every node of $G$ gives a gate of the circuit, which is the constant-1 gate for $t$, and which is otherwise the disjunction, over all outgoing edges $e$, of the conjunction of the variable corresponding to $e$, and of the gate for the end vertex of $e$. (Incidentally, the functions $\phi_G$ for $G$ an acyclic graph do not seem to achieve all possible monotone Boolean functions, and I don't know what is the precise class of functions that are achieved.)
My question is: for a general (non-acyclic) graph $G$, can I also construct in linear time a representation of $\phi_G$ as a monotone Boolean circuit? (or even as a non-monotone Boolean circuit?) I know it can be done in quadratic time, intuitively by making $G$ acyclic by creating $n$ copies of it. But I don't know how to do it in linear time in this case. I suspect it is impossible (and that it could be shown on specific graph classes, e.g., grid graphs), but I don't know how to show it. Are there any relevant circuit lower bounds that could help here?


texts: Kolmogorov Complexity of an arbitrary string

texts:
For an arbitrary string sampled from $\{0,1\}^n$, what would be the probability that the string has a Kolmogorov Complexity $\geq$ length of the string, $n$.

In other words, how many strings are there in the above set that satisfy the definition of random, as defined in Kolmogorov Complexity.


texts: Well-formedness condition for inductive types

texts: I work on implementing a simple dependently typed language. I want to implement inductive types there. However, I want them to be well formed. From what I've seen in Coq not all types are acceptable. What can I read about them? Could give a simple enough well-formedness condition which I can use?


texts:
Is the set of satisfiable Horn formulas sparse?

A sparse language contains a polynomially bounded number of srings at every length.


texts: "Learning" when test and train distributions don't match

texts:
We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis.

Question: what if the train/test(evaluation) distributions don't match; is there any result that tells us we can still learn something (say when the training distribution is log-concave and the test distribution is uniform).


texts: Longest path in a DAG that's not too long

texts:
The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is maximized, subject to the constraint that the sum of the weights is less than or equal to some upper bound W. Hence the title of this post, that the longest path not be "too long".

I am aware that the general longest-path problem is NP-Hard, and that the standard longest-path problem on DAGs is easily solved in O(|V|+|E|) time using topological sort and edge-relaxation (i.e. DP) (or we can solve this as shortest path by negating edge-weights).

I've frustratingly searched for a while on the web and came up with nothing on this problem; one would think that so simple a variant would at least be mentioned somewhere (if even in the general case, not limited to DAGs; or perhaps phrased as a shortest path problem where the path shouldn't be "too short").

I thought perhaps simply modifying the edge-relaxation condition to include the upper-bound constraint would do the trick, but I realized this is flawed: a "heavier" path may look attractive at the moment, but may end up violating the constraint (and so we should've stuck with the previous, albeit "lighter" estimate). I've not been able to find some alternative way of modifying the DP method to make this go through.

Efficient solutions are appreciated, or, conversely, a proof that this problem is hard. Relevant sources or references would also be appreciated.