texts:
Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it):

  The most common complaint is that physicists and journalists explain
  the meaning of a p-value incorrectly. For example, if the p-value is
  0.000001 then we will see statements like “there is a 99.9999% confidence that the signal is real.” We then feel compelled to correct
  the statement: if there is no effect, then the chance of something as
  or more extreme is 0.000001.

  Fair enough. But does it really matter? The big picture is: the
  evidence for the effect is overwhelming. Does it really matter if the
  wording is a bit misleading? I think we reinforce our image as pedants
  if we complain about this.

Which got me thinking -

  Are there good examples of pedantry in TCS ? Such an example would
  consist of

  A claim that is commonly made in the popular press
  A standard correction that people insist on making
  The correct "big picture" that the claim does capture even while being imprecise.

  where the claim is mathemtically wrong  but "morally right" and the
  correction is technically correct but doesn't change the intuitive
  understanding.

To lead things off, my example would be:

Claim - NP-complete problems take exponential time to solve
Correction - No in fact we just don't know if they can be solved in polynomial time
Big picture - NP-complete problems are HARD

Caution: I know there are many on this forum whose head will explode at the idea of claims that are wrong but "morally correct" :). Remember that these are statements targeted towards the public (where some degree of license can be permitted), rather than statements made in a research paper.


texts: Is there a simple argument for this Hemi-Icosahedron Boolean function?

texts:
This is problem 1(e) from Homework 1 of the course about Analysis of Boolean functions at CMU in 2012 as well as problem 1.1(n) on p.34 of Ryan O'Donnell's Analysis of Boolean Functions.

Compute the Fourier expansion of the hemi-icosahedron function $HI: \{-1,1\}^6 \to \{-1,1\}$, defined as follows: $HI(x)$ is 1 if the number of $1$'s in $x$ is $1,2,$ or $6$. $HI(x)$ is $-1$ if the number of $-1$'s is $1, 2,$ or $6$. Otherwise, $HI(x)$ is $1$ if and only if one of the ten facets of the following diagram has all three of its vertices $1$:

My question: Is there a quicker way to see that the solution should be the answer I got below by brute force? I get how to calculate the Fourier expansion by brute force in general, but I don't feel like I have been very successful at trying to exploit symmetries in special cases like these.
My attempt at a solution
I wasn't sure how to predict how the coefficients might cancel out nicely, and I didn't want to feel dumb by making no attempt, so I did it by brute force. What I got as the final result was: $$\frac{1}{4}[x_3x_4x_6 + x_3x_4x_5 + x_2x_5x_6 + x_2x_3x_5 + x_2x_4x_6 + x_1x_5x_6 + x_1x_4x_5 + x_1x_3x_6 + x_1x_2x_3 + x_1x_2x_4 - x_6 -x_5 -x_4 -x_3 +\frac{1}{2} -\frac{1}{2}x_1 -\frac{1}{2}x_2 +\frac{1}{2}x_1x_2   ] $$ This doesn't give the right answers and seems pretty obviously to be the result of an algebra mistake (which seems kind of inevitable when attempting to solve such a large problem by brute force using pen and paper).
So, basically arguing by wanting my answer to look less ugly, and hoping that this would work, I guessed that the actual answer, from which the one I calculated deviates for terms of degree $\le 1$, is the following: $$\frac{1}{4}[x_3x_4x_6 + x_3x_4x_5 + x_2x_5x_6 + x_2x_3x_5 + x_2x_4x_6 + x_1x_5x_6 + x_1x_4x_5 + x_1x_3x_6 + x_1x_2x_3 + x_1x_2x_4 - x_6 -x_5 -x_4 -x_3 -x_2 - x_1] $$
This actually seems to work for all of the inputs I have tested. Basically it seems like there is a degree three term for each of the ten facets of the hemi-icosahedron, plus a correction term for each of the six variables for some reason. But why or how should I have predicted this result?


texts: Describing state machines mathematically

texts:
The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me.
On the one hand, I am surprised to see that an important hardware protocol called "two-phase handshake" can be derived from a trivial program, simply by mathematical substitution.
On the other hand, I think that this example is (and should be) chosen deliberately. What I doubt about is its generality. If this method (i.e., describing state machines mathematically and deriving a protocol from its specification by mathematical substitution) is so fresh that researchers have not developed a general theory, I would like to see more examples.

My question is straightforward:

  Is this derivation a coincidence? Could anyone offer more examples or related references?

The derivation of the "two-phase handshake" protocol from a trivial program:

The trivial program mentioned above is just to alternately perform the $\mathcal{P}$ and $\mathcal{C}$ operations:

  $\mathcal{X}: \textrm{ loop } \mathcal{P} \textrm{ } ; \textrm{ } \mathcal{C} \textrm{ endloop}$

By introducing a variable $pc$ to represent the "program counter", $\mathcal{X}$ can be described as the following state machine:

  $Init_{\mathcal{X}} \triangleq (pc = 0) \land Init_{\mathcal{PC}}$
  $Next_{\mathcal{X}} \triangleq \big( (pc = 0) \land \mathcal{P} \land (pc' = 1) \big) \lor \big( (pc = 1) \land \mathcal{C} \land (pc' = 0) \big)$

where $Init_{\mathcal{X}}$ denotes the set of initial states; $Next_{\mathcal{X}}$ specifies the next-step transition. $Init_{\mathcal{PC}}$ specifies the initial values of the variables in $var_{\mathcal{PC}}$ involved in $\mathcal{P}$ and $\mathcal{C}$. The primed variable ($pc'$ here) is used to represent the modified version of its unprimed counterpart ($pc$ here).

The two-phase handshake protocol can be described as follows, where $p$ and $c$ are initially equal.

  \begin{eqnarray}
\mathcal{Y} :  & \textrm{ process } & Prod: \textrm{ whenever } p = c \textrm{ do } \mathcal{P} \textrm{ } ; \textrm{ } p = p \oplus 1 \textrm{ end} \\
& \Arrowvert & \\
& \textrm{ process } & Cons: \textrm{ whenever } p \neq c \textrm{ do } \mathcal{C} \textrm{ } ; \textrm{ } c = c \oplus 1 \textrm{ end}
\end{eqnarray}

Note that process $Prod$ reads $c$ and writes $p$ while $Cons$ reads $p$ and writes $c$. It is not hard to find out that $\mathcal{Y}$ alternately performs $\mathcal{P}$ and $\mathcal{C}$.

The protocol $\mathcal{Y}$ can also be described as a state machine:

  $Init_{\mathcal{Y}} \triangleq (p = c) \land Init_{\mathcal{PC}}$
  $Next_{\mathcal{Y}} \triangleq Prod \lor Cons$
  $Prod \triangleq (p = c) \land \mathcal{P} \land (p' = p \oplus 1) \land (c' = c)$
  $Cons \triangleq (p \neq c) \land \mathcal{C} \land (c' = c \oplus 1) \land (p' = p)$

The amazing observation is:

  $\mathcal{Y}$ can be obtained from $\mathcal{X}$ by substituting $p \oplus c$ for $pc$ in their state machines.


texts:
Suppose I have a set of squares. I get them in iterative way – one after another.

I would like to place the squares  in some structure according to set of rules:

When a new square arrives all squares which arrived before it are already placed. The new square arrives with dependency flag to one of squares, which was treated. The dependency flag can be L or R.

If the dependency  is L and a new square i depends on j it can be placed:

If the dependency  is R and a new square i depends on j it can be placed:

Note: In general we have to use placement options the preferable placement is 1
if it is impossible 2 or 3 (2/3 have the same priorety) 4,5 are used only if it is impossible to use one of 1,2,3.

If j is totally surrounded by another squares i is placed "after" surrounding squares based on dependency flag.

The placement goal is to generate as compact a "mesh" as possible.

For example if squares arrive in the format: new_square, dependent_on_square, dependency_flag

And we have

1, NULL, NULL

2, 1, R

3, 2, R

4, 2, L

5, 4, L

6, 5, L

7, 6, L

8, 7, L

9, 8, L

It is possible to create two arrangement 1) compact  2) not compact

Definition for compact layout(placement):

If we will pad the acquired layout with empty squares ,in such a way that we will get rectangular the number of empty squares will be minimumal in obtained layout.

Note : The rectangular obtained as a result of padding shoud be as small as possible.

I mean that if the width if layout before padding is w the  generated rectangular will be by width w.(The same regarding the height) .

Demonstartion in the above examples

Could someone propose an algorithm to do such kind of placement?


texts: Number of non-isomorphic induced subgraphs of a graph

texts:
Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs).

Does anyone know the computational complexity of this problem? Are bounds known?


texts: NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

texts:
I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is either unsatisfiable or has a unique solution. Thus showing that SAT does not admit an efficient algorithm even under the promise of there being at most one solution.

Through a parsimonious reduction (a reduction that preserves the number of solutions), it is easy to see that most NP-complete problems (I could think of) also do not admit an efficient algorithm even under the promise of there being at most one solution (unless $\mathbf{NP = RP}$). Examples would be VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.

Hence I was wondering if there was any NP-complete problem that was known to admit a poly-time algorithm under a uniqueness promise.


texts: Is this an equivalent condition for algebraic posets?

texts:
The definition of "algebraic poset" in Continuous Lattices and Domains, Definition I-4.2, says that, for all $x \in L$,

