texts: Diagonalization arguments for QMA type proof systems

texts: Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in stages and diagonalizing any $\cal{P}$ machine against that oracle. Similarly, diagonalization arguments can also be used to diagonalize a $\cal{BQP}$ machine against an oracle like the Grover oracle, and achieve a separation between $\cal{BQP}$ and $\cal{QMA}$. I was wondering whether I can use diagonalization (against $\cal{QMA}$ machines) to separate classes like $\cal{QMA}$ and $\cal{PP}$, or $\cal{QMA}$ and $\cal{AWPP}$. Is there any literature on these types of separations? A subtlety that I note is that for the diagonalization argument against $\cal{BQP}$ machines, the essential idea is that the quantum machine cannot "search for a needle in a haystack", meaning that if there are an exponential number of query states to keep track of, a quantum machine is almost blind to the change in any one of them. However, if you have a prover as well as a quantum machine, the prover can just "give you the needle"; meaning, the prover can just send you the right state to query. Can diagonalization still work in these settings?


texts: Circuit lower bound for NAND based arbitrary deterministic computation

texts: What is the lowest known lower-bound on the number of NAND gates needed in order to perform an arbitrary deterministic computation with a fixed length input and output?


texts: Network design with reachability pattern

texts:
We are given two sets of terminals $A$ and $B$. For each $a\in A$, we are also given $R_a\subseteq B$. Let $|A|+|B|=n$.

We want to find a directed acyclic graph $G$ where $A$ and $B$ are subsets of the vertices, such that $a\in A$ can reach $b\in B$ if and only if $b\in R_a$. We want to optimize the number of edges.

I'm pretty sure this is studied somewhere, but I can't find the right keyword to search for it.


texts: Minimum communication cost for zero knowledge proofs of three colorability

texts:
Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1].  If a graph has $n$ vertices and $e$ edges, a secure hash has $b$ bits, and we seek error probability $p$, the total communication cost is

$$O(ben \log(1/p))$$

over $O(1)$ rounds.  Using a gradually revealed Merkle tree, the total communication can be reduced to $O(be \log n \log (1/p))$ at the cost of increasing the number of rounds to $O(\log n)$.

Is it possible to do better than this, either in terms of total communication or number of rounds?

http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.


texts: Total orders which are the transitive closure of a set in P

texts:
I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.

Consider $T \subseteq \mathbb{N}^2$, a set representing a total order. That is we have some total order $\preceq$ such that $i \preceq j$ iff $(i, j) \in T$.

Does there exist $T$ and a subset $S \subseteq T$ such that:

The decision problem $(i, j) \in T$ is "probably not in P". e.g. is NP-hard or is provably not in P.
The decision problem $(i, j) \in S$ is in P
$T$ is the transitive closure of $S$ (i.e. the smallest set $M$ containing $S$ such that if $(i, j), (j, k) \in M$ then $(i, k) \in M$)

Note that if e.g. there's some polynomial $p$ such that for all $(i, j) \in S$ there exists some $k \leq p(i, j)$ with $(i, k), (k, j) \in T$ then the decision problem for $S$ is necessarily in NP (because you can provide such a k and verifying that it works is polynomial in $i, j$), but I suspect there are examples which don't satisfy this.


texts:
There is the size hierarchy theorem for non-uniform circuits.

  Do we have any size hierarchy theorem for any kind of uniform circuits ?

(By uniform here, I mean DLOGTIME uniform. But I don't know if this matters.)

For example, do $O(n)$-size constant depth threshold circuits have less power than the ones with size $O(n^{10})$ or even super-polynomial ?


texts: What relation is between constraint satisfaction problems and constraint programming?

texts:
Are programs written in the constraint programming (CP) paradigm more expressive than problems defined as constraint satisfaction problem (CSP)?

Wikipedia says about Constraint_programming:

  Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints.

and later:

  The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x <= 5"), and others.

If I understand that correctly CPs can describe superset of problems which can be described by CSP.

I'm especially interested in these programs of puzzle solvers written using CP. In the paper they wrote that some rules can not be described using CP so they used something which looks like imperative paradigm. If I cut off imperative part of programs is that valid CSP problem definition?


texts: What does it mean for a language to have "order"?

texts:
In calculus, a polynomial has order $n$ if it contains terms that raise the unknown to a power $n$.

I'm trying to figure out how this definition of "order" relates to the use of the same word when talking about formal languages.

We say a logic or language is "first order", "second order", or "higher order".  I know it is related to what kinds of states of expressible within that language,b ut what does this mean, fundamentally, and why is it called the "order" of the language?


texts:
The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations.
I would like to know why the name clique width is given to this definition. How it is related to clique definition.


texts: Possibly small circuit complexity class containing REG?

texts:
What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}?

If we believe Theorem 2 in

Koucký, Circuit Complexity of Regular Languages, LNCS 4497, 2007,

then it's NC¹. Is the author right? Are tighter upper bounds on REG known in the meantime?


texts: Definition of fractional in theoretical CS

texts:
What is the definition of the word "fractional" in algorithms? I have encountered the word in phrases like "fractional algorithm", "fractional node routing problem".

Note: English is not my native language


texts: Is it a rule that discrete problems are NP-hard and continuous problems are not?

texts: In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually through gradient techniques. Are there exceptions to this?


texts:
Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and fold functions: they are parameterized by a function, but they don't really do anything interesting with it except invoke it on pieces of other input data.

Some are also second-order but somewhat more interesting:

Fingertrees parameterized by monoids
Splitting a fingertree on a monotonous predicate
Prefix sum algorithms, again usually parameterized by a monoid or a predicate etc.

Finally, some are "truly" higher-order in the sense that is most interesting to me:

The Y combinator
Difference lists

Do there exist other nontrivial higher-order algorithms?

In attempt to clarify my question, under "nontrivial higher-order" I mean "using higher-order facilities of the computational formalism in a critical way in the algorithm's interface and/or implementation"


texts: Reference for NP-hardness of 3-colouring?

texts:
I have a historical question.

I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard.

The tempting answer is “Karp’s original paper”, but that is wrong. Here’s a scan: Reducibility among Combinatorial Problems, Karp (1972). It proves that Chromatic number (Input: a graph. Output: $\chi(G)$) is hard. That’s a harder problem, and the reduction is different from the standard gadget construction (with 3 colours, True, False, and Ground) that implies hardness of 3-colourability.

Garey and Johnson, Computers and intractability, have $k$-colourability as [GT4] and refer to Karp (1972).


texts: Which computational models support bigotous programs?

texts:
A bigotous program is a program which decides if its input is semantically equivalent to itself. Of course, this is impossible in a Turing complete language due to Rice's theorem.

In fact, its pretty hard to find any computational model that supports such a program. Indeed, even extending a computational model with the ability to write bigots often results in contradictions.

What are some computational models that do support bigots?


texts: Optimum first stage solution of two stage stochastic shortest path induces tree

texts:
I struggle with the proof of Lemma 1 in the Paper "Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems" by Ravi and Sinha and hope this is the right community to ask for help.
Problem setting:
There is a graph $G(V,E)$ with edge costs $c_e$ and a source vertex $s \in V$. Now there are $m$ scenarios for the second stage, with scenario $k$ specified by a destination vertex $t_k \in V$, a multiplicative cost scale factor $f_k$ and a probability $p_k$ with which the scenario occurs.
If we chose a set of edges $E' \subset E$ in the first stage they have the cost $\sum_{e \in E'}c_e$. Then in the second stage a scenario $k$ occurs and we have to calculate a second stage solution for the shortest path $P_k$ between $s$ and $t_k$. We assume that the edges of the first stage ($E'$) have now cost zero while the remaining edge costs increase by $f_k$. This results in the following total first and second stage costs:
$$\sum_{e \in E'}c_e + f_k \sum_{e \in P_k \setminus E'}c_e$$
The objective is to find the edge-subset $E'$ that minimizes the total costs.
Lemma:
Now they say that there exists an optimum solution where the set $E'$ induces a tree containing the source $s$. I copy their proof here for simplicity:
My problems and thoughts:

At first I had problems with the first sum $\sum_{P_k \ni e}p_kf_k \ge 1$, but now I think it means, that, in optimum, for any first stage edge the expected cost increase for all scenarios in which the edge is part of a shortest path must not be smaller than 1. Because if the sum was smaller than one, I would save cost if I get the edge in the second stage, which contradicts the optimum assumption. Is this correct?
Now i don't get, how this statement implies $\sum_{k \in K'} f_k \ge 1$. I get that for every scenario in $K'$ there is at least one edge used for $P_k$ for which the above statement is true, but I don't see the logical transition from the edges to the sum of cost factors. I see that this sum is already bigger than 1 if there is only one scenario with $f_k > 1$ but this doesn't help me to grasp the implification.

Thank you in advance
T3K14


texts: Number of graphs with prescribed spectrum

texts:
I have a question relevant to the number of graphs with prescribed spectral ratio.
Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) eigenvalue. Moreover, assume the following (larger than a constant) spectral ratio constraint $$\frac{\lambda_1}{\max\{\lambda_2,|\lambda_n|\}} \ge \Omega(\log(n)).$$
What is the fraction of graphs (out of the $2^{O(n^2)}$ many) that have the above spectral property?

In other words, what is the fraction of graphs on $n$ vertices with increasing spectral ratio?

Edit: A relevant question that might be easier: 'is there a combinatorial property on the graph that leads to an $Ω(\log(n))$ ratio?'


texts: Why exactly are complexity theorists interested in closed timelike curves?

texts:
Context:

There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which shows that certain forms of time travel can make classical and quantum computing equivalent i.e. quantum computers provide no computational advantage if they can send information to the past through closed-timelike curves.

Questions:

The abstract clearly says that closed timelike curves are not known to exist. So why exactly are complexity theorists interested in this topic? Does the study of CTCs provide some non-trivial insight into the fundamentals of complexity theory?
Are there any other world lines that are popularly studied in the context of complexity theory? If yes, why? If not, why not (and then what's so special about CTCs)?

I haven't really gotten around to working through the CTC papers, but I'm trying to get an idea of the "big picture" here, so as to understand the motivation behind studying this topic.

Note: I previously asked about this on Quantum Computing SE, in the context of quantum information theory, but here I'm specifically trying to view it through the lenses of a complexity theorist or computer scientist.


texts: How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

texts:
In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of some general Hamiltonian $H$, which will be given by $e^{-iHt}$. If $H$ is sparse, and the entries of $H$ are available via some blackbox function then there are efficient algorithms to simulate this evolution operator to within some constant distance $\epsilon$ in the trace norm.

According to Berry, Ahokas, Cleve and Sanders, Commun. Math. Phys. 270, 359–371 (2007) 1-sparse Hamiltonians can be simulated efficiently using only 2 black box queries. However, the citations that go with this are to a masters thesis which does not appear to be online and to a STOC 03 paper on quantum random walks by Childs, Cleve, Deotto, Fahri, Gutmann and Spielman which seems to only deal with a specific subset of such Hamiltonians.

I guess that this is in fact true for all 1-sparse Hamiltonians, as the paper seems to indicate, but there is obviously something I'm missing (which is probably in the unobtainable thesis). I would be very grateful if someone could tell me whether or not this is true in general, and if so explain how it can be done (or point to a paper which contains it).

For what it's worth, I am specifically interested in the case of simulating diagonal Hamiltonians.


texts: Complex analysis in theoretical computer science

texts: There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't think of any result in TCS that relies on complex analysis (outside of quantum computing, where complex numbers are intrinsic in the model). Does anyone has an example of a classical TCS result that uses complex analysis?


texts: Terminology for types of universal computation

texts:
Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.

Other models are universal only as far as the input and output are encoded:
$\exists$ a set $A$ such that $\forall$ computable functions $f:\mathbb{N} \rightarrow \mathbb{N}$ the model can compute a function $f':A \rightarrow A$, such that $\forall n \in \mathbb{N},\ f(n)\ = \ d(f'(e(n)))$, for some encoding and decoding functions:
$e:\mathbb{N} \rightarrow A$
$d:A \rightarrow \mathbb{N}$
with suitable constraints on the computability (and possibly the complexity) of these functions.

What are the names for these two types of universality?
Is there any further relevant distinction to be made?

If I understand correctly, there are proofs of universality of systems, such as the Wolfram's 2-state 3-symbol Turing machine which are controversial because of subtleties regarding enconding.


texts:
We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$ is the size of the independent set).

What about approximating it in FPT time?

  Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

What about other $f(k)$s?


texts: Do we have any nontrivial uniform circuits?

texts:
Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$.
On the other hand, it might be that we have much smaller uniform circuits for that problem, even if $t(n)$ is an optimal running time. The circuits may take longer than $t(n)$ to generate, but they are small.
But do we actually know how to build such things? I think the initial question to ask is

(1) Do we have any constructive examples of nontrivial uniform circuits, i.e. uniform circuits whose size is smaller than the best-known running time of any algorithm for the same problem?

Now, I believe that if a problem is in $\mathsf{DTIME(t(n))}$, then we have an exponential-time algorithm to find optimal circuits using an exhaustive search: Given $n$, we write down the answers on all $2^n$ inputs (taking time $(2^n)t(n)$); then we enumerate all circuits on $n$ inputs in increasing size until one is found that gives all the correct answers. The search terminates at either the size of the trivial conversion, $t(n) \log t(n)$, or the truth table of the function, $2^n$ if outputs are $\{0,1\}$. (Edit: Thomas points out that the bound is $O(2^n/n)$ due to Shannon/Lupanov.)
So we have an unsatisfactory "yes" to question (1): Take a language that is hard for any time above $2^n$, but still decidable; the above procedure outputs a truth table of size $2^n$.
So we should refine question (1). I think the two most interesting cases are

(2) Do we have any constructive examples of polynomial-size nontrivial uniform circuits? (Even if they are generated by very slow algorithms.)
(3) Do we have any constructive examples of polynomial-time generatable, polynomial-size nontrivial uniform circuits?

This may be too much to ask. How about an easier question: Do we even know that such a thing is possible? Perhaps no nontrivial uniform circuits exist?

(4) Is the following statement known to be false for any $s(n) = o(2^n)$? (Edit: $o(2^n/n)$, thanks Thomas.) "If a language $L$ has uniform circuits of size $O(s(n))$, then it also has algorithms running in time $\tilde{O}(s(n))$." (If so, then what about when "uniform" is replaced with "polynomial-time-uniform", "logspace uniform", etc?)

Finally, if the above questions are too hard,

(5) Do we have any constructions of uniform families of circuits that are not simply conversions of algorithms into circuits (or writing down the truth table)?

Postscript. An expert I asked about this mentioned "On Medium-Uniformity and Circuit Lower Bounds" (pdf), Santhanam and Williams 2013, which maybe is the most closely related work, but it proves lower bounds (that poly-time-generatable circuits are not too powerful). I'd be interested in any other related work!


texts: Packing $n$ objects into $m$ bins whose size is variable

texts:
Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put these objects into bins. If in the process of putting an object to bins, there is a step where there is not enough room in any of the bins to put the object, we can increase $a$ so that we have larger buckets. Starting at $a=1$, the problem is to find the smallest $a$ where all objects can go to bins. Obviously, if $a$ is very large, we can put all objects in one bin.

Is this similar to a known problem in computer science?
Can this be modeled using some variation of bin-packing?
Can you suggest a heuristic?

Thank you.

EDIT:

I implemented the following heuristic and also the optimal version using the integer programming. The average ratio of $a_{heuristic}/a_{optimal}$ is 1.02 (worst case was 1.23) over 200 runs of the simulation for 20 objects, varying number of bins and randomly generated ball and bin sizes. The heuristic is as follows:

$(1)$ Sort objects from largest to smallest using a priority queue. Set $a = 1$. Assume $U_i$ is the total size of all objects in $B_i$.

$(2)$ Remove the biggest object and call it $O$.

$(3)$ For all bins, find the $1 \le i \le m$ for which $(U_i+O)/B_i$ is the least. Add $O$ to $B_i$ and $U_i = U_i + O$.

$(4)$ $a = max(a, U_i/B_i)$.

$(5)$ Goto $(2)$ if there are more balls.


texts: Impossibility result on metric learning?

texts:
Are there any fundamental limitations (impossibility results) known for metric learning?

Are there any direct connection reduction from/to that I can use results in clustering? (e.g. this: 2 )

2 Kleinberg, Jon. "An impossibility theorem for clustering." Advances in neural information processing systems (2003): 463-470.


texts: What is the best way to find an induced cycle basis of a graph?

texts:
My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph of the original graph)?

I can think of the following naive approach:
Let $T$ be any spanning forest of $G$. Now repeat operation (a) until there are no two edges $e_1 = (u_1, v_1)$ and $e_2 = (u_2, v_2)$ so that $e_1, e_2 \in E(G) \setminus E(T)$ and the path in $T$ from $u_1$ to $v_1$ contains the path in $T$ from $u_2$ to $v_2$. Operation (a) adds edge $e_2$ to $T$ and removes one of the other edges in the path from $u_2$ to $v_2$ in $T$. Finally, construct the cycle basis of $G$ according to the resulting $T$.

Now, there are several things that I am interested in:

I believe the correctness of the algorithm above is intuitive but I might be wrong. Have I missed something?
Even if correct, the above algorithm is obviously very inefficient. Is there an efficient way to implement that idea?
Are there other efficient methods of finding an induced cycle basis of a graph?
Among different algorithms for doing that, are there any time/space trade-off that I should consider? I am willing to spend a little more on computation if it means smaller memory footprint.
The above algorithm only works for undirected graphs. What about directed ones?


texts:
What is known about the time complexity of the following problem, which we call 3-MUL?

Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?

This problem is similar to the 3-SUM problem, which asks whether there are three elements $a,b,c\in S$ such that $a+b+c=0$ (or equivalently $a+b=c$). 3-SUM is conjectured to require roughly quadratic time in $n$. Is there a similar conjecture for 3-MUL? Specifically is 3-MUL known to be 3-SUM hard?

Note, the time complexity should apply in a "reasonable" model of computation. For instance, we could reduce from 3-SUM on a set $S$ to 3-MUL on set the $S'$, where  $S'=\{2^x\mid x\in S\}$. Then a solution to 3-MUL, $2^a\cdot 2^b=2^c$, exists if and only if $a+b=c$. However, this exponential blow-up of the numbers scales very badly with various models, like the RAM model for example.


texts: Different hardness proofs w.r.t different classes

texts:
Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard).

Is there a natural/interesting example of a problem that is known to be $C$ hard, but that the proof of $D$ hardness is significantly different?

For example, $TQBF$ is PSPACE-hard, but proving $NP$-hardness is trivial (by reduction from $SAT$), but I wouldn't consider this example very interesting, as $TQBF$ is a generalization of $SAT$. I am looking for a problem whose natural formulation is e.g. PSPACE hard, but one can show NP-hardness in a different way.

I'm not sure how interesting this question is, but I am curios to see such examples.


texts:
Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by helicopter)?

Or in terms of Graphs:
Given an un-directed, connected, weighted Graph, what is the optimal start vertex and shortest path that visits every edge at least once (return to the start vertex not required)?

This question is an altered version of the Route Inspection Problem or Chinese postman problem.

The solution I have working is O(n^5) and I'm trying to improve this.

A Slow-ish Solution

First we need to change the graph so that an Eulerian Path exists. We can do this by finding the Minimum Weight, Perfect Matching between all odd vertices (removing two odd vertices since we want a Path and not a Cycle!)
We can use Edmonds' Blossom Algorithm to make the Matching computation efficient. My implementation is currently O(n^3)
Adding the computed edges into the Graph ensures an Eulerian Path exists (using the two skipped Vertices as start and end point)
We then compute the Eulerian Path and have an optimal solution for the chosen start and end vertex

Question:

The big questions is which two odd vertices to use as the start and end point for the Eulerian Path. So far I am computing all possible Matchings using the Blossom algorithm and taking the one with the minimum weight.

Is there a way that we can do this better? Potentially already integrating it into the Blossom algorithm? Are there any assumptions we can make about the vertices that are optimal? I.e. in a lot of cases two odd vertices with largest distance in the original graph are the best choice, however this is not always true (see Example 3).

  How can we adjust e.g. this implementation to consider only Matchings of maximum size - 1?

Example 1

Here is the optimal solution for a maze (the coloring indicates the chosen path). The computation for a given start-end vertex pair is relatively fast (around 100ms). However since this needs to happen for every odd-vertex pair, the overall computation time is over an hour.

There are 278 odd vertices in the maze. Hence we have to compute a Matching (278 * (278 - 1)) / 2 = 38503 times.

Example 2

In this example it is obvious that the optimal start and end points are very far apart.

Example 3

The maximal distance between two odd Vertices (the one at the top and the one at the bottom) is 50. However for the optimal path the distance is only 11.

PS: Had all the terms nicely linked in the question, but can only include two links due to not having reputation. Oh well...


texts: Number of connected components of a random nearest neighbor graph?

texts:
Let us sample some big number N points randomly uniformly on $[0,1]^d$.
Consider  1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph).

Question What would the number of connected components depending on d ?
(As a percent of "N" - number of points.)

Simulation below suggest 31% for d=2,   20% for d=20, etc:

Percent Dimension:
31 2
28 5
25 10
20 20
15 50
13 100
10 1000

See code below. (One can run it on colab.research.google.com without installing anything on your comp).

If someone can comment on more general questions here:
https://mathoverflow.net/q/362721/10446
that would be greatly appreciated.

!pip install python-igraph
!pip install cairocffi
import igraph

import time
from sklearn.neighbors import NearestNeighbors
import numpy as np

t0 = time.time()

dim = 20
n_sample = 10**4

for i in range(10): # repeat simulation 10 times to get more stat
  X = np.random.rand(n_sample, dim)
  nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree', ).fit(X)
  distances, indices = nbrs.kneighbors(X)
  g = igraph.Graph( directed = True )
  g.add_vertices(range(n_sample))
  g.add_edges(indices )
  g2 = g.as_undirected(mode = 'collapse')
  r = g2.clusters()
  print(len(r),len(r)/n_sample*100 , time.time() - t0)


texts:
Am looking into writing up a Lindenmayer systems implementation. I've looked at a few example implementations and the one thing that's giving me trouble at this stage is how symbols and substitutions are meant to work (if this is even specified in the original treatise).

For example, the implementations I've seen tend in most cases to start with axioms based on A. Let's take the simplest example of this where the Axiom is (just) A.

When this is drawn (depth 0), what should I expect to see? If otherwise undefined, is A meant to render as anything at all? Or does it need to be defined as one full length (whichever symbol is used for this; I have seen pipe being used to this purpose) before it will render out?

Taking a second example, let us say that A renders out, irrespective of what the answer to the above is. If part of F's definition is B, and B is not defined, should B render as a full length?

The way I would expect this to work is that without F being defined at all, nothing should be drawn at depth 0 and subsequently at no other depth, either.

Yet in L-systems Explorer (LSE) and in this web-based implementation, even where a symbol is not defined, it will still be rendered as a full length. The question is, why?


texts: On complexity of linear programming with quadratic equality/inequality constraints?

texts:
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ many quadratic (not necessarily convex constraints)

equality constraints in $P$?
inequality constraints in $P$?

  Can $k=\Omega(poly(n))$ hold in both cases? At least can $k>0$ hold at least for $1.$?


texts: Is there any work that relates the liveness of a Petri Net to the complexity of determining coverability?

texts:
I'm working on a problem where the formalism appears to be an abstraction of a kind of Petri net, and it is possible to construct an equivalent Petri net from this formalism with the same behavior. The Petri net that is constructed is bounded, and a transition is either $L0$-Live or $L1$-Live. So in this net, a transition fires only once or not at all.

I've looked into the coverability of Petri nets and it appears that the coverability problem in general has $\text{EXPSPACE}$ complexity (https://www7.in.tum.de/~blondin/papers/BFHH16.pdf). However, I could not find any literature that relates the liveness of a Petri net to its coverability, and the impact on complexity. Is there any work that has looked into this?


texts: Solving a linear diophantine equation approximately

texts:
Consider the following problem:

Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in standard binary representation.

Output: $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

In the above notation $d(\mathbf{x}, S)$ for $\mathbf{x} \in \mathbb{R}^n$ and $S \subseteq \mathbb{R}^n$ is defined as $d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$, i.e. it's the natural euclidean distance between a set of points and a single point.

In words, we're given a hyperplane and we're looking for the point in the integer lattice that is closest to the hyperplane.

The question is:

  What is the complexity of this problem?

Note that polynomial time here will mean polynomial in the bitsize of the input. As far as I can see the problem is interesting even in two dimensions. Then it's not hard to see that it's enough to consider only those solutions $(x_1, x_2)$ with $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ but that's superpolynomially many options.

A closely related problem is solving a linear diophantine equation, i.e. finding an $\mathbf{x} \in \mathbb{Z}^n$ such that $\mathbf{a}^T\mathbf{x} = b$ or determining that no such $\mathbf{x}$ exists. So, solving a linear diophantine equation is equivalent to determining whether there exists a solution of value 0 to the problem I defined above. A linear diophantine equation can be solved in polynomial time; in fact even systems of linear diophantine equations can be solved in polynomial time by computing the Smith normal form of the matrix $\mathbf{A}$ giving the system. There are polynomial time algorithms that compute the Smith normal form of an integer matrix, the first one given by Kannan and Bachem.

To get intuition about linear diophantine equations we can consider the two dimensional case again. Clearly, there is no exact solution if $\mathsf{gcd}(a_1, a_2)$ does not divide $b$. If it does divide $b$, then you can run the extended GCD algorithm to get two numbers $s$ and $t$ such that $a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$ and set $x_1 = sb/\mathsf{gcd}(a_1, a_2)$ and $x_2 = tb/\mathsf{gcd}(a_1, a_2)$. Now you can see how the approximate version is different: when $\mathsf{gcd}(a_1, a_2)$ does not divide $b$, how do we find integers $x_1, x_2$ such that distance between $(x_1, x_2)$ and the line $a_1x_1 + a_2x_2 =b$ is minimized?

The problem to me sounds a little like the closest vector problem in lattices, but I do not see an obvious reduction from either problem to the other.


texts: On the class of the FNP version of the Hamiltonian Cycle problem

texts:
This post is linked to: FNP complexity class

Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in polynomial time.

Suppose I ask someone "Does a Hamiltonian Cycle exist?" and she answers "YES", then how can I (in polynomial time) verify that she is not lying? (I am assuming here that the solution I got "YES" is the only thing I have with me)

Alternate interpretation: Is "Any given solution to L can be verified quickly (in polynomial time)" to be interpreted as "Given some solution to the Hamiltonian Cycle problem for this graph, it can be verified quickly"?

If it is the latter, then things fall into place.

Quoting from http://en.wikipedia.org/wiki/FNP_(complexity):
"This means that the FNP version of every NP-complete problem is NP-hard."

Is this necessarily true?

And comparing with the Hamiltonian Cycle problem, if she (the solver) says "YES and here it is ..." then I can take that and verify if it is actually a Hamiltonian Cycle. Hence, shouldn't this (FNP) version actually be NP-Complete not be NP-hard? What am I missing here?


texts: What precisely is the extra power afforded by using deeper nets?

texts:
For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can't? (for any $k$ and with no restriction on width on any of the two DNNs)

I am equally happy to know of results which pertain to width restrictions on either side or vary the activation function between the two sides.

I am not asking about approximation ability gaps like what have recently been proven by Elden and Shamir between $2-$DNN and $1-$DNN.


texts: Common solutions to 3SAT and 2SAT models comprised of the same variables

texts:
I have a problem which is a combination of 3SAT & 2SAT instances.
Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of variables in L.
The actual boolean formula to solve is $B = S_3(L) \wedge S_2(L)$. So the solution for B is an intersection of the solution sets of $S_3(L)$ and $S_2(L)$.
Both $S_3$ and $S_2$ can be solved separately, and then we can select a common solution to solve B. I was wondering if I can use the 2SAT solution to more efficiently solve the 3SAT instance, for e.g. can I use the implication graph from the solution of the 2SAT instance to guide the search for solution to the 3SAT instance?
I am aware we build an implication graph when solving a 3SAT instance through DPLL. So can we use an existing graph to guide the DPLL solver?
Edited to better (hopefully) specify the problem


texts: Oracle Construction for Grover's Algorithm

texts: In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's algorithm, there seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. Specifically, my question is this: given some f(x) such that for some x value, f(x)=1, but for all others, f(x)=0, how does one construct an oracle that will get us from our initial, arbitrary state |x>|y> to |x>|y+f(x)>? As much explicit detail as possible (perhaps an example?) would be greatly appreciated. If such a construction for any arbitrary function is possible with Hadamard, Pauli, or other standard quantum gates, a method for construction with these would be appreciated.


texts: Complexity of computing generalised determinants. (P - #P transition)

texts:
Computing the determinant of a matrix can be done in polynomial time, while computing the permanent is known to be #P-hard. Let $A$ be an $n \times n$ matrix. Define a generalised determinant function as follows,

$$ Det_ \theta (A) = \sum_ {\mu \in S_n} e^{i \theta ~ sign(\mu)} A_{1,\mu (1)} \ldots A_ {n , \mu(n)}$$.

$S_n$ is the symmetric group on $n$ elements. It can be readily seen that  $Det_0 (A) = Perm(A)$ and $Det_{\pi/2}(A) = i Det(A)$.

For what value of $\theta$ does the computation of $Det_\theta{A}$ cease to be #P-hard?
For what value of $\theta$ does $Det_\theta{A}$ become poly time computable?
As $\theta$ varies how does the complexity of computation of $Det_\theta{A}$ change in general?

ps - Some physics- Prima facie $Det_\theta{A}$ looks like the analogue of Slater determinant corresponding to Anyon wavefunctions.


texts: Complexity of hidden polygon puzzle on square grids?

texts:
Hiroimono

 is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle.

The problem is:

Input: Given a set of points on on a $n$x$n$ square grid and integer $k$

Question: Is there a rectilinear polygon (its sides parallel to the $x$ or $y$-axis) such that the number of points on the polygon's corners is at least $k$?

Every corner of the polygon must be at one of the input points (so bends are only allowed at an input point).

  What is the complexity of this problem? What is the complexity if the solution restricted to convex rectilinear polygons?

EDIT April 13: Alternate formulation: Find a rectilinear polygon with the maximum corners on the given points.


texts: Efficient encoding of integers with constant digit sum

texts:
How can a large set of integers all with a known constant digit sum be encoded?

Example of integers in base 10, with digit sum 5:

14, 41, 104, 113, 122, 131, 140, 203 ....

The most important factor is space, but computing time is not completely unimportant.


texts: Does the $\mathsf{TC^0}$ hierarchy collapse?

texts:
Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?

The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between depth 2 and 3.

Also is there a standard reference for the fact that $\mathsf{AC^0_d}$ hierarchy does not collapse?


texts:
Consider the problem

$\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$

where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem computationally hard?


texts: The complexity of the disjoint union of a sequence of complete problems

texts:
Suppose that for every $k \in \mathbb{N}$ the decision problem $A_k$ is hard for $\mathsf{N}k\text{-}\mathsf{ExpTime}$.
What is the complexity of their disjoint union $A = \{ (k,x) \mid k\in \mathbb{N}, x\in A_k \}$?
It is in the fourth level of the Grzegorczyk hierarchy $\mathcal{E}^4$ and
is hard for $\mathsf{Elementary}$.
But can we say more?
Motivation
I am studying the complexity of the satisfiability of monadic logics
with several equivalence symbols in agreement.
Let $k$ be the number of equivalence symbols allowed.
If $k$ is fixed then problem is complete for $\mathsf{N}k\text{−}\mathsf{ExpTime}$.
I am looking for a nice characterization of the complexity of the problem
when $k$ is not a fixed parameter but part of the input.


texts: Is there a relation between $l_p$-norms of functions with same Fourier spectra but w.r.t different measures on the Hamming cube?

texts:
Informally, I want to ask if two functions $f$ and $g$ on the Hamming cube have the same Fourier spectra but w.r.t different measure and basis, then is $||f||_p$ related to $||g||_p$? (Where each $p$-norm is measured according to the appropriate measure.) This question requires some notation to set up more precisely.

First, for the Hamming cube $\{0,1 \}^d$,  given a bias parameter $0 \leq b \leq 1$, we may construct a biased measure $\mu_b$ that assigns a weight $b$ to $0$ bits and $1-b$ to $1$ bits as follows:

\begin{equation}
\mu_b(x) = b^{\sum_i x_i} (1-b)^{d - \sum_i x_i}.
\end{equation}

We continue that expectations and $l_p$-norms can also be defined under this measure. So for example, $ E_b[f] = \sum_{x \in \{0,1\}^d} \mu_b(x) f(x)$ and $||f||_p =
\left( \sum_{x \in \{0,1 \}^d} \mu_b(x) (f(x))^p \right)^{\frac{1}{p}} $. We note now an Fourier parity basis for the space $F_b$ of all functions $f: \{0,1\}^d \to \mathbb{R}$ when $\{0,1\}^d$ is associated with measure $\mu_b$. First for each $x \in \{0,1\}^d$ and $i \in [d]$ we define:
 \begin{equation}\chi_i^b =  \begin{cases}
      \sqrt{\frac{b}{1-b}} & x_i = 0 \\
      -\sqrt{\frac{1-b}{b}} & x_i = 1 \\
   \end{cases}
\end{equation}

This set of $\chi_i^b$ essentially correspond to a bit wise parity basis, which we can extent to arbitrary $S \subset [n]$ as
$\chi_S^b(x) = \prod_{i \in S} \chi_i^b(x)$. The collection $\{\chi_S^b \}$ over all $S \subset [n]$ is now our desired orthonormal basis. All this notation reduces to the standard Fourier basis and notions for $b = \frac{1}{2}$.

Now after all that lengthy build-in, here is my question. Suppose $f$ is a function over $\{0,1 \}^d$ with measure $\mu_{1/2}$ and $g$ is a function over $\{0,1 \}^d$ with measure $\mu_b$ (for $b \neq \frac{1}{2}$) and suppose $f$ and $g$ have the same Fourier cofficients w.r.t their corresponding bases elements $\chi_S^{1/2}$ and $\chi_S^b$ . Parseval's immediately implies $||f||_2 = ||g||_2$, where each norm is calculated according to the measure of the space the function lies in ($\mu_{1/2}$ and $\mu_b$ respectively). Is this true for all the $l_p$ norms? Is there a general relation between $||f||_p$  and $||g||_p$?


texts:
Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through computational biology, on physics through quantum information processing, and AI and complexity theory seem to regularly interact with neuroscience. The natural sciences seem relatively comfortable with TCS.

Thus, my question is in regard to the impact of TCS on the social sciences.

  What novel and important insights into the social sciences has TCS provided?

I am vaguely aware of the impact of algorithmic thinking on economics (through game theory). In fact algorithmic game theory is now a part of the 'standard domain' of TCS, so lets exclude AGT answers unless they specifically altered existing theories in the social sciences.

Another example I recall is from linguistics in the learnability vs. innateness of grammar (i.e. poverty of the stimulus) debate. Gold's theorem about the unlearnability of context free grammars provided a strong argument for innate-ness and helped convince some skeptics (I am not sure if this is still valid, since SCFG seem to be learnable). I am more interested in examples of this type, where TCS thinking helped change or shape existing theories in the social sciences.

References to books/surveys are appreciated.


texts: conceptual tools for illustrating types of computation?

texts:
From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc.

The common theme is that they cannot be explained in terms of the concepts I already know, so have to somehow develop a new vocabulary for them. But even once I think I understand a given concept I am still not really sure if I do.

I am wondering if you know of any effective ways to illustrate or explain such concepts graphically. I'm no good at following a formal mathematical exposition so that unfortunately doesn't help at all.


texts:
Given an arbitrary SAT instance, I would like to find the solution with the minimum weight. The weight of a valid assignment is computed using a function.

Is this a known problem or are there other problems that I can reduce this one to?


texts:
Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity).  Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ delete-min and find-min?  That is, can delete-key be reduced to $O(1)$ at the cost of more expensive other operations such as find-min, meld, and reduce-key?  Here delete-key means remove a particular key given a pointer to that key in the data structure.

This data structure would be necessary to fix my broken answer to this question: Nontrivial algorithm for computing a sliding window median.


texts: Are there natural separations in the nondeterministic time hierarchy?

texts:
The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973).  The theorem states that for any real numbers $r_1$ and $r_2$, if $1 \le r_1 \lt r_2$ then NTIME($n^{r_1}$) is strictly contained in NTIME($n^{r_2}$).

One key part of the proof uses (an unspecified) diagonalization to construct a separating language from the elements of the smaller class.  Not only is this a nonconstructive argument, but languages obtained by diagonalization usually provide no insight other than the separation itself.

If we want to understand the structure of the NTIME hierarchy, the following question probably needs to be answered:

  Is there a natural language in NTIME($n^{k+1}$) but not in NTIME($n^k$)?

One candidate might be k-ISOLATED SAT, which requires finding a solution to a CNF formula with no other solutions within Hamming distance k.  However, proving the lower bound seems is tricky, as usual.  It is obvious that checking a Hamming k-ball is clear of potential solutions "should" require $\Omega(n^k)$ different assignments to be checked, but this is by no means easy to prove.  (Note: Ryan Williams points out this lower bound for $k$-ISOLATED SAT would actually prove P ≠ NP, so this problem does not seem to be the right candidate.)

Note that the theorem holds unconditionally, regardless of unproved separations such as P vs. NP.  An affirmative answer to this question would therefore not resolve P vs. NP, unless it has additional properties like $k$-ISOLATED SAT above.  A natural separation of NTIME would perhaps help to illuminate part of the "difficult" behaviour of NP, the part which derives its difficulty from an infinite ascending sequence of hardness.

Since lower bounds are hard, I will accept as an answer natural languages for which we may have a good reason to believe a lower bound, even though there may not yet be a proof.  For instance, if this question had been about DTIME, then I would have accepted $f(k)$-CLIQUE, for a non-decreasing function $f(x) \in \Theta(x)$, as a natural language that probably provides the required separations, based on Razborov's and Rossman's circuit lower bounds and the $n^{1-\epsilon}$-inapproximability of CLIQUE.

(Edited to address Kaveh's comment and Ryan's answer.)


texts: Knapsack with dependent profits (pairs of items)

texts:
I'm working on a problem which MAY be reduced to the following version of Knapsack:

Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in the knapsack, then for some $i$ and $j$, the combined profit of $e_i$ and $e_j$ is NOT $p_i+p_j$. It could be lower or higher. Note that in general, profits could be additive, but for some pairs of elements, our new rule holds, and we know in advance the value of $profit(\{e_i\} \cup \{e_j\})$ for such pairs. As always we want to maximize total profit.

So my question is, has work been done on such a variant of knapsack? Are there papers that can I read to better understand this formulation? I am not well-versed with the entire literature of Knapsack, and I tried to search for this but came up empty.


texts:
Recently,  I worked on the problem for computing the approximate sum of a list of sorted nonnegative numbers. For any fixed $\epsilon>0$,  an $O(\log n)$ time approximation scheme has been derived such that it gives an $(1+\epsilon)$-approximation for the sum. The paper is posted at http://arxiv.org/abs/1112.0520, which has not been finalized.

I have been looking for existing works for this problem, but I only got a few remotely related papers,  and cited them.  Was this problem studied before?   If someone knows any existing researches about this problem, please let me know. I will appreciate the help, and update the citations accordingly. If the results are old, the paper will be dumped into a garbage can.


texts:
A switch network (the name is invented) is made with three types of nodes:

one Start node
one End node
one or more Switch nodes

The switch node has 3 exits: Left, Up, Right; has two states L and R and
a target state TL or TR. Each switch can be traversed with the following rules:

always from Left to Up; the state of the switch changes to L
always from Right to Up; the state fo the switch changes to R
from Up to Left only if the switch is in state L; the state doesn't change
from Up to Right if the switch is in state R; the state doesn't change
never from Left to Right or Right to Left

Figure 1. Switch node in state L with target state TR
These properties also hold:

0, 1 or 2 of the exits of a switch can be isolated (not connected to another switch);
a path can just "touch" a switch to change its state: enter from Left and exit from Left or enter from Right and exit from Right;
there are no restrictions on the number of times a switch can be traversed / touched.

The decision problem is: "Does a path from the Start node to the End node
exist such that all the final states of the switches match the corresponding target state?"
Obviously, all the switches that are not initially in their target state must be traversed (or touched) at least once;
This is a quick draw of a trivial network (made with Excel ... I'll make a better one):

A trivial solutions is:
S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

Is this problem known? ---> you gave me the good reference to the Hearn's thesis (constraint graphs);

The problem is in $NPSPACE = PSPACE$; before posting a sketch of my proof that it is in NP, I found an error; so the open questions are again:

2 . Is it $\mathsf{NP}$?
3 . Has the problem any chance to be $\mathsf{NP\text{-}complete}$?


texts: Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

texts:
While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:

  Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent to the notion of self-reducibility. This is the case not only due to syntactic considerations, but also due to the following inherent reason. An oracle to any decision problem returns a single bit per invocation, while the intractability of a search problem in $\mathcal{PC}$ must be due to lacking more than a "single bit of information" [...].

For those unfamiliar with Goldreich's text, self-reducibility is used in the sense that a search problem $R$ is Cook-reducible to deciding membership in the respective solution set (i.e., the problem "given $x$, is $x$ a solution to $R$?"). $\mathcal{PC}$ is the class of polynomially verifiable search problems. The text in this chapter appears to be an expanded version of an article intitled "On Teaching the Basics of Complexity Theory" by the same author (Springer, non-paywall link).

Regarding the last quoted sentence, the text refers to an exercise to prove that, for any search problem which is in $\mathcal{PC}$ but not in $\mathcal{PF}$ (i.e., the class of search problems for which the solution can be found in poly-time) and which is self-reducible, the respective (Cook-)reduction performs at least (asymptotically) log queries to its oracle. (The proof is also not hard; if using only log queries, then the oracle may be replaced by a brute force subroutine without affecting the reduction's poly-time complexity.)

My question is two-fold:

What does Goldreich mean by "syntactic considerations"? Does he simply mean it is cumbersome to define self-reducibility by other means than using reductions?
What relation does the exercise referred to in the text have to the claim regarding "lacking more than a 'single bit of information'"? (After all, the exercise is about log many queries, not a single one.) And what does this have to do with the inherentness of reductions to self-reducibility?

I assume Goldreich is alluding to widely-known facts here. Apologies if this can only be answered by the man himself.


texts: Hamiltonian Cycle as an integer linear programming problem

texts:
I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea:

Create variables $e_{ij}$ for every edge $(i,j)$ in the graph. Require each $$e_{ij}\in \{0,1\}$$. Create additional variables $v_i$ for every vertex $i$ in the graph, and define $$v_i = \sum_{\{j:(i,j)\in E\}}e_{ij}$$ (so that $v_i$ counts how many edges are connected to vertex $i$). Specify an integer linear program where the goal is to maximize $\sum_{(i,j)\in E}e_{ij}$ subject to the constraint that $v_i = 2$ for all $i\in V$.

As I see it, this should find a solution (if one exists) of exactly $n$ edges in the graph which form cycles. However, there's no guarantee that these cycles are a single tour of the graph. For example, consider a complete graph of 6 vertices. The above problem might find a "solution" which consists of two cycles each of 3 vertices, instead of finding the correct solution of a single cycle which includes all vertices. In short, the sticking point is requiring that the linear program finds only one cycle. Is there a way to enforce a limit on the number of cycles found via a linear programming constraint? I'm stumped on this.

Thanks!


texts: How to solve Knapsack problem with real numbers where weights equal to costs

texts:
I am testing an idea for the integer factorization algorithm based on quadratic-sieve. It works as follow:
Let $N$ be the number we wish to factor.

Pick a smooth bound $B$
Find $B+1$ smooth values that are also smooth mod $N$
For each smooth pair of $x \equiv y \pmod{N}$, factor $x$ and multiply $x,y$ by each prime factor with an odd power. It will turn $x$ into a square
then continue solving as with quadratic sieve after $B+1$ B-smooth values have been found

Finding the B-smooth values is not easy, here is how I plan on doing it.

Let $n$ be $\log{N}$
Let $S$ be the log group of all the primes up to $B$ such that $S_i = \log{B_i}$
Find a multiset $S'$ such that

each variable in $S'$ is a member in $S$
the sum of $S'$ is bigger than $n$
the sum of $S'$ is minimal

the exponential of the sum $S'$ should be the closest B-smooth value to $N$, and as such should have a high chance of being itself a smooth value.
repeat the steps above with $\log{kN}$ where $k$ is a small integer until you found $B+1$ smooth values.

The problem of finding the minimal $S'$ can be seen as a special case of the knapsack problem where weights equal to costs.
I have been trying to solve it via the two approaches below

Convert $n, S$ to integers. I could only use a very small precision of 1000 before I ran out of memory. I ended up having values $y$ values of the size of $N$
Build $S'$ by picking random values between $0$ to $B$ (including non-primes) when the sum of $S' > n - log(B_B)$, pick the last value by doing a binary search on the range of $0-B$ searching for the closest value $\log{}$ for $n - log(B_B)$. This one was more successful and gave $y$ values of the order of $\sqrt{N}$. The reason it worked is that any value on the range $0-B$ must be a prime or a composite of one of the $B$ bounded primes.

But the conclusion is that both of those methods are not good enough for finding the nearest B-smooth value to $kN$.
Have someone already try this direction? Is there a better way of calculating $S'$?


texts: Obtaining a lower bound of a matrix norm

texts:
I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower bound, with high probability, on the spectral norm:
$$ \left\| \frac{1}{n} \sum_{i=1}^n \vec X_i \vec X_i^T - \hat{\vec\mu} \hat{\vec\mu}^T - \mathbb{I} \right\|$$
without having to depend my bound on $\|\vec\mu\|$.
In the above quantity, $\hat{\vec\mu}$ denotes an estimate of the mean value, for which I have that, with high probability and $n=O(\text{something})$ it holds $\| \hat{\vec\mu} - \vec\mu \| \leq \epsilon$ i.e. I can get a "good" approximation to $\vec\mu$.
Given that the covariance matrix of $\vec X_i$ is merely $\mathbb{I}$, this should be enough for me to lower bound the above quantity without $\|\vec\mu\|$.
It seems to me intuitive that I should be able to get the above quantity a lower bound (with high probability) without relying on some bound of $\|\vec\mu\|$ but I'm not sure how to obtain that. Trying to break the $\frac{1}{n} \sum_{i=1}^n \vec X_i \vec X_i^T$ into $\frac{1}{n} \sum_{i=1}^n (\vec X_i - \vec\mu) (\vec X_i - \vec\mu)^T$ hasn't led me somewhere (?), because then I need to additionally bound terms like $$\left\|\vec\mu \left( \frac{1}{n} \sum_{i=1}^n \vec X_i - \vec\mu \right)^T \right\|$$ which would introduce into my bound the terms $\|\vec\mu\|$ that I do not desire.
What could I do to lower bound the above quantity and avoid any dependence on $\|\vec\mu\|$?
In the above, $\|\cdot\|$ denotes the Euclidean norm for vectors and the spectral 2-norm for matrices.


texts: Running Simon's algorithm on D-wave machine

texts:
I was wondering whether Simon's algorithm could be run on a D-wave machine.
The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained binary optimization problems. So, we need to convert the Simon's algorithm into an optimization problem. Is that possible?

Simon's algorithm is special because of its query complexity. Hypothetically, each query may correspond to a clock cycle. In that case, the difference between the number of cycles on a classical and a quantum computer will be different. On a D-wave computer we don't run a program over clock cycles. But it is true that the evolution of the Hamiltonian is traced over iterations and it could be correspondences to hypothetical clock cycles. Is there any way we could redefine the query complexity in the context of D-wave computer?

D-wave's famous Chimera architecture is a bipartite graph. Can we create an instance of Simon's algorithm on the bipartite graph?


texts:
(My original question still has not been answered. I have added further clarifications.)

When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require the graph to be non-bipartite so that the fundamental theorem of Markov chains applies.

What happens if the graph $G$ is instead bipartite? I am specifically interested in the hitting time $h_{i,j}$, where there is an edge between $i$ and $j$ in $G$. Say the bipartite graph $G$ has $m$ edges. We can add a self-loop to an arbitrary vertex in the graph to make the resulting graph $G'$ non-bipartite; applying the fundamental theorem of Markov chains to $G'$ we then get that $h_{i,j} < 2m+1$ in $G'$, and this is clearly also an upper bound for $h_{i,j}$ in $G$.

Question: Is it true that the stronger claim $h_{i,j} < 2m$ holds in $G$? (It have seen this claimed in analyses of the random walk algorithm for 2SAT.) Or do we really have to go through this extra step of adding the self-loop?


texts: Is Biological Computation a theme covered by the Theoretical Computer Science?

texts:
I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an empirical theory of computation in the natural world than applications of biological systems in the industry of the computation.

Reference:
MITCHELL, Melanie. Biological Computation.


texts: Can multipebble automata decide all deterministic context-sensitive languages?

texts:
A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is written on the tape between two end-markers as $ \# w \# $ ). During the computation, a MPA can detect whether the symbol under the head has a pebble, and then it can put a pebble (remove the pebble) if there is no pebble (a pebble).

$ h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k $ is a homomorphism, where $ \sigma $ is a symbol and $ k>0 $.

For any deterministic context-sensitive language $ \mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right), $ it is not hard to show that there exists a $ k>0~ $ such that $  h_k( \mathtt{L} ) $ can be recognized by a MPA. So, loosely speaking, we can say that

  any "problem" decidable by a linear-space DTM (deterministic Turing machine) can be decidable by a MPA.

Is it also true for any language in $ \mathsf{DSPACE(n)} $? Can MPAs decide all deterministic context-sensitive languages?

$ |w| $ is the length of $ w $.

$ w_i $ is the $ i^{th} $ symbol of $ w $, where $ 1 \leq i \leq |w| $.

$ h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace $.


texts: Definitional function extensionality for functions out of $\mathbf{2}$

texts:
Denote by $a$ and $b$ the canonical terms of $\mathbf{2}$.
For any map $f:\mathbf{2}\to \mathcal{U}$ we have the eliminator$$\mathrm{ind}_{\mathbf{2}}(f) : \big(f(a) \times f(b)\big) \to \prod_{x:\mathbf{2}} f(x).$$
Can we add the rule that for any $f:\mathbf{2}\to \mathcal{U}$ and any $g:\prod_{x:\mathbf{2}} f(x)$ we have a definitional equality $$g=\mathrm{ind}_{\mathbf{2}}(f)(g(a)\times g(b))$$and have decidable equality checking and decidable type checking?
So for example take $f=\lambda x:\mathbf{2}.\mathbf{2}$. Then this rule would imply a definitional equality $$\lambda x:\mathbf{2}.x=\mathrm{ind}_2(f)(b\times a)\circ \mathrm{ind}_2(f)(b\times a).$$


texts: Complexity of maximising weighted sum of and functions on a set of binary variables

texts:
Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land  x_k$$ in which
$$\{x_1,...,x_k\}\subset\{a_1,...,a_n\}$$

Suppose that each variable $a_i$ has also a cost $c_i$ assigned to it and every function $f_j$ has a profit $p_j$ associated with it. Both variables are non-negative $\forall i,j: p_j,c_i\ge 0$.

The problem is how to maximise profits minus costs over the set of all possible $a_i$s:
$$(1) \max_{a_1,...,a_n} \left\{\sum_j^m p_j f_j - \sum_i^n c_i a_i \right\}$$

Another related problem is to maximise the profit with constrained costs for some constant $C$:
$$(2)   \max_{\sum_i c_i a_i \le C} \left\{\sum_j^n p_j f_j \right\}$$.

Now here here the questions I have:

Can $(1)$ be solved in a strictly polynomial, or
pseudo-polynomial way?
Can $(2)$ be solved in
pseudo-polynomial time?

By pseudo-polynomial we mean assuming bounds on $|c_i|$ and $|p_j|$, can a polynomial time algorithm be achieved?

It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f_j=a_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems.


texts: How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

texts:
c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-free graph, i.e., there is no induced path of length 3.

The paper denotes the c-chromatic number as $c(G)$ and proves that $c(G)\le \lceil \frac{1+\Delta}{2} \rceil$ in Remark 12 on page 4. The proof can be used to convert any coloring to a coloring of at most $\lceil \frac{1+\Delta}{2} \rceil$ colors, in polynomial time.

In the study of the classic graph coloring, i.e., the chromatic number $\chi(G)$, greedy coloring was discussed. The performance of greedy coloring is determined by the order of vertices. In the worst case, a graph needs $\frac{|V|}{2}$ colors while $\chi(G)=2$. This implies that the approximation ratio of greedy coloring is arbitrarily bad.

Similarly, when we are coloring graph into cographs, we can use the greedy coloring. Given a order of vertices, label each vertex with the smallest color ( assume colors are labeled as 1, 2, 3, ....) such that each color class is a cograph.

My question are :

what is the worst behavior of greedy coloring on cograph coloring?
Is it possible that the greedy coloring needs more than $\lceil \frac{1+\Delta}{2} \rceil$ colors?


texts: When does a set of infixes determine a set of ($\omega$-) words

texts:
If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for the set $W = \{ 0, 1 \}$ all words in $X^* \setminus \{ 0^\omega, 1^{\omega} \}$ have it as infixes, and if I have $V = \{ 011, 110, 101 \}$ it determines the three words
$$
 011011011011\ldots, \quad
 110110110110\ldots, \quad
 101101101101\ldots.
$$
What could be said about the relations about infix-sets and $\omega$-languages, are there any results or articles on this topic?


texts:
I am reading through through a paper called HMF: Simple Type Inference for First-Class Polymorphism by Daan Leijen of Microsoft Research.

In the paper it describes how to calculate the polymorphic weight of an expression:

I am having trouble understanding why the above example [[forall a. [forall b. a -> b]]] has a weight of 1 rather than two. there are two type abstractions where both type variable are not free in their bodies, should these not be added together?


texts: Data Strcuture to represent dependencies amongst modules

texts:
Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in the figure, module $m_3$ and $m_4$ are dependent on the output of module $m_1$. If we are given a set if inputs $I$ and a set of outputs $O$, the objective is to find a set of modules which produce this output.

For example, if the output set $O$ is $\{o_1, o_2\}$ then all of the modules would have to be used. However if the output set $O$ is $\{o_2\}$ then only $\{m_2, m5, m_7\}$ needs to be used.

A graph is a natural model for such an objective. Are there any alternative data structures to represent this description?

Consider a modification to the earlier example as shown in the figure below, where all the outputs produced are $o_1$ and the output set required is also $O = \{o_1\}$. In this scenario we have two possible set of modules which satisfy our goal of $O$ :  $\{m_2, m_5, m_7\}$ and $\{m_1, m_3, m_4, m_6\}$. We wish to select the set which minimizes the number of modules used, hence the set $\{m_2, m_5, m_7\}$ would be our desired set $O$. Would a graph still be the most natural representation of such a scenario or some other data structure would be better off?


texts: Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?

texts:
Question 1:  Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean circuit of size $p(n)$ can be $\epsilon$-approximated by a monotone Boolean circuit of size at most $q(n)$.

A function $f$ is $\epsilon$-approximated by a function $g$ if they agree on at least $(1-\epsilon)$ fraction of inputs.

We can ask a slightly more general question. Let $\mu_p$ denote the Bernoulli measure on $\{0,1\}^n$ where every variable is '1' with probability $p$. For a (non-constant) monotone function $f$ let $p_c(f)$ be the value such that $\mu_{p_c}(\{x: f(x)=1\})=1/2$.

Question 2:  Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function $f$ on $n$ variables, there is a Boolean function $g$ that can be expressed by a monotone Boolean circuit of size $q(n)$ such that for $p=p_c(f)$, $\mu_p(\{x: f(x) \ne g(x) \}) \le \epsilon$.

Of course, the instinctive thought is that the answers for both these question is NO. Is it known? Razborov famously proved that matching cannot be expressed by a monotone Boolean circuit of polynomial size. But matching can be approximated in its critical probability by the property that there are no isolated vertices and this property admits a monotone (low depth) circuit.

I asked the analog questions (Problems 1,2,3) for $AC^0$ and $TC^0$ in this blog post.


texts: Complexity of simple undirected graph isomorphism problem

texts:
We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices.

My question:

What is the complexity of the best known algorithm for the simple undirected graph isomorphism problem?

I assume it should be a special case of the exponential algorithm by Babai et. al introduced in Canonical labeling of graphs.

As described in Reading List: Graph Isomorphism by Dave Bacon, this is not among the classes for which we have efficient algorithms. Thanks in advance for your answer.


texts:
A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees $T_v$ consist of precisely those maximal cliques in $G$ that contain $v$. $T$ is then called the clique tree of $G$.

Now my question is the following.

  Is any tree can be represented as a clique tree of some chordal graph?

Any counter example or hint of proof is welcome.


texts: Is counting the words in a finite regular language #P-complete?

texts:
Almost the exact same question was asked here, but nobody proved or cited its #P-completeness! I found this question because I proved it is #P-complete (proof below), and the proof was trivial, but I couldn't find it anywhere on the web or in the discussion on that question! (One person commented "I suspect it is #P-complete".) So either my proof is wrong, which you can judge for yourself, or the result is novel, which I would think is highly unlikely. Which is it?

Proof:

Consider the set of regular expressions formed by the union and concatenation of symbols from $(\Sigma\cup{.})$, where $\Sigma$ is an alphabet and $.$ is a symbol for any $l\in\Sigma$. I will show that #SAT reduces in $O(mn)$ time to counting the number of strings that satisfy such a regex, where $m$ is the number of clauses and $n$ is the number of variables in the given formula $\varphi$.

The reduction is very simple. First, reduce #SAT to #UNSAT by noting that if $\varphi$ has $n$ variables, then $\#\text{SAT}(\varphi) = 2^n - \#\text{UNSAT}(\varphi)$. So now we have to count the number of falsifying assignments of the variables of $\varphi$.

To falsify $\varphi$, it suffices to falsify just one clause. We therefore want to find
$$\left|\bigcup \limits_{C\in\varphi}F(C)\right|$$
where $F(C)$ is the set of assignments of literals that falsify $C$.

We thus write a regex representing the language of falsifying assignments for each clause. Using $\Sigma = \{0,1\}$, and letting $r_i$ be the $i^{th}$ symbol of a regex $r$, the regex for the language of assignments that falsify a clause $C$ is
$$
r_i = \begin{cases}
         0 & \text{if } x_i\in C \\
         1 & \text{if } \overline{x_i}\in C \\
         . & \text{otherwise}
      \end{cases}
$$

We then take the union of the regexes for each clause $C\in\varphi$. For example, if $\varphi = (x_1\vee \overline{x_2}\vee x_3) \wedge (x_1\vee x_3\vee \overline{x_4})\wedge (\overline{x_1}\vee \overline{x_4})$ we would have $r = $010.|0.01|1..1, where | denotes union.

The construction yields a union of $m$ strings, each of $n$ symbols. Thus the reduction takes $O(mn)$ time and the size of the regex-counting instance is polynomial in the size of the formula. Further, any regular expression that uses only concatenation, dot, and union represents a finite regular language (specifically, there is no Kleene star). So since we can solve #SAT by counting strings that satisfy such a regex, we can say that counting the words in a finite language is #P-complete.


texts:
Could anyone please point to both introductory and advanced papers/books showing how to use SAT technology to solve Computer Vision tasks (e.g. edge detection, object recognition, facial recognition, ...)?

More precisely: I'm looking for SAT-based techniques to extract knowledge from images and reason about such knowledge (e.g. is object $X_1$ in front of object $X_2$? Is object $X_3$ partially hidden by object $X_4$? Is person $X_5$ in image $I_1$ the same as person $X_6$ in image $I_2$?).


texts: Minimum number of real multiplications to multiply two quaternions

texts:
Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows:
$$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$
We only need the products $ac$, $bd$ and $(a+b)(c+d)$. Does there exists a similar trick for quaternion multiplication? A naive multiplication would need $16$. This can probably be reduce to $9$ using the same trick as above (and taking into account that quaternion multiplication is non-commutative). My question is it known that $9$ is the lower bound? If not, does there exist an algorithm, which does quaternion multiplications in less than $9$ real multiplications?


texts:
Wikipedia has the following definition:

  Thread safety is a computer programming concept applicable in the
  context of multi-threaded programs. A piece of code is thread-safe if
  it only manipulates shared data structures in a manner that guarantees
  safe execution by multiple threads at the same time. There are various strategies for making thread-safe data structures.[1][2] ... and so on ( http://en.wikipedia.org/wiki/Thread-safety )

So, code is thread-safe if it operates in thread-safe manner! Hmm...

However, precise definition seems not to be simple. A naive approach is:

Thread-safety means that program's observable behavior does not depend on eligible thread scheduling order.

Still, it may be incorrect definition. Say, threads may log  messages into log file, and reodering of log messages may be OK. So program observable behavior may vary, but the program may be considered thread-safe.

Probably, we need to specify allowed types of different program observable behaviors while being thread-safe.

Yet another complication: there may be  thread-safe (or thread-unsafe) code, not the whole program. (One may think about compositional properties of (non-)thread-safe code and so on)

So, the questions are: how to precisely define thread safety? Is there concise definition? What work was done to define thread safety?

UPDATE: Thanks for all the high quality links you supplied. The links contain answers to additional question(s) that I planned to ask. Feel free to add new (appropriate) links even though I have chosen my prefered answer.


texts: How to generate Skolem function in practice

texts:
Context: Skolemization is the process of removing the existential quantifiers in a first-order formula. The existential bounded variables are replaced with existential quantified function.

Questions: How, in practice, are these functions generated by an algorithm? Do we have another choice than a brute force strategy over all the possible functions? Is it of any practical use?

Example: Assume the formula $\forall{x}.\exists{y}.x \neq y$, then the Skolem form is $\exists{f}.\forall{x}.x \neq f(x)$ where $f$ is the function that explicits the dependency between $x$ and $y$. With resolution or any other method, how to, algorithmically, decide what is the result of $f(x)$? Is it all the values of the domain of discourse of $y$? If yes, does it mean that the role of the function is actually to "forbid" the value of $f(x)$ to change when a variable other than $x$ (if there was any) is instantiated?

Partial answer: As given below, we do not need to interpret the function $f$ to prove the validity. However, what about finding a model that satisfies the formula?

As I understood it...: Replying to myself to close this question. I guess there is no magic and we need to consider every function $f$ until we find a model. So if $f$ takes 2 arguments, it can maps to $|U| * |U|$ values ($|U|$ being the cardinality of the universe of discourse) and hence, the Skolem function is equivalent to the initial $\exists$ quantifier.


texts: Conflicting definitions regarding TM and Recursively Enumerable languages

texts:
In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. However, according to Wikipedia (and pretty much everywhere else) it's $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$. The difference is that in the first case you can't write and move at the same time.

In the same book, a language $L$ is recursively enumerable if there is a TM so that: $w \in L \iff$ the TM halts on $w$. Note that in this book the TM only has halting states. In wikipedia, halting states are actually also accepting states. I also came across TM definitions where there is a distinction between accepting and rejecting states. In these cases, the definition of a recursively enumerable language changes to "... the TM accepts $w$".

Now it's obvious that in both cases all definitions are obviously perfectly equivalent. I'd like to know which defintions have prevailed so that I can follow those.


texts: Do we care about confluence because of unique normal forms?

texts:
Confluence implies uniqueness of normal forms, which is great. It is also much simpler to reason about, allowing more reusable proofs (indeed I don't imagine a way to prove UN directly for the $\lambda$-calculus).

It is however strictly stronger than UN, saying something about computations without any NF: they can be joined.

That's a nice result, but does anyone really care? What are really the practical goals of proving your calculus is confluent?


texts:
I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below.

Since toroidal graphs can be recognized in $P$ , what are some different known characterizations of toroidal graphs ?
There are more than thousand forbidden minors for toroidal graph class, and only four of them does not contain $K_{3,3}$ as a subdivision (This paper). Where can i find a bigger list of forbidden structures of toroidal graphs ?
Two disjoint copies of $K_5$'s are not toroidal. Is it true that if a graph $G$ have two vertex disjoint non-planar induced subgraphs, then $G$ is not a toridal ? If not, then what is special about disjoint copies of $K_5$'s ?


texts: Machine models based on group-labeled digraphs?

texts:
Following an earlier question, I would like to suggest the following generic computation model. Let $\Gamma$ be a group, we say that a $\Gamma$-labeled digraph is a digraph $G$ whose arcs are labeled by $\Gamma$ and such that for each directed cycle $C$, the product of the labels equals $1_{\Gamma}$. Let $F,G$ be two $\Gamma$-labeled digraphs with two distinguished vertices $s_F,t_F$, resp. $s_G,t_G$. We say that an equivalence relation $R$ on $V(F) \cup V(G)$ is a bisimulation if:

(1) $s_F ~R~ s_G$ and $t_F ~R~ t_G$,

(2) whenever $u ~R~ v$ holds, if $F$ contains a path $u \rightarrow^*_a u'$ and $G$ contains a path $v \rightarrow^*_a v'$ then $u' ~R~ v'$ also holds (and conversely).

Let $O(G)$ denote the set of bisimulations of $G$. Fix two digraphs $F,G$ with $V(F) = \{v_1,\ldots,v_m\}$, $v_1 = s_F, v_m = t_F$, and $V(G) = \{w_1,\ldots,w_n\}$, $w_1 = s_G, w_n = t_G$. We may then define a relation $R$ on $O(F) \times O(G)$ as follows. Given $J \in O(F), K \in O(G)$, we say that $(J,K) ~R~ (J',K')$ holds if there is a $\Gamma$-labeled digraph $L$ and an arrangement of curves $\gamma_1,\ldots,\gamma_m, \delta_1,\ldots,\delta_n$ forming a grid-like shape such that:

(*) we can arrange the vertices of $L$ on the union of these curves, and if we let $H_i$ the part mapped to $\gamma_i$ and $V_j$ the part mapped to $\delta_j$, then we have: (a) $H_1 = J, H_n = J'$, $V_1 = K, V_m = K'$, (b) for every $1 \leq i < m$, there is a bisimulation $R_i$ between $H_i$ and $H_{i+1}$ such that for each class $C$ of $R_i$ and $j \in \{i,i+1\}$, the elements of $V(H_j) \cap C$ are "consecutive" on $\gamma_j$, (c) the same condition holds for the pairs $V_j,V_{j+1}$.

Despite the apparent complexity of the formulation, the motivation is simple: first, we want to break the word/machine dichotomy of TMs by restoring some symmetry between the "computer" and the "data"; second, we try to abstract the geometric "grid-like" structure of a TM and the locality properties of the computation, which are here expressed by the nullity constraint on cycles.

As I come back to ground, I'm not sure if my model has any practicality though, but it may interest some researchers in machine models. Even though the target audience is probably narrow, I'd like to ask: (i) what is the computation power of the model depending on the group $\Gamma$, (ii) can we exploit the geometric definition to get some interesting properties (i.e. possibility of composition by grid juxtaposition)?


texts: For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime?

texts:
Title pretty much explains the question. E.g.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Should there in theory also be an algorithm with guaranteed runtime that is also linear?

Not looking for a response to this specific case necessarily, but more generally.

Thanks all.


texts:
This is the first time I ask a question on cstheory, so I am very sorry for my english.
I have a (maybe very trivial) problem when trying to find a well-form representation for a root of a recursive equation in pi-calculus.

buffer(x) = out!<x>.buffer<x> + in?(y).buffer<y>

The equation above represents behaviors of a "mutable" single data buffer, it is very simple: the buffer's states are parameterized by x, that means its data cell's value is x. So the buffer can be read by the channel out! and updated by the channel in?. The buffer is somehow a fixpoint of the equation.

Firstly, it seems to me that it is easy to find out a well-formed representation for buffer (using the basic syntax of pi-calculus). The persistent output can be represented by replicating like !out. But latter, for the input, it is not easy as it seems.

Can anybody give me some suggestions ?

(I try to express some reactions from suggestions of @Martin Berger)

If we take an input with $\overline{in}\langle z \rangle$:

$\overline{in}\langle z \rangle \vert buffer(x) \rightarrow buffer(z)$ (recursive definition)

$\overline{in}\langle z \rangle \vert (\nu a)\big(\overline{a}\langle x\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big) \Rightarrow$
$(\nu a)\big(\overline{a}\langle z\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big)
$ (encoding version)

And now we get an output with $out(t).P$:

$out(t) . P \vert buffer(z) \rightarrow P\lbrace z/t\rbrace \vert buffer(z)$ (recursive definition)

$out(t) . P \vert (\nu a)\big(\overline{a}\langle z\rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big) \Rightarrow$
$P\lbrace z/t \rbrace \vert (\nu a)\big(\overline{a}\langle z \rangle | !a(x).( in(y).\overline{a}\langle y \rangle + \overline{out}\langle x \rangle.\overline{a}\langle x \rangle\big)$ (encoding version)


texts: Resolution augmented with the rule of symmetry or the rule of extension

texts:
Krishnamurthy (here is the abstract of his paper) showed that resolution augmented with the principle of symmetry forms a proof system (referred to as SR) in which certain formulas (which do not admit short proof in resolution proof system) can exhibit  short proofs.

This also holds for the resolution proof augmented with the rule of extension (referred to as ER). He however left open the question if these proof systems SR and ER p-simulate each other.

Is there any recent work on this question?

Does SR polynomially simulate ER?


texts: any connection between binary/integer multiplication and matrix multiplication?

texts:
is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it?

some related history: Schonhage/Strassen give a fast algorithm for binary multiplication and Strassen also gave a faster matrix multiplication method.

A. Schonhage and V. Strassen, “Schnelle Mu ¨ ltiplikation grosser Zahlen,” Computing 7 (1971),
281–292


texts: Citation showing minors are topological minors for subcubic graphs

texts:
If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Wikipedia cites this result from Diestel's "Graph Theory". It's listed as Prop 1.7.4 in the latest version of the book. The book lacks proof or citation.

Are the whereabouts known for an (original) proof of this?

Furthermore, is there a reference proving that if $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$? It's mentioned here briefly but lacks reference.


texts: Is there an example of a non context-sensitive language?

texts:
I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).

Is there any language with such restrictions that isn't a Context-Sensitive language?


texts: Non-termination, strict positivity and free monads

texts:
Using the standard encoding of a free monad in Haskell and its fmap instance:

data Free f a = Pure a
              | Roll (f (Free f a))

Writing an equivalent to this in a dependently typed theory gets rejected because of the strict positivity condition.

Is it possible to cause non-termination with this encoding of a Free monad?

If this isn't the case does it point to some known relaxation of the strict positivity condition?

If this is the case is there a strictly positive datatype which acts as Free for strictly positive functors?

I don't specify the exact type theory I am working in, as some might allow addition of features to allow this. The base theory might be something like Coq's CoC.


texts:
Suppose you have some boolean function $f: \{-1,1\}^n \rightarrow \{-1,1\}$ with rational coefficients such that all degree 1 monomials of $f$ have a nonzero coefficient and the degree $n$ monomial has a nonzero coefficient.
Can we lower bound the number of monomials in $f$ by $2^{\Omega(n)}$?
One can show a lower bound of $n^2$ monomials as follows. Take $f^2(x)$. This will be a constant function always equal to 1, so all monomials must have coefficient 0. But when we look at the product of $f^2$, we see the degree 1 monomials and the degree $n$ imply degree 2 and degree $n-1$ monomials with nonzero coefficients. So there must be at least one other monomial present for each of these terms so the coefficients sum to 0.


texts: Encrypting or obfuscating transport stream identifiers in SSL-like connections

texts:
First, a longish prologue.

Assume typical SSL/IKE/SSH-like connections where a Diffie-Hellman exchange is done first to establish session encryption and decryption keys, where those keys are subsequently used for all transmission in the connection, with a symmetric encryption algorithm, such as AES. Also assume that a single peer has many separate connections, with separate symmetric keys.

If the connections are not separated by other external means (such as TCP connections), a peer receiving a packet needs some way to distinguish which connection a packet belongs to, to know which symmetric keys to use for decrypting it.

This is obviously trivially handled by prefixing each message by a connection id (that is not cryptographically significant). This is the approach taken by IPSEC, for example (security association id, 32-bit integer).

And, here comes the question:

What would be a method to encrypt the connection id in such a way, that nobody else but the recipient can tell which packets belong to which connection?

The simple solution would be to encrypt the connection id with an asymmetric encryption method for the recipient's public key, and prefix this block to each message. However, this solution is computationally too expensive to be done per packet, atleast with the traditional methods of asymmetric encryption (RSA, ElGamal, Elliptic Curves, etc.).

An incomplete solution would be that the recipient server has one shared connection id encryption key, which is revealed to each communicating party inside the Diffie-Hellman handshake. This way, no passive attacker can know which packet belongs to which connection - but every party in active communication with the recipient has the same shared symmetric encryption key, and can tell all the connections apart.

Yet another solution would be for the recipient just to trial decrypt each packet with every symmetric key it has, and see which decryption produces a valid authenticator for the packet. But this becomes computationally too expensive, if the recipient has more than a few connections.

So, my question is really - are there any other methods I haven't thought of that could be used for the purpose? There are all sorts of funky encryption methods one could use, such as homomorphic encryption, but I haven't really come up with anything solid. Or is this problem a straight case of asymmetric encryption (or trapdoor function), for which there are no sufficiently fast solutions?

Or, if such a method can not be found, then I would like to find a simple obfuscation method, that wouldn't really give any guarantees, but which would make it hard for an attacker to determine the connection identities from just a few packets.


texts:
I was reading the Wikipedia page Random self-reducibility and it states:

  If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$.

I am trying to understand that statement. It seems to say if we find a problem where a random instance is hard it would prove a bunch of complexity classes are equal. Is this correct? Which complexity classes?


texts:
Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be twins if $u$ and $v$ have the same set of neighbours, that is, if $N(u)=N(v)$.

  Given a graph $G$ on $n$ vertices and $m$ edges as input, how fast can we find a pair of twins in $G$, if such a pair exists?

We can check whether two given vertices are twins in $O(n)$ time, by comparing their neighbourhoods. A straightforward algorithm is to find twins is thus to check, for each pair of vertices, whether they are twins. This takes $O(n^{3})$ time (and also finds all pairs of twins). Is there is significantly faster way to find (if there exists) a pair of twins in the graph? Is there known work in the literature that addresses this problem?


texts: Terminology and references for a learning model

texts:
Let's say we're doing regression over $[0,1]^d$ -- either in the PAC sense with bounded-range agnostic noise or in the more classical-statistics sense with additive Gaussian noise. Suppose further that an additional hindrance stands between the data and the learner: The space $[0,1]^d$ is divided into a grid of cubes with side length $\eta$, and rather than seeing the full labeled sample $(X_i,Y_i)$, the learner only knows how many points $X$ fell into each of the grid cubes and the average of their $Y$ values in that cube.

Questions: 1. Terminology: Is there a name for this learning setting? "Summary" or "aggregate" statistics come to mind, but I want to be consistent with the known literature. 2. Prior results: Either in the PAC or the the additive-noise setting, is anything known? Efficient algorithms, minimax rates?


texts:
The reduction from $k$-SAT to 1-in-$k$ SAT is known.

Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.


texts: Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy?

texts:
Consider the following problem: given a matrix $M\in\{-m,\dots,0,\dots,m\}^{n\times n}$, indices $i,j\in\{1,\dots,n\}$ and an integer $a$. Replace $M[i,j]$ by $a$ and call new matrix $\hat M$. Is $per(M)>per(\hat M)$?

Is this problem in the polynomial hierarchy?


texts: Weakest model of computation that can typecheck?

texts: What's the weakest (known) model of computation (or smallest language class) that can decide whether a simply-typed lambda calculus program type checks? What about an (explicitly typed) CoC program?


texts: Context weakening as an explicit rule for languages of the the lambda cube?

texts:
I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in the rules for PTS in different resources.
In Type Theory and Formal Proof: An Introduction, Nederpelt and Geuvers add context weakening as an explicit rule:
Γ ⊢ e : T
x \notin Γ
Γ ⊢ U : s
---------------------- t_weak
Γ, x : U ⊢ e : T

---------------------- t_var
Γ, x : T ⊢ x : T

Their formalization clearly requires t_weak, since t_var can only type the last variable in the context.
In ATAPL, Pierce instead chooses a more powerful rule for typing variables, and forgoes an explicit context weakening rule.
x : T \in Γ
----------- t_var'
Γ ⊢ x : T

Presumably, one would be able to derive a weakening rule from the rules Pierce chooses.
Are both these systems indeed equivalent? Is there any reason to choose one over the other for the sake of formalization in a proof assistant?


texts: What happens if we try to extract a witness but it actually does not exist from a term of existential type?

texts: Given a term t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y)) in Martin-Lof's type theory, what's the value of w(t(0)), where w is the operator that extracts the witness of a term of existential type?


texts: Symbolic Execution is a case of Abstract Interpretation?

texts: This is written in the wiki entry of Symbolic Execution, but I can't find any reference for it. Can anyone show me a pointer? Thank you.


texts: Are there complexity theory consequences of the collapse NEXP=EXP^NP?

texts:
It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\subseteq NEXP$ is true.
Are there any complexity theoretic conjectures which suggest this is not true and hence $EXP^{NP}\not=NEXP$?