texts: Are recursive forms of Godel's statement possible?

texts:
The self-referentiality of the P/NP problem has sometimes been highlighted as a barrier to its resolution, see, for instance, Scott Aaronson's paper, is P vs. NP formally independent?  One of the many conceivable resolutions to P/NP would be a demonstration that the problem is formally independent of ZFC or true but unprovable.

It's conceivable that the self-referentiality of the problem can pose a deeper challenge in proofs of independence, for example, if statements about its provability are themselves unprovable or otherwise impossible to reason about.

Suppose we call a theorem T Godel_0 if it is true but unprovable in the sense of Godel's theorem.  Call T Godel_1 if the statement "T is Godel_0" is true, but unprovable. Call T Godel_i if the statement "T is Godel_{(i-1)} is true.

We know that Godel_0 statements exist, and a few examples have been found "in the wild" that are not constructed explicitly for this purpose, as in this article.

My question is: do there exist any Godel_1 statements or higher?  Are such statements a natural consequence of Godel's theorem?

What about a statement about which we can prove absolutely nothing: ie, one for which for every k > 0, T is Godel_k?

I can ask an analogous question for formal independence, although I suspect the answer is "no" there.

To return to the P vs. NP question, let me ask whether there's even a hint that Godel's theorem is relevant to questions of class separability.  Have any true but unprovable statements been identified with respect to complexity classes -- beyond, of course, the obvious connection between halting problem and Godel's theorem?


texts: Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

texts:
I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?

I understand lots of things that might cause a log factor to be multiplied in the run time, e.g. sorting or tree based algorithms, but what could cause you to divide by a log factor?


texts:
Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT arbitrarily well is provably NP-hard by the PCP Theorem.

A canonical algorithm for approximating WEIGHTED-MAX-3SAT is MAX-WalkSAT. Looking around I found some information on other algorithms (i.e. branch-and-bound, the DPL algorithm) which are commonly used to find solutions to 3-SAT or (unweighted) MAX-3SAT, but I didn't see any discussion of how well these would work for the weighted version. Intuitively, without being adapted they would not work as well.

I'm wondering what other algorithms are commonly used to approximate WEIGHTED-MAX-SAT, if there are well-known WEIGHTED-MAX-SAT solvers, and the relative quality of these algorithms/solvers.


texts: Cluster Assignment in the Stochastic Block Model

texts:
Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are assigned to clusters in different versions of the SBM.

Consider a graph $G = (V,E)$ with $n$ vertices.

In [1], the SBM is defined in the following way:

  Each vertex $v \in V$ is assigned independently a hidden (or planted) label $\sigma_v$ in $[k]$ under a probability distribution $p = (p_1,...,p_k)$ on $[k]$. That is, $P(\sigma_v = i) = p_i$, $i ∈ [k]$.

  Then the cluster $V_i$ is given by all vertices $v$ with label $i$, i.e., $V_i = \{ v \in V : \sigma_v = i \}$.

  (Then randomly add edges between the clusters. This is not relevant to this question.)

In [2], the SBM is defined as follows:

  Partition the vertex set $\{1,2,...,n\}$ into $k$ clusters $V_1,V_2,...,V_k$ , of sizes $n_1,n_2,...,n_k$, respectively.

  (Then randomly add edges between the clusters. This is not relevant to this question.)

Observe that in the setting of [1], the assignment of the vertices to the clusters $V_i$ is random. Even the sizes of the clusters $V_i$ are random variables. In [2], both the cluster assignments and the sizes are deterministic.

My question is as follows:

  Are the models of [1] and [2] incomparable? Or does there exist a reduction s.t. the results of [1] can be used for [2] or vice versa?

[1] Abbe, Sandon: "Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery." FOCS 2015.

[2] Jalali, Han, Dumitriu, Fazel: "Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models." NIPS 2016.


texts: Is there a space efficient way to represent numbers on the lambda calculus?

texts:
This is something I've been thinking. While it is agreed that Lambda Calculus is equivalent to a Turing Machine in power, is it actually so? Church Numerals are not very space efficient and I'm not aware of any better way to represent numbers using the LC. This leads me to the intuitive conclusion that, while, theorically, LC is as powerful as a TM, there is a natural limit that states that a program in LC will never be able to compute natural numbers as fast as a TM, given a physical world and limited resources.

Now I've throw many ideas and it is hard to define most of what I'm saying formally, but does that intuition make any sense?


texts:
In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times.

Consider the following "improvement" of the run length encoding. In run length eXtreme (RLX), the code stream consists of tuples $(c_i, p_i,l_i)$, where now $p_i$ specifies a position.
Given a code stream $(c_1,p_1,l_1)\cdots(c_K,p_K,l_K)$ we start with an infinite all 0 string and for $k=1,\ldots,K$ write the character $c_k$ to positions $[p_k,p_k+l_k-1)$ overwriting whatever may have been written in these positions before. At the end we output the length
$$n=\max_k (p_k + l_k -1)$$
prefix of this string.

For simplicity let us not worry about the bit length of the code words and take each code word as unit cost. Given a string $s$, let RLX(s) denote minimum number of code words that produce $s$ when decoded as described above.

How fast can we calculate RLX(s)?

Let us fix a string $s$ which does not contain any 0s and denote by $r(i,j)=\mathrm{RLX}(s[i..j])$. We can write a recurrence for $r$ as so:
\begin{align}
r(i,j) &= \min\begin{cases}
    1 + r(i+1,j)\\
    \min_{i<k\le j: s[i]=s[k]}r(i+1,k-1)+r(k, j)
\end{cases}
\end{align}
To see this, consider the optimal encoding $E$ of $s[i..j]$. Either $s[i]$ has a dedicated code word or multiple characters in the final string $s$ are produced by the code word which produced $s[i]$.

If $s[i]$ has a dedicated code word in E, clearly $r(i,j) = 1+r(i+1,j)$. Otherwise, let $k$ be the index of the leftmost character produced by the same code word. Then we have $r(i,j) = r(i+1,k-1) + r(k,j)$.

Taking this recurrence literally leads to an obvious $O(n^3)$ dynamic programming algorithm.

  Is there a faster algorithm for calculating RLX via a custom algorithm or a dynamic programming optimization?

Submodular interval functions:

An interval function maps two integers $i\le j$ to a real. An interval function is called submodular (aka concave, Inverse-QI, Inverse-Monge, etc.) if
for $i\le i'\le j\le j'$ we have
$$f(i,j') + f(i',j) \le f(i,j) + f(i',j').$$

Note that the $r$ we have defined above satisfies $r(i,j)\le r(i,k) + r(k+1,j)$ so one may hope r is submodular, at least when restricted to indices of the same character. But even such restricted forms of submodularity is false. Consider:

/*       5
 *      111
 *     44444
 *    3333333
 *   222222222 234
 *  111111111111111
 */

s = 123415143212341

We have r(1,11) + r(7,15) = 6+5 but r(7,11) + r(1,15) = 4 + 9.
Further the $r(\cdot,\cdot)$ is not a totally monotone matrix either.
Are there other dynamic programming optimization that may still apply to this problem?


