texts: A total language that only a Turing complete language can interpret

texts:
Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind of "ultimate" non Turing complete language; the one(s) that can only be interpreted by a Turing machine. These languages would not necessarily be able to compute all total functions from naturals to naturals nor would they necessarily be isomorphic (that is maybe ultimate languages A and B exists such that there exists a function F that A can compute but B cannot). Agda can interpret Godel's system T and Agda is total so that such an ultimate language should be strictly more powerful that Godel's system T it would seem. It seems to me that such a language would be at least as powerful as agda too (though I have no evidence, just a hunch).

Has any research been done in this vein? What results are known (namely is such an "ultimate" language known)?

Bonus: I am worried that there exists a pathological case that can not compute functions that Godel's System T could yet can still only be interpreted by a Turing machine because it allows some really odd functions to be computed. Is this the case or can we know that such a language would be able to compute anything Godel's System T could compute?


texts: What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

texts: The only techniques i know are those in the title.


texts:
Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by YUSTER and ZWICK states that the problem is not known to be in $P$ nor is it known to be $NP$-complete.

  Is there any recent result that resolves the complexity of the even cycle problem in directed graphs?


texts: Complexity of a variant of the max word problem. NP-complete?

texts:
I'd like to be able to state that the following problem is NP hard.
I am wondering whether anybody have any pointers to related/recent work?

The problem:
Given a finite set of transition matrices $A$ and two non-negative vectors
$\vec{x}$ and $\vec{y}$.

Do there exist $A_1, A_2, ..., A_n \in A$ such that

$$\vec{x} \, A_1 \, A_2 ...  A_n \, \vec{y} \geq P$$


texts:
I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It should be possible to efficiently find the $k$-th element in the sequence for a given $k$.

Nonexamples:

A linear congruential generator is not increasing, but it is possible to generate the $k$-th element, $x_k = A^kX_0+(1+\dotsc+A^{k-1})B \pmod{p}$, using $O(log(k))$ arithmetic operations.
Accumulating the sum of a linear congruential generator gives a sequence with the desired pseudorandomness property, but I don't know how to get the $k$-th element efficiently.


texts: Find minimum number of transformations to transform from input to target string

texts:
Given that I have an input string, for example:  aab
And I am given a target string, for example: bababa
And then I am given a set of transformation rules. For example:

ab -> bba
b -> ba

There can be N rules.
The characters for the input and output string don't have to be just a and b, they can be any characters.

How could I do an algorithm that would find the minimum number of transformations that would need to be applied in the input string to get the target string.

In this example, for example, the number would be 3.  Because we would do:

1 - Apply rule 1 (abba)
2 - Apply rule 1 again (bbaba)
3 - Apply rule 2 (bababa)

It could happen that given an input and a target, there is no solution and that should be noticed too.

Also, it can be that the target string is shorter than the input string.

I am pretty much lost in strategies on doing this.  It comes to my mind creating an automata but I am not sure how would I apply in this situation.  I think is an interesting problem and I have been researching online, but all I can find is transformations given rules, but not how to ensure it's a minimum.

Thanks


texts: Complexity of finding typing derivation trees

texts: In type theories where type checking is decidable do we have estimates for how much time/space it takes to find a typing derivation tree of a valid typing judgment? Do any published references do this kind of analysis?


texts:
I'm trying to reduce the following problem to a more well-known formulation.

I have a bunch of subsets $\{S_i \}_{i \in I}$ of some finite set.

I would like to put them into (disjoint) groups $\{ G_j \}_{j \in J}$ such that $\max_{j \in J} \left| \bigcup \{S \in G_j\} \right|$ is as small as possible.
The number of groups $|J|$ is a fixed constant $k$.

An example: $k = 2$, $S_1 = \{a, b\}$, $S_2 = \{b, c\}$.

If $G_1 = \{S_1\}$ and $G_2 = \{S_2\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1|, |S_2|\} = 2$$

If instead $G_1 = \{S_1, S_2\}$ and $G_2 = \{\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1 \cup S_2|, |\{\}|\} = 3$$

so the latter grouping is worse than the former.


texts: What is the role of the Bicolored Calculus of Constructions?

texts:
So, I'm reading a bit about elaboration, particularly, algorithms based on the Bicolored Calculus of Construction, and I'm a bit confused. I don't understand what exactly the purpose of the $CC^{bi}$ is. It seems to be identical to $CC$ except there is a distinction between implicit and explicit arguments for functions. In particular, I don't see how it allows you to write $(id\; 0)$ instead of $(id\; \mathbb{N}\; 0)$. If we assume a system for global definitions, then,

$id : (\Pi A\; |\; \mathsf{Type}\; . (\Pi x : A\; . A))$

and

$id = (\lambda A\; |\; \mathsf{Type}\; . (\lambda x : A . x))$.

Do the rules really allow for $(id\; 0)$? Of course the syntax does, but I don't see it in the typing relation. Am I missing something? Am I understanding the role of $CC^{bi}$ incorrectly?

Also, isn't the property of confluence lost? I guess my problem is that I'm reading about elaboration without having read much about $CC^{bi}$ before this. What's a good paper that introduces it and it alone?

Edit: To be more specific, I am asking how $(id\; 0)$ is accepted in place of $(id\; \mathbb{N}\; 0)$ when the rules for both explicit and implicit $\Pi$ application are identical modulo sytnax. I see no difference between $:$ and $|$ the rules for both seem the same.

Edit: I am not talking about the Implicit Calculus of Constructions, which is a different theory and has different rules for explicit $\Pi$'s (application vs. generation.)

Edit: Okay, I think I'm starting to understand this but I won't answer this question until I'm sure. Basically $(id\; 0)$ does not type check and in fact it is just elaborated to $(id\; \mathbb{N}\; 0)$ right before type checking or done as a secondary responsbility of the type checking algorithm. Essentially these implicit calculi are intended to be interface (user-end) languages which are elaborated into the usual (explicit) calculi or at least the explicit fragment of the implicit calculi before the terms are type checked. If that is the case, then I think I see the big picture. Can someone please confirm this?


texts: 3-partition problem without the restriction to triplets

texts:
In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$.
Consider the variant without the restriction that the size is $3$ (but with the restriction that there must be $m$ subsets with a sum of $T$). Are these problems computationally equivalent?
[NOTE: often there is an additional restriction that each input number is in $(T/4 , T/2)$; in this question there is no such restriction - the numbers in both variants can be any positive integers].
There is an easy reduction from the triplet-variant to the subset-variant: given an instance of the triplet-variant with target-sum $T$, construct an instance of the subset-variant by adding $2 T$ to each element and changing the target-sum to $7 T$. Every solution to the triplet-instance is also obviously a solution to the subset-instance. Conversely, in every solution to the subset-instance, each subset must have exactly 3 elements, since the sum of any 2-element subset is at most $6 T$ and the sum of every 4-element subset is at least $8 T$.
Is there a reduction in the opposite direction? Particularly, given an instance of the subset-variant, how can I construct an instance of the triplet-variant, that has a solution whenever the original instance has one?
Note that, since standard 3-partition is NP-hard and the unconstrained partition problem is in NP, there must be a polynomial-time reduction between these problems, maybe going through some other problems. But I am looking for a more direct reduction. Such a direct reduction can be useful, for example, for applying approximation algorithms for one problem (for optimization variants of the problem) to the other one.
Note: the question was posted in cs.SE about two months ago - no answer there


texts: How to efficiently verify if a semantic symmetry of a CNF formula is valid?

texts:
It is easy to verify that a syntactic symmetry of a CNF formula is correct.

Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is correct?

What is the complexity of the problem of checking the validity of a CNF formula's semantic symmetry?

Note that a syntactic (resp. semantic) symmetry $\sigma$ of a CNF formula $F$ is a permutation of its literals such that for all literal $x$, $\sigma(\neg x)=\neg \sigma(x)$ and  $\sigma(F) = F$ (resp. $\sigma(F) \equiv F$).


texts:
Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP.  Are there any known #EXP-complete problems?  In particular, has #Succinct Sat (the natural candidate) been shown to be #EXP-complete?

Papadimitriou and Yannakis mention this class in a 1986 paper (1) but I have not been able to find more recent results.

As an aside, they mention an interesting natural candidate for a #EXP problem: given a number $n$ in binary, return the number of planar graphs with $n$ nodes.  Is anything further known about the complexity of this problem?

Papadimitriou, Christos H., and Mihalis Yannakakis. "A note on succinct representations of graphs." Information and Control 71.3 (1986): 181-185.


texts: Primal Dual model in the continuous domain

texts:
The continuous max flow problem is posed as follows :

sup $\int_\Omega  p_s(x)dx$

subject to :

$|p(x)| \le C(x);  \forall x \in \Omega $

$p_s(x) \le C_s(x);  \forall x \in \Omega $

$p_t(x) \le C_t(x);  \forall x \in \Omega $

$\nabla \cdot p(x) - p_s(x) + p_t(x) = 0;  \forall x \in \Omega $

Here $p(x)$ is a field vector and is analogous to the flow in the discrete domain. $\nabla \cdot p$ is the divergence of the field p.

How do i find out the dual of this maximization problem using the lagrangian dual technique, i.e. the equivalent min cut formulation of the problem in the continuous domain.


texts: Best known hidden constant in complexity of AKS sorting networks

texts:
The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$.
The latest discussion of the hidden constants behind this construction that I could find were in the Zig-Zag sorting paper, where (if I correctly understood) the author states that $13 613 047$ is the currently best known constant.
Question:
Is this, as of 2020, still the best known hidden constant for a deterministic oblivious sorting algorithm with optimal complexity?


texts: Which algorithms can be expressed using a total functional language with data parallel operators?