the set $A(x) = {\downarrow} x \cap K(L)$ should be a directed set, and
$x = \bigsqcup ({\downarrow} x \cap K(L)$.

Here $L$ is a poset, $K(L)$ is the set of compact elements of $L$, and ${\downarrow} x$ means $\{y \mid y \sqsubseteq x\}$.

I was a bit surprised by the first condition.  It is an easy argument to show that, if $k_1$ and $k_2$ are in $A(x)$ then $k_1 \sqcup k_2$ is also in $A(x)$.  So, all nonempty finite subsets of $A(x)$ have upper bounds in it.  The only question is whether the empty subset has an upper bound in it, i.e., whether $A(x)$ is nonempty in the first place.  So,

Is it ok to replace the first condition with $A(x)$ is nonempty?
What is an example of a situation where $A(x)$ is empty?

Note added: How is $k_1 \sqcup k_2$ in A(x)?  First, since $k_1 \sqsubseteq x$ and $k_2 \sqsubseteq x$, we have $k_1 \sqcup k_2 \sqsubseteq x$.  Second, $k_1$ and $k_2$ are compact.  So, any directed set that goes "beyond" them must "pass" them.  Suppose a directed set $u$ also goes beyond $k_1 \sqcup k_2$, i.e., $k_1 \sqcup k_2 \sqsubseteq \bigsqcup u$.  Since it has gone beyond $k_1$ and $k_2$, it must have passed them, i.e., there are elements $y_1, y_2 \in u$ such that $k_1 \sqsubseteq y_1$ and $k_2 \sqsubseteq y_2$.  Since $u$ is a directed set, it must have an upper bound for $y_1$ and $y_2$, say $y$.  Now, $k_1 \sqcup k_2 \sqsubseteq y \in d$.  This shows that $k_1 \sqcup k_2$ is compact.  The two pieces together say $k_1 \sqcup k_2 \in A(x)$.


texts: Compressing information about the halting problem for oracle Turing machines

texts:
The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.

More precisely, it is possible to compute from a description of $2^{n}-1$ Turing machines and an $n$-bit advice state the answer to the halting problem for all $2^{n}-1$ of the Turing machines, assuming the advice state is trustworthy - we let our advisor choose the bits to describe how many of the Turing machines halt in binary, wait until that many halt, and output that the remainder do not halt.

This argument is a simple variant of the proof that Chaitin's constant can be used to solve the halting problem. What surprised me is that it is sharp.  There is no computable map from a description of $2^n$ Turing machines and an $n$-bit advice states to $2^n$ bits of halting output that gets the right answer, for each tuple of Turing machines, for some tuple of bits. If there were, we could produce a counterexample by diagonalizing, with each of the $2^n$ Turing machines simulating what the program does on one of the $2^n$ possible arrangements of the $n$ bits and then choosing its own halting state to violate the prediction.

It is not possible to compress information about the halting problem for Turing machines with a halting oracle at all (without access to some kind of oracle yourself). The machines can just simulate what you predict on all possible inputs, ignoring the ones where you don't halt, and choosing their halting times to give the lexicographically first answer you didn't predict on any input.

This motivated me to think about what happens for other oracles:

  Is there an example of an oracle where the halting problem for Turing machines with that oracle can be compressed at an intermediate growth rate between linear and exponential?

More formally, given an oracle, let $f(n)$ be the greatest $m$ such that there exists a computable partial function from $m$ oracle Turing machines and $n$ bits to $m$ bits, such that for each $m$-tuple of oracle Turing machines, there is an $n$-tuple of bits, where the value of the function evaluated on that input equals the $m$-tuple of $1$ for each oracle Turing machine that halts and $0$ for each oracle Turing machine that runs forever.

Is there an oracle where $n<f(n)<2^{n}-1$? Is there an oracle where $\omega(n)=f(n)=o(2^n)$?


texts: Complexity of Finding the Eigendecomposition of a Matrix

texts:
My question is simple:

  What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?

Does eigendecomposition reduce to matrix multiplication or are the best known algorithms $O(n^3)$ (via SVD) in the worst case ?

Please note that I am asking for a worst case analysis (only in terms of $n$), not for bounds with problem-dependent constants like condition number.

EDIT: Given some of the answers below, let me adjust the question: I'd be happy with an $\epsilon$-approximation.  The approximation can be multiplicative, additive, entry-wise, or whatever reasonable definition you'd like.  I am interested if there's a known algorithm that has better dependence on $n$ than something like $O(\mathrm{poly}(1/\epsilon)n^3)$?

EDIT 2: See this related question on symmetric matrices.


texts: How much bigger does a precomputed lookup table get when salt is added?

texts:
I am trying to wrap my head around the benefits of salt in cryptography.

http://en.wikipedia.org/wiki/Salt_(cryptography)

I understand that adding salt makes it harder to precompute a table. But exactly how much harder do things get with salt?

It seems to me, like when you add salt, the number of entries in your precomputed table would = number of common passwords to precompute x number of entries in the password table (ie number of different possibile salts).

So if you have a list of 100 common passwords, then without salt, you would have 100 hashed passwords. But if you have 10 users on a system, with 10 different salts, then you would now have 1000 different combinations to check.

So as the numbers of users or the size of common password list increases, the precomputed table gets so big that you can't pre-compute it easily (if at all)

Am I getting this? Do I have it right?


texts:
I know that the question "does a first order formula $\phi$ have a model" is undecidable in general.

Could anyone give me a link or a book which give the answer for finite models. If I have a first order formula $\phi$, is it decidable whether $\phi$ has a finite model? I am pretty sure that the question is well known, but I do not even know where to begin the search for an answer. (For example, I would have expected it to be in Libkin's "Elements of finite model theory", but it seems that I can not find it.)

The second part of my question is: Are there known restrictions such that the problem is decidable?

For example, the problem may become decidable for first-order formula with only monadic predicates. Or when we have monadic predicate plus a successor relation. But I cannot imagine an algorithm to decide if there exists a (finite) model over those restrictions.


texts: Is there any justification to believe that $NL\neq L$?

texts:
I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?

It is known that $NL \subset L^2$.
The literature on derandomization of $RL$ is pretty convincing that $RL=L$.
Does anyone know about some articles or ideas convincing that $NL\neq L$?


texts: Is perfect zero knowledge sequentially composable without auxiliary input?

texts:
It is known that plain and computational zero knowledge proof systems are not sequentially composable without auxiliary input (see for example http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.7073). The proofs that I've found for this seem to rely on the fact that the transcripts generated by the simulator are only computationally or statistically indistinguishable from those generated by the verifier-prover interaction, so there is some "leeway" for the simulator to work with.

What about perfect zero knowledge proof systems, i.e. proof systems where the prover has unlimited computational resources and for any given verifier-prover pair, there exists a simulator with an identical statistical distribution of transcripts?

Are those sequentially composable without auxiliary input?


texts:
Consider the following algorithm:

Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time complexity, we want to measure the running time as a function of input size, so the complexity of this algorithm is $O(N)=O(2^{\lg N})$.  I have always felt a little uneasy that this simple algorithm is actually has an exponential running time.

More examples of such problems include integer factorization, knapsack (and a lot of other related papers Google throws up) which all have a running time that is pseudo-polynomial in the size of the input(also called as weakly NP-complete problems). Is there any survey/book that treats these problems in detail? Are there any interesting aspects of these problems (as in, they have some properties that characterize them distinctly from strongly NP-complete problems) that are well-known?


texts: Are register based machines on von neumann architecture diametrically opposed to functional programming style?

texts:
We are so used to von neumann architecture and say a register machine like the x86. (Also with   programming languages built for those machines x86 assembly, C, etc)  Is that approach to computing completely separate from a language and system like haskell?

What would a machine look like that was based functional programming paradigms look like? and  one not running on a register or stack machine.

This article is relevant to my question:

http://www.stanford.edu/class/cs242/readings/backus.pdf


texts: Find all hyperplanes separating unique sets of `k` points

texts:
I have a series of n points in d-dimensional continuous space.  I want to find a series of hyperplanes such that k points are below the hyperplane and that the set of k points below each hyperplane is a unique set.  It does not matter what the hyperplane is (e.g. if it connects d points or if it is another hyperplane not intersecting any points).  I can discretise the space if it helps.  "below" is defined as the negative direction for the first dimension.

The way I have approached is to try all hyperplanes defined by all sets of d points, project each point on to this hyperplane, and test if the projection is above the point.  This results in n^(d+1) complexity.

Is there a better way?  What is it?


texts: The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

texts: How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?


texts:
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every function in that class.
It is known that $\epsilon$-biased spaces fool the class of parities over subsets. (see Alon-Goldreich-Hastad-Peralta for some nice constructions of such spaces). The question I want to ask is a generalization of this to arbitrary symmetric functions.

  Question: Suppose we take the class of arbitrary symmetric functions
  over some subset, do we have
  distribution (with small support) that
  fools this class?

Some small observations:

It is sufficient to fool exact thresholds ($\text{ETh}^S_k(x)$ is 1 if and only if $x$ has exactly $k$ ones amongst the indices in $S$). Any distribution that $\epsilon$-fools these exact thresholds will $n\epsilon$ fool all symmetric functions over $n$ bits. (This is because every symmetric function can be written as a real linear combination of these exact thresholds where the coefficients in the combination are either 0 or 1. Linearity of expectation then gives us what we want)
A similar argument also works for general thresholds ($\text{Th}^S_k(x)$ is 1 if and only if $x$ has at least $k$ ones amongst the indices in $S$)
There is an explicit construction of a distribution with support $n^{O(\log n)}$ via Nisan's PRG for LOGSPACE.
Arbitrary $\epsilon$-biased spaces will not work. For example if $S$ is the set of all $x$ such that the number of ones in x is non-zero mod 3, this is actually $\epsilon$-biased for very small $\epsilon$ (from a result of Arkadev Chattopadyay).   But clearly this does not fool the MOD3 function.

An interesting subproblem may be the following: suppose we just want to fool symmetric functions over all n indices, do we have a nice space? By the above observations, we just need to fool the threshold functions over $n$-bits, which is just a family of $n+1$ functions. Thus one can just pick the distribution by brute-force. But are there nicer examples of spaces that fool $\text{Th}^{[n]}_k$'s for every $k$?


texts: Axioms of Minimum Size Resolution Refutations

texts:
Let $\phi$ be an unsatisfiable CNF formula and let $\Pi$ be a resolution refutation of $\phi$ of minimum size. Let $\psi$ be the subformula of $\phi$ containing the clauses that actually appear as axioms in $\Pi$. Is there anything interesting that can be said about $\psi$?

Some specific questions:

Is $\psi$ minimally unsatisfable? (i.e., are all proper subsets of $\psi$ satisfiable?)
Are all variables appearing in $\psi$ necessary for unsatisfiability? (i.e., is there an assignment to all but one variable that does not falsify any clauses in $\psi$?)
Is $\psi$ a minimum unsatisfiable core of $\phi$?

All of these properties seem unlikely to hold in general but I cannot think of any counterexamples.


texts: Maximizing a convex function with linear constraint

texts:
The problem is
$$\max  f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$

where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$,
$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$, and
$\mathbf{A} \in \mathbb{R}^{M\times N} $

$f(.)$ is in the form of $\sqrt{1+y^2}$. Hence f(.) is a convex function.
which is bounded in $[\sqrt{2}, 2]$.

I am looking for efficient algorithms which solve the above problem or convex maximization problem, in general.

Also, is it possible to solve the above problem using standard convex optimization tools by putting more constraints?


texts: Is $AC^0$ with bounded fanout weaker than $AC^0$?

texts:
In the survey "Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2), I read the following sentence:

  The classical version of $QAC^0$ (in which $AND$ and $OR$ gates have at most constant fanout) is provably weaker than $AC^0$.

A reference for this claim is missing. I will call this class $AC^0_{bf}$, where $bf$ stands for "bounded fanout". (The Complexity Zoo is down and I can't verify if such class has already a name in the literature).
If we assume unbounded fanout for the input bits, then these circuit seem to be equivalent to constant depth formulae up to a polynomial increase in the size, so the above claim doesn't make sense.
Instead, if we assume bounded fanout for the input bits too, then I cannot think of any language that separates this class from $AC^0$. A possible candidate could be the language $X := \{x | \mbox{weight}(x) = 1 \}$, i.e., the language of the strings with only one 1. It is easy to show $X \in AC^{0}$, but I didn't manage to prove that $X \notin AC^{0}_{bf}$.

The questions are:

  Is $AC^0_{bf}$ actually weaker than $AC^0$? If it is, any idea or any reference on how to prove it? And what is a language that separates those two classes? What about $X$?


texts: What are some examples of algorithmic applications of noncommutative rational identity testing?

texts:
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.

The related problem of noncommutative rational identity testing (NCIT) is known to have a deterministic polynomial algorithm.

I've seen many algorithmic applications of PIT, that work by reducing the detection of some combinatorial object (e.g. existence of a Hamiltonian cycle in a graph) to the verification that a polynomial corresponding to that object is nonzero.

Are there any analogous algorithmic applications of NCIT?


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

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

Given:

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

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

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


texts: NP-hardness of coloring uniform hypergraphs

texts:
Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable  for $k=1,2$  is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen proofs in many places.

The situation changes if we look at $s$-uniform hypergraphs for $s \geq 3$, then the problem of deciding if an $s$-uniform hypergraph is $2$-colorable becomes NP-hard. I have read this fact multiple places, but without reference. What is the reference for classifying when the problem of deciding if an $s$-uniform hypergraph is $k$-colorable is NP-hard?


texts: Do dependent types give you everything subtyping does?

texts: Types and Programming Languages focuses quite a bit on subtyping, but as far as I can tell, subtyping doesn't seem especially fundamental. Does subtyping give you anything more than dependent types do? Working with dependent types is bound to be more work, so I can understand why subtypes might be useful in practice. However, I am more interested in type theory as a foundation for mathematics than as a basis for programming languages, should I pay much attention to subtyping?


texts: Partition planar graph of vertices with at most degree 3 into connected subgraphs

texts:
I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) connected subgraphs of size at most k. The graph I am working with is planar and each vertex has degree at most 3.

I know that graph partitioning is in general NP-hard, but I was hoping that there is some polynomial time algorithm or approximation algorithm that could solve this problem. If anyone has a reference to some paper that deals with this problem or has a solution themselves, I'd love to hear from you.

EDIT: If you also have an algorithm that covers the graph, rather than partition, post that as well!


texts:
Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number.  I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t.

$$H\left(X~|~\{X_0,\ldots,X_k\}\right) = 1-\frac{k}{n}$$

That is, each additional $X_k$ provides $1/n$ of the information of $X$, until everything is revealed by $X_n = X$.  Is there a nice construction for this sequence?


texts: Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

texts:
Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the promise that the language accepted by this automaton $L(M)$ is a deterministic context-free language and outputs a deterministic pushdown automaton $N$ which accepts precisely the language accepted by $M$?

An equivalent problem would be to construct an algorithm which takes as input a pushdown automata $M$ (with the promise that $L(M)$ is deterministic, as above) and a deterministic pushdown automata $N$. The output would be yes if $L(M) = L(N)$ and no if $L(M)\neq L(N)$.

I believe that an algorithm solving the first would give an algorithm solving the second by the decidability of equivalence of deterministic pushdown automata. I think a solution to the second would imply a solution to the first as we enumerate all deterministic pushdown automata and run the algorithm on them one by one, once we get a yes instance we output that automaton.

I wonder if anyone knows anything about this? Maybe it's a known problem and/or has a known solution? As an aside, I believe it is decidable if you introduce the restriction which says that the language generated by the PDA is the word problem of a group.


texts: Minimum length walk from s to t covering a subset of vertices

texts:
I want to find the current literature for the following problem (I have searched
on google/asked friends/some Profs didn't get much useful results yet):

  Input: weighted undirected graph G = (V,E), $S \subseteq V$, $ s, t \in V$, $ w : E \mapsto R^+$

  Output: A walk W = $(s,v_1, v_2,..,v_k, t)$ of minimum length such that:

  1) $I = \{v_i : i \ge 1 \wedge i \leq k\}$, $S \subseteq I$
  2) $ (s, v_1), (v_k, t) \in E$
  3) $ (v_{i-1}, v_i) \in E$  $\forall i \geq 2,i \leq k$
  4) Length of walk is = $w(s,v_1) + w(v_k,t)$ + $\Sigma_{i=2}^k w(v_{i-1}, v_i)$