texts: Erdos conjecture, number of cliques, Turan`s graph

texts:
Erdos&Stone conjectured in 1946-08 that

there are at least $ck-1$ (k+1)-cliques in $G=(V,E)$
whenever $|V|=ck$, $|E|-1$ is the edge-count in Turan's
$T(|V|,k)$, i.e.,

$|E|= 1+\lfloor {(k-1)|V|^2} / (2k) \rfloor$.

I am looking to see whether this conjecture has been proved in literature.
Didn't see a trace of it myself.

Thanks in advance.


texts: Complexity of counting all connected subgraphs

texts:
Let G be a connected graph.

  What is the complexity of counting all connected subgraphs if G is of the following types?

  G is general.
  G is planar.
  G is bipartite.

I don't care about any structures or ..., just need to count all the connected subgraphs!
I'm also interested in the complexity of counting all connected subgraphs with exactly k nodes in G.

Pointers to papers and books are also welcomed!


texts:
The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it.

I deliberately write this question very informally. Lacking details, it is possibly stated a bit incorrectly. Please feel free to point out the corrections in your answers.

In the following papaper:
Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork, and Moni Naor, SIAM Rev. 45, 727 (2003), DOI:10.1137/S0036144503429856,
the authors write:

  Suppose researcher A has obtained a proof that P ≠ NP and wishes to communicate this fact to professor B. Suppose that, to protect herself, A proves her claim to B in a zero-knowledge fashion...

There are several standard NP-complete problems, like satisfiability (SAT), Graph-Hamiltonicity, and Graph-3-Colorability (G3C), for which zero-knowledge proofs exist. The standard way of proving any NP-theorem is to first reduce it to an instance of the aforementioned NP-complete problems, and then conduct the zero-knowledge proof.

This question pertains to such reduction. Assume that the P vs. NP is settled in any of the following ways:

P = NP
P ≠ NP
P vs. NP is independent of the standard axiomatic set theory.

Let σ denote the proof. Then, P vs. NP is in an NP language (since there exists a short proof for it). The reduction from the theorem (say, P ≠ NP) to the NP-complete problem (say SAT) is independent of σ. That is:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

This is well beyond my imagination! It seems that, even if we are given the proof σ, it is unlikely that we can construct such formula ϕ.

  Could anyone shed some light on this?

In addition, let L be an NP language in which P vs. NP lies. The language is consists of infinitely many theorems like P vs. NP, of arbitrary sizes.

  What is a candidate for L?
  Can L be NP-complete?


texts: Faster pseudo-polynomial time algorithms for PARTITION

texts:
I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or differ only by 1 (if n is odd).

I think we can do this in pseudo polynomial time $O(n^2 A)$, where $A$ is the sum of numbers in the set.

Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c < 2$?

Thanks in advance!


texts: A more intuitive proof of the Zone theorem ?

texts:
The Zone theorem says that if we stab an arrangement of n lines with another line, the total complexity of its zone, the set of all 0-, 1-, and 2-faces adjacent to it,  is O(n). The actual constant is something like 6n at least as stated in various textbooks, and the proof is by induction with a reasonably careful charging argument.

I was asked this question in class, and don't have an answer:

  Is there an alternate, more intuitive
  proof of the Zone theorem ?

Now I realize that many people find induction quite intuitive and would be offended by my implication, and am willing to amend the above to merely "alternate" for them. But is there any such proof ? Or even a proof from the book ?


texts: Is "two or zero" matching in a bipartite graph NP complete?

texts:
I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is incident to exactly two or exactly zero selected edges, and each right-hand vertex is incident to at most one selected edge?

Obviously if replace "two" with one we have the matching problem, which can be solved in polynomial time. I've tried in vain to solve my problem using network flow or matching, and am also stumped when I try to reduce from NP-complete problems.


texts: What is "distributed computing" as a field of computer science?

texts:
I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. Algorithms and computational techniques are should be discussed in High-performance computing sub-area.

Am I wrong ? Where I can read strong thesis about distributed computing and it hierarchy ?

Thanks.


texts: What are the must-read search trees paper?

texts:
I would like to ask a help from researchers who conduct a research in an area of search trees. Could you please write the list of the must-read papers and most recent papers which are important to read
if I want to write papers about search trees.

I personally has the following list of papers (It's nonuniform, quite old and affects different topics. There is also a huge amount of papers about finger search tree but I didn't write references to them).
Thank you for help.

Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (July 1985), 652-686. DOI=http://dx.doi.org/10.1145/3828.3835
Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (June 1983), 362-391. DOI=http://dx.doi.org/10.1016/0022-0000(83)90006-5
Scott Huddleston and Kurt Mehlhorn. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 2 (June 1982), 157-184. DOI=http://dx.doi.org/10.1007/BF00288968
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu. 2009. The geometry of binary search trees. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 496-505.
Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased Search Trees. SIAM Journal on Computing 1985 14:3, 545-568
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak:
Self-Adjusting Binary Search Trees: What Makes Them Tick? ESA 2015: 300-312

Since I conducted research in area of fast concatenation of search trees:

Haim Kaplan and Robert E. Tarjan. 1996. Purely functional representations of catenable sorted lists. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96). ACM, New York, NY, USA, 202-211. DOI=http://dx.doi.org/10.1145/237814.237865
Purely Functional Worst Case Constant Time Catenable Sorted Lists. Lecture Notes in Computer Science.  Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas.  Algorithms – ESA 2006, Chapter 18, 172-183. Berlin, Heidelberg.  http://link.springer.com/10.1007/11841036_18


texts: When polynomial GI implies polynomial (edge) colored GI?

texts:
Crossposted from MO.

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).

There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge colored GI the simplest
is to replace colored edge by a GI preserving gadget encoding
the color (subdividing edge enough times is the simplest case).
For vertex colored GI, attach some gadget to a vertex.

Suppose GI is polynomial for some graph class $C$.

  Q1 For which $C$ polynomial GI implies polynomial
  (edge) colored GI?

Using a reduction with gadgets might make the graphs
not members of $C$.

On the other hand certain gadgets/transformations
might make the graphs members of some other polynomial
GI class.

Example of edge colored reduction $ G \to G'$.

Make a clique of $V(G)$. Color edges in $E(G)$ with $1$
and non-edges with $0$.  It is the coloring function
that preserves $G$ and to recover $G$ from $G'$ just
take the edges colored $1$. $G'$ is clique, cograph,
permutation graph and almost sure in many other nice
classes. Subdividing the edges odd number of times
(distinct for $0,1$ removes the colors and makes $G'$
perfect bipartite graph, preserving isomorphism).

Maybe another approach is to take the line graph
of $G'$ and add pendant (universal) vertices connected
to vertices corresponding to $E(G')$.

  Q2 Are there nice gadgets/transformations for similar
  constructions?

Thought about planarizing $G'$ by choosing some
universal drawing of the clique and replacing
edge crossing by planar gadgets preserving colors
say $C_4,C_6$ for equal colors and something else
for distinct colors. Don't know if this preserves
isomorphism.

Another possible approach might be automorphism
preserving coloring or subdivide every edge of
$K_n$, use 3 colors ${0,1,2}$ for vertices $V(G),E(G),E(\overline{G})$
and try to recognize self complementary graphs by
automorphism exchanging $E(G)$ and $E(\overline{G})$.

  Q3 Is the automorphism group of the subdivision of $K_n$
  tractable to compute?

The orders after the few initial terms are $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$
which is A052565

Dima suggests this might be easy for $n$ large enough and the initial
terms are exceptions.

  Q4 Given vertex colored subdivision of $K_n$ for $n > 4$ and its automorphism group
  where the high degree vertices are colored $0$, some degree $2$
  are $1$ and the other are $2$, what is the complexity to find
  automorphism exchanging $1$ and $2$?

Added The paper On Recognizing Cayley Graphs p 86 claims:

  Given a class C of Cayley graphs, and given an edge-colored
  graph G of n vertices and m edges, we are interested in the problem of
  checking whether there exists an isomorphism φ preserving the colors
  such that G is isomorphic by φ to a graph in C colored by the elements
  of its generating set. In this paper, we give an O(m log n)-time algorithm
  to check whether G is color-isomorphic to a Cayley graph.

This appears close to the question, is it relevant?


texts: What is the query and randomness complexity for very efficient PCPs?

texts:
In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11).

  Theorem 1 (informal). There is a PCP system where, to prove and verify
  that a program $P$ accepts the input $(x, w)$ within $T$ steps for some
  witness $w$ (with $|x|, |w| \leq T )$ [... in parallel time,] the prover runs
  in parallel time $O((\log T)^2)$, when also given as input the transcript of
  computation of $P$ on $(x, w)$ [and] the verifier runs in parallel time
  $O((\log T)^2)$.

I'm having trouble determining whether the authors state the asymptotic randomness used and queries made for this PCP verifier. I see that Lemma C.8 (on page 134) gives an expression for the number of queries used and amount of randomness used. However, I would be grateful if someone could interpret this into a big O notation formula.

  What is the number of queries and amount of randomness used by this PCP
  verifier?


texts: Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

texts:
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational hierarchy) of the nonrational phenomena... using rational relations as a tool for comparison. Rational sets are at the bottom of this hierarchy. Moving upward one encounters 'algebraic phenomena,'" which lead to "to the context-free grammars and context-free languages of Chomsky, and to several related topics."

But Eilenberg never published volume C. He did leave preliminary handwritten notes for the first few chapters (http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html) complete with scratchouts, question marks, side notes and gaps. But they do not reveal much beyond the beginnings of the well-known power series approach to grammars.

So, my actual question -- does anyone know of work along the same lines to possibly reconstruct what Eilenberg had in mind? If not, what material is likely closest to his ideas?

The site http://x-machines.net/ is about x-machines, one of Eilenberg's key innovations, but it deals mainly with applications of x-machines rather than further developing the theory as Eilenberg seemed to promise.

Also, anyone know why Eilenberg stopped before making much progress on Volume C? This was the late 70's, and he lived until 1998, though he did not appear to have published any math after Volume B. Yet he seemed to have the math for Volumes C and D largely done, at least in his mind.

(Same question asked on math.stackexchange -- https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages -- apologies if this is considered cross-posting.)


texts: Follow-the-leader algorithm in swarm formation: literature on the subject?

texts:
In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum decision without general knowledge of the map).

I'm trying to get a more rigorous understanding of any background literature on similar algorithms. Surely this is not an original idea, but I don't even know what terms to start googling for.

Here is diagram of the functioning of the algorithm.

Every circle is a soldier, with the center number representing a uniquely assigned soldier_id. Soliders have finite vision range but know the global position of the "X".

When prompted to form a swarm, soldiers start looking for the soldier within its vision range that had the smallest soldier_id and follows it. If it is itself the lowest soldier_id in range, it starts going in direction of the X. This leads to an organic formation of all the soldiers, with the soldier with the lowest soldier_id at the helm.

As I said, I'm trying to get a sense of general literature on similar algorithms and I don't have nearly enough experience general knowledge of computer science to know where to start. Perhaps there are similar ideas in place in bee or ant colonies or other biological systems. Perhaps even in cell formation?

I'm not even sure this is the appropriate place to ask this question. If it isn't, any pointers would be appreciated.


texts: Ensemble of tree decompositions for all-pairs problem

texts:
Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of self avoiding walks on $G$ passing through nodes $u$ and $v$ for all pairs of nodes $(u,v)$. For a single pair $(u,v)$, one approach is dynamic programming on a  tree decomposition of the graph constrained to have a bag containing both $u$ and $v$. For all pairs of nodes, one may need to consider several tree decompositions, so that every pair of vertices is contained in some bag of some decomposition. The interesting question is how to come up with a such a set of tree decompositions so that they the overall problem complexity is kept low. Has this kind of problem been studied?

Some other problems where "tree decomposition ensemble" might be useful

all pairwise marginals in a graphical model
two-point correlation function for Ising/Potts/hardcore models on finite graph
Hessian of $f:\mathbb{R}^{|V|}->\mathbb{R}$ where $f$ is some function whose computation relies on tree decomposition of $G$. For instance, $f$ could be multivariate Potts polynomial of $G$, some general labeled graph polynomial or partition function of Gibbs distribution on $G$
computing how some FP+C definable graph invariant is affected by deletion of any pair of vertices


texts: Can I apply the constraint while constructing the Lagrangian?

texts:
Consider the problem:

$\min_X ||XAX^T||_F$

s.t. $X^TX=I$

If A and X are real matrices, the lagrangian will be $tr(XAX^TXA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$ where $\alpha_i$ and $\beta_{ij}$ are Lagrangian multipliers.

Can I apply $X^TX=I$ here such that the Lagrangian becomes $tr(XAA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$?


texts: Categories a computer scientist should know about

texts:
I am a computer scientist with a CS degree from the 80's.
I am learning category theory by myself.
I am looking for advice about learning category theory.
E.g. it is quite helpful in learning category theory
to have examples from a familiar topic like logic or programming languages.
What I know
I have read the answers to this question and the paper
Physics, Topology, Logic and Computation: A Rosetta Stone
which builds up concepts with parallels between category theory,  logic, and theory of computation.
I know about the following categories:
• categories
• monoidal categories
• braided monoidal categories
• closed monoidal categories
• symmetric monoidal categories
• closed braided monoidal categories
• compact monoidal categories
• cartesian categories
• closed symmetric monoidal categories
• compact braided monoidal categories
• cartesian closed categories
• compact symmetric monoidal categories
Questions

Are there any other major categories that a computer scientist should know about?

Were there any that have fallen out of favor?
If yes, why?
Have they been replaced with other categories?

When thinking about categories should I
focus on the arrows first before the objects?


texts:
A homomorphism $h: G\to H$ from a graph $G$ to a graph $H$ is a function from the vertices of $G$ to those of $H$ which preserves edges, that is, if $(x,y)$ is an edge of $G$ then $(h(x),h(y))$ is an edge of $H$.
A homomorphism induces an equivalence class on the vertices of $G$: two vertices are equivalent if they are mapped to the same vertex. We say that a homomorphism identifies at most two vertices if all the equivalence classes are singletons except one which may possibly contain two vertices.
A decomposition of a homomorphism $h: G \to H$ is a sequence of graphs $G=G_0, G_1,..,G_n=H$ such that:

For every $i\in[0,n-1]$, there is a homomorphism $h_i:G_i \to G_{i+1}$ which identifies at most two vertices.

$h=h_{n-1}\circ \dots \circ h_0$ .

The width of such decomposition is the maximum tree-width of the graphs $G_i, i\in[1,n]$.
Of course, any homomorphism between two graphs of tree-width k can be decomposed, but I do not know if I can bind the tree-width of the intermediary graphs. I am wondering then if the following result is true:
Conjecture:   For every integer $k$, there is  $k'$ such that every homomorphism between graphs of tree-width $k$ admits a decomposition of width $k'$.
At the beginning, my conjecture was that $k'=k$, that is, every homomorphism between graphs of tree-width $k$ can be decomposed without exiting the class of tree-width $k$ graphs. But for certain homomorphisms between graphs of tree-width $2$, every decomposition is of width at least $3$.
Do you know this problem? Do you have bibliographical recommendations which can help me attack this problem?


texts: What constitutes denotational semantics?

texts:
On a different thread, Andrej Bauer defined denotational semantics as:

  the meaning of a program is a function of the meanings of its parts.

What bothers me about this definition is that it doesn't seem to single out what is commonly thought of as denotational semantics from what is commonly thought of as non-denotational semantics, namely structural operational semantics.

More precisely, the key ingredient here is modularity, or compositionality, of the semantics, or put differently, the fact that they are defined according to the abstract structure of the program.

As most (all?) formal semantics nowadays tend to be structural, is this the required definition?

So, my question is: What is denotational semantics?


texts: I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview of the basic uses of them?


texts: Distance of arbitrary vectors to Hadamard code

texts:
Let $n$ be a positive integer and $N = 2^n$. The Hadamrd code of "block length" $N$ can be generated using the inner product $f_u(x) = \langle u,x \rangle$ mod $2$ for all $u \in \{0,1\}^n$. It is straight forward to show that two different elements of the Hadamard code differ on exactly a fraction of $1/2$ of their values, e.g. their relative distance is exactly $1/2$.

What about the distance of arbitrary vectors to the Hadamard code? I've read in certain papers that this distance is also bounded by $1/2$ but other papers explicetely consider the case of vectors having distance $> 1/2$ to all elements of the code. Can anyone help me?


texts:
Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307:

  Given a tree $S$, define … $\#$ is the
  least hereditary, symmetric,
  irreflexive relation on $Tran_S$ such
  that $(s,a,s')\#(s,b,s'')$ if $s'\neq s''$.

What is a hereditary relation? If I replace in the quote “the least hereditary, symmetric, irreflexive relation” with “the least hereditary relation”, do I get the equivalent statement?


texts: Can Non-termination be considered an algebraic effect?

texts:
Non-termination is sometimes considered an effect.  I have been reading about algebraic effect systems (What is algebraic about algebraic effects and handlers?), and I suspect non-termination (like that arising from a fixed point operator) could fit in the algebraic effect framework.

For instance if effects systems act like continuations, it seems easy to add a handler that supplies "fuel" for possibly non-terminating computations.

Another way to encode a non-termination effect might be though SKI combinators, since they are Turing complete and I think they can be presented as an algebra.

The programing language Koka has a non-termination effect, but it is a built in "primitive" effect.  So it's unclear to me if it could be encoded by a user in their standard effect system.

Can non-terminating computation be considered an algebraic effect?  If so, are there standard ways to do it?  Any references would be great.


texts: A constrained shortest path problem. What is the complexity?

texts:
I've got the following problem:

Consider a graph $G=(V,E)$ with $V=\{v_1,\ldots,v_n\}$, and edge-set $E=\{e_1,\ldots,e_m\}$, with associated costs $c_1,\ldots,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,\ldots,t_k\,$, taking into account these costs. This is the shortest path problem. So minimize the sum of total costs from $s$ to all $t_1, \ldots , t_k$.

My problem is similar, but now with the constraint that the total number of vertices (not counting $s$ and $t_1, \ldots ,t_k$) used by these shortest paths is bounded (upperbound) by an integer $M$ satisfying $0 \leqslant M \leqslant n - k - 1$. If a vertex is used by multiple paths, it only counts once for the constraint. So these paths can, together, use no more than $M$ vertices to go from $s$ to $t_1, \ldots, t_k$.

What is the complexity of this problem, is it polynomial or exponential?
Is this problem NP-hard?


texts: SUBSET-SUM with binary - unary - "positional" encoding

texts:
I don't know if my question is too simple (I'm not an expert, so feel free to delete it)

SUBSET-SUM (given a set of integers $<x_{1},...,x_n>$, find if the sum of one or more non-empty subset equal 0) is NP complete

If we use unary encoding $<x_{1},...,x_{n}> = 0^{x_{1}}1...0^{x_{n}}1$ we fall back in P (UNARY-SUBSET-SUM)
Proof: if m is the initial length of the unary input, reduce input size to $log(m)$ switching to binary representation -> simulate a nondeterministic TM that solves the SUBSET-SUM in polynomial (linear) time $O(log(m))$ -> the simulation is $O(2^{log(m)})$ -> welcome in P .

But if we map $<x_{1},...,x_{n}>$ to a number N in which each bit "positionally" represents $x_{i}$, i.e.
if $x_{i} = -1$ then set bit 0
if $x_{i} = 1$ then set bit 1
if $x_{i} = -2$ then set bit 2
if $x_{i} = 2$ then set bit 3
... and so on (for example we encode the subset $<-1,-2,2,4>$ with $10110001$ (bit 0 is on the left), the subset $<1,3,-4>$ with $0100011$, ...)
(perhaps the simplest enumeration of finite subsets of $Z$) ... I'll call it POSTIONAL-SUBSET-SUM (perhaps it has another name :-)

It seems that we cannot apply the same strategy used to prove that UNARY-SUBSET-SUM is in P
(for some inputs switching from "positional" to binary representation expands the input)

So, my question: is POSITIONAL-SUBSET-SUM in P ?
If not ... is POSITIONAL-SUBSET-SUM NP-complete ?

Thank you in advance,
Vor


texts: Number of $0/1$-monochromatic rectangles and communication complexity

texts:
What is the relation between number $0$-monochromatic rectangles in characteristic matrix and communication complexity?

What is the relation between number $1$-monochromatic rectangles in characteristic matrix and communication complexity?

Precisely how does this connect to logrank conjecture?

Is the number of $0$-monochromatic rectangles always almost same as $1$-monchromatic rectangles?


texts: Number of binary gates needed to compute AND and OR of n input bits simultaneously

texts:
What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard
gate elimination technique does not work here as by assigning a constant to any of the input variables
one trivializes one of the outputs.

The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener
in a slightly different form: "Let $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$. By the elimination method one
can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."


texts:
Statistical tests are used to check whether a source of randomness is "good". Blum and Goldreich (1992) mentioned two types of statistical tests : (1) deterministic polynomial time statistical tests and (2) logspace statistical tests. They also state that "all the statistical tests used in practice can be implemented by logspace machines". To give some examples, Sivakumar showed that the statistical tests corresponding to set discrepancy problem, lattice approximation problem and Johnson-Lindenstrauss Lemma can be implemented by a logspace machine with an index tape and an advice tape.

I am looking for statistical tests that are in $LogCFL$ but not known to be in logspace. Are there any such tests ?


texts: Subexponential algorithms vs separations

texts:
Williams (see also slide 29 here) has shown that an $\frac{2^{n}}{n^{10}}$ algorithm for satisfiability of circuits belonging to a class $\mathcal{C}$ imply that $\mathrm{NEXP}\nsubseteq \mathcal{C}$.

What are the consequences of an algorithm running in time $2^{o(n)}$ for satisfiability of circuits on class $\mathcal{C}$? Would this imply that some smaller class, such as $\mathrm{EXP}$ is not included in $\mathcal{C}$? What would be the smallest class which would be separated from $\mathcal{C}$ by such a faster algorithm?

Obs1: $n$ is the number of variables.

Obs2: I'm mostly interested in the case in which $\mathcal{C}=\mathrm{NC}^1$

See also the following references:

1) Williams, Improving Exhaustive Search Implies Superpolynomial Lower Bounds, 2010

2) Williams, Algorithms for circuits and circuits for algorithms, 2014


texts: Minimum cost cut with discount - what is the complexity?

texts:
Consider an undirected graph $G=(V,E)$ with non-negative edge costs. Given an integer $k$ with $0\leq k\leq |E|$, let us call an edge set $C\subseteq E$ a $k$-discounted cut, if the following hold:

$C$ is a cut in the usual sense.
The cost of the $k$ most expensive edges in $C$ is changed to 0. (If $k\geq |C|$, then all edge costs in $C$ are changed to 0.) This cost reduction is the "discount." The cost of the $k$-discounted cut is the sum of the edge costs in $C$, after the cost reduction, i.e., the remaining cost after taking the discount.

Task: Given $k$, and the graph with edge costs,  find a  minimum cost $k$-discounted cut.

Question: Is anything known about this problem? Can it be solved in polynomial time?

Note: It is well known that the (conventional) minimum cost cut can be found in polynomial time. It is not clear, however, how the discount influences the complexity.


texts: Relativization with Respect to Non-Recursive Oracles

texts:
In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets.

In another paper Relative to a Random Oracle $A$, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability $1$, Bennett and Gill put forward the notion of random oracles, which are almost surely non-recursive sets. (See the comments below.)

I wasn't aware of any other non-recursive relativizations, unless I came up with one (see this question and Joshua's answer to it.)

  What are the implications of non-recursive relativizations? How are they useful in structural complexity theory?


texts: Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

texts:
Suppose P != NP.

We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

For any hard 3-SAT instance, we would have to add the set of all 3-SAT instances it reduces to via looping through the NP-Completeness reduction cycle, but I don't foresee this adding to the number of hard instances very much.

In this world, we could construct an algorithm that polynomially solves all NP complete problems, except an exceptional few.

Edit:
A softer variant of the question: even if we showed P!=NP, how could we know whether a given method to generate size n 3-SAT problems actually generated hard one with some requisite probability?  If there's no way to know from P!=NP alone, what is required to show that we can generate a hard NP-complete problem?


texts: Difference between 'string relations' and 'tree relations' w.r.t. synchronous CFGs

texts:
Context: http://www3.nd.edu/~dchiang/papers/synchtut.pdf

On page 3, under the section Properties, at the end of the paragraph labeled Closure under composition?, the author mentions 'tree relations definable by synchronous CFGs' in contrast to 'string relations'.

I can't quite make out what he means here. If he hadn't made that claim, I'd have naively and happily believed that every synchronous CFG was effectively (reductively...) taking two parse trees and relating them production by production and thus trivially representing some tree-like relation.

What's the difference between the two?


texts: Breaking encrypted file store with a file?

texts:
Let's say you have an encrypted file store of some kind such as an encrypted hard drive, ZIP file, etc.  You don't have the private key or password to this file store, so a brute-force attack is not a good option.

But what you DO have is a copy of a file -- a file that you know for certain is on that file store.

Does this help reduce the complexity of an attack? In other words, would I be able to crack the encryption in less time by knowing part of the contents of the encrypted file store?

(Forgive me if this is obvious, encryption is not my specialty.)


texts: Is it known whether hypergraph minimal covers are P-enumerable?

texts:
Is it known or unknown whether hypergraph minimal covers are P-enumerable? I would be most happy with lower bounds. I'd also like to hear about conditional results, which assume some conjecture is true. Of course, I'd also want to know about closely related problems (such as independent sets and cliques).

Motivation. I have a problem to which enumeration of minimal covers in hypergraphs can be reduced, and an algorithm that is exponential in the worst case and works OKish in practice.  I wonder whether doing much better is possible; or are there good reasons I haven't found something better? (The problem arises in the context of static analysis of programs.)

Background. A hypergraph is a pair $(V, E)$ of vertices $V$ and edges $E:(V\to2)\to2$, the latter being subsets of vertices. A cover $U$ is a subset of vertices that intersects all edges: $\forall e:E\;\exists u:U\;(u:e)$. A cover is minimal when no strict subset of it is a cover.

Judging from the results of googling ‘P-enumerable’, the term is not too popular. I'm referring to the definition given by Valiant [1]:

  A relation $R$ is P-enumerable iff there is a polynomial $p$ such
  that for all $x$ the set $\{y:R(x,y)\}$ can be enumerated in time
  $|\{y:R(x,y)\}|\times p(|x|)$.

Related. According to Johnson et al. [2], in 1988 it was unknown whether minimal covers of hypergraphs are P-enumerable.  The equivalent problem for graphs, when $\forall e:E\;(|e|=2)$, is known to be P-enumerable, since 1977 [3]. But, [2] explains why the method of [3] cannot be generalized to hypergraphs. The related decision problem of finding one minimal cover is clearly in P. The related counting problem is #P-complete for graphs [1].

I also found some sources [4, 5] which I find hard to read: one uses many concepts I'm not familiar with, and the other is long.  For example, Theorem 1.1 in [4] seems to imply that there exists a quasi-polynomial algorithm; but, [5] has an extra condition (1.2, submodularity) that wouldn't hold for the covers problem. Moreover, [5] mentions an obstruction (Proposition 5.2) similar to the one alluded to by [2] (‘exercise for the reader’) for the methods of [3]. So, it seems to me that it was still unknown in 2002 whether hypergraph minimal covers are P-enumerable, although I'm not completely sure I interpret [4 and 5] correctly.

[1] Valiant, The Complexity of Enumeration and Reliability Problems, 1979.

[2] Johnson, Yannakakis, Papadimitriou, On Generating All Maximal Independent Sets, 1988.

[3] Tsukiyama, Ide, Ariyoshi, Shirakawa, A New Algorithm for Generating All Maximal Independent Sets, 1977

[4] Boros, Elbassioni, Gurvich, Khachiyan, Makino, Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities, 2002

[5] Elbassioni, Incremental Algorithms for Enumerating Extremal Solutions of Monotone Systems of Submodular Inequalities and Their Applications, 2002


texts: Is there a specific time that the Journal of the ACM is released? Monthly, quarterly, etc? Or does it depend on how many significant papers have been gathered to warrant a new issue? I couldn't find anything specific on their website on this point.


texts: Categorical semantics for S5 modal logic?

texts:
Does anyone know where I can look to find out what the generally categorical semantics of S5 is?

For S4, the answer is well-known: we want a Cartesian closed category with a product-preserving comonad to model $\Box$ and a monad strong with respect to the comonad to model $\Diamond$.

In Awodey's book on category theory, on page 235 he remarks in passing that this setup becomes S5 when the monad is left adjoint to the comonad. However, he doesn't give a reference.


texts: Number of common neighbors of any two adjacent vertices in a edge transitive graph is same or different?

texts:
We have a theorem that, if the graph G is symmetric (both vertex and edge transitive) then G^p (by joining the vertices which are at the distance at most p in G) is also symmetric. See the reference ''Chromatic sets of power graphs and their application to resource
placement in multicomputer networks'' by N. Imani, H. Sarbazi-Azad, S.G. Akl, P. Moinzadeh;
Computers and Mathematics with Applications 58 (2009) 403–413.

But if you take Hypercube powers (Q_n)^p, the above question doesn't work out.


texts: Lowest Common Ancestor Problem in Directed Acyclic Graphs

texts:
What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"?

Edit: I am working on all-pair reachability problem in DAG and I strongly feel that I can achieve O(mn) time for the problem stated above by extending my approach. I have searched the internet enough to find the current best algorithm for this problem but all I can find is the solution to this problem: "For any pair of vertices in a given graph G, return one LCA for the same". And this problem is trivial and easy. And you don't need to google it for me! And read the problem correctly, it has more content than simply "lca" and "dag"! So, can someone please tell me now about the current best algorithm for the problem stated.


texts: Is there a name for this unimodilarity-related property?

texts:
Consider an arbitrary integer linear program of the form

$\min f(x,y) \\
@ \  Ax + By \leq c\\
x,y \in \mathbb{Z}_+$

If you continuous-relax the integer constraint and still always get integer points as solutions, we talk about the unimodularity property.

But what if you relax the integer constraints and always get integer solutions for $x$, but not necessarily for $y$? Is there a name for this property, and is this type of problem covered anywhere in literature/research?


texts: Gift bits when encoding a sequence of messages, how is that?

texts:
Recently a friend of mine asked a question I couldn't give immediate answer to.

Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ bits. So far so good, information quantity is additive.

But, from another side of view, besides coding the meaning of $n$ messages we also gave an order to them, this gives us additional $ \log _2( n!) $ bits. How is that?

I told that unordered messages are meaningless, but he replied, "Take something like photos or novels for example, clearly the order doesn't matter and we can use it to pass additional information".

Can you please explain this apparent paradox?


texts: Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

texts:
DISCLAIMERI do apologize in advance if this question turns out to be
  silly, for some trivial reason that I may be overlooking in this
  moment.

Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ is true: it is possible to efficiently simulate quantum computation by classical deterministic computation.

Now, from that very little I know about quantum computing (I'm much less than an amateur when speaking about it), if I'm not wrong a Quantum Turing Machine is able, by its very definition, to generate true randomness.

Henceforth, if $\mathbf{P} = \mathbf{BQP}$, then there exists a classical deterministic algorithm which is able to quickly output true randomness (by just quickly simulating some Quantum Turing Machine).

But... what would randomness be then? Would it even exist at all? Would you be willing to continue to call it randomness?

John Von Neumann once said: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin". But the above classical deterministic algorithm would indeed be an arithmetical method of producing random digits, no? When thinking a bit about it, I was also considering Max Tegmark's view (expressed in his last book) according to which randomness does not exist at all: he believes it is only an illusion, more precisely the subjective feeling you perceive each time you get cloned (i.e. each time the Universe you live in gets branched in 2 or more Universes).

From my amateur point of view, if I were told that we live in a $\mathbf{P} = \mathbf{BQP}$ world, then I would believe that there is no such thing as randomness. How could it even exist, if it is perfectly producible by a mechanical procedure? Where would it reside? If true randomness can be implemented into a C++ concretion of the above classical deterministic algorithm, then where would it actually be? Would it be hidden somewhere? Would it continue to be present somehow, inspite there is no trace of it in the C++ code? For me, simply it would not exist.

Now, to summarize, this question is not about how likely you consider $\mathbf{P} = \mathbf{BQP}$ to be. Rather, the question boils down to the following:

  In a world where $\mathbf{P} = \mathbf{BQP}$, would randomness exist at all?


texts: Neighborly properties in a bipartite graph

texts:
Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.
Question: Decide whether there exists a subset $S\subseteq A$ with $\emptyset\ne S\ne A$ such that $|S|=|N(S)|$.
My attempts so far: First some observations. If $a \in A$ has $\deg(a) = 1$, then we are done so it suffices to consider the case where $\deg(a)\ge2$ for all $a\in A$. Further, if we can find a proper subset $S\subseteq A$ such that $|S|\ge|N(S)|$ then we are also done (remove a well chosen vertex of $S$ one at a time). The problem is straight-forward to solve if $G$ is a tree.
Various greedy approaches have been tried and have thus far failed e.g. consider the following counter-example for greedy by smallest degree.

I am beginning to suspect that the problem is NP-hard, but I do not have any good reduction sources (Hamilton Cycle comes to mind, but that uses all the vertices of the graph).


texts: How can algorithms with nested combinatorial searches be quasi-linear?

texts:
I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without stating any relaxing conditions. Since I haven't encountered any proofs that specifically target this issue, I wonder if there is something obvious I'm missing in algorithm analysis.

The example comes from this paper by Spielman and Teng, more specifically section 2.1, algorithm Nibble. The algorithm is a for-loop (with the number iterations defined approximately by $log_2(n) ln(n)$, where $n$ is the number of vertices in the graph). However, step 3.c states that the algorithm will exit, if a suitable set of $j$ vertices exists that satisfies some conditions. This set is in the paper's terminology designated as $S_j(q_t)$ and is defined as "the set of $j$ vertices $u$ that maximize $\frac{q_t(u)}{d(u)}$", where $d(u)$ is the degree of vertex $u$.

Note that the focus here is on the general problem of generating a subset of elements that fulfills some conditions and is subject to a constrained number of elements. Other aspects of the algorithm were covered in the proof.

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set. Also, I found no mention of it in the proof section. That, the reputability of the authors and the prominence of the paper makes me think that it's something obvious.

My question is what factors would make such an algorithm quasi-linear? Citing a paper where a similar algorithm's complexity is proven and the proof focuses this issue is most welcome.


texts: What exactly are the classes FP, FNP and TFNP?

texts:
In his book Computational Complexity, Papadimitriou defines FNP as follows:

Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation $R_L$ such that for all strings $x$: There is a string $y$ with $R_L(x,y)$ if and only if $x\in L$. The function problem associated with $L$, denoted $FL$, is the following computational problem:
Given $x$, find a string $y$ such that $R_L(x,y)$ if such a string exists; if no such string exists, return "no".
The class of all function problems associated as above with language in NP is called FNP. FP is the subclass resulting if we only consider function problems in FNP that can be solved in polynomial time.
(...)
(...), we call a problem $R$ in FNP total if for every string $x$ there is at least one $y$ such that $R(x,y)$. The subclass of FNP containing all total function problems is denoted TFNP.

In a venn diagram in the chapter overview, Papadimitriou implies that FP $\subseteq$ TFNP $\subseteq$ FNP.
I have a hard time understanding why exactly it holds that FP $\subseteq$ TFNP since problems in FP do not have to be total per se.
To gain a better understanding, I've been plowing through literature to find a waterproof definition of FP,FNP and sorts, without success.
In my very (humble) opinion, I think there is little (correct!) didactic material of these topics.
For decision problems, the classes are sets of languages (i.e. sets of strings).
What exactly are the classes for function problems? Are they sets of relations, languages, ... ? What is a solid definition?


texts: Algebraic formulation for packing problem

texts:
My question is regarding the algebraic formulation for packing problems in graphs.

Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint triangles in a given input (undirected) graph. I am aware of techniques that approach this problem combinatorially. Is there a way to frame this problem algebraically?

Also, in context of graph theory, are algebraic methods less powerful when compared to combinatorial methods? Or is there any particular intuition that governs which approach is more effective in certain problems?

I apologize if my question sounds too general. The purpose of this question is to try and form an understanding of algebraic vs combinatorial methods in the context of graph theory.


texts: Is the question about closed reduction using token-passing nets still open?

texts:
The question about possible implementation of closed reduction using token-passing nets is asked on page 17 in Token-passing Nets for Functional Languages by Jose Bacelar Almeida, Jorge Sousa Pinto, and Miguel Vilaca:

  It would be interesting to explore the applicability of this idea to encode closed reduction as defined by Fernandez et al.

Is this question still open?


texts: Decide whether a point is a vertex of a polytope?

texts:
Inspired by the question, I would like to ask the following question:

Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection
$f(\Theta)= \{(\vec{c}_1\cdot \vec{x}+ d_1, \cdots, \vec{c}_m\cdot \vec{x}+d_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$

Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity?

I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm.


texts: Error correction with asymmetric channel

texts: Suppose A is trying to transmit a message to B over a noisy low bandwidth channel, while B has the ability to simultaneously transmit arbitrary amounts of information losslessly to A. Are there particular encoding algorithms adapted to this scenario? It seems like the ability to provide feedback to A should allow for faster information transmission. I've tried searching for this, but I haven't found anything, partly because I don't even know what terms to search for.


texts: Results on universal approximation for learners other than ANNs

texts:
I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) states (Wikipedia):

  "the standard multilayer feed-forward
  network with a single hidden layer
  that contains finite number of hidden
  neurons, and with arbitrary activation
  function are universal approximators
  on a compact subset of $R^n$. "

I wondered if there are any similar results (in terms of approximation power) for other types of learners (e.g. decision trees, boosting methods, SVMs, etc.).

This leads me to a second but related question: Is this a topic that is formally studied in TCS? If so, are there any good texts for somebody with an applied background?

Thanks


texts:
What does it mean for a distribution to be efficiently samplable?

This came up in the discussions about the distributions used in the recent attempted P!=NP proof.

The context was that a distribution modeled as a directed graphical model that can be factored such that each factor is sub-exponential in size or dependent on a polylog number of parents then it is efficiently samplable.  In contrast, if a factor is dependent on O(n) parents then the table size is exponential and no longer efficiently samplable.

The barrier here to efficient sampling appears to be the exponential size of the table required to describe the factor that depends on O(n) parents.  Is this the key point or is there some other barrier?

I should clarify, that if one could replace the exponential sized table for the conditional distribution that depends on O(n) parents with a polynomial time function that returns the value of $P(x_n;x_1...x_{n-1})$ given the parents then it seems the problem becomes efficiently samplable.


texts: Low rank approximation of matrix under $l_2$ norm

texts:
Theorem 14 of this paper by Tam´as Sarl´os gives a relative error rank-$k$ approximation of a given matrix $A$ under the frobenius norm. I am looking for reference of a similar result (relative error low rank approximation) under the $l_2$ norm.

Pls let me know I am  able to put the question clearly.


texts: Secure MAC when the adversary has a verification oracle

texts:
A message authentication code (MAC) is defined by a triple of efficient algorithms $(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$, which satisfy the following (the definition is taken from section 4.3 of the Katz-Lindell book):

On input $1^n$, the algorithm $\mathsf{Gen}$ generates a key $k \ge n$.
On input $k$ generated by $\mathsf{Gen}$, and some message $m \in \{0,1\}^*$, the algorithm $\mathsf{MAC}$ generates a tag $t$. We write $t \gets \mathsf{MAC}_k(m)$.
On input a triple $(k,m,t)$, the algorithm $\mathsf{Verif}$ generates a single bit $b$. We write $b \gets \mathsf{Verif}_k(m,t)$.

It is required that for all $k$ output by $\mathsf{Gen}$ and all $m \in \{0,1\}^*$, we have $\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$.

The security requirement is defined via the following experiment, between the challenger and the adversary $A$:

$k \gets \mathsf{Gen}(1^n)$.
$(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$.
Let $Q$ denote the set of all queries that $A$ asked to its oracle.
The output of the experiment is defined to be 1 if and only if:

$\mathsf{Verif}_k(m, t) = 1$, and
$m \notin Q$.

The MAC is considered secure if the probability that the experiment outputs 1 is negligible in $n$.

The experiment above resembles a "chosen plaintext" experiment against a symmetric encryption scheme, where the adversary can obtain ciphertexts corresponding to messages of his choice. In a more powerful attack, called "chosen ciphertext" attack, the adversary is allowed access to a decryption oracle as well.

So, my question is:

  What happens if we allow the MAC-adversary to access a verification oracle as well? In other words, what if line 2 of the experiment is replaced with the following:

  $(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$.

  Notice that in the new experiment, $Q$ only includes queries $A$ asks from the $\mathsf{MAC}_k$ oracle.


texts: Computable function $f = \Theta(g)$ with $g$ uncomputable

texts:
This question most likely has a simple answer; however, I do not see it.

Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that, for all $n$ large enough: $g(n) \leq f(n) \leq c \cdot g(n)$ (that is $f(n) = \Theta(g(n)$)?


texts: How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

texts:
Can anyone help me with the following problem?

I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the differences $a_i-b_j\pmod N$ (for example $N=251$), without knowing the concrete corresponding relation. Since the values $a_i,b_j\pmod N$ are not uniquely defined given the differences $a_i-b_j\pmod N$, we look for any  valid assignment of values.

Definitely, trying each permutation of the $K^2$ numbers in the list (totally $K^2!$ possible cases) and then solving the modular equations with $a_i,b_j$ as the variables is infeasible.

In fact, this problem arises in a paper on the cryptanalysis to an early version of NTRU signature scheme (http://eprint.iacr.org/2001/005). However, the author wrote only one sentence “A simple backtrack algorithm ﬁnds one solution…” (in Section 3.3) and so can anyone give more explanations? What’s more, the author also mentioned that “every circular shift $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ or a swap $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ results in the same pattern of $a_i-b_j\mod N$” and is this statement helpful?


texts: Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?

texts:
Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$,   (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. So, the question is
is there an analog of the Berman Hartmanis conjecture for the class NP$_{\mathbb{R}}$? Of course, the question posed here is dependent on the model - in other words, as the definition of NP$_\mathbb{R}$ uses the BSS model, do all of NP$_{\mathbb{R}}$-complete problems have the same structure using the BSS model(this approximates the Berman-Hartmanis conjecture for NP over reals)?


texts:
Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability the strings in the language and always rejects strings not in the language.

QMA's definition is based on verification algorithms: it contains language for which there is a quantum verifier algorithm that, for yes-instances, there is a quantum proof that makes the verifier accept with probability at least $\frac{2}{3}$ and for no-instances, all proofs make the verifier accept with probability at most $\frac{1}{3}$.

Each of them seems to have a property that makes it accept some language that seem hard for the other. NQP can recognize languages for which the acceptance probability is exponentially small. However, QMA allows some error for no-instances.

The connection between perfect soundness version of QMA (do not allow error for no-instances) and NQP was proved by Kobayashi, Matsumoto and Yamakami. Now, I'm wondering about the relation between QMA and NQP.


texts: Joining lists with some common elements in average case

texts:
What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?


texts: Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

texts:
Background

It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.

Although some natural problems are known to exist, many of them are in someway equivalent to simulating Turing machines or the lower bound result is heavily dependent on the machine model.

See this question for more details: Problem in deterministic time $n^p$ and not lower

Question

Does there exist $k \geq 2$ such that there exist problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not computationally hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Update: As pointed out by @NealYoung in the comments, when $k=2$, no such problems exist.  Also, for the computational model, let's go with multitape Turing machine.

Why does it matter?

I suspect that if the answer is false (meaning that no such problems exist), then all polynomial time problems have non-uniform nearly linear size circuits.

Let me try to explain.

Let $k \geq 2$ be given.

Suppose for a minute that every problem in $DTIME(n^k) - DTIME(n^{k-1})$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Next, consider a problem $X$ that is complete for $DTIME(2^{k \cdot n})$ (such as the problem of simulating a $2^{k \cdot n}$-time bounded Turing machine on an input).  By the time hierarchy theorem, this problem cannot be solved in much less than $2^{k \cdot n}$ time.

Then, convert this problem $X$ from binary inputs to unary inputs to get a problem $X'$.  We have that $X' \in DTIME(n^k) - DTIME(n^{k-1})$.  By the assumption, it follows that $X'$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Finally, we can build small non-uniform circuits for $X'$ because there are so few possible unary input strings.  Also, we can build a small circuit for any nearly linear time reduction.  Combining these together, we get small circuits for all problems in $DTIME(n^{k-1})$.

Maybe we can get a contradiction based on some known circuit lower bounds?  Or, there could even be relativized results that come into play.  Any thoughts are greatly appreciated.  Thank you!


texts: Generalized geography on solid grid graphs

texts:
A post here For which families of graphs is Generalized Geography in $P$? mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows no results, but I wanted to see if anyone with more familiarity with the area can confirm.

Related to this question, I also wonder if Generalized Geography on grid graphs with holes or thin graphs are also open? What about on bipartite graphs, expander graphs...etc?


texts:
Consider the following problem:

Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle.

Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the matroid is minimum.

Question: What is known about this problem? Is it solvable in polynomial time?

Note: This is a direct generalization of the minimum cut problem. The latter is well known to be solvable in polynomial time. Since both a matroid and the family of cuts have quite a bit of structure, there might be hope to find a polynomial time algorithm for the generalized problem, as well.


texts: Is it possible to create a "quote" function that, given a native λ-term, returns its λ-encoded representation?

texts:
Suppose we implement the λ-calculus inside the λ-calculus itself with λ-encodings and Bruijn indices:

Lam = λ body .        λ Lam . λ App . λ Var . Lam body
App = λ fun . λ arg . λ Lam . λ App . λ Var . App fun arg
Var = λ idx .         λ Lam . λ App . λ Var . Var idx

Is it possible to implement a quote() function that, given a native term, returns its own λ-encoded representation? For example:

quote(λ f . λ x . f (f x))

Would return:

Lam (Lam (App (Var 1) (App (Var 1) (Var 0))))

If not, is it possible if given a type?

quote(Arr(Arr(T,T),Arr(T,T)), λ f . λ x . f (f x)))

Where Arr(Arr(T,T),Arr(T,T)) represents that the term we want to quote has the following STLC type: (o -> o) -> o -> o.


texts: Complexity of finding even cuts for a graph

texts:
Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in $V_a$ has an even number of neighbours in $V_b$ and every vertex in $V_b$ has an even number of neighbours in $V_a$? In particular I am interested in the time and depth complexity of solving this problem, or the corresponding decision problem.

I realise that this may correspond to a well studied problem, and if so I would appreciate a pointer to the relevant literature. It seems closely related to a number of SAT problems, but I have not yet managed to find an exact correspondence.


texts:
Which is the easiest way to find a valid Invariant for a While Program in the Hoare program correctness verification?
Is there a "guided" way to do that?


texts: Examples of algorithms and proofs that seem correct, but aren't

texts:
In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've never been asked to show that an algorithm isn't correct.

Are there any classic examples of algorithms that look correct, but aren't? I am looking for cases where the Initialization-Maintenance-Termination approach catches something that first-glance intuition doesn't.


texts: Kth best problem that is NP-hard for K polynomial

texts:
A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to decide whether there are K solutions that achieve a given value.

Garey and Johnson list several NP-hard Kth best problems: Kth Best Spanning Tree, Kth Shortest Path, Kth Largest Subset, and Kth Largest m-Tuple. However each of these problems can be solve in polynomial time if K is restricted to be polynomial in the size of the rest of the input.

Is there a Kth best problem that is NP-hard even if K is restricted to be polynomial in the size of the rest of the input (but poly-time solvable for K=1)? The problem should be natural enough that other Kth best problems can reduce to it, or at least be a good example for how to show NP-hardness of a Kth best problem.


texts: Non-commutative quantum counting with aggregate constant work per increment

texts:
Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work:

class Counter:
    def __init__(self):
        self.bits = []
    def increment(self):
        for i in range(len(self.bits)):
            self.bits[i] = !self.bits[i]
            if self.bits[i]:
                return  # SHORT CIRCUIT
        self.bits.append(True)

Although any given increment may take $O(n)$ work individually, it must also create a situation where the following increments are cheap due to short-circuiting.

When working with qubits, the above approach doesn't work. The short-circuiting test would require a measurement, and various parts of the superposition would have to short-circuit at different times.

With that in mind, consider the following circuit. It keeps applying some unspecified and possibly varying operation to a qubit then doing a conditional increment:

Each increment here is being done naively, so each of the $n$ increments requires $O(\lg n)$ gates and the overall circuit has $O(n \lg n)$ cost. Even though, within each component of the superposition, most of that work is wasted on most increments. Classically we would only need $O(n)$ gates total.

Is there some way to optimize the circuit down to $O(n)$ gates, without depending on the details of $U$?

My initial idea for this problem was to store all the controlled outcomes separately, then merge them pairwise until they were all in a single counter. That would be $O(n)$ aggregate work as desired. But for it to work identically to the original circuit you need to uncompute all the sub-counters used during merging, and the uncomputing doesn't seem to work when the counted values don't commute (e.g. if $U = H$).


texts: Curious about computer-assisted NP-completeness proofs

texts:
In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that

This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be instructed to randomly generate various input configurations and test whether the defined relation was non-affine, non-bijunctive, etc.

Of course, this is a limitation:

The fruitfulness of such an approach remains to be proved: the enumeration of the elements of a relation on lO or 15 variables is Surely not a light computational task.

I am curious that

  Are there follow-up researches in developing this idea of "computer-assisted NP-completeness proofs"? What is the state-of-the-art (may be specific to $\textsf{3SAT}$ or $\textsf{3-Partition}$)?
  Since Schaefer has proposed the idea of "computer-assisted" NP-Completeness proof (at least for reductions from $\textsf{SAT}$), does this mean there are some general principles/structures underlying these reductions (for the ones from $\textsf{3SAT}$ or $\text{3-Partition}$)? If so, what are they?
  Does anyone have experience in proving NP-completeness with a computer-assistant? Or can anyone make up an artificial example?


texts:
While formalizing the gadgets for the proposed reduction of the question
Efficient algorithm for existence of permutation with differences sequence? the following problems came to my mind:

Problem 1 (I call it the "crazy frog problem" :-))

Given a $n \times n$ partially filled board (some cells are empty, some are already filled), a starting cell $c_0 = (x_0,y_0)$ and a list of jump distances $(\Delta x_1,\Delta y_1),(\Delta x_2,\Delta y_2),...,(\Delta x_m, \Delta y_m),\; -n < \Delta x_i, \Delta y_i < n$; is there a sequence $(s_1,s_2,...,s_m), s_i \in \{+1,-1\}$ such that the sequence of
jumps: $$c_j = ( x_{j-1} + \Delta x_j * s_j, \quad y_{j-1} + \Delta y_j * s_j ) $$

makes the frog visit every empty cell of the board exactly once? (every jump must be within the boundaries of the board, at every jump the target cell must be empty, after the jump the cell becomes filled)

Figure 1. An instance of the CFP on the left and its solution on the right.

Problem 2

What is the complexity of the Hamiltonian path problem on grid graphs with holes, if we force the path to be an alternating sequence of horizontal/vertical moves (i.e. two consecutive horizontal/vertical moves along the path are forbidden).

Are these problems already known and what is their complexity?

Notes: there is an immediate reduction from problem 2 to problem 1; probably there is a reduction from problem 1 to the problem of finding a valid permutation from a difference sequence (which I'm trying to prove NPC).


texts:
I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so.

I know that in general it is #P-hard to compute the volume of $\mathcal{H}$
-polytopes, which doesn't exclude the existence of a subclass of $\mathcal{H}$-polytopes where a volume computation could be done efficiently.

Analysing a particular subclass of polytopes I realized that order polytopes belong to this subclass. The volume computation of order polytopes corresponds to computing the number of linear extensions in an underlying poset, which is known to be #P-complete.

Does that imply that volume computation in my special class of polytopes is #P-hard, too?

My thought is yes, because a polynomial time algorithm for my special class would solve the problem of computing the number of linear extensions efficiently. I'm not that familar with complexity theory, so I'm not sure if this argument suffices.

Edit: The special class of polytopes are defined by $P=\lbrace x\in\mathbb{R}^n : Ax\leq b\rbrace$, such that the normal vectors (rows of A) are elements from the set

$R_n:=\lbrace e_i-e_j: i,j\in \lbrace 1,...,n\rbrace, i\neq j\rbrace \cup \lbrace \pm e_1,...,\pm e_n\rbrace$,

where $e_1,...e_n$ are the canonical unit vectors.

Order polytopes are defined by a partially ordered set $(PO,<_{PO})$ with $PO=\lbrace a_1,...,a_n\rbrace$ and

$O(PO)=\lbrace x\in\mathbb{R}^n : 0\leq x_i\leq 1$ for all $i=1,...,n$ and $x_i\leq x_j$ if $a_i<_{PO} a_j$ in $PO\rbrace$.

Hence their normal vectors are precisely from the set $R_n$.

Edit 2: With $\mathcal{H}$-polytopes I mean polytopes given in their halfspace representation (intersection of halfspaces $P=\lbrace x\in\mathbb{R}^n : Ax\leq b\rbrace$).


texts: Maximum number of geometrically disjoint paths - is the complexity known?

texts:
Let $G$ be an undirected  graph, given with a planar drawing.
We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct point in the plane, and each edge is represented by a continuous planar curve between its endpoints. Assume that no other vertex can lie on such a curve, but we allow unlimited intersections among these edge-curves.

Let $s,t$ be two distinguished vertices in $G$. We say that two $s-t$ paths are geometrically disjoint, (with respect to the given drawing), if their geometric representations  do not share any point, other than $s$ and $t$. Note that it is a stronger requirement than being (internally) vertex disjoint in the graph theoretic sense, because they may be vertex disjoint, yet they may share some intersection point of the curves that represent the edges, when we follow through the paths as geometric curves.

Questions:

What is the complexity of finding the maximum number of geometrically disjoint $s-t$ paths?
How about the special case when the edges are restricted to be straight lines?

Remark: Finding the max number of vertex- or edge-disjoint paths is well known to be solvable by network flow techniques in polynomial time. Does the geometric requirement make the problem harder?

Edit: Let us assume that the vertices have polynomially bounded integer coordinates, in terms of the number of vertices. Furthermore, assume an oracle is available that can determine for any two edge-curves whether they intersect or not. When the edges are represented by straight lines, this is straightforward, but in the general case it may be hard to decide whether two curves intersect.


texts: Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover

texts:
In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound is $\Theta(log_{r-1}n)$, while the upper bound is $\Theta(log_{r-1}(nlogn))$, where $n$ is the number of nodes of the graph.

I would like to know (even just empirical) lower and upper bounds on the diameter of non-random $3$-regular graphs. More precisely, such non-random $3$-regular graphs in which I'm interested are those arising after reducing practical real world problem instances (which are known to be structured instead of random) to the $\sharp P$-complete problem $\sharp3$-regular Vertex Cover. In other words, suppose you have a real-world instance of a $NP$-complete problem, and suppose you want to count its solutions: following a chain of reductions, you come out with a $3$-regular graph $G$, whose number of vertex covers encodes the number of solutions of your initial instance.

  Questions

  How is $G$? Is it still structured, as the original instance? Or did it destroyed the initial structure?
  If $G$ is structured, which are the lower bound and the upper bound on its diameter? Do the bounds given by Bollobás and Fernandez De La Vega still hold? Or are such bounds completely different in the structured case?
  Does there exist any automated tool (along the lines of ToughSAT) that, given an instance of a $NP$-complete problem, produces the graph $G$?


texts:
Does any body know any good reference for meaning of straight-line simulatability?
I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for meaning of straight-line simulatability.
Any help is appreciated.


texts: Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

texts:
I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.

I've seen the question regarding the other way around here “Directed” problems that are easier than their “undirected” variant, but I'm looking for for hardness on the directed side.

For example, Feedback edge set is known to be NPC on directed but polynomial time solvable on undirected graphs.

Which other natural problems have the same property?


texts:
Let the Edge Cover Equilibrium Problem be the following:

INPUT: a simple undirected graph $G$.
OUTPUT:

YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge covers of $G$ having even cardinality.
NO, otherwise.

Question:
Which is the best known algorithm to solve it? Has such problem been investigated in the literature? What do we know about it? Can this equilibrium property be reduced to checking some other property of $G$?


texts: Avi Wigderson have a paper on how to derandomize the matrix-valued Chernoff bound. I would like to know whether there exists a simple version of paper on how to derandomize the real-valued Chernoff bound. Thanks so much!


texts:
I've asked the same question on CSSE but with no luck (https://cs.stackexchange.com/questions/89611/is-agda-sound-as-a-proof-system). Therefore I ask it again here in cstheory and hope that more research-oriented audience can give more insights.

I was browsing Agda's stdlib source code, since I was trying to get into it seriously and therefore wanted to know more. I was amazed at that Agda is way more developed than I thought and it's significantly much closer to Haskell than Coq.

However, I was quite a bit panicked when I see some code like following:

toList∘fromList : ∀ s → toList (fromList s) ≡ s
toList∘fromList s = trustMe

It seems there is an observable hole in the system, and it means Agda is not entirely built from ground up by axiomization. Then I saw this,

https://github.com/agda/agda-stdlib/blob/master/src/Data/Colist.agda

data Colist {a} (A : Set a) : Set a where
  []  : Colist A
  _∷_ : (x : A) (xs : ∞ (Colist A)) → Colist A

I took Colist is the same as List in Haskell, allowing optionally infinite length, and from Wiki https://agda.readthedocs.io/en/v2.5.3/language/coinduction.html

  The type constructor ∞ can be used to prove absurdity!

Just as I suspected, optional infinity introduces absurdity. To this point, I felt I was more scared than amazed.

I understand that being practical must come with some trade off. However, Agda is more or less considered as a proof system, arguably more than a progarmming language. There are lots of papers these days are based on Agda. However, a quick code scan has shown holes in many disguises. (Sure Coq also has that, but it's considerably easy to discover: just grep axiom, admit will tell a lot, and Coq supports printing axioms for each lemma.)

Since I am trying to enter Agda, I have no idea what I should expect from it. So the title says all my question: are the system and the results based on it, sound?


texts: What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse systems there are even better algorithms. However, I was wondering if there was some comlexity-theoretic characterization of this problem. For example, is the corresponding decision problem in $\mathbf{NC}$? Is it complete for any complexity class?


texts: Fastest way to find an s-t min-cut from an s-t max-flow?

texts:
Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.

How could I use a sparse s-t flow to find an s-t min-cut in time proportional to the size of the flow and the number of my nodes, for the sparse/low-volume max-flow case?


texts: Good references for understanding the underlying abstractions/ideas of functional programming?

texts:
What are some good references, not very dense, to understand the underlying math and computability aspects of the notion of "functional programming"? I'd like to have something that talks about it from a math point of view and if/when I learn a functional programming language I can have the necessary "aha" moments when seeing the ideas being implemented.

I've read SICP, but that's Scheme specific and is a dense read. I don't really "get" functional programming after reading it and was looking for something more sublime and closer to the underlying math and computability points of views.


texts: What's the complexity of this estate-division game?

texts:
Alice and Bob are splitting their deceased uncle Charlie's estate (a finite collection $X$ of discrete items) according to his wishes.  First A picks an item, then B, then A, and so on.

Alice and Bob each have additive utility functions $u_A, u_B$, so that if Alice ends up with the set $Y \subseteq X$, her utility is $\sum_{y \in Y}u_A(y)$.

These utility functions are common knowledge, as is the fact that Alice and Bob are perfectly rational utility-maximizers.  This implies that the players will not always follow a greedy approach, grabbing the item of greatest worth to them; they will be more strategic.

So, what is the computational complexity of implementing the players' strategies?  It's doable in polynomial space, and that's all I know.


texts: Turing Machine which generates order on the set of its states

texts:
The Turing machine (TM) is an abstract model for effective implementation of (finite algorithmic) calculation. TM is defined over some alphabet of symbols L and reading data performs a finite sequence of operations on these symbols in the manner described a kind of mapping, let's call it the transition mapping. TM has a certain inner state q which may be one element of a finite set Q. Transition mapping T specifies that if the machine reads in the current cell the symbol x from L.changes it to a symbol x ', and next data would be read from right (R) or left (L) cell. During this operation the state machine will change q to q '.
We say that TM is defined as structure $ TM(L,Q,T,\{ START \},\{ STOP \}) $. But for this discussion it would be easier to say that we define certain sets as $ L'= L + \{ L,P \} $ and $ Q' = Q + \{ START,STOP \} $ and then we obtain "symmetric" $ T`: L' \times Q' -> L' \times Q' $. Then we omit any primes when it possible, and we define TM as $ TM(L,Q,T) $.