texts:
Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are disallowed:

explicit loops (not much use without side-effects anyhow)
recursion
arbitrary first-class functions (no y-combinator)

The language does, however, have:

top-level functions
lexically scoped let bindings
branching control flow
common scalar math and logic functions
some simple array constructor like fill(n,x) which creates an n-element array with identical values x
most importantly: a restricted set of higher-order operators which perform parallel structured iteration (such as map, reduce, scan, all-pairs).

To be more specific about the data parallel operators:

y = map(f,x) => y[i] = f[i]
y = reduce(f, a, x) => y = f(a, f(y[p[0]], f(y[p[1]], ...))) for some permutation p
y = scan(f, a, x) => y[i] = reduce(f, a, y[0...i-1])
y = allpairs(f, x, y) => y[i,j] = f(x[i], y[j])

We could have other operators as well, but to qualify they should have polynomial running time, be implementable under some reasonable model of data parallel computation, and use at most polynomial space.

There are obviously some constructs which can't be expressed in this language, such as:

while f(x) > tol:
    x <- update(x)

What can we express in this system? Are we limited only to search problems in FP? Can we capture all polynomial time algorithms? Also, is there some minimal set of operators for this class?


texts: Bivariate low-degree polynomial testing of Polishchuk-Spielman

texts:
In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized $PCP$ for an $NP$ problem, one of the key ingredients is a low-degree test for bivariate polynomials.

The following paragraph just provides some information about the paper and context for my question. Strictly speaking, it may be skipped. My question itself is concerned with simple multivariate polynomial algebra

Essentially, to test if the function values on a set of evaluation points correspond to a bivariate polynomial of maximum degrees $(d,d)$, we check whether the restriction of this to axis parallel lines (i.e. rows and columns) are all degree $d$ univariate polynomials (This is an equivalence condition in the absolute case, which is easy to verify. The interesting part is the robustness of the test: that is, if the function values on the restrictions to axis parallel lines agree with low-degree polynomials on "most" points, then there is a bivariate low degree polynomial which also agrees with the function on most evaluation points). The proof of robustness uses the notion of error-corrector polynomial to capture the "bad" evaluation points, polynomial interpolation and then uses resultants.
I am intentionally not being too precise here because none of this is relevant to my actual doubt, which is probably a minor algebraic technicality in a part of the proof:
http://cs.yale.edu/homes/spielman/PAPERS/holographic.pdf

The problem

Consider section 5: "Piecing it together" in the above paper. The polynomials $P(x,y)$ and $E(x,y)$ are interpreted as univariate polynomials in $y$ over the field of rational functions in $x$ over $\mathbb{F}$, that is $\mathbb{F}(x)$ . We would ultimately like to show that $E(x,y)$ divides $P(x,y)$ as bivariate polynomials in $\mathbb{F}[x,y]$, and this is shown by arguing that $E(x,y)$ divides $P(x,y)$ as univariate polynomials in $y$ over $\mathbb{F}(x)$, and then use Gauss's lemma to imply the former.

I am unable to see how Gauss's lemma trivially establishes this implication.

For instance, suppose $P(x,y)=y^2x$ and $E(x,y)=yx^2$. Then $E$ does divide $P$ as polynomials in $y$ over $\mathbb{F}(x)$, but clearly not as bivariate polynomials in $\mathbb{F}[x,y]$.

(Gauss's lemma states that if a univariate polynomial in $\mathbb{D}[x]$ (where $\mathbb{D}$ is a UFD) is reducible as a polynomial in $\mathbb{K}[x]$ (where $\mathbb{K}$ is the field of fractions of $\mathbb{D}$), then it is reducible in in $\mathbb{D}[x]$ itself.)


texts: Implications of the rule of cumulativity in the Calculus of Constructions

texts:
Please help me understand some type theory research.

As suggested in "Type Checking with Universes" by Robert Harper and Robert Pollack, we can add the following rule to our otherwise standard COC or PTS type inference rules.

$$
\frac{\Gamma \vdash M : \text{Type}_{i}}{\Gamma \vdash M : \text{Type}_{i+1}} \text{(Cumulativity)}
$$

Doesn't that mean that if I declare Boolean : Type₀ that Boolean is implicitly of type Type₁, Type₂, and so on? And doesn't that mean that Typeᵢ ≡ Type₍ᵢ₊₁₎ and furthmore that ∀ i, j . Typeᵢ ≡ Typeⱼ by equational reasoning?

How does this differ from a predicative type theory where Type : Type?

Furthermore, this allows us to have dependent types even if our Π-formation rule is written as follows

$$
\frac{\Gamma \vdash \alpha : s \hspace{3em} \Gamma,x :a \vdash \beta : s}{\Gamma \vdash (\Pi x : \alpha . \beta) : s} \text{(}\Pi\text{-formation)}
$$

where the types of α, β and the resulting formation are (implicitely) required to be equivalent, right?


texts: Does the order of declarations in an inductive type matter?

texts:
I was wondering if the order of declarations of an inductive type can matter.

For example in Coq you can define Nat either by:

Inductive Nat :=
  | O : Nat
  | S : Nat -> Nat.

or

Inductive Nat :=
  | S : Nat -> Nat
  | O : Nat.

This will perhaps change the order of the parameters in the automatically generated eliminator, but that’s not a big deal.

What I’m wondering is if it is possible to write a declaration like

Inductive typewhereordermatters :=
  | cons1 : type1
  | cons2 : type2.

where type2 is a dependent type, depending on cons1? (and in this case, write the declarations in the other order would not have any meaning, because type2 would be referring to cons1 which does not exists yet).


texts: Intersection graphs of squares and rectangles

texts: Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)?


texts: a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem

texts:
Given a multiset of integers $S$, in the Equ-Sum problem we want to check
 whether
or not $S$ can be divided into two disjoint subsets, say $X_1$, $X_2$ such that  $\sum_{x_i \in X_1}x_i = \sum_{x_j \in X_2}x_j $.
In the 3-Equ-Sum problem for given multiset
$S$ we want to  check whether
 $S$ can be divided into
three disjoint subset say $Y_1$ , $Y_2$ , $Y_3$ such that $\sum_{x_i \in Y_1}x_i = \sum_{x_j \in Y_2}x_j = \sum_{x_k \in Y_3}x_k$ .

as we know both of these problems are NP-complete so both of them can be reduced to each other, a reduction from EQU-SUM to 3-EQU-SUM is obvious as we can add $x = \frac{\sum_{x_i \in S}x_i}{2}$ to $S$ but I'm working on a direct reduction from 3-EQU-SUM to EQU-SUM. can anybody help me?


texts: The theory of definitions in first order logic

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


texts: Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs

texts:
Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs.

  Has a similar algorithm been found for planar directed graphs?

To clarify what I mean, although there are several different ways one could generalise the planar Ising model to directed graphs, I have in the mind the following:

The 2-local term in the standard Ising model is the symmetric matrix $J_{ij}$. The directed graph would be represented by unsymmetric matrix $J_{ij}$! So the sum over the partition function would be unsymmetrical. I hope this helps.


texts:
Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks?

I have researched a fair amount on how quantum walks operate and their properties but I would like to know the end goal of studying them at a deep level? Is it simply for the sake of it in terms of mathematics or computer science, or are there actual real-world applications that can benefit from this research?


texts: Hidden constant in eps-sample size computation

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

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

Thanks in advance for any reference

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


texts: For each edge, find a matching that containing it and has maximum weight

texts:
Given a weighted graph $G=(V,E)$. For each edge $e\in E$, we are interested in finding a maximum weight matching over all matchings that contains edge $e$.

If $G$ is bipartite, then this can be done in $O(n^3)$ time:

Apply the standard reduction to min-cost flow.
Find a min-cost flow.
Compute all-pairs shortest path in the residual graph, and use the augmenting paths to extract the desired matchings.

Is there an $O(n^3)$ time algorithm in general graphs?


texts: NP-completeness: sum of "some" paths in a spanning tree

texts:
I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful:

Instance: undirected, unweighted, connected graph $G=(V,E)$, positive integer $K \in \mathbb{Z}^+$

Question: Is there a spanning tree $T$ of $G$ such that
$$\sum_{e=(u,v) \in E-T}d_T(u,v) \leq K$$

where $d_T(u,v)$ is the length (ie: number of edges) of the path from $u$ to $v$ in $T$. Note that the sum ranges over the complementary edges of $T$.

There is a similiar problem in the book by Garey and Johnson, namely "Shortest Total Path Length Spanning Tree" which was proved to be NP-complete in the paper "The complexity of the network design problem" (by Johnson, Lenstra and Rinnooy Kan). The difference is that the sum ranges over all pair of vertices.

The only technique I know so far is to find a reduction, is there a more suitable technique in this case? Any comment, suggestion or bibliographic reference will be of invaluable help.


texts:
This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow )

As we know, in mathematics even famous mathematicians, superstars and geniuses are doing serious mistakes time to time. For example, both 4-color theorem and Fermat theorem provide us dramatic cases of how even brightest minds can be deluded. It even can take years to prove the incorrectness of some falsy proofs.

My question is - can you provide some outstanding examples of such mistakes in computer science? I don't know, something like "Dr. X has proved in 1972 that it is impossible to do Y in less than O(log n) time, but in  1995 it turned out that he actually was wrong".


texts: Why isn't it "enough" to prove induction with one extra "INat" argument?

texts:
It is well known that it is impossible to prove the induction principle for Natural numbers on the Calculus of Constructions. That is,

Nat =
  ∀ P : *
  ∀ S : P -> P
  ∀ Z : P
  P

Zero =
  λ P : *
  λ S : P -> P
  λ Z : P
  Z