I know this is somewhat related to TSP/Hamiltonian paths but I think that it is significantly different.
I came to investigate this problem because I am thinking about solving this problem in a special
geometric setting. So, It would be helpful If I could get to know the complexity class to which it is known to
belong and any results for planar graphs, grid graphs.

Thanks,
Rizwan.


texts:
Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.

I know about the NP-completeness of determining interval numbers but the above problem is different.
Now, in the literature I found this work by A. Gyárfás and D. West on multitrack interval graphs but I'm not sure if it is relevant to above problem.

Any citation to existing literature on the above or similar problem would be helpful. Also please let me know if there is a formal name for the above problem.


texts: What are the algorithms and the data structures for GUIs and input management?

texts:
I'm studying how, given:

an input from the user ( like a click of the mouse or the input from a key )
a well defined data structure that represent the graphical layout inside a window ( a tree/graph like structure for now )

I could possibly create what is generally called as a "G/UI toolkit", which means that I should be able to create a responsive UI and a mapping between the input from the user and the functionality given to the UI itself.

I found absolutely no paper, no technical explanation, no articles, about both the data structure and the algorithms used to perform this kind of mapping, and I'm wondering if someone could help me with this.

I found some sparse reference to some tree-like data structure like kd-tree or quadtree that are used to subdivide the 2D space in the window and so when the signal will be fired, the coordinates generated by the signal, the click of a mouse, will be injected in the tree to find the corresponding widget to activate.
This approach feels really old and I don't think it will scale that well.

I also found some reference to what is called the third generation of rasterizers and UIs which seems to be based on linear algebra/vectors and sounds really nice because it's highly scalable and simple to reason about, the problem is I can't see any implementation or algorithms or data structures.

Someone can point me in the right direction ?


texts: Complexity of reachability in linear dynamical systems over finite fields

texts:
Let $A$ be a matrix over the finite field $\mathbb{F}_2 = \{0,1\}$ and $x$, $y$ be vectors of the space $\mathbb{F}_2^n$. I am interested in the computational complexity of deciding whether there exists $t \in \mathbb{N}$ such that $A^t x = y$, i.e., in the reachability problem for linear dynamical systems over finite fields.

The problem is clearly in $\mathbf{NP}$ (guess $0 \le t < 2^n$ and compute $A^t$ in polynomial time by repeated squaring). Me and my colleagues were also able to prove the $\mathbf{NP}$-completeness of the related problem of establishing whether there exists $t \in \mathbb{N}$ such that $A^t x \ge y$, where $\ge$ is componentwise inequality.

This problem seems quite natural, but I have not been able to find references to its computational complexity in the literature, probably because I am not aware of the exact terminology. Do you know if the problem with the equality is $\mathbf{NP}$-complete or if it is actually in $\mathbf{P}$?


texts: Graph rewriting with one-to-many pattern matching?

texts:
In the single-pushout approach to graph rewriting, many nodes in a pattern graph can be matched to a single node of a target graph.

My question is if there is a notion of graph rewriting where the inverse is true: that a single node in the pattern graph can match to many nodes of the target graph. For example, the pattern graph $A \rightarrow B$ should be able to match a subgraph isomorphic to $X \rightarrow Y \leftarrow Z$, with the mapping $A \mapsto \{ X, Z \}, B \mapsto \{Y$}.  I'm especially interested in a definition where $A \mapsto \{X\}, B \mapsto \{ Y\}$ would not be a valid match for any graph that contains $X \rightarrow Y \leftarrow Z$ as a subgraph.

As an example application, consider the problem of for-loop desugaring. This for-loop:

for (int i = 0; i < n; i++) {
  if ( i % 3 == 0) {
    printf("Divisible by 3\n");
    continue;
  }
  printf("%d\n", i);
}

desugars to:

int i = 0;
while (i < n) {
  if (i % 3 == 0) {
    printf("Divisible by 3\n");
    i++;
    continue;
  }
  printf("%d\n", i);
  i++;
}

A key part of this desugaring -- that the "step" part of the for loop be inserted at the end of the loop and before every "continue" statement -- is most easily expressed as a rewrite on the control-flow graph, where that statement is inserted before every predecessor of the condition (except for before the loop runs).