We may describe states of TM as $ q_{ij} $ where $ i = 0...N $, $ j = L,P $ and $ q_{0L} =q_{0P} =START $, $ q_{NL} =q_{NP} =STOP $. Transition function is defined such that for given $ q_{ij} $ and symbol $ a_k $ from alphabet $ L $ machine in state $ q_{ij} $ reads $ a_k $ and goes to state $ q_{nm} $ and writes symbol $ a_s $ on the tape. That is:

$ T'(q_{ij}, a_k) = T(q_i, a_s,) = (q_n, a_s, x) $

where $a_k, a_s \in L $ and $x \in \{ L,P \}$

  We may ask when $T(q_{ij}, a_k)$
  defines any ordering relation on $ L \times Q $ or on $Q$ or even on $ L \times Q \times {L,P} $ ?

Of course in general there is no such possibility, but in certain situation we may for example has $T(q_{ij}, a_k)$ such that for any $j,k$,

$T(q_{ij}, a_k) = (q_{ nm }, a_s)$ and  $i \leq n $.

In such situation T defines partial order. In such situation $ Q $ may be a lattice with relation generated by order generated by transition function T.

  Are there any interesting facts about
  TM with such (or similar) property?

Remark/Motivation

I wonder if certain relation of this type,may give us algebraic structure on LxQ set. When the answer is yes, we may ask if TM will stop his computation for every data for example. Of course there are is in some way trivial examples of such transition function T. But suppose what if structure generated by T' is much more complicated for example if it is lattice. I suppose in certain situations it may be not trivial ( trivial one is when You have STOP and START as bounding extrema, and all other states are at the same level) So when it occurs, TM has certain and nontrivial data flow through it graph of states. And structure of it ( eg. lattice) may give us a tool for proving specific properties.