Succ =
  λ n : Nat
  λ P : *
  λ S : P -> P
  λ Z : P
  S (n P S Z)

NatInd :
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (Succ n)
  ∀ Z : P Zero
  ∀ n : Nat
  P n

There is no term of type NatInd on CoC, for either this or any other representation of Nat. But I've noticed that the following slightly different type can be constructed:

INat =
  λ n : Nat
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (S n)
  ∀ Z : P Zero
  P n

NatInd2 :
  ∀ P : Nat -> *
  ∀ S : ∀ (n : Nat) -> P n -> P (Succ n)
  ∀ Z : P Zero
  ∀ n : Nat
  ∀ i : INat n
  P n

Here, we first define a new type, INat : Nat -> *. That type is isomorphic to Nats and can be easily constructed for any natural number. Then, NatInd2 is a term that, given a proposition indexed on Nats, a base case Z, a step case S, for any nat n and its corresponding INat n, proves P(n) holds for every n. Or, in simpler words, NatInd2 is essentially induction, except that you must provide an additional argument i of type INat n, which you can always construct anyway. You could as well use dependent pairs to conveniently store Nat, INat pairs together.

It seems like this accomplishes the same one would expect from induction, i.e., you prove all cases from a base and a step case. Of course, there is an extra argument, but that argument is trivial to construct. For a "human reader", any proof using the method above would be equally convincing that some property holds for all n. So, my question is: is there any reason for the above method to be insufficient in general? Why is it so important to have the former unaltered definition of NatInd?


texts: Asymptotically sub-optimal but provably optimal algorithms in a finite range for NP-Hard problems?

texts:
Given a formula in propositional logic with $100$ variables. We know that there can be no SAT-checking provably faster than $O(2^n)$, unless P=NP. Now let's say I could find an algorithm which does SAT-solving provably in $O(2^{{n\choose3}/10^6})$. Now this algorithm is asymptotically poor, but is provably optimal till $n=1000$.
Question: Are there such algorithms in literature ? i.e asymptotically sub-optimal but provably optimal in a certain range ?

Edit : I mistakenly wrote $O(2^{{n\choose3}/10^6})$ as $O({{n\choose3}/10^6})$. Thanks @Yonatan N


texts:
I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "hold" a bunch of boolean formulas (or truth tables) and queries to the oracle will specify an index $x$ of a particular formula $\phi_x$ and an assignment $y$ of the variables in that formula. The oracle responds with $1$ if the formula is $\textbf{not}$ satisfied by that assignment (i.e. $\phi_x(y) = 0$) and $0$ otherwise. For simplicity I'll assume that for every $n$ we consider $2^n$ formulas each having exactly $n$ variables (so $x,y \in \{0,1\}^n$). That way the index for the formula and the assignment are both $n$-bit strings. So:

Input to oracle: $\langle x y \rangle$, where $|x|=|y|=n$

Output: $O(\langle x y \rangle)= 1 \oplus \phi_x(y)$, which is $1$ if the formula is not satisfied by the assignment $y$ and $0$ otherwise

I can then consider the language $UNSAT(O) = \{ 0^nx | \forall y \in \{0,1\}^n, O(\langle x y \rangle) = 1 \}$.

Clearly this language is in $coNP^O$, but I'm not sure how to show that it's not in $NP/poly^O$. It's relatively easy to show that it's not in $NP^O$ through diagonalization (enumerate all $NP^O$ machines, for each one consider some input formula which is unsatisfiable; if the machine rejects then it's wrong and we move on, if it accepts that means that there is some accepting path making polynomially many queries to the oracle; keep the answers to those queries the same, while changing the formula so that it's satisfiable).

The intuition is that because we are considering a new formula for each $x$, there are $2^n$ formulas for the same input length $2n$. However, the  advice $a$ is the same for all of these and is only polynomial in size so it can't be of much help for exponentially many inputs. And therefore (big leap) if an $NP$ machine with polynomial advice could solve this, then an $NP$ machine without advice also could and that would lead to a contradiction. Unfortunately I haven't been able to formalize that intuition. I guess the idea is to show that I can always consider $2^n$ formulas such that there is no advice of polynomial length that can make the $NP$ machine decide correctly on all of them. Of course, there are $2^{poly(n)}$ possible advice strings and it's unclear to me how I can rule out all of them.

In fact, I'm not even sure how to show that $coNP^O \not\subseteq P/poly^O$.

(I'm aware that in the unrelativized setting, if $coNP \subseteq NP/poly$ the polynomial hierarchy collapses at the 3rd level, but I'm not sure that helps and in any case I'd like to operate only on these complexity classes)


texts: I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is the best ratio achieved via this approach. Please mention the formulation along with the integrality gap. Any other information/comments are invited. My primary interest includes to know about the alternate ways that lead to 0.8 approximation for max-cut or near to it (preferably via primal dual scheme).


texts: List of number theoretic or algebraic problems in various complexity classes

texts:
I am looking for a list about the known or unknown complexity of various number theoretic  /algebraic problems. For example,

GCD in $NC^1$ is open,
factoring in $P$ is open,
computing sheaf cohomology is $\#P$-hard,
Arora and Barak state that a variant of factoring is $NP$-complete (though this is not clear based on the discussion at An NP-complete variant of factoring.),
Barbulescu et al's breakthrough work on discrete logarithms.

Adleman once published a list focused on $P$ and $NP$ but it seems outdated. Mumford has a paper on what is computable in algebraic geometry without regard to complexity.

Does anyone know a list of (major) discoveries since these lists were published?

  What are some problems of a number theoretic/algebraic flavor whose complexity classes are possibly already known (since the above lists were published), unknown but conjectured, or unknown and not conjectured?

Some avenues of problems could be interpolation problems (univariate or multivariate, over various fields), Chinese remainder theorem, complexity of point counting over curves, etc.


texts: Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

texts:
In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by
Abboud, Vassilevska Williams, and Weimann available [here][1]. The term of a certain size in the title of this question refers to the support set being $\{-n^3,\ldots,n^3\}$:
Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$
If there was an algorithm solving this exact version of 3SUM with complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0,$ what would be the impact on the Exponential Time Hypothesis?
Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be "obvious" in your comments and answers.


texts: A game of positioning overlapping circles to maximize travel time between them

texts:
I encountered the following game. I'll migrate this as requested.

A bug is visiting circles, and an adversary wishes to maximize his travel time.
The adversary places a circle on every turn.
The bug walks from it's current position directly toward the center of the newest circle, then stops when it encounters the interior of the circle (thus: it doesn't walk if a circle is played covering its location). This is the bug's turn.
There are $N$ circles available to the adversary.
Each subsequent circle has radius less than the previous circle.
Each circle must intersect the intersection of all previously played circles. That is, all circles must have a common intersection once all are played.

EDIT:  The adversary is free to choose the radii of the circles, subject to the constraint that the radii monotonically decrease.

Questions and Answers:

Is the distance as $N\to\infty$ bounded? A: No, an example of an adversary strategy is given by this Answer
What is the maximum distance the bug must travel over the playing of $N$ circles. A: it grows at $\Theta(\log(N))$, by the same answer.

Variant 2: The bug walks directly toward the intersection of the two most recently played circles.

UPDATE: This variant was addressed, under the assumption that the bug can only remember the last 2 circles played here. The result was again an unbounded distance.

What impact does unliminted memory have? i.e., the bug goes to the intersection of all previously played circles. This produced a "loose" bound of $O(d)$, where $d$ is the diameter of the first circle. Obviously it cannot be less than this. See here. The current upper bound was $1000\times d$. This was obtained by approximating the worst-case path as a tour around progressively smaller circles. It was shown that the bug always makes progress towards the final intersection, thus reducing the next-step distance it must travel.

I suspect the distance traveled is a small constant times the circumference of the first circle, but I'm not currently able to provide a good proof.


texts: Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?

texts:
I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result is also mentioned in Chazelle's book at the start of chapter 6. He gives the following hint: "Compare the number of possible sequences mod 2 and the number of matrices." and I am not really sure how to use it.

I tried to reformulate a slightly weaker statement but could not prove it. Let us have a circuit with $x_1, \dots, x_n$ as inputs and each gate computes $g_1 \pm g_2$ where the $g_i$'s are two previously computed gates. The circuit computes $Ax$ if there are $n$ nodes with values $Ax_i$ for any $x \in \mathbb{R}^n$. The size of the circuit is the number of edges and the complexity of $A$ is the size of the smallest circuit computing $A$. The proposition I want to show is that most matrices of this form have complexity in $\Omega(n^2/\log n)$.

Here is my attempt at a counting argument. We count the number of circuits: If we order the gates topologically, we see that the gate at step $k$ needs to choose 2 gates $g_1$ and $g_2$ from the ones previously computed and 1 from 3 ways to combine them ($g_1 + g_2$, $g_1 -g_2$, $g_2-g_1$, this yields $3\binom{k-1}{2}$ possibilities. We can bound this by above with $\frac{3k^2}{2}$. Now, if a circuit has size $s$, then there is going to be that much choice for each $k \in \{n+1, \dots, s\}$ and the product of all these terms is bounded above by $\frac{3^s}{2^s}(s!)^2 \leq \frac{3^s}{2^s}\left(\frac{s^s}{2^s}\right)^2$. Putting $s = n^2/\log n$ yields at most $\left(\frac{3n^4}{8\log^2n}\right)^{n^2/\log n}$ possible circuits, but we can write the number of matrices as $2^{n^2} = n^{n^2/\log n}$, and we clearly see that this is smaller than the number of circuits we computed before. I know that I am clearly over counting because some circuits might compute the same matrices and I use non-tight bounds, but I don't see the actual argument that gives this result.

Thanks for any help.


texts: What would be a good source for open problems for (weak) epsilon nets? Is there a good survey/article that summarizes the recent advancements on the topic?


texts: Bounds on approximating frequency moments

texts:
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be

$\displaystyle F_k = \sum_{i=1}^n m_i^k.$

In their well-known paper, The space complexity of approximating the frequency moments, Alon et al. give a streaming algorithm that approximates $F_k$ using roughly $O(n^{1-\frac{1}{k}}(\log n + \log m))$ space. They also use communication complexity techniques to obtain a lower bound of $\Omega(n^{1-\frac{5}{k}})$ for $k > 5$. For $k = 0,1,2$, they provide more or less matching upper and lower bounds.

Have there been improvements to these bounds since then, and has there been progress for $k = 3,4,5$?


texts:
I have the following problem:

given

a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds) is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=[a,b]$ for some $a\in \mathbb{Q}_0^+,b\in \mathbb{Q}_0^+\cup\{+\infty\}$ and $a\leq b$,
two vertices $s,t\in V$ and
an integer $h$ encoded in binary,