texts: Convex mixed linear integer programming with real nuclear norm objective and linear integer objective

texts:
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ over integer points in a convex set in $\Bbb R^k$. Is similar parametrization possible with nuclear norm?

This is my reasoning nuclear norm is convex and algebraic and therefore there has to be a semialgebraic convex representation. Then by Heinz https://core.ac.uk/download/pdf/81196255.pdf it should be fixed parameter polynomial time.

The precise problem is as follows:

We have $n$ integer variables
We have $r$ real variables
We have $m$ convex semi algebraic constraints with only integer variables
We have $t$ polyhedral constraints with real and integer variables
We have a linear or semi algebraic convex objective function that depends only on integer variables
We have a nuclear norm minimization objective function that depends only on real variables

Is it possible to find a feasible solution in $O(n^{poly(n)}poly(rmt))$ time or at least in time $O((rn)^{poly(rn)}poly(mt))$?

At least without $5$ (no integer objective but only nuclear norm objective) can we do this in the time mentioned?


texts: Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

texts:
1)
Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops can be combined to one loop. If $A$ contains more loops in sequence, then these loops can also be combined to one loop.
So suppose that $A$ contains exactly one loop. Since $A$ must finish the factorization after finitely many steps and output $x$ with $1 < x < n$, $x|n$, there must be an if-then statement which tests if $1 < x < n$, $x|n$ or any other mathematically equivalent test. Hence in each step $1,\cdots,t$ we have a number $a_i \in \mathbb{N}$ which is tested. But then letting $g_i = \gcd(a_i,n)$ we have $1 \le g_i \le n$. It could happen that $g_i = g_j$ for $i \neq j$.

Heuristic: We imagine that the numbers $g_i$ are drawn with replacement from the urn $\{1,\cdots,n\}$.

2) Let $n=pq$ be the prime decomposition of $n$ and let $n=2^e$.
Let us suppose that $p \equiv q \equiv \sqrt{n}$.
Let $p_n$ be the probability to have a number $1 \le x \le n$
with $1 < \gcd(x,n) < n$ and as such to also have a non-trivial factor of $n$.
Then we have
$$p_n = 1-\frac{\phi(n)}{n}=1-\prod_{p|n}{(1-\frac{1}{p})} = 1-(1-\frac{1}{p})(1-\frac{1}{q}) $$
$$ = 1-(1-\frac{1}{\sqrt{n}})^2 = 1-(1-\frac{1}{\sqrt{2^e}})^2 $$
Suppose there exists a factoring-algorithm which runs in polynomial time $f(e)$ which draws with replacement a number $x$ and computes $\gcd(x,n)$.
Let $X$ be the number of numbers $x$ with $1 \lt x \lt n$ and $1 \lt \gcd(x,n) \lt n$ which the algorithm
finds after $f(e)$ steps. Then by definition of the algorithm we must have
$ 1 = P(X \ge 1) $
But on the other hand we have
$$ P(X\ge 1) = 1 - P(X=0) = 1 - (1-p_n)^{f(e)}  $$
$$= 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} $$
The last equality is by definition of the algorithm valid for every $e$.
But for $e \rightarrow \infty$ we have
$$1 = P(X \ge 1) = 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} \rightarrow_{e \rightarrow \infty} 0$$
hence for $e \rightarrow \infty$ we have the contradiction $1 = 0$.

My question is, if someone has an idea how to replace the condition $p \equiv q \equiv \sqrt{n}$ with a more rigorous condition.
My second question is, how does one prove, that no (general purpose) factoring algorithm can do without a loop? Maybe using Kolmogorov complexity of the primes to be factored?

Edit:
As @D.W. pointed out the heuristic with $g_i$ is clearly wrong. What I meant to write is that we imagine that the $a_i$ are chosen with replacement from the urn $\{m,m+1,\cdots,M-1,M\}$, where
$ m = \min_i(a_i), M = \max_i(a_i)$. Let $N= M-m+1$ and $N_1 = |\{ k | m \le k \le M, \gcd(k,n)=1 \text{ or } \gcd(k,n)=n\}|$. Then the probability $p_n$ to have a non-trivial factor of $n$ is $p_n = 1 - \frac{N_1}{N}$
If $X$ counts the number of successes of the algorithm , then by definition of the algorithm we must have:
$$1 = P(X \ge 1) = 1-P(X=0) = 1-(1-p_n)^t$$
Now for this argument to be valid, one would need a number theoretic formula for $N_1$.
Also what I meant with loop is not the reading of the number $n$ but a loop for "the search for the solution".
If there is such a loop which produces the numbers $a_1,\cdots,a_t$ then there must be a criterion to stop the loop after $t$ steps.
The loop will terminate earliest when an $x$ ( a solution) such that $1<x<n$ and $1 < \gcd(n,x) < n$ is found. So in this fashion, one might see the statement, "there must exist an if-then statement such that..".


texts: Approximation for counting the number of simple $s$-$t$ paths in a general graph

texts:
I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does anyone know of a good reference on this subject?

Background: counting the exact number of paths in a general graph is #P-complete but there may exist polynomial time approximations for the problem. I'm especially interested in random approximations.

Thanks in advance.


texts: Recent publications on NP ?= coNP question

texts:
I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic.

For the record, I know that this question is intimately connected to the question of whether P equals NP or not (such that if NP != coNP then P != NP).

Cheers,
Derek


texts:
I have defined a finite state machine

    Q = {Σ, S, s0, δ, F}

    where

    Σ = {'[r]equest', '[o]ut', '[i]n', '[e]nd'}

    S = {'[R]eady', '[I]nitiating', '[W]aiting', 'Re[C]eived', 'Re[S]etting'}

    s0 = R,

    F = {R}

    δ =  (q ∈ S and x ∈ Σ)

     q      x      q
    -------------------
     R      r      I
     I      o      W
     W      i      C
     C      e      S
     S      ∈      R

However, I have a transition from  W to S via a temporal event†. How should I represent it?
If I add an epsilon-move
     W    ∈      S
it is not intuitive that it is a temporal event.

†possibly a timeout


texts:
Consider a convex optimisation problem in the form

$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$

where $f_0, f_1, \dots, f_m$ are convex functions. Without loss of generality, we can assume that $f_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln (n/\varepsilon))$ computations of the values and $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that

$$p(n,m) = n^3 (m+ n), \qquad q(n,m) = n^2$$

At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(\cdot)$ expressions are somehow dependent on the functions $f_i$, e.g., on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. this discussion on MathOverflow.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(\cdot)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.


texts: Is the lower bound proof in this paper correct?

texts: In this paper on "Circle Packing for Origami Design Is Hard" by Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, on page 15, figure 13, they claim that the side length of the smallest square that encloses two circles of area 1/2 each is 1.471299. By my calculations I am getting side length 1.362 and area 1.855. Have I made a mistake or is there a mistake in the paper?


texts: Function input to output size relationship. What is it? Any notable research on it?

texts:
I'm working on a problem and I've come to a point where I need to define the input/output complexity of an algorithm. I don't remember ever studying this systematically like I did time complexity or space complexity, so what are some notable papers that deal with this problem?

Note: I'm calling it input/output complexity, but I have no idea what the actual name of this is, that would be helpful to know too! Incase it's unclear I am calling the relationship between a functions input and it's output, "Input/Output Complexity"

Examples:

F({1,2,3,4}) = {1,2} //where the relationship is n/2
F(some 20 byte input) = 2bytes of header + 10bytes of output //the relationship is 2+n/2
F(2 byte header + 10byte data) = 6 bytes output // n3/5 - 2

A more concrete example would finding be the average and best input/output complexity of a compression algorithm

Defining this is out of scope of my paper so I am hoping to find a definition/solution to reference.


texts: What is the VC dimension of Turing machines with specified maximum size?

texts:
Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.

I chose Turing machines in the question to make the question concrete, but I'm also more generally interested in known VC bounds for Turing-complete languages with a limit on the program length (to avoid infinite vc dimension).

The closest I've seen is this article giving VC dimension for recurrent neural nets, which can be Turing complete, but have finite VC dimension in terms of the number of weights and the length of the inputs.


texts: Are there semi-decision procedures for this theory?

texts:
I have the following typed theory

|- 1_X : X -> X
f : A -> B, g : B -> C |- compose(g,f) : A -> C
F, f : A -> B |- apply(F,f) : F(A) -> F(B)

with equations for all terms:

f : A -> B, g : B -> C, h : C -> D |- compose(h,compose(f,g)) = compose(compose(h,f),g)
f : A -> B |- compose(f,1_A) = f
f : A -> B |- compose(1_B,f) = f
F |- apply(F,1_X) = 1_F(X)
f, f : A -> B, g : B -> C |- apply(F,compose(g,f)) = compose(apply(F,g),apply(F,f))

I am looking for a semi-decision procedure that will be able to prove equations in this theory given a set of hypothetical equations. It is also not clear whether a complete decision procedure exists or not: There doesn't seem to be any way to encode the word problem for groups into it. Neel Krishnaswami showed how to encode the word problem into this, so the general problem is undecidable. The associativity and identity subtheory can easily be decided using a monoid model of the theory, while the full problem is harder than congruence closure. Any references or pointers would be most welcome!

Here is an explicit example of something we would hope to be able to automatically proved:

f : X -> Y, F, G,
a : F(X) -> G(X), b : G(X) -> F(X),
c : F(Y) -> G(Y), d : G(Y) -> F(Y),
compose(a,b) = 1_F(X), compose(b,a) = 1_G(X),
compose(c,d) = 1_F(Y), compose(d,c) = 1_G(Y),
compose(c,apply(F,f)) = compose(apply(G,f),a)
|- compose(d,apply(G,f)) = compose(apply(F,f),b)


texts: Set-systems with some version of independence

texts:
Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is,
$$
\Pr_{\substack{T\subset [N]\\|T| = m}} [|T \cap S| > k] \quad=\quad p
$$