texts:
I am looking for an (elegant, fast, etc.) algorithm to draw a binary tree, where the root is distinguished, as well as the left and right children of each node. A typical example is a binary search tree. The goal is to have the densest possible drawing, with the constraints:

The child of a node is below its parent, and in particular the root is alone on top of the drawing;
Each node is symmetric: If it has two children, it must be centered between its children and the children must be vertically aligned;
If a node has a single child, the node and its child are not horizontally aligned: the child must be either on the left or on the right;
Edges between nodes don't go through nodes;
Two nodes are at a minimal distance, say $1$.

The goal is to compute coordinates for each node. The way to make the actual drawing, using any relevant format (SVG, PS, TikZ, etc.), and is not part of my question.
Is there a known (efficient) algorithm for such a drawing?
For now, I use the following algorithm, in which all nodes at the same height in the binary tree are vertically aligned, and :

Recursively, compute the drawing (= coordinates) of the left and right children of the root;
For each child and each height, compute the leftmost and the rightmost nodes;
For each height, compute the minimal distance between the left child and the right child for the distance between nodes to respect the minimal distance;
Take the maximum of these minimal distances ($1$ if one child is empty), and compute from these a shift to apply to the coordinates of both children;
Finally compute the coordinates of the root, vertically centered between its two children.