we have to decide whether or not there exist

a path in $G$, possibly with repeated vertices and edges, $v_0 \cdot v_1 \cdots v_{n-1}\cdot v_n$, with $v_0=s$ and $v_n=t$ and
a list of values $d_0,\ldots,d_n\in\mathbb{Q}_0^+$,
such that $\sum_{i=0}^n d_i = h$ and for all $i=0,\ldots, n$, $d_i\in d(v_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE.
We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Have you ever seen a similar problem? Can you come up with an NP algorithm? Or do you know some connected literature?


texts: Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

texts:
Question

  Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? Would it disprove the ETH (Exponential Time Hypothesis)?


texts: Proof that CIC or Dybjer-style eliminators are strongly-normalizing?

texts:
Related to this question

I'm wondering, what is the standard technique for showing that dependent types with eliminators are strongly normalizing? I'm thinking something like the Calculus of Inductive Constructions, or Dybjer-style inductive families.
I've heard that they are strongly normalizing. For example, in dependent pattern matching, compiling to eliminators is touted as a way of getting guaranteed termination.

I've seen the standard logical relations approach for non-dependent-type systems (Godel's system T) as well as System F, and I've seen hereditary substitution for dependent types without inductives (i.e. LF). But I've never seen the two combined.

What's the standard technique for proving that these calculi are strongly normalizing? Do logical relations work, and if so, what do you have to do to get the inductive-measure to work? (i.e. step-indexing, structural-indexing, multiset-orderings, etc.)


texts:
Even if it isn't a crucial point, I don't see any literature around this question. Are there relativisation results ?

Wouldn't it be quite straightforward to prove strict inclusion by adapting non-deterministic time hierarchy theorem by exploring all possible paths of the NP machine ?


texts: BPP fragment of a PSPACE complete problem

texts:
Consider a PSPACE-complete problem (e.g., TQBF).

Is there a sub-problem in BPP, that is not known to be in P?
Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e., not completely contrived languages)?

By "sub-problem" I mean a promise problem whose yes/no instances are respectively contained in those of the original language.

For example, asking the same question with NP instead of BPP, we can take the problem $\exists$TQBF (where the promise is that all the quantifiers are existential), namely SAT.

CLARIFICATION:
I'm interested in finding some PSPACE-complete problem that has such a BPP sub-problem. It would be good if the PSPACE-complete problem is a "natural" one, such as TQBF, but I'm open to suggestions.


texts: What does research in theoretical computer science involve?

texts:
I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do?

I know a significant time is spent on teaching, supervising graduate students, applying for funding, and departmental duties. Putting them aside how do you spend your research time? What are the major activities you typically do? I am guessing that you read papers, think, have meetings, and write documents. Are there any others?


texts: Is SAT in $c^{\sqrt{n}}$ time with preprocessing worthwhile?

texts:
We may be able to solve SAT in $c^{\sqrt{n}}$ for $n$ variables and a constant $c$.  Now we can suppose that we require a certain amount of preprocessing to get this result.  For example, in this answer, Ryan Williams points out that we could have a large amount of preprocessing, and SAT in QP (quasi-polynomial) would still be interesting.

So my question is, if we solve SAT in $c^{\sqrt{n}}$, how much preprocessing can we have and still have an interesting result?  In other words, if we had something like $2^{2^n}$ preprocessing, would this remain an interesting result?  Basically, we would be saying that SAT has $c^{\sqrt{n}}$ sized circuits.


texts: Lower bounds on single-source shortest paths in directed graphs

texts:
Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights?  Can we rule out the possibility of an algorithm with $O(n+m)$ running time?  Are there any lower bounds in any restricted models, e.g., in the decision tree model, or something like that?

Dijkstra's algorithm can be implemented to run in $O(m+n \log n)$ time, with suitable data structures.  I understand Thorup has an algorithm whose running time is $O(n + m \log \log n)$ in the RAM model, and other algorithms are known in the RAM model.  However, I have not found any algorithm with $O(n+m)$ running time, nor any lower bound to rule out the possibility of such an algorithm.

(I know there is a $O(n+m)$ time algorithm for undirected graphs with non-negative integer edge weights, due to Thorup, but here I am asking about directed graphs.  I found Is there a tight lower bound on the complexity of SSSP on a graph?, but that is asking about undirected graphs and allows negative edge weights; I want to know about directed graphs, and am focusing on the case with non-negative edge weights.)


texts:
While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind.

Suppose that we have a polynomial time Turing machine $M$ that on input $1^n$ generates a graph $G_{M,n}$ with $n$ nodes.

We can define the problem $\Pi_M$:

  ("Tiny" GI): Given a graph $G=(V,E)$, is $G$ isomorphic to $G_{M,|V|}$?

In other words we must compare a given graph with a "reference" graph of the same size generated by a fixed polynomial time Turing machine $M$.

  For all polynomial time Turing machines $M$, we have $\Pi_M \in NP$, and for many of them we have $\Pi_M \in P$.
  But is it true for all $M$? Is the problem known?

At first glance, I thought that every $\Pi_M$ should be much easier than $GI$, because for every $n$ there is only one "reference" graph of that size and perhaps the symmetries/asymmetries of the graphs generated by $M$ can be exploited and an efficient ad-hoc isomorphism tester can be built ... but it's not true: $M$ can contain some sort of polynomial timed Universal Turing machine that uses the (unary) input $1^n$ to generate completely different (in the structure) reference graphs as $n$ increases.


texts:
Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$.  For convenience, we can assume $\mathbb{K}$ is a finite field, to avoid addressing issues with the model of computation.

Let $C(f)$ denote the complexity of computing $f$, i.e., the complexity of an algorithm that, given $x$, returns $f(x)$.  Can we somehow characterize $C(f)$, based on the properties of $f$?  For instance, are we guaranteed that $C(f)$ is polynomial (in $n$) for all symmetric polynomials $f$?

As special case, it looks like (a) we can compute the power sum polynomials in time $\text{poly}(n)$, and (b) we can compute the elementary symmetric polynomials in time $\text{poly}(n)$, using Newton's identities.  As a consequence, if $f$ is a weighted sum of monomials where no variable is raised to a power higher than 1 (i.e., if $f$ is multilinear), then $f$ can be computed in polynomial time (since it can be expressed as a weighted sum of elementary symmetric polynomials).  For instance, when $\mathbb{K}=GF(2)$, then every symmetric polynomial can be computed in polynomial time.  Can one say anything more than this?


texts: Does a depth knowledge on theory of computation helps to be a better practitioner

texts:
I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would it help to also know automata (for compilers, types, programming languages), computability and complexity?

If it would be wise to obtain more knowledge, what references can I read. For undergraduate education, I know basic stuff such as Hopcroft, Sipser, Ullman.


texts:
Motivation