Question: Given a (sane) parameter $t$, is there an explicit family of sets $\mathcal{F} = \{ S_1,\dots S_t \}$, where each $S_i$ is a subset of $[N]$ of size $n$ such that:
$$
\Pr_{\substack{T\subset [N]\\|T| = m}} [\forall i \in [t] \;:\; |T \cap S_i| > k] \quad \leq \quad p^{t/1000}
$$
Here are some examples for which such a bound holds:

If each $S_i$ is picked at random, then the probability is $p^t$, as the events are truly independent.
If each $S_i$ is disjoint, then the probability is $p^t$ (again as the events are independent).
If $t$ is large enough to allow $\mathcal{F}$ to be the set of all subsets of size $n$, then any choice of $T$ would surely miss some set (if $m \ll N$)

The sort of set system I have in mind is something like a Nisan-Wigderson design (where pairwise intersection between the $S_i$'s are small, and $t \gg N$). The vague intuition is that mutually disjoint sets are independent events, and for  almost disjoint sets we ought to have an exponential drop (maybe not $p^t$, but $p^{t/1000}$ or $p^{\sqrt{t}}$ or something).


texts: Splitting a graph into minimum number of subpaths

texts:
I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There is no edge greater than L. How to find out the minimum number of paths neccessary and how to find out these paths?

First I thought about Chinese Postman, but it gives one big path, which might not be the optimal solution. I also thought about bin packing problem, but I am not sure how to ensure the edges in every "bin" form a path.


texts: What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (which also appears as Chapter 1 of his book "Selected Papers on Analysis of Algorithms")?


texts: Are social networks typically good expanders?

texts:
I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility of these graphs. One basic question is: Are these graphs typically good expander graphs?

Has anyone checked, say, the facebook graph's spectral gap? Or the spectral gap of other large real-world networks? I am hoping that someone can point me in the right direction to learn about this topic.


texts:
I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where
$f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ in polytime such that $f$ has a real root iff $g$ has a real root in [0,1]$?


texts: Does simulating chiral gauge theories lie within BQP?

texts:
In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated in a limit computable manner efficiently on a quantum computer. However, there is the challenge of finding an efficient limit computable simulation of chiral gauge theories on a quantum computer. Does this problem lie within $\mathsf{BQP}$?

[1] Richard P. Feynman. Simulating Physics with Computers. International
Journal of Theoretical Physics, Vol. 21, Nos. 6/7, 1982


texts:
Acer et al. "Finite-time Analysis of the Multiarmed Bandit Problem" show that the Upper Confidence Bound 1 (UCB1) algorithm has expected regret bounded by

$$\left[ 8 \sum_{i: \mu_i < \mu^\ast} \frac{\log n}{\Delta_i} \right]+ \left(1 + \frac{\pi^2}{3}\right) \sum_i \Delta_i$$

when run for $n$ steps, where $\mu_i$ are the means of the $K$ arms, $\mu^\ast = \max_i \mu_i$, and $\Delta_i = \mu^\ast - \mu_i$.

However, this bound explodes as any $\Delta_i \to 0$, i.e. when there a nearly optimal non-best arm.  Certainly the true expected regret does not go singular in this case (for any strategy), and intuitively I would expect UBC1 to do fairly well if there are several nearly optimal arms.

Question 1: Is there a nice regret bound for UCB1 which doesn't have this singularity?

Question 2: If no, is there a modified version of UCB1 with such a nonsingular bound?


texts: Zero Obstructed vertex induced subgraphs

texts:
Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:

It has no isolated vertices.
It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).

Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j < i$.

Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.

I'm interested in $0$ obstructed vertex induced subgraphs.

  Questions

  Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.
  If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?
  If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?

I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.

Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.


texts: $BPL$ with polylog random bits is in $L$

texts:
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.

My question is about a $BPL$ machine that uses only polylog many bits of randomness. In one of Goldreich's papers, it is mentioned in passing that a language decided by such a $BPL$ machine is actually in deterministic logspace $L$. But I am unable to find any explanations of this remark anywhere.

Why can it be derandomized completely in logspace?


texts: Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

texts: Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in multitape Turing machine model.


texts: How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d?

texts:
An $\varepsilon$-net for a range space $(X,\mathcal{R})$ is a subset $N$ of $X$ such that $N\cap R$ is nonempty for all $R\in \mathcal{R}$ such that $|X\cap R| \ge \varepsilon |X|$.

Given a range space $(X,R)$ of VC-dimension $d$, an $\varepsilon$-net of size $O\left(\frac{d}{\varepsilon}\log\left(\frac{d}{\varepsilon}\right)\right)$ can be computed in time $O(d)^{3d}\left(\frac{1}{\varepsilon^2}\log\left(\frac{d}{\varepsilon}\right)\right)^d|X|$ (see [1], Thm 4.6).

To what extent is the $O(d)^{3d}$ term intrinsic to this problem?  Specifically, can it be improved to $2^{O(d)}$?  Are there lower bounds known?

A related question: are there general conditions on $(X,R)$ for which such an improvement is known to exist?

[1] Bernard Chazelle.  The Discrepancy Method.  2000.


texts: What are alternatives to the random oracle model for modelling hash functions?

texts:
I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as having been picked from a family of functions). Are there any other?

EDIT -- To make my question less vague: It seemed to me that the ROM or CRS was not modeling what a hash function is in reality and so proofs of security in the ROM model were problematic (considering all real hash functions are deterministic, keyless, and WILL always have collisions that can be found -- facts ignored by ROM and CRS). So I was looking for alternatives.

David Cash pointed out the Rogaway paper that deals exactly with the problem I'd been having. His reply below summarizes how the paper deals with this issue -- i.e., by requiring the explicit knowledge of the collision finding algorithm by an adversary.


texts: What is the origin of logical relations?

texts:
I actually have two questions:

Who first used logical relations to relate semantics?

I traced them back to Reynold's "On the Relation Between Direct and Continuation Semantics", but I can't claim to have made an exhaustive search.