This gives reasonably good results, but does not ensure constraint 4. It may also not construct the densest possible solution, since it forces all nodes of a same height to be vertically aligned. And it is not particularly elegant, though this notion is of course ill-defined.


texts: Complexity class of phase information in Gauss sum

texts:
Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?

Actually I was looking for something more than the answers given. It is known Gauss sums have a random walk behavior than is exploited in designing low-correlation sequences. Also Montogomery's conjecture provides a tighter bound than the Weil bounds of Deligne under the assumption of random behavior (deeper exposition in the book by Katz and Sarnak - the material of which I am not familiar). I was actually curious whether such randomness has been utilized in computer science. It seems very possible there are uses.


texts: reduction of maximum independet set to minimum distance of code

texts: Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity check matrix?


texts: Bottleneck $k$-link path in a complete DAG

texts:
Let $G$ be a complete DAG: It has vertices $v_1,\ldots,v_n$, and $v_iv_j$ is an edge if and only if $i<j$.
Let $w(i,j)$ be the weight of the edge $v_iv_j$. The weight has the property that $w(i,j)<w(i,j+1)$ and $w(i+1,j)<w(i,j)$.

We are given an integer $k$. We are interested in finding the minimum $\lambda$, such that there exists a path of length $k$ from $v_1$ to $v_n$, such that each edge in the path has weight at most $\lambda$.
Let the optimal value be $\lambda^*$.