Imagine a huffman compressed file that gets downloaded partially, like in P2P software, so we allocate disk space for the whole file first and then start downloading random file chunks. One of the huffman codes (but we don't know which) is an end code, so if this code is decoded, we stop. Assuming the file consists of several huffman compressed streams, we can try to decompress some of them before the download finished.

The way the disk space is preallocated is important now: Let's assume we have the start of a huffman stream, but it isn't complete, so we run into the preallocated disk space. Usually, this space is all 0, so we'd keep decoding symbols with huffman code 00... If this isn't our end code, we don't notice the "invalid" data and f.e. if there's 2 GB of preallocated space, we're doing much useless decoding.

So we'd like to preallocate the space in a way to make decoding stop as soon as possible.

The question

I'm looking for the shortest bitstring that acts as a "Huffman terminator", meaning if we decode this string, we'll decode every Huffman code at least once, so we'll definitely receive an end code. This should work for every combination of Huffman codes of length 1..n bits.

Note: I know there are simple solutions to the hypothetical scenario above (using 00.. as an end code, using P2P segment data to detect chunks not downloaded yet), but this is just an example scenario to show a theoretical use of a "Huffman terminator" bitstring, I'm not interested in solving this scenario, but looking for algorithms/ways/ideas to generate/find bitstrings that act as "Huffman terminator".

I've asked the same question on Stack Overflow, but decided to post it here, too, because it's a very theoretical question and most likely won't have many real world applications.

Example

Let's look at the possible Huffman code combinations for n = 2: [0, 1], [00, 01, 1], [0, 10, 11], [00, 01, 10, 11]. Now let's start with a bitstring that contains every possible bit sequence of length 1..n (0, 1, 00, 01, 10, 11):

001011

Decoding with the different Huffman code combinations gives (huffman codes are assigned to symbols A..D):

Combination   Decoded symbols
[0, 1]        AABABB
[00,01,1]     ACBC
[0,10,11]     AABC
[00,01,10,11] ACD

This is a good start and it already decodes every Huffman code for the first three ones, but if we decode it with [00, 01, 10, 11], we're missing symbol B (Huffman code 01). So let's just append this to our bitstring:

00101101

This is a valid "Huffman terminator" for n=2, 8 bits in length. If we'd preallocate our disk space with this byte, we'd be sure to terminate all huffman codes that won't exceed 2 bits. We even know there won't be shorter terminator strings for n=2 because it's the minimal length for the combination [00, 01, 10, 11] to decode each symbol once.

I also found a "Huffman terminator" for n=3, 0001011001110100111010011100010101111101110 (43 bits), but I'm not 100% sure if it's correct and I don't know if it's the shortest one.

What I'm looking for

Algorithms/ideas to find or generate Huffman terminators for a given n. My attempt would be similar to the example: generating a start string and appending bits as needed to satisfy all different Huffman code combinations. But I'm sure there are better ways.
Specific Huffman terminators, n=8 and n=16, although it might be computational expensive to generate them and they will perhaps be very long.
Papers/links about this problem (or similar ones) if there are any.

Bonus

Bonus points for finding "Huffman terminators" that also work if we start at bit position 1..n, so it even terminates if data was decoded before and we won't arrive and start a new huffman code at the first bit.


texts: Dealing with duplicates in Genetic Algorithm

texts:
I'm using Genetic Algorithm to create a rota for home-care organisation. All the groundwork is complete, I'm getting the results, but results are not as good as expected.
If I calculate fitness for existing rota made by somebody, I get about £6000 (I measure fitness in money - great point for management).

When I run my GA, the best I manage to get is £8K after about 30K generations.
So I know the better solution exists and I'm trying to get better result.
I have tried different approaches - big population, small population, different number of crossover points, swap-mutation, random-mutation, hill-climber-mutation.
And nothing improved the results.

The resulting curve looks like this:

I can run GA much longer, but it does not give me any better results - the curve is just flat horizontal to the right.

I figured that I get quite a lot of duplicated individuals in final population. And that slows down the improvement of the solution.
I learned how to find duplicate individuals. But what do I do with them? I have tried replacing them with randomly created solutions, but usually their fitness is much worse then every body else in the solution space, so they get "killed" quite soon without giving any offsprings or other influence to the solution space.

Any ideas/suggestions/papers will be highly appreciated, as I've run out of ideas and research papers and almost no time left.

UPD: some description of the problem:
There are number of visits(shifts) that are located in different geographical places (distances between locations are known). Currently I work with 700 visits per week with durations from 30 minutes to 5hrs. There are workers with different levels of contractual arrangements: some have 0 contracted hours - relief workers, there are part-timers and full-timers.
I need to allocated workers for every shift in a best possible manner with this factors in mind:

Minimise travel distance for workers. When they have number of shifts in a day, the locations should be roughly in the same area
Workers should not do a lot of overtime hours
Workers should not work less than their contract says
Workers with 0-contracts should be allocated no or very limited working hours
Minimise waiting time between shifts. So no situations when somebody starts one visit at 9am to 10am, and next  visit is at 6pm.
There is a limit of total number of hours that can be worked per day
There is a minimum of working hours per day: nobody should be deployed for only 30-minute visit and no other visits per day.
At least 2 days off allocated for anybody, but can be more
At least 2 days off must be adjacent.

And other minor fitness function adjustments.
I hope this is sufficient for description.


texts: Does Karp reducibility yield a total order?

texts: Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?


texts:
Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"):

Two players randomly split in two decks a standard deck of cards.  Each player gets one deck.

The players alternate placing down in a stack the next card from their deck.

If a player (A) places down a special card, i.e. a I, II, or III, the other player (B) has to place down consecutively the corresponding number of cards.

If in doing so B places down a special card, the action reverses, and so on; otherwise, if B places down the corresponding number of cards but no special card, A collects all the cards that were put down and adds them to their deck.  A then restarts the game by placing down a card.

The first player to run out of cards loses the game.

Note: The outcome of the game depends exclusively on the initial partition of the deck.  (Which may make this game look a bit pointless ;-)

Question: Does this game always terminate? What if we generalize this game and give any two sequences of cards to each player?


texts: Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm

texts:
First thing first - I am not a CS guy. I am EE student (Systems and Signals). So it would help if you didn't use any big words :)

The Multi-terminal cut the input is a graph G and a subset T of its vertices. The task is to remove the minimum number of edges from G such that there is no path connecting any distinct vertices of T. Dalhaus et all showed that its NP-Hard for $k\ge 3$ for arbitrary.

Question - Why is this class of problem important? Do they show up in some engineering application.

A few years ago I found a simple algorithm proposed as an approximation of the Multi-terminal cut problem for arbitrary weighted slow-coherent graphs. (Strong connected components which are weakly connected with each other). I did a performance analysis of the algorithm from a linear algebra point of view and was able show that algorithm should be work for these classes of graphs.

I would like to take the algorithm and apply it to an application area and see how it fares compared to the "standard".


texts: What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?

texts:
I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula.
As for the fast algorithms for k-SAT, we see
biased-PPSZ, PPSZ, Schöning's local search, algorithms which combine PPSZ and Schöning's local search, algorithms which derandomize PPSZ or Schöning's local search.

There are many papers which are discussing improvement and property of PPSZ.
However, where are other deterministic algorithms going? Is there no future for every deterministic algorithm which is not a derandomization of PPSZ or Schöning's local search or their improvement,combination?

There exists deterministic fast branching algorithms which are not derandomization from some randomized algorthms for k-SAT where time complexity is in terms of m and l, i.e. the number of clauses in a formula and the length of a formula. And there is a branching algorithm, and in the early papers which discuss k-SAT in terms of n, there is also algorithm using branching algorithm to obtain a speed which is from Burkhard Monien and Ewald Speckenmeyer. For 2-SAT, there is linear time deterministic algorithm based on strongly connected components of a contructed graph.

After Hertli reveals that unique-SAT bounds for PPSZ hold in general, work turns from derandomizing and improving Schöning's local search to derandomize PPSZ and improve that. Are there any possibilities for those deterministic algorithms without derandomization like some branching algorithms? What if some techniques like measure and conquer are contributed to k-SAT? No matter how, it must be admitted that PPSZ and Schöning's local search are both simple and efficient.

Papers I mention are as follows.

schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction k Problems
Evgeny Dantsin, Andreas Goerdt, Edward A Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and Uwe Sch¨oning. A deterministic (2-2/(k+1))n algorithm for k-sat based on local search. Theoretical Computer Science, 289(1):69–83, 2002.
S. Cliff Liu, Simpler Partial Derandomization of PPSZ for k-SAT
Daniel Rolf. Derandomization of PPSZ for unique- k-sat. In 8th International Conference on Theory and Applications ofSatisfiability Testing, SAT 2005, pages 216–225, 2005.
S. Cliff Liu, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT∗
Robin A. Moser and Dominik Scheder, A full derandomization of schöning’s k-sat algorithm. In 43rd Annual ACMSymposium on Theory ofComputing, STOC 2011, pages 245–252, 2011.
Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Dominik Scheder and John P. Steinberger, PPSZ for General k-SAT – Making Hertli’s Analysis Simpler and 3-SAT Faster∗
Pavel Pudlák, Dominik Scheder, and Navid Talebanfard, Tighter Hard Instances for PPSZ
Burkhard Monien and Ewald Speckenmeyer. 1985. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 3 (1985), 287–295.
Jianer Chen and Yang Liu, An Improved SAT Algorithm in Terms of Formula Length
Bengt ASPVALL, Michael F. PLASS and Robert Endre TARJAN, A LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS
Timon Hertli. 2014. Breaking the PPSZ Barrier for Unique 3-SAT. In Proc. of41st ICALP I. 600–611.
Ramamohan Paturi, Pavel Pudlák, and Francis Zane. 1999. Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. (1999).
Tong Qin and Osamu Watanabe. 2018. An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. In International Workshop on Algorithms and Computation. Springer, 93–105.
Thomas Hofmeister, Uwe Sch¨oning, Rainer Schuler, and Osamu Watanabe. A probabilistic 3sat algorithm further improved. In 19th Annual Symposium on Theoretical Aspects ofComputer Science, STACS 2002, pages 192–202. Springer, 2002.
Improving PPSZ for 3-SAT using Critical Variables


texts:
I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 would match abc;abc but not abc;cba, lazy or not greedy repetition operators [ab]+?ba$ would match abba or aaaabbbbba but not ababa.
I know that things like anchors (^ and $), optional operator (a?), character classes ([abc], or [^abc]) and the plus operator can be reduced to nominal regex operations or are simple checks in the end.


texts: minimum distance r-dominating set on tree

texts: Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every vertex v not in S, there is a vertex u in S such that d(u,v) $\leq$  r. Distance is defined by the length of shortest path on graph. Does anyone know papers that solve this problem on a $\textbf{tree}$?


texts:
Let $f$ be a Boolean function  of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\epsilon/2$.

I am interested in cases where it is computationally hard to approximate $g$. Let me fixed a notion of "approximation" (but there may be others): A Boolean function $h$ approximates $g$ if $h(x)=1$ when $g(x)\ge 0.9$ and $h(x)=0 $ when $g(x)\le 0.1$.A counting argument (based on the existence of positive rate error correcting codes) seem to give that there are Boolean functions for which any such approximation requires an exponential size circuit. But the question is what happens when $f$ to start with is in NP or in its neighborhood.

Q1: Is there an example of $f$ described by NP circuit (or P-space) so that every $h$ is NP hard, or hard in some weaker sense.

To see that $h$ might not always be easy (I thank Johan Hastad for useful discussion about it) we can consider the property of graphs of having a clique of size $n^{1/4}$, for random input, it is conceivable that it is hard to detect if there is a large clique but this is manifested by having more than expected cliques of size log n in the noisy graph. In this case any $h$ will be likely-hard (but not provably, and not terribly hard as quasi-polynomial circuits will be telling).

Q2: What is the situation if $f$ to start with is low complexity. ($AC^0$, monotone $TC^0$, $ACC$ etc.)

Q3: What is the situation for some basic examples of Boolean functions. (The question can be extended also to real-valued function.)

Q4: Can the above question be asked formally for the uniform (Turing-machine) model of computation?

Update: In view of Andy's answer (Hi there, Andy) I think that the most interesting question is to understand the situation for various specific functions.

Update Another question Q5 [Q1 for monotone functions] (also in view of Andy's answer). What is the situation if $f$ is monotone? Can we still encode robustly an NP complete questions>


texts: Gap between $BB(n)$ and "second largest" $BB(n)$

texts:
If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$.

What can we say about the second largest number in $HT(n)$?  Call this $BB_2(n)$.

$BB_2(n)$ is trivially uncomputable, since it lets one compute $BB(n)$: just wait for one more machine to halt.  Naively, I would expect the gap $BB(n) - BB_2(n)$ to be "busy beaver-like", growing faster than any computable function.  Is this provable?


texts: Simply-stated restriction on imperative programming language that captures the elementary functions?

texts:
The language of while programs can express the computably enumerable functions.  (This is true even if the only arithmetical operations on variables are, say, incrementation and decrementation.)

If while is replaced by for, making loops always bounded, the language can then express only the primitive recursive functions.

I recently became aware of the class of elementary functions, which are strictly below the primitive recursive functions, but still strictly above the exponential hierarchy.

Obviously it would be possible to define an imperative programming language which captures exactly the elementary functions, say by introducing operators for bounded sum and product.  However, my question is,

  Is there a syntactic change to the language of while programs which restricts it to the elementary functions and which can be stated as simply as the (while -> for) restriction to primitive recursive functions?

A restriction on for programs instead would also suffice, of course, and perhaps I should clarify that I'm not looking for something that is absolutely as simply-stated, just something with comparable simplicity which does not require the addition of extra operators or the like.

Edit: An example of a representative for language is PL-{GOTO} from Brainerd and Landweber's "Theory of Computation" (1974), in which each program has a finite but unrestricted number of variables, each of which can contain a natural number, and which consists essentially of the following commands:

X <- 0 (assign 0 to a variable)
X <- Y (assign the value of Y to X)
X <- Y + 1 (assign the successor of the value of Y to X)
LOOP X; ... END; (repeat the contained block of code X times; does not alter X)

The authors give a proof that this can express exactly the primitive recursive functions.  The language PL does not match the question perfectly, as it uses GOTO instead of while, and PL-{GOTO} is derived from PL by removing GOTO from it.  However, PL programs are just as powerful as while programs, and this GOTO-removal transformation is just as simply stated as replacing while with for.  (Arguably perhaps even a bit simpler.)

Edit 2: http://en.wikipedia.org/wiki/Total_Turing_machine suggests this result goes back to: Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.


texts: Could a descriptive complexity version of Rice's theorem be used to separate AC0 and PSPACE?

texts:
In this question, it was mentioned that there are descriptive complexity versions of Rice's theorem.  I found a proof of the following theorem:

  Given a complexity class C, nontrivial properties of languages in C cannot be computed in C

I had previously posted the proof I found, but because it was so long and because it was pointed out in the comments that this paper contains a proof of that theorem already, I removed it.  (If for some reason you are desperate to see my proof, please see the previous revisions of this question.)

My interest is in whether or not this theorem could be used to separate AC0 and PSPACE.  Here's the argument:

Consider the property P of the complexity class AC0 defined as follows:

P:  the property of being an FO query that accepts a particular fixed structure, namely the structure consisting of one element, no functions, no constants, and no relations

Clearly, by the theorem above, P is not decidable in AC0; it is a non-trivial property of FO queries.

However, a little examination should show that computing whether or not an FO query accepts such a simple structure can be decided as easily as TQBF; thus, P is decidable in PSPACE.

To ensure clarity on this point (that P is computable in PSPACE):  Note that the property we are interested in requires that the structure be FO.  So, we are trying to determine whether a FO query that is running on a single-element structure with no relations accepts.  Because there are no relations to deal with, it should be clear that the task of deciding such an FO query is equivalent to deciding an instance of TQBF; there are no relations, so the only challenge that remains is to evaluate whether or not the quantified boolean formula is true.  This is basically just TQBF, so P is computable in PSPACE.

Because P is computable in PSPACE but not AC0, we should be able to conclude that AC0 != PSPACE.  Is this reasoning correct, or have I made a mistake somewhere?  I'm particularly concerned about the preceding paragraph; I'll try to clarify and update the argument tomorrow after I get a chance to give a little more thought to the exposition.

I would accept as an answer an example of a FO query that, when computing on the one-element, relation-free structure I've described, clearly does not make sense as an instance of TQBF.  (I'm suggesting that there isn't one, so if you can show that there is one, that would be a counterexample.)

Thanks.


texts: Extensionality of lambda calculus models

texts:
I'm translating a book on LISP and naturally it touches some elements of $\lambda$-calculus. So, a notion of extensionality is mentioned there alongside some models of $\lambda$-calculus, namely: $\mathcal{P}_\omega$ and $D^\infty$ (yes, with the infinity at the top). And it is said that $\mathcal{P}_\omega$ is extensional while $D^\infty$ is not.

But... I was looking through the Barendregt's Lambda Calculus, It's Syntax and Semantics, and (hopefully, correctly) read there exactly the opposite: $\mathcal{P}_\omega$ is not extensional, $D_\infty$ is.

Does anybody know about that strange model $D^\infty$? Could it be just the same model as $D_\infty$, but erroneously written? Am I right about the extensionality of the models?

Thanks.


texts: Why use joint trees in Graphical Models?

texts:
I am wondering why some methods transform the underlying DAG-based graphical model (Bayesian Networks for example) to a joint tree$^1$? What are the advantages?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to jointtrees?

Speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

$^1$ Also known as jointree, junction tree, tree decomposition.


texts: Optimal comparison-based stable sorting in constant space

texts:
For a comparison based sorting algorithm, it is desirable to:

Be stable
Run in $O(n\ \log n)$
Operate in $O(1)$ space

I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?


texts: Does $P=BPP$ say anything about space complexity?

texts: There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to streaming does derandomizing time have anything to do with $L=RL$?


texts: Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

texts:
I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent sets $V_1,V_2,\dots,V_k$).
MulitColoredClique with Simple Modules
Instance: A graph $G$, an integer $k$, and a $k$-coloring $V_1,V_2,\dots,V_k$ of $G$ such that
$\quad\qquad\;\ $for every pair of colors $i$ and $j$, $V_i\cup V_j$ induces the disjoint union of
$\quad\qquad\;\ $ a complete bipartite graph with an independent set.
(in other words, if $x\in V_i$ has a neighbor in $V_j$, and $y\in V_j$ has a neighbor in $V_i$, then $x$ and $y$ are neighbors).
Question: Is there a clique of size $k$ in $G\,?$
Is this problem NP-hard?  (or even W[1]-hard?)
I have a feeling that it is indeed NP-hard, but I am unable to prove it.
Or, is this problem in P?
If it is in P, an interesting combinatorial problem will also be in P.
Is this or any related problem (other than MultiColoredClique) studied in the literature?
PS: Sorry, I asked the wrong question. Somehow, I assumed that bipartite complement of biclique+isolated vertices was again biclique+isolated vertices. What I wanted to ask is here: Complement of Multi-colored Clique with an extra condition


texts: Categorical equivalent of higher order logic

texts: From Simply typed lambda calculus and higher order logic, I get the impression that HOL is STLC + equality + equality axioms. I was wondering if there is a particular kind of category modelling this.


texts: Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

texts:
Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. Computing $\Delta$ is $\#P$-hard.

Let $A$ be an algorithm behaving as follows:

The input of $A$ is $G$, together with a positive integer constant $C_1$ (as huge as you wish).
$A$ runs in time polynomial in the size of $G$.
The output of $A$ is another graph $H$ having all these properties:

The minimum degree of $H$ is equal to or greater than $C_1$.
The $\Delta$ of $H$ is the same as the $\Delta$ of $G$.
$H$ has a number of nodes equal to $C_2 \cdot n$, where $n$ is the number of nodes of $G$, and $C_2$ is another constant (much bigger than $C_1$, but still constant in the size of $G$).

The existence of $A$ allows us to densify $G$, by increasing its minimum degree to any constant we desire.

  Questions:

  The question that interests me most is the following: what are the consequences of the existence of $A$? Does its existence implies some complexity class separation / collapse? My sensation is that it does not, but at the same time that maybe its existence could be nevertheless interesting under some point of view (I feel that just because I'm unaware of any known algorithm behaving like it).
  Another question is: does computing $\Delta$ (or also $O + E$) has been studied for such graphs? My sensation is of course that by increasing the minimum degree the instance gets easier and easier (maybe it is still exponential time, but with the degree of the exponent which gets lower and lower as the minimum degree gets higher and higher). I wonder if there is a point at which $C_1$ is so astronomic that the instance becomes solvable in sub-exponential time (has anyone studied that?). The limitation of $A$ is that the number of nodes of $H$ grows faster than the minimum degree, so you can never make the minimum degree be a non-constant function of the number of nodes.

  Motivation:

  My motivation is that a recently developed, very promising research avenue relates the existence / non-existence of algorithms to the existence / non-existence of lower bounds (and thus to complexity class separation / collapse). Of course the algorithm $A$ described here is not the same kind of algorithm usually described in those papers, as it does not solve the given instance: it just reduces it to another instance having a certain property. Nevertheless I wonder if it can fit into the global picture in some way.


texts:
Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.

Now consider two strings $x,y\in\Sigma^*$ and define $K(x,y)$ to be the number of elements of $DFA(n)$ that accept both $x$ and $y$.

Question: What is the complexity of computing $K(x,y)$?

This question has implications for machine learning.

Edit: Now that there's a bounty on this question, I suppose a bit more precision in the formulation is in order. For $n\ge1$, let $DFA(n)$ be the collection of $n^{2n}2^n$ automata, as defined above. For $x,y\in\{0,1\}^*$, define $K_n(x,y)$ to be the number of automata in $DFA(n)$ that accept both $x$ and $y$. Question: can $K_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?


texts: Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

texts:
Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in coefficients. This is the Lenstra-Lenstra-Lovasz algorithm.

$1$. Arrange members of $\Bbb Z[x]$ with some bound on coefficients in some order. If I ask if the $t$th factor has $j$th bit in $i$th coefficient a $1$ is this algorithm known to give an $ACC^0$ circuit?

$2$. What is the smallest complexity class for the same query as $1$ if I say I only need at least in a randomized sense and for an algorithm that factors only a constant fraction of primitive polynomials?

Link https://mathoverflow.net/questions/258467/existence-of-randomized-polynomial-time-algorithm-and-some-arithmetic-analog-of/258477?noredirect=1#comment637557_258477.

$3$. Consider the overall Hensel lifting step in Zassenhaus' algorithm. If I ask is the $i$th digit has $j$th bit $1$ when lifting to $p^t$ can we have an $ACC^0$ circuit? Hensel lifting is just reading $p$-adic digits and may be this step is in $ACC^0$? If so Zassenhaus' algorithm would give $ACC^0$ circuit for thus answering $2$. There is a linear system interpretation here in section 8.1.2 https://www.nada.kth.se/~johanh/algnotes.pdf which might put the decision version in here to be in $ACC^0$.

Refer algorithm 10 and theorem 2 here http://www.mmrc.iss.ac.cn/~lzhi/Course/mchapter15.ps.

Please also check corollary $1.79$ here http://compalg.inf.elte.hu/~tony/KedvencKonyvek/InfoKonyvtar/03-Algorithms%20of%20Informatics%201,%202,%203/AlgofInfVol1Oct24.pdf for a log depth implementation of Hensel Lifting. Can it be reduced to constant depth?


texts:
I am interested in a SAT variation where the CNF formula is monotone (no variables are negated). Such a formula is obviously satisfiable.

But say the number of true variables is a measure of how good our solution is.  So we have the following problem:

MINIMUM TRUE MONOTONE 3SAT

INSTANCE: Set U of variables, collection C of disjunctive clauses of 3 literals, where a literal is a variable (not negated).
SOLUTION: A truth assignment for U that satisfies C.
MEASURE:  The number of variable that are true.

Could someone give me some helpful remarks on this problem?


texts: intuition that VP=?VNP is (not?) connected to P=?NP

texts:
recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1]

  what is an outline/ overview of an intuition that VP=?VNP is connected or not (closely?) connected to the P=?NP problem?

am looking for "not complex" or "straightforward" sketches or constructions, not necessarily "rigorous".

[1] Recent Progress on Arithmetic Circuit
Lower Bounds / Ramprasad Saptharishi, Bulletin of EATCS

  The field of arithmetic circuit complexity has lately seen a flurry of results.
  Several of these results are centered homogeneous depth four circuits,
  and come tantalizingly close to separating the algebraic analogue of
  P from the algebraic analogue of NP.

[2] Does $VP \neq VNP$ imply $P \neq NP$?


texts:
Martin Fowler in his blog post on "The LMAX Architecture" tried to describe the component called Disruptor as a multicast graph of queues

  At a crude level you can think of a Disruptor as a multicast graph of
  queues where producers put objects on it that are sent all the
  consumers for parallel consumption through separate downstream
  queues...

I'm having difficulties understanding the nature of a multicast graph


texts: Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

texts:
Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt using $f(n)$ alternations and space $g(n)$.

Ruzzo proved that $\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n)$. He also showed that $\mathsf{NC}^k \subseteq \mathsf{AALTSP}(\log^k n, \log n) \subseteq \mathsf{NC}^{k + 1}$.

Is $\mathsf{NC}^k = \mathsf{AALTSP}(\log^k n, \log n)$?


texts:
The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One can reduce 3SAT to it pretty easily so that the number of variables becomes roughly the number of clauses in the original instance, and so because of sparsification, under ETH you won't be able to get a subexponential time algorithm. (Also, it's known that NAE-SAT for unbounded length clauses requires $2^n$ time under Strong ETH.)

My question is, what is the best exponential time running time in terms of the number of variables?

There is a trivial reduction to 3SAT that does not increase the number of variables $n$ so that the fastest 3SAT algorithm has the same running time on NAE-3SAT instances (the best known is by Hertli, $1.308^n$).
Is there a faster known algorithm for NAE-3SAT than the one for 3SAT?
(Or is there a reduction that shows that the two problems are equivalent with respect to exact algorithm running times?)

What about monotone NAE-3SAT? Here there are no negated variables. It's known that this problem is also NP-complete. What's the fastest algorithm for it?


texts: Is Escardó's metric semantic for PCF+timeouts fully abstract ?

texts:
In his 1999 workshop paper "A Metric Model of PCF", Martín Escardó  showed that it is possible to give a simple interpretation of PCF in the category of complete ultrametric spaces and nonexpansive maps.

He showed this model was adequate, and that it could model the addition of a timeout construct (i.e., an operator which would run its argument for some finite number of steps, and either yield an answer or signal an error if it failed to terminate within the time limit). He then suggested that it would be natural to investigate whether the metric model was fully abstract with respect to PCF+timeouts.

Has anyone investigated this, and if so, what's the answer?
Does PCF+timeouts realize the same functions as Turing machines, including at higher type?

(As an aside, how do you put accents into the text? I've dropped an accent from both  his first and last names. EDIT: Name fixed. I'm leaving this parenthetical in so that the comments to the post continue to make sense.)


texts: Is it possible to MAC a quantum state with a classical key under reasonable assumption?

texts:
Assume that classical one-way functions secure against quantum adversaries exist.  Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that:

One who knows $k$ can recover $Q$, provided that $AuthQ$ has not been altered.
If $AuthQ$ has been altered, this can be detected with high probability.

It may or may not be possible to recover the original state without the secret key.  What matters is that, given the secret key, one can be confident that:

The creator of the quantum state had the secret key
The message has not been tampered with since.


texts: Conversion technique/tool from temporal logic CTL,CTL* or LTL to μ-calculus

texts:
Suppose one wants to use a μ-calculus model checker, but specify things in temporal logics, which is easier (more intuitive). Is there a technique (even better, a tool) that automatically translates formulae in any of these logics (CTL,CTL* or LTL) to the μ-calculus?

Thanks very much in advance!


texts: Is it possible to encrypt something in such a way that it can be decrypted by two different keys?

texts:
I'm a lowly web dev / programmer of 10 years who's never tried to wrap his brain around the high concept stuff, so apologies is this is a stupid question (or if it belongs in programmers.stackexchange.com)

I started wondering the other day, is it possible to encrypt something and have it decryptable by two different keys?

Suppose you wanted to have a user's data encrypted by a user-defined key, but you also wanted a safely stored "backup" key in case the user forgot their key. Is that even theoretically possible?


texts:
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against matching the amortized complexity of certain operations with a worst-case bound).

The only reference I've been able to find so far is a survey from COCOON by S.R. Kosaraju and M. Pop.

Are there any other good surveys or set of papers to read regarding de-amortization?


texts:
Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable?

Of course this might seem silly, since there are linear time algorithms for HORN-SAT. On the other hand, HORN-SAT is P-complete, which means it does not have log-space algorithms unless P=L. Accordingly, restrict the computational abilities of the verifier to L. Now the verifier is very feeble, so the problem is no longer silly.

Another twist on this is whether it can be a zero-knowledge proof.


texts: Computational power of cellular neural networks

texts:
A cellular neural network is a kind of recurrent neural network that could be thought of as a hybrid between neural nets and cellular automata.

As I understand it, the classic Chua-Yang CNN is limited to a fairly small set of functions, but addition of a second layer or a different choice of nonlinearity expands the function set to all computable. This sounds very similar to traditional neural networks, where Kolmogorov's 1957 theorem says that a two-layer net can represent any continuous function arbitrariliy close.

However, there is also the significant caveat that traditional shallow neural nets are very inefficient at representing complicated functions. Do universal CNNs have a similar weakness? Do they require excessively large network sizes or take too long to converge when used for complicated function computation?


texts: What language $L \in NCM$ has $\overline{L} \not \in NCM$?

texts:
$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not closed under complement.

However, I've never seen a proof of this given explicitly. In Ibarra's paper,
the non-closure is implied because if NCM were closed under complement, subset would be decidable.

However, I've never actually seen an example of a language where $L$ is in $NCM$ but $\overline{L}$ isn't.

I'm wondering, can anyone provide such an example, and preferable, a source describing it that I could cite in a paper?


texts: The semantics of Parsing Expression Grammars

texts:
Is there a simple and intuitive explanation for the fact that the following parsing expression (where S is the starting symbol, $ denotes end-of-string and / is ordered choice)

S <- X $
X <- 'a' X 'a' / 'aa'

only matches strings of 'a's with a length that is a power of 2? (The same grammar interpreted as a CFG would match strings of 'a's with a length that is a multiple of two.)

And how can PEGs be suitable for the specification of computer languages if ordered choice makes the language defined by a PEG that unintuitive to understand?


texts: Function with space-depending computation time

texts:
Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at least $n^2$ (where $n$ is the length of the input) and is NP-hard when there is only linear space.

If there is such a function, please show one.


texts:
In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a graph exists, or can give a construction.
Given two integers $d$ and $k$, I seek an undirected bipartite graph $G=(L∪R,E)$ with:

All vertices in $L$ have degree either $d$ or $d+1$.
Exactly $k$ vertices in $R$ have degree $d−1$, all other vertices in $R$ have degree exactly $d$
The graph is $d−1$ edge-connected.

I really believe that such a graph does exist. But it is a bit difficult to come up with a proof, or a construction. Anyone can show that such a graph exists?


texts: Does using Normal Order Evaluation instead of Normal Order Reduction lose the Normalization theorem?

texts:
Normal Order Reduction (NOR)
reduce the leftmost, outermost redex.

Normal Order Evaluation (NOE)
reduce the leftmost, outermost redex, but not within the body of abstractions.

So (λw. (λx.x) z) is in normal form under NOE, but not under NOR.

Does using NOE instead of NOR weaken the Normalization property?

The Normalization property states that if there is a normal form under beta-reduction, that NOR will find it.
Edit:
Sorry, it's the Curry/Feys Theorem that says that NOR always finds a normal form if it exists.


texts: What is a precise definition of "in-place"?

texts:
"In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition?

To further clarify the discussion, what models of computation can we say are in-place? We can probably say whether a specific C program running on a specific machine is in-place. Can we say whether a C program is in-place, independent of its implementation? Can we say whether a Turing machine is in-place? Can we identify in-place algorithms with known complexity classes?


texts: Gap in degree of representations of candidate boolean functions

texts:
Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be one of the following Boolean function:

$0)$ Equality function - $Eq_k^n(x)=1\iff x_1+\dots+x_n= k$

$1)$ Threshold function - $Th_k^n(x)=1\iff x_1+\dots+x_n\ge k$

$2)$ Majority function - $Maj_n(x)=1\iff x_1+\dots+x_n\ge \lceil\frac{n}{2}\rceil$

$3)$ Modular-$s$ function - $MOD_k(s)=s\iff x_1+\dots+x_n\equiv 0\mod k$

If a function 'represents' $P(x_1,x_2,\dots,x_n)$, that means the function and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$.

If a function is rational then its degree is the sum of degrees of numerator and denominator.

What is known about the smallest degree of a:

$A)$ polynomial $p(x_1,x_2,\dots,x_n)\in\mathbb R[x_1,x_2,\dots,x_n]$

$B)$ rational function $r(x_1,x_2,\dots,x_n)\in\mathbb R(x_1,x_2,\dots,x_n)$

that represents $P(x_1,x_2,\dots,x_n)$ in each case of $0,1,2$ and $3$?

In which case the gap is the largest? It seems intuitively that $2,3$ should be the most complex with possibly the largest gap for $3$.

Note that both the polynomial and the numerator and denominator of the rational function can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.


texts: canonical complete problems for $\Delta^P_n$

texts: Finding whether or not a QBF can be satisfied is a canonical complete problem for both $\Sigma^P_n$ (start from $\exists$) and $\Pi^P_n$ (start from $\forall$). What is the canonical complete problem for $\Delta^P_n$?


texts: Question about an old result of Erdős and Simonovits

texts:
My question concerns the  following result of Erdős and Simonovits.

A graph $G$ is $d$-almost-regular if $d\delta(G)\geq \Delta(G)$. Theorem 1 of the above paper states that a large $n$-vertex graph $G$ with $n^{1+\alpha}$ edges contains a large $d$-almost-regular subgraph $H$ for a constant $d$ depending only on $\alpha$. I cannot follow the proof of the theorem:

In case a) of the proof, if $C_1$ represents less than $\frac{1}{2}n^{1+\alpha}$ many edges, then we consider $G-C_1$. The resulting graph has only then at least $\frac{1}{2}n^{1+\alpha}$ edges, if $n$ refers to the order of the graph we are considering right now in the inductive step and not the order of the original graph (unless we are in the first step of the induction).

When we later show that the induction terminates after a bounded number os steps, however, we estimate the number of edges by $\frac{1}{(4A)^k}n^{1+\alpha}$. This holds only true if $n$ refers to the order of the original graph throughout the induction.

I tried to modify the proof such that case a) works, that is, $n$ refers to the order of the current graph in the inductive step. It is not hard to show that also then the induction terminates. However, with those modifications I cannot obtain that the subgraph $H$ is still large.

Am I misunderstanding something? Is there a newer presentation of this theorem?


texts: What is the computational complexity of "solving" chess?

texts:
The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work backwards to all the possible moves/positions that would allow White to move in to one of those positions. If White ever found herself in such a position she could win by moving to the relevant checkmating move. Now we work backwards another step and so on. Eventually we get back to all the possible first moves White could make. The point is, once we've done this, we know that we have White's best response to any move Black makes.

Recently (last five years or so) Checkers was "solved" in this way. Obviously Noughts and Crosses (what the colonials might call "Tic-Tac-Toe") has been solved for ages. At the very least since this xkcd but presumably long before.

So the question is: what factors does this sort of procedure depend on? The number of possible legal positions, presumably. But also perhaps the number of legal moves at any given node... And given this, how complex is this sort of problem?

Bonus question: how long before a $2000 PC can solve checkers in a day? Chess? Go? (Of course for this you also have to take into account increasing speed of home computers...)

I've added the graph-algorithms tag because you can represent these games as trees, but if I'm abusing the tag please add something more appropriate


texts: Enumerating all simply typed lambda terms of a given type

texts:
How can I enumerate all simply typed lambda terms which have a specified type?

More precisely, suppose we have the simply typed lambda calculus augmented with numerals and iteration, as described in this answer. How can I enumerate all lambda terms of type N (natural number)?

For example, the first few lambda terms of type N are

zero
succ zero
succ (succ zero), K zero zero
succ (succ (succ zero)), K zero (suc zero), K (suc zero) zero, iter zero suc zero

and so on. How can I systematically continue this pattern, while ensuring that only well-typed terms are generated?


texts:
Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome.

How hard is it to find the size minimal palindrome cover? (this seems doable by dynamic programming, but I'm not sure it works).
Does the problem become harder if given as input is also a bound $b$ on each palindrome length?

Consider the simple greedy algorithm, which always takes the longest palindrome which starts at the current location. For example, if $w=1213312$, then it'll output $(121)\cdot(33)\cdot(1)\cdot(2)$, while the optimal cover is $(1)\cdot(213312)$.

Does the greedy algorithm provide 2-approximation for the problem?


texts: Standard format for representing large graphs

texts:
I am aware of the "famous" DIMACS graph format (which frankly looks a little clunky to me - "c" for a comment line ?) and the METIS file format.

While it's not particularly hard to invent my own graph format, it's nice to follow something accepted so that reuse of code for generating examples and testing algorithms is easier.

  Is there a standard accepted format for representing graphs for use
  with testing graph algorithms ?


texts: Generalized Secretary Optimization Problem

texts:
In the standard Secretary Problem, the goal is to hire the best secretary from a list of candidates.  I've recently witnessed a failed hiring attempt for a needed position and it inspired a similar game:

The goal is to maximize the net score.  Each candidate has a value that (if hired) would be added to the score.  And each day that goes by without hiring a candidate costs the company 1 point of score.  Starting score is 0.

Each day, the company either interviews a new candidate or attempts to hire a previously interviewed candidate.  The value of the candidate is discovered during the interview and is uniformly distributed between $0$ and (known) $v$.  There is an unlimited number of possible candidates to interview.

If the job is offered to a candidate, then the candidate will accept with a probability of $d^k$ for (known) constant $d$ and $k$ being the number of days since the candidate was interviewed.  You may only attempt to hire a candidate once.

So the question is: what is the best strategy for this game given $v$ and $d$?  Other natural questions: what is the best strategy if $v$ and/or $d$ are unknown?

Any insights, answers, or references to similar games would be appreciated.


texts: What is known about data structures for encoding a set while considering approximate Rank queries?

texts:
Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$.

There are many data structures that allow storing $S$ while answering Rank queries of the form:

  How many items in $S$ have identifier smaller than $i$, for some $i\in\mathcal U$? I.e., we are looking for $R_i(s)\triangleq|\{j\in S\mid j\le i\}|$.

These data structures use $n(1+o(1))$ bits and answer such queries in $O(1)$ time (we can get improved memory bounds if some bound $m<n$ is known on the set size).

Assume now that we want sub-linear space, and are willing to settle for approximate Rank queries. That is, given $i$, we want to return an estimate $\widehat{R_i(S)}$.

  For some $\epsilon>0$, what is known about the size of such data structures that when queried produces estimates that satisfy ${R_i(S)}\le\widehat{R_i(S)}\le{R_i(S)}(1+\epsilon)$ in $O(1)$ time?


texts: Fixed dimension Linear Integer Programming in $NC$

texts: We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?


texts: Minimal polynomial reduction of dominating set to max clique

texts:
Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$

It is well known that it is NP complete to determine the  minimal dominating set of $G$ and that is usually done via the vertex-cover problem.

As the title suggests, I would like to reduce dominating set to the max clique problem. One can of course use the standard reductions to do so, but I would like to find a as "small as possible" reduction. That is I would like to be able to reduce a graph $G$ to a graph $\widehat{G}$ that is as small as possible and so that $\gamma(G)$ can be efficiently determined from $\omega(\widehat{G}).$ Here $\gamma$ and $\omega$ are the size of the dominating set and clique number respectively.

Can someone suggest such a reduction?