I have found references to logical relations dating earlier (Tait, '67), but not for relating semantics.
What is the best current introduction for logical relations?

I know of Mitchell's "Type Systems for Programming Languages" from the Handbook of TCS. What other expositions are there?


texts: Hardness of Horn-modulated Satsifiability problem?

texts:
It is known that there is sharp complexity jump between Horn 3-SAT and 3-SAT problems. The former is $P$-complete while the later is $NP$-complete. I would like to see a continuous spectrum of hardness variation between these two problems.
I'm interested in finding the influence of the number Horn clauses in general 3-SAT problem. Suppose the number of Horn 3-SAT clauses in input 3-SAT formula is given as a function $f(n)$ in the number of variables $n$. What is known about the complexity of the 3-SAT(f) problem where $f(n)$ is one of the following cases:

1- $f(n)$ is $O(1)$

2- $f(n)$ is $O(\log n)$

3- $f(n)$ is $\Omega(n)$

4- $f(n)$ is $o(n)$

My intuition is that the first case is tractable while the third one is intractable. Also, I guess the second case is of intermediate complexity (NPI). What is known about the complexity of this problem? I'm looking for formal proofs of complexity?

EDIT: There is no restriction on the number of anti-Horn 3-SAT clauses. A 3-SAT clause must be either Horn or anti-Horn but not both.


texts:
In Luo's UTT (type theory which is used in Agda, Idris, and other dependently typed programming languages), there're are two rules for $\Pi$ types. One for $\mathsf{Prop}$ and one for $\mathsf{Set}$. In the one for $\mathsf{Prop}$ we have no constraints on the universe of a parameter. In the one for $\mathsf{Set}(i)$, we have.

Why it was done in this way? Will anything bad happen in such a case?

P.S. Basically I want to understand why $\mathsf{Prop}$ has special treatment in the theory. I.e. why we can't choose $\mathsf{Type}(0)$ for propositions, then removed the $\mathsf{Type}(i)$ condition in the $\Pi$ types' argument, and as a consequence have more uniform set of axioms.

P.P.S. In Luo's thesis I read that Calculus of inductive constructions (CIC) where this universe was introduce was created as a mix between Martin-Löf type theory (MLTT) and System F. Does $\mathsf{Prop}$ correspond to the union of all the existing universes?

P.P.P.S. UTT is described in Luo's PhD thesis and book here: http://www.cs.rhul.ac.uk/home/zhaohui/books.html


texts:
I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. $r_1\vee r_2=( r_1\cup r_2)^+$, where ${}^+$ is transitive closure.

I'm interested in the residual $\ominus$ to $\vee$. Standard residual theory seems to tell me that $r_2\ominus r_1= \bigvee\{ r\mid r\vee r_1\subseteq r_2\}$.

Did I get this right? I'm not really on safe ground here... Also, this formulation is, well, somewhat indirect: does there exist a more direct formula?

Edit: To perhaps de-mystify this a bit, let me give the definition of residual: $\ominus$ is a residual to $\vee$ if it holds for all $r_1$, $r_2$, $r_3$ that $r_1\vee r_2\subseteq r_3$ iff $r_1\subseteq r_3\ominus r_2$. (Yes, this looks like adjoints in category theory; like adjoints, residuals are unique up to isomorphism if they exist.)


texts: High probable polynomial time algorithm for NP-hard problems?

texts:
Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the SAT problem. Randomly generated SAT problems are greatly different from industry collected SAT problems. The solvers behave quite different.

I am thinking about an approximation scheme that given an unknown distribution $D$ over the problem instances, there exists a polynomial time algorithm $A$ that solves the problems drawn from $D$ successfully with a probability $1-\eta$. $\eta$ somehow relates to the divergence between the $D$ and the random distribution.

Furthermore, if we have samples from $D$, we can estimate $A$, and address the sample complexity and the consistency issue.

I wonder whether such a scheme already exists or not. If so, what is the name and what are the milestones?


texts:
Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$.

Consider the following problem:

  Let $v_1,v_2,\cdots,v_n\in \mathbb{R}^k$, integer $m\le n$, and a target vector $t\in\mathbb{R}^k$, decide if there exist an index set $I\subset [n]$, such that
  $$\sum_{i\in I}v_i\succ t,$$and $|I|\le m$

Is this problem NP-hard? (Note that, when $k$ is not constant but scale as $n$, this problem is NP-hard by reduction from set cover problem.)

In particular, is this problem hard for $k=2$? (Note that, there is a pseudo-polynomial dynamic programming algorithm for integer vectors).


texts: Fast computation of Frobenius norm under memory limits

texts: Given a large dense matrix $A^{n \times n}$, that does not fit to the memory (RAM). Is there any fast way to compute the exact Frobenius norm of the matrix or its accurate approximation (perhaps, via sampling with reasonable bounds provided)? What if this matrix is a subtraction of two $n \times n$ matrices: $\| A - B \|_F$, where $A$ is sparse, and B is dense?


texts: Is there a name for this property of a term rewriting system?

texts:
Given TRS let's call it top-reducible or left-reducible if no rule's right hand side is contained in any rule's left hand side non-trivially.

A term A is contained in an other one B trivially if they overlap at their roots e.g. 2(y) is contained in 1(2(x)) non-trivially while 1(y) is contained in 1(2(x)) trivially) (I also don't know if this 'containment' has a name)

E.g.

A TRS with a single rule 1(2(x)) -> 2(x) is not top-reducible.
A TRS with rules 1(2(x)) -> 3(x), 4(3(5(x,y))) -> 1(5(x,y)) is not top-reducible.


texts: Barriers and Monotone Circuit Complexity

texts: Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit complexity. Is there any progress towards identifying such barriers ? Are there other barriers in the monotone setting ?


texts: Polynomial Time Algorithm for Graph Isomorphism Testing

texts:
"Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.

The paper is given in arXiv. The companion website gives a proof-of-concept program which runs the algorithm. (The password for the program is given in the paper.)

I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?


texts: Embedding a graph in the euclidean space

texts:
Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the opposite $||f(u)-f(v)|| > r$ for some given $r$.
One could also view this problem as embedding a unit disc graph back into the euclidean space.

Now I have been told that - while the problem is NP-complete - the usual way to do it is as follows. This is where the hearsay starts, so excuse me if I am a little vague.

The proposed approach places an arbitrary node at $0$. Then, run a linear (or quadratic?) program that maximizes $\sum_{v \in V} g(f(v))$ under the side condition stated above, i.e. for all edges $(u,v) \in E$, $(f(u) - f(v))^2 \leq r^2$. $g$ is probably some norm, maybe $L_1$ or $L_2$.

This is how I more or less understood it. The general gist was to fix the position of an initial node and then "spread" the graph apart using the linear program.

I tried to find some sources on that, maybe a paper that introduced this approach, but so far my efforts failed - there are just too many ways to embed a graph in the $\mathbb R^d$. In particular, I am interested in how this approach deals with noisy data. For example, consider a grid graph of size $n \times n$ which should be perfectly embeddable in the euclidean plane. Now, add an edge from $(0,0)$ to $(n,n)$. Intuitively, in an embedding I would like to ignore the edge since the rest of the graph is a perfect grid. The approach above, however, would most likely produce a weird embedding.

Can anyone give me some pointers to work describing this approach?


texts: Detecting bridges in Hypergraph S-t Reachability

texts:
Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, decide whether there exists a hyperarc $A=\langle X, y\rangle \in G$ so that removing $A$ makes target node $t$ unreachable from source nodes $S$.

I am using the usual notation of reachability in hypergraphs as follows: $t$ is reachable from $S$ if $t$ belongs to the minimum set $Z$ satisfying the two following conditions:

$S \subseteq Z$
For all $\langle X, y \rangle \in G$, if $X \subseteq Z$ then $y \in Z$.

Obviously, one can detect bridge arcs in quadratic time by first finding a path from $S$ to $t$ and, for each hyperarc in that path, checking in linear time if $t$ becomes unreachable from $S$ by removing that hypoerarc. I'm looking for anything that might improve on this quadratic upperbound.


texts: Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

texts:
The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description of the mathematical game to be played to make predictions on the outcome of  experiments performed in our Universe.

As I understand it, quantum physics, used to create models of quantum computation (as used, for example, in the construction of Shor's algorithm) is a mathematical game contained within the Standard Model. Thus, in this sense the Standard Model is a generalization of quantum physics.

Is it at all conceivable that the Standard Model can allow for the construction of more general Standard Model computers? Or is there an obvious reason why quantum physics extracts all the benefit modern physics brings over classical models of computation and thus computer scientists should only reason according to quantum physics? Has any fundamental work been done on this? Is my question even well posed? Supposing that a Standard Model of physics computer could be a well-posed mathematical object more general than quantum computers, is there any reason at all to think that there could be any use to reasoning about that? Has there been any work done related to this question?

More informally, you might think of this question as something of the form "could we make a 'Higg's Boson' computer?" a rather natural justification for research in particle physics. Note that I know very little of the Standard Model (but a good deal about quantum physics) so this question might be ill posed, and if so, knowing that would be a clarification of my understanding.


texts: Is the primality problem with unary input NLOGSPACE-Hard?

texts:
Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard?

The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my automata research.


texts:
Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$.
Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to final distance:
$$ \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \}$$

There are other measures of quality though: Dhamdhere et al study the "average" distortion:
$$ \sigma = \frac{\sum d(x,y)}{\sum f(\mu(x), \mu(y))}.$$

However, the measure I'm interested in here is the one used by MDS-like methods, which looks at the average additive error:
$$ \varepsilon^2 = \sum | d(x,y) - f(\mu(x), \mu(y))|^2$$

Although MDS-like methods are studied extensively outside the theoryCS community, I'm aware of only one paper (by Dhamdhere et al) that examines optimization under this measure, and that too for the limited problem of embedding onto the line ($Y = \mathbb{R}$) (side note: Tasos Sidiropoulos' 2005 MS thesis has a nice review of earlier work)

Is there any more recent work that people are aware of regarding rigorous quality analysis under this notion of error ? While these problems are generally NP-hard, what I'm more interested in are approximations of any kind.


texts: One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup attacks.  Do we have any similar result for other code based systems using codes other than goppa? There are many code based systems coming up (being proposed) regularly and I don't see if such resistance will be trivially adapted by such variants.


texts: Question on Turings Dissertation *Systems of Logic based on Ordinals*, Axiomatic Properties

texts:
I have a question on Alan Turing's Dissertation Systems of Logic Based on Ordinals, a scanned copy you can find here, or rewritten in LaTeX here, and also a copy of the published version here (but in section 3 I found some errors not present in the original scan, so maybe the original one is preferable).

The unclear paragraph comes quite early at the end of section two. After the abstract, introducing the $\lambda$ calculus and what it means for a function to be "effective calculable" he writes:

  Those computable functions which take only the values $0$ and $1$ are of particular importance, since they determine and are determined by computable properties, as may be seen by replacing "0" and "1" by "true" and "false". But, besides this type of property, we may have to consider a different type, which is, roughly speaking, less constructive than the computable properties, but more so than the general predicates of classical mathematics. Suppose that we have a computable function of the natural numbers taking natural numbers as values, then corresponding to this function there is the property of being a value of the function. Such a property we shall describe as "axiomatic"; the reason for using this term is that it is possible to define such a property by giving a set of axioms, the property to hold for a given argument if and only if it is possible to deduce that it holds from the axioms. Axiomatic properties may also be characterized in this way. A property $\psi$ of positive integers, such that $\psi(x)$ is true if and only if there is a positive integer $y$ such that $\psi(x,y)$ is true. Or again $\psi$ is axiomatic if and only if there is a W.F.F F such that $\psi(n)$ is true if and only if F(n) conv 2.

I do not understand what he wants to say here. My ideas are, that with computable functions he always means total computable functions (otherwise the term property would not make much sense, and how I interpret the statemets). So, a property $\psi(x)$ is axiomatic if there exists some total computable function $f : \mathbb N \to \mathbb N$ such that $\psi(x)$ holds iff $x \in f(\mathbb N)$. So as $f$ is computable, it is given by some set of recursive equations (the axioms), and by totality we can successively "derive" the equations $f(1) = ..., f(2) = ..., f(3) = ...$ and so on, and if we find some equation of the form $f(k) = x$ we know that $\psi(x)$ is true, and if not than we will not find such an equation (or a "proof" of this equation).

But now to his other characterisation: A property $\psi$ is axiomatic iff there is a computable property $\phi$ of two positive integers, such that $\psi(x)$ is true if and only if there is a positive integer $y$ such that $\phi(x,y)$ is true. For one direction, I guess what he means is the property that $\phi(x,y)$ is true iff $f(x) = y$, and this surely is computable if $f$ is computable. But just given such a property, how can $f : \mathbb N \to \mathbb N$ look like? Maybe he meant partial computable functions, then for each $x$ we can search for an $y$ which makes $\phi(x,y)$ true, and take some as an image, but then my first interpretation would not make any sense...

So, could someone explain what Turing meant here?


texts: Nominal Tree Languages i.e. with Binders and Infinite Symbols?

texts:
I'm wondering if there has been any research done into automata that accept languages of trees that can bind arbitrary variables, and are considered equal under alpha equivalence.
I've found so far:

Dependency Tree Automata which seems to only support a finite set of bound variables, given beforehand
Nominal Regular Languages which supports an unbounded number of variables, but only on words, not on trees. So it can't support i.e. sets of $\lambda$-calculus terms, just sequences of commands.
Higher-order model checking which seems to only support checking of there is 0 or 1 trees in a given language, but doesn't do i.e. intersection, union, or other set operations.

I'm basically looking for a way to categorize languages of $\lambda$-calculus terms, but only considering structure i.e. I don't need to reason about $\beta$-reductions. I need a class of languages that is closed under union and intersection, with decidable emptiness checking.
Does anything like this exist?


texts: Is there a pair of different lambda terms in the normal form that behave identically when applied to any input?

texts: Let f and g be lambda terms in the normal form, such that f is intensionally different from g - that is, their string representation using bruijn indexes isn't the same. Is there any choice of f and g such that, for any x that is also a lambda term, f x == g x?


texts:
AFAIU, we don't know any problem
which is complete for $\mathsf{TC^0}$ w.r.t.
many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$).
On the other hand,
proving that they don't exist would separate $\mathsf{TC^0}$ from $\mathsf{NC^1}$,
i.e. we also don't know they don't exist.

I have seen a conjecture stating that
it is unlikely for $\mathsf{TC^0}$ to have any complete problem w.r.t. $\leq^\mathsf{AC^0}_m$ reductions.

  What is the intuition/evidence/argument behind this conjecture?
  For example, are there results that say "bad" things would happen
  if $\mathsf{TC^0}$ had complete problems w.r.t. $\leq^\mathsf{AC^0}_m$?
  Do we need the full power of Turing/oracle reductions
  for the completeness of the problems like majority?
  In other words,
  do we know any problem which is complete for $\mathsf{TC^0}$
  w.r.t. a weaker type of $\mathsf{AC^0}$ reductions?
  Do all known $\mathsf{TC^0}$-complete problems belong to
  the same equivalence class of $\equiv^\mathsf{AC^0}_m$?
  Or are there $\mathsf{TC^0}$-complete problems
  which are not known to be $\leq^\mathsf{AC^0}_m$ reducible to each other?


texts: Is there a definitive reference for Turing machines with multiple oracle tapes?

texts: Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a good paper or thesis which provides an overview of what is known about such machines? In particular I am interested in P with multiple oracles.


texts: An edge partitioning problem on cubic graphs

texts:
Has the complexity of the following problem been studied?

Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$

Question: is there a partition of $E$ into $|E|/3$ parts of size $3$ such that the sum of the orders of the (nonnecessarily connected) corresponding subgraphs is at most $t$?

Related work
I found quite a few papers in the literature that prove necessary and/or sufficient conditions for the existence of a partition into some graphs containing three edges, which is somehow related, and some others on computational complexity matters of problems that intersect with the above (e.g. the partition must yield subgraphs isomorphic to $K_{1,3}$ or $P_4$, and no weight is associated with a given partition), but none of them dealt exactly with the above problem.

Listing all those papers here would be a bit tedious, but most of them either cite or are cited by Dor and Tarsi.

20101024: I found this paper by Goldschmidt et al., who prove that the problem of edge partitioning a graph into parts containing AT MOST $k$ edges, in such a way that the sum of the orders of the induced subgraphs is at most $t$, is NP-complete, even when $k=3$. Is it obvious that the problem remains NP-complete on cubic graphs, when we require strict equality w.r.t. $k$?

Additional information

I've tried some strategies that failed. More precisely, I found some counterexamples that prove that:

maximising the number of triangles does not lead to an optimal solution; which I find somehow counter-intuitive, since triangles are those subgraphs with lowest order among all possible graphs on three edges;
partitioning the graph into connected components does not necessarily lead to an optimal solution either. The reason why it seemed promising may be less obvious, but in many cases one can see that swapping edges so as to connect a given subgraph leads to a solution with smaller weight (example: try that on a triangle with one additional edge connected to each vertex; the triangle is one part, the rest is a second, with total weight 3+6=9. Then exchanging two edges gives a path and a star, with total weight 4+4=8.)


texts:
Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as:

  $R_P(q) = \sum_{x \in P} q^{r(x)}$.

This definition can be applied to several interesting posets, for instance:

when $P$ is the Boolean lattice over $n$ elements, we have $R_P(q) = \sum_{i = 0}^{n} \binom{n}{i} q^i = (1+q)^n$,
when $P$ is the $n$-permutohedron, we have $R_P(q) = \prod_{i = 1}^{n} [i]_q$, where by convention $[n]_q = \sum_{i = 0}^{n-1} q^i$.
more generally, when $G \subseteq S_n$ is a permutation group with basis $B$, we may define the rank of an element $x \in G$ as the length of a minimum decomposition of $x$ over $B$.

The last case seems the most interesting: is it then possible to compute $R_P(q)$ in polynomial time given a presentation of $G$?

Also, are there other examples of graded posets for which a closed formula is known?


texts: Tiling a rectangle with weighted cells (min-max problem)

texts:
Given a sparse matrix $A[1..n, 1..n]$ containing cells with integer value of either $0$ or $1$, partition it in $J$ non-overlapping axis-parallel 2D rectangles, such that each $1$-cell is covered by exactly one rectangle, and a $0$-cell is covered by at most one rectangle. Given that weight of a rectangle is $a * \mbox{perimeter} + b* \mbox{sum_of_cell_values_inside}$, design an algorithm which minimizes the maximum weight of a rectangle.

Ideally, we would like an approximation algorithm with competitive ratio=2 and $O(n \log n)$ time complexity. We would be fine with probabilistic guarantees.

The matrix is sparse, that is the number of non-zero elements in the matrix is $O(n \log n)$. In addition, $a, b > 0$, $J \ll n$.

We posed the same question on MathOverflow.

We hope anyone can give us any leads on this problem. Thanks a lot :)


texts: Making algorithm comparison when algorithms use parameters

texts:
Say you have 3 algorithms, A B and C.  You want to present a comparison of A B and C based on:

Precompute overhead (say tree building etc that occurs prior to runtime)
Runtime speed (say query response time)

The problem is, however, A B and C each have their own unique set of parameters that will dictate the quality of the results.

A has 3 parameters x, xx and xxx
B has 1 parameter y
C has 2 parameters z and zz

If A has it's parameter x increased from 10 to 50, say, then A's precompute overhead doubles, and A's runtime speed is halved.

If B has it's parameter y increased from 0 to 0.001 say, it's precompute time stays the same but it's runtime speed becomes 1/3 of it's former speed.

So each algorithm has it's own set of quirks and behaves differently, depending on how you set each algorithm's parameters.

But we are interested in comparing A B and C based on the two categories (precompute and runtime) listed above!

How can you compare algorithms A B and C?


texts:
Given a weighted undirected graph $G = (V, E)$ with maximum degree $\mu$ and with positive edge weights, is it possible to construct another graph $H = (V \cup V', E')$ with maximum degree $\mu' = o(\mu)$ (ignoring poly-log factors) such that the following two conditions are satisfied: (1) the exact distance between each pair of vertices $u, v$ remains unchanged; and (2) each edge in $H$ has a positive weight?

Has this problem been studied? Does this problem have a name? Are there any known lower and/or upper bounds on $\mu'$? Are there efficient algorithms to construct, if at all possible, such a graph $H$? What if I am also interested in the poly-log factors?

Do the answer to any of the above questions change if we consider the special case of unweighted graphs?

Clearly, the problem is of interest only if $\mu = \Omega(|V|^{\varepsilon})$ for some $\varepsilon > 0$. Also, note that the problem is extremely trivial if we do not require the second condition. Also, assume that $G$ is a connected graph.


texts:
I have a  (word) Term Rewriting System (TRS in short) and I want to check for a simple accessibility condition.

In symbols, let $\Sigma$ be a finite alphabet. For $a\in \Sigma$, and any words $u,v,w \in \Sigma^*$, then my rewriting system is simply: $(au,vaw)\to (uv, w)$.

Starting from arbitrary configuration, I am searching for accessibility of Identity, that is, if for two words $u,v\in \Sigma^*$, I check if there exists $w$ such that $(u,v)\to^*(w,w)$ where $\to^*$ denote the transitive closure of $\to$.

The configuration space is exponential (the accessibility problem itself is NP-complete). I would like to add some memoisation policy for the non valid configurations met so far during the exploration. I can design an ad-hoc and specialized one but after some naive tries, it turns out to be more intricate.

To be slightly more precise, I am looking for proper data-structure to store the intermediate results. Simply caching the result of a configuration (pairs of string) is not efficient since there are many configurations that can be proved derived to be non valid with one non valid configurations. Furthermore, the efficiency of the naive caching highly depends on the exploration strategy and understanding that is already difficult to me.

It seems to me that it is a quiet natural question when one is trying to explore the derivation space of TRS, and I would suspect that some literature already exists on the subject, although I fail to find one in classical books and by duckduckgoing it rapidly.


texts:
I expect the answer is no, but I could not actually construct a counterexample.  The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.

By a dovetailing argument (for example, see this question), if there is a c.e. set of Turing machines $M_i$ deciding a language $L$ such that $∀ε>0 ∃M_i ∈ O(n^{2+ε})$, then $L$ is in $\mathrm{DTIME}(n^{2+o(1)})$.

Given a Turing machine, whether the machine runs in time $n^{2+o(1)}$ is $Π^0_3$-complete. Whether a language (given a code for a machine recognizing it) is in $\mathrm{DTIME}(n^{2+o(1)})$ is $Σ^0_4$ (and $Π^0_3$-hard); whether a language is in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ is $Π^0_3$-complete.  If we can prove $Σ^0_4$ completeness (or just $Σ^0_3$-hardness) of $\mathrm{DTIME}(n^{2+o(1)})$, that would solve the problem, but I am not sure how to do that.

The problem would also be solved if we find a sequence of languages $L_i$ such that
* $L_i$ has a natural $O(n^{2+1/i})$ decision algorithm (uniformly in $i$).
* Each $L_i$ is finite.
* Not only is the size of $L_i$ undecidable, but an algorithm cannot rule out $w∈L_i$ much faster than $O(n^{2+1/i})$ (for worst case $w$), except for finitely many $i$ (dependent on the algorithm).

I am also curious whether there any notable/interesting examples (for $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) \setminus  \mathrm{DTIME}(n^{2+o(1)})$ or an analogous relation).


texts: Power law for degree distribution of random KNN graphs?

texts:
Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d"
and consider a KNN (K-nearest neigbour) graph for some K.
Look at the degree distribution (say "IN"-degree, cause "OUT"-degree = K ).
Question 0 What is known about the degree distribution of such graphs ?
It is distribution on integers (>=0 ) it might be well-known for experts (see some info on median, std, percentiles here:  cross validated 500250 :  )
For high dimensions the distributions seems to  follow  power law for large "d" - see figure C (power law - sloped line in loglog plot) - which is typical for many graphs in nature - "scale free network", (although it is not always happen CSTHEORY14633).
Question 1 Is the exponent of power law known (how it depends on "d" and "K") ? (Does power law strictly hold true (when number of points tends to infinity) or it is kind of approximation or even illusion ) ?
Question 2 The distribution of degrees of KNN graph based on data cloud on the sphere and torus (uniform) is drastically different - the "tail" is much less "fatter" (see plot below) , is there any explanation for that ?

Remarks: The difference between sphere vs uniform/Gauss has been  noted in similar context in  The Hubness Phenomenon: Fact or Artifact? 2013.
It also manifests itself in number of connected components analysis - see https://cstheory.stackexchange.com/a/47181/2408 .  The simulation can be found in https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48919017 .
======================
Background and motivation: KNN graphs and related KNN-predictors (classifier/regressor)
are often used in machine learning. It was noticed that in higher dimensions the degree distribution
becomes extremely skewed - see figures A, B (that means nodes with very high degree begin to appear - they are called "hubs" sometimes). It seems that is somewhat unexpected, because naively one might expect degree should not go far from "K", but actually it can go very far if dimension "d" is high.  It is claimed that "hubs" cause problems for machine learning algorithms, certain techniques to fight with them appeared.
=======
Some other question about NN graphs is discussed here: Number of connected components of a random nearest neighbor graph?
============================
Code:
Plots A,B from my notebook version 4: https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48224880
Plot C from same notebook but version 6: https://www.kaggle.com/alexandervc/knn-graphs-study-degree-distribution?scriptVersionId=48230153
Uniform distribution can be found there also.


texts: Longest path from every vertex in a tournament

texts: I have a tournament (directed complete graph) with $V$ vertices. For every vertex I want to find the longest path starting in it (so the longest path starting in the first vertex, longest path starting in the second vertex etc.). In general, longest path problem is NP-complete, but this is a very special case so I guess there exist a polynomial (in terms of $V$) time algorithm.


texts: MACing from an arbitrary high min-entropy shared secret

texts:
Let $\gamma$ be such that $\, 0<\gamma \,$. $\hspace{.1 in}$ Define $H_{\infty}$ to be min-entropy.

If $S_n$ is a shared secret between Alice and Bob such that $\, n^{\frac12+\gamma} \leq H_{\infty}(S_n) \,$,
then Alice can use that to securely encrypt a message for Bob.
(Alice uses a strong extractor, such as in either of Theorem 2/3,

to get the key, and sends the seed along with the ciphertext.)

This idea does not obviously suffice for Alice to authenticate a message to Bob, since a false

acceptance could be caused by someone changing both the message and the reported seed.

  Is there a way for Alice to authenticate a message to
  Bob from an arbitrary high min-entropy shared secret?

Potential Clarifications:

a. $\,$ I am fine with "high" meaning something much closer
$\hspace{.24 in}$to $n$ than I used in the encryption construction.

b. $\,$ I really do mean "Alice to authenticate a message to Bob"; that is,
$\hspace{.24 in}$it does not need to work from Bob to Alice or for more than one message.

c. $\,$ I would nonetheless be interested in whether or not
$\hspace{.24 in}$the restrictions described in (b) could be relaxed.


texts:
Possible Duplicate:
  Best Upper Bounds on SAT

I'm working on the obstruction-set-free grid coloring problem; a specific instance of it is described in this previous question on coloring 17x17 grids. One possible approach to individual instances of the problem involves encoding the problem in 4-CNF and running it on a SAT solver.

I'm interested in the current state-of-the-art for SAT solvers (of which I know almost nothing). Specifically, I'm interested in both which algorithm has the largest adoption in practice and WHY (though perhaps less so than the following...), and whether there are recent results that are better purely in terms of complexity. To divorce this as far as possible from any type of specific engineering problem, I'll ask the question in the following form:

What are the current "best" SAT solver algorithms?

Feel free to interpret "best" in the most fitting form. Clickable reference links would be appreciated!


texts: How to determine proper rounding in linear programming relaxations?

texts:
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such that for every ${(u,v)\in E}$ at least one of ${u}$ or ${v}$ belongs to ${S}$.

Let us apply the methodology described in the first section. Given a graph ${G=(V,E)}$ and vertex costs ${c(\cdot)}$, we can formulate the minimum vertex cover problem for ${G}$ as an ILP by using a variable ${x_v}$ for each vertex ${v}$, taking the values $0$ or $1$, with the interpretation that ${x_v=0}$ means that ${v\not\in S}$, and ${x_v=1}$ means that ${v\in S}$. The cost of the solution, which we want to minimize, is ${\sum_{v\in V} x_v c(v)}$, and we want ${x_u+x_v \geq 1}$ for each edge ${(u,v)}$. This gives the ILP

$\displaystyle \begin{array}{lll} {\rm minimize} & \sum_{v\in V} c(v) x_v \\ {\rm subject\ to} \\ & x_u + x_v \geq 1 & \forall (u,v) \in E\\ & x_v \leq 1 & \forall v\in V\\ & x_v \in {\mathbb N} & \forall v\in V \end{array} \ \ \ \ \ (2)$

Next, we relax the ILP $(2)$ to a linear program.

$\displaystyle \begin{array}{lll} {\rm minimize} & \sum_{v\in V} c(v) x_v \\ {\rm subject\ to} \\ & x_u + x_v \geq 1 & \forall (u,v) \in E\\ & x_v \leq 1 & \forall v\in V\\ & x_v \geq 0 & \forall v\in V \end{array} \ \ \ \ \ (3)$

Let us solve the linear program in polynomial time, and suppose that ${{\bf x}^*}$ is an optimal solution to the LP $(3)$; how do we “round” it to a $0/1$ solution, that is, to a vertex cover? Let’s do it in the simplest possible way: round each value to the closest integer, that is, define ${x'_v = 1}$ if ${x^*_v \geq \frac 12}$, and ${x'_v = 0}$ if ${x^*_v < \frac 12}$. Now, find the set corresponding to the integral solution ${{\bf x}'}$, that is ${S:= \{ v : x'_v = 1 \}}$ and output it. We have:

The set ${S}$ is a valid vertex cover, because for each edge ${(u,v)}$ it is true that ${x^*_u + x^*_v \geq 1}$, and so at least one of ${x^*_u}$ or ${x^*_v}$ must be at least ${1/2}$, and so at least one of ${u}$ or ${v}$ belongs to ${S}$;
    The cost of ${S}$ is at most twice the optimum, because the cost of ${S}$ is

$\displaystyle \sum_{v\in S} c(v)$

$\displaystyle = \sum_{v\in V} c(v)x'_v$

$\displaystyle \leq \sum_{v\in V} c(v)\cdot 2 \cdot x^*_v$

$\displaystyle = 2\cdot opt(LP)$

$\displaystyle \leq 2\cdot opt(VC)$

And that’s all there is to it! We now have a polynomial-time 2-approximate algorithm for weighted vertex cover.

Question:

I realize that depending on what we pick as our rounding point, that is what our approximation bound is going to be. Therefore since we picked $1/2$ as our rounding point, approximation bound is $2$. If we picked $1/3$ as our rounding point, meaning if $x_v >= 1/3$ then $x_v=1$ and if $x_v < 1/3$ then $x_v=0$, our approximation bound would be $3$.

My question is how to find and show that the rounding we pick is optimal?

Thanks in advance!


texts: Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time

texts:
I need a simple augmentation to support median/order statistic queries in
O(log log n) time,without increasing the time for other operations.


texts: Period of a Multivariable Function using Quantum Computing

texts:
consider a function

$$f(x_1,x_2...x_n)$$

I am told it is possible to compute the period of the function as a vector

$$<l_1,l_2...l_n>$$
where each l denotes the period of the function for that corresponding variable using a generalization of the fourier transform.

My question is:

Is the time complexity of running the multivariable version of the quantum fourier transform still polynomial in the bit complexity of a function being evaluated?


texts: Algorithm for finding the largest subgraph without a directed triangle

texts:
I would like to find the largest set of vertices in a directed graph. This set should not contain a cycle with exactly three vertices. Cycles with less vertices aren't possible with the given graphs; larger cycles can be in the set.

Do you know an algorithm for that?


texts: What is worst case complexity of number field sieve?

texts:
Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ to factor $N$.

I looked for information on worst case complexity on this randomized algorithm. However I am unable to locate information.

(1) What is the worst case complexity of Number field sieve?

(2) Also can randomness be removed here to give a deterministic subexponential algorithm?


texts: Undecidable problems not Turing-complete?

texts: are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting problem (for ordinary TMs)?


texts: Looking for approximation class between NPO and Exp-APX

texts:
I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) is trivial, although obtaining solutions with any quality higher than 0 is NP-hard.

If I get it right, problem A cannot be in Exp-APX: any polynomial-time algorithm would return solutions with 0 quality, so the performance ratio (i.e. quality of best solution / quality of found solution) of any polynomial-time algorithm would be infinite in the worst case. Thus the performance ratio cannot be exponentially bounded.

On the other hand, finding some bad solution for problem A is trivial, which is not the case of NPO-complete problems such as e.g. MAX {0,1}-LINEAR PROGRAMMING or MAX WEIGHTED 3-SATISFIABILITY, where finding any valid solution is NP-hard. Therefore, problem A cannot be NPO-hard, right? In particular, an AP-reduction couldn't map 0-valued solutions of problem A into some solutions of MAX {0,1}-LINEAR PROGRAMMING, as finding any solution to the latter problem is NP-hard.

So, is there any known approximation class X such that problem A could be X-hard?

Related question 1: What version of TSP is said to be Exp-APX-complete? Is it "all pairs of nodes are connected" + "the minimal distance between nodes is 1"? If finding some hamiltonian cycle weren't easy, or if 0-length round trips could exist, then the problem couldn't be in Exp-APX, could it?

Related question 2: Is there any "Max TSP" variant (i.e. finding longest round trips) that is Exp-APX-complete? Or any other Exp-APX-complete problem (preferably a maximization one) I could use to prove the Exp-APX-hardness of A?