Assume one has an oracle that takes $i,j$ and output $w(i,j)$. One does not have to inspect the entire graph in order to find $\lambda^*$.

First, given a $\lambda$, we can decide if $\lambda < \lambda^*$ in $O(n)$ time using a greedy algorithm.

Second, consider the sorted list of elements in $S= \{w(i,j) | 1\leq i<j\leq n\}$. $\lambda^*\in S$. One can select the $i$th largest value in $S$ in $O(n)$ time, because $w(i,j)$ forms a matrix sorted in both row and column (For example, see this). Hence we can do binary search over the elements in $S$, which takes in $O(n\log n)$ time. ($\log n$ iterations, and $O(n)$ time to get the ith element)

Is there a faster algorithm?


texts: Keyword selection problem in search engine marketing auction

texts:
First of all, I am still not sure whether cstheory is well adapted for this question, so I won't be offended if the crowd thinks it is not the case...

In search engine marketing, several problems are interesting. Design of fair (and profitable) auction mechanisms and computation of optimal bidding strategies under bounded monetary resources are two examples of interesting (and well documented) problems.

Another problem of interest is the one of keyword selection: how to select the most profitable keyword (without any link to the amount of money available or to the "topic" of the keyword). "Profitable" can be either giving the best revenue, or the best profit. These problem deals with uncertainty: the clickthrough rate of a keyword is not known, the conversion rate is not known either.

Are you aware of some theoretical work related to this problem?


texts:
Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard?

I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to enumerate the cliques (in particular k-cliques in k-partite graphs). On complexity, they only comment that the max-clique problem is generally hard, but nothing on the specific case.

Note: This is an edit of my earlier question: whether the max-clique problem in a $k$-partite graph is NP-hard, with $k$ being part of the input? As Austin pointed out in the comments, it is easy to see that the answer is trivially yes by a reduction from the general max-clique problem; any graph $G$ on $n$ vertices can be considered $n$-partite.
The new question, however, is more specific and a reduction does not seem so obvious. For example, (and contrary to the original question) for $k=n$ one can easily check if an $n$-partite graph contains/is an $n$-clique. What about general $k$?


texts: Is there a certificate definition for polyL?

texts: Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?


texts: Does kd tree requires triangular inequality for finding k-nearest neighbors

texts:
I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is the function:

$x,y \in [0,255]^3$

$r=\frac{x_1+y_1}{2}$
$dist(x,y)=\sqrt{(2+\frac{r}{256})*(x_1-y_1)^2 + 4*(x_2-y_2)^2 + (2+\frac{255-r}{256})*(x_3-y_3)^2}$

My question now is:

Do I need triangular inequality, given that all other conditions of a metric are fulfilled, for the guarantee that all k-nearest neighbors to a given point can be found.


texts: What is the proof for the inconsistency of impredicativity + excluded middle + large elimination in type theory

texts:
Why is the combination of

impredicativity + excluded middle + large elimination

inconsistent in dependent type theory?

My understanding of large elimination is I am doing large elimination if I am eliminating an inductive type to build a type.

I am trying to learn more about large elimination and how large elimination interacts with other constructs like predicativity and EM. In particular, I would like to know whether such inconsistency can be derived in for example, the impredicative Prop in Coq when large elimination is allowed and if so, how it's derived.


texts:
Consider the 3SUM problem: given a set $S$ of $n$ numbers identify $x$,$y$,$z$, s.t $x + y = z$. It is believed that the simple $O(n^2)$ algorithm is the best possible; reductions from 3SUM have been used to prove lower bounds for other problems assuming 3SUM is hard [Patrascu 2010].

Is it possible to prove that a small amount $n^\delta$ ($\delta < 1$) of free cache does not help for 3SUM? (An algorithm can store information in the cache and access it for free while accesses to regular RAM cost 1.)


texts: Agnostic query learning of decision trees

texts:
Gopalan, Kalai, Klivans gave an algorithm
https://dl.acm.org/citation.cfm?id=1374376.1374451
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given black-box query access to a target function. They use discrete Fourier analysis. Question: How might one extend this to learning decision trees over $\mathbb{R}^n$? Obviously there is no "uniform distribution", unless we limit the domain to a (say) ball, which I'm perfectly happy to do.


texts: Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its optimal solution. How would you construct that?