texts:
What is the smallest widely-known complexity class to which
$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\land & j\ \text{is a binary encoding of a nonnegative integer}\ \hat\jmath\\\land & \hat\imath>\hat\jmath\end{array}\right\}$$
belongs to? The language is probably nonregular, but definitely in DLOGSPACE. Does this language lie in any smaller well-known class?


texts: Linked List size in constant time or linear time

texts:
The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it.

In the Boost C++ library one finds that the size() function can be constant time or linear time.

I was wondering what the differences are in getting the size to be constant time over getting it to be linear?

Can anyone elaborate on the algorithm differences?


texts: I was reading a paper A Generic Cyclic Theorem Prover. This paper explains about automated theorem prover based on various instantiations like the notion of first order logic equations with inductive definitions using cyclic proofs. I was unable to understand about why cyclic proofs are required. As far as I understand, sometime with the induction rules, we can go to an infinite loop, to avoid this condition of going into infinite loop, they introduced cyclic proofs. Can anyone please correct me if I am wrong?


texts:
Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.

Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\sigma$ to a string $w$ of length $n$ by permuting symbols of $w$ according to $\sigma$ and  we denote the new string by $\sigma(w)$.

Let $L(\sigma)=\{\sigma(w) \mid w \in L\}$.

What interesting classes $C$ one can define s.t for any finite regular language $L$, either $L$ has a DFA in the class $C$ (L is recognized by a DFA which satisfies properties of class C) or there is a permutation $\sigma$ such that $L(\sigma)$ has a DFA in the class $C$.

Effect of permutation, an example: $L =\{ww | w \in \{0,1\}^n\}$ has only acyclic DFA of size $\Omega(2^n)$ but there is a $\sigma$ such that $L(\sigma) =\{w_1^2w_2^2\cdots w_n^2 | w \in \{0,1\}^n\}$ has $O(n)$ size DFA. I refer $L(\sigma)$ as a deformation of $L$.

Is there some references for study of these kind? are similar questions for CFL studied?

Thank you.


texts: Measurable language which is not $\omega$-regular

texts:
Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider
$$
  d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)}
$$
to be the metric on $\Sigma^\omega$ which makes the latter being the Cantor space. Denote by $\mathscr B(\Sigma^\omega)$ the Borel $\sigma$-algebra of this space, and let's call its elements measurable languages. It follows from Proposition 6 here that any $\omega$-regular language is measurable. I am looking for an example of a measurable language which is not $\omega$-regular, so any hints are appreciated.


texts: Christofides algorithm for directed graph

texts:
Is it possible to implement the Christofides algorithm for an directed Graph?

Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to itself). But the weights of the edges, don't necessarily have do be the same in both ways (unsymmetrical).

For Example you think of a Street Map, in which there are a lot of oneway streets.

We now want to find an approximation for the traveling salesman tour through all the vertices.

First of all the Christoffides algorithm is not defined for such an TSP, because the Minimum Spanning Tree ist not defined for an directed Graph.

But still we start the algorithm by finding the optimum branching with Edmonds algorithm to the start point of the tour as the root.

Then we find a minimal perfect matching for the branching, so that it becomes an Eulerian graph. This will happen with the Hungarian algorithm, wich finds an minimal matching so that every vertex in the branching has afterwords the same amount of edges coming in an out.

In the last step we find the euler tour and optimize the tour by taking shortcuts.

I have to questions:

Is the way I want to implement the algorithm right, or did I made a mistake and it can't work
If it works, is it still bounded bei 1,5 of the optimal solution for the tsp?


texts: research papers for undergraduate students

texts:
The papers presented at conferences like SODA, FOCS are hard to understand for undergraduates. Also a lot of background knowledge is assumed for understanding such papers. Are there any conferences/resources/websites where I can find interesting research paper readable by undergrads.

thanks


texts: Online/approximate weighted and capacitated bipartite matching

texts:
I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.

Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\in R$, it has capacity $c_i$ which means that at most $c_i$ nodes from $L$ can be matched to $r_i$. The objective function to maximize is $\sum_{i=1}^{n_2}x_iw_i$ where $x_i$ is the number of nodes in $L$ matched to $r_i$ and $w_i>0$ is the weight. The constraints are (1) $x_i\in\{0,...,c_i\}$, (2) any node in $L$ can be matched at most once and (3) any node $l_j$ is allowed to be matched to $r_i$ if $(l_j, r_i)$  $\in E$.

Is there any paper that solved the exact problem as I described above (provides either approximate or online algorithm)? To be clear, I am asking for references, and methods are not necessary.


texts: Does the following type of hitting problem have a name?

texts:
Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the cardinality of the union $B_1\cup B_2\cup\dots\cup B_m$ is minimized. In other words, I want to hit each of the families $\mathcal F_i$ using as few elements of the ground set as possible.

Edit (an example for a special case): A scheduling problem that can be interpreted in this way is where you want to schedule a set of jobs indexed by $i$ (given by earliest start time $r_i$, latest completion time $d_i$  and processing time $p_i$) on a single machine of infinite capacity, and the objective is to minimize the total busy time of the machine. In this setting, the family $\mathcal F_i$ would just be the set of intervals $\{[r_i,r_i+p_i-1],[r_i+1,r_i+p_i],\dots,[d_i-p_i+1,d_i]\}$, and the problem can be solved efficiently (Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. “Real-time scheduling
to minimize machine busy times”. In: Journal of Scheduling 18.6 (2015), p. 561-573, doi:10.1007/s10951-014-0411-z)

I am looking for references where this problem (or something similar) has been considered with more general families $\mathcal F_i$.


texts: Do there exist "odd times" cover problems and what do we know about their approximability?

texts:
I am currently investigating a problem which can be formulated as a cover problem, in which real intervals have to be covered an odd number of times by integers.

My question is just, if anybody has heard of cover problems in which the items have to be covered an odd number of times. And if so, are there any results about the (in)approximability of such problems known.


texts:
In Wadler's Recursive Types for Free! [1], he demonstrated two types, $\forall X . (F(X) \rightarrow X) \rightarrow X$ and $\exists X . (X \rightarrow F(X)) \times X$, and claimed they are dual.  In particular, he pointed out that the type $\exists X . X \rightarrow (X \rightarrow F(X))$ is not the dual of the former.  It seems the duality in question here is different from De Morgan duality in logic.  I wonder how the duality of types is defined, specfically for the three types mentioned, why the second is dual of the first while the third is not.  Thanks.

[1] http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt


texts: Proving the set of powers of 2 over ternary alphabet to be non regular.

texts:
It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it.

But the powers of 2 represented in ternary appears to be non regular. Pumping lemma or residue classes is hard to apply as there seems to be very little pattern among the strings. How do I solve it?

In general, for what powers of $k$ represented in base $r$, is the set regular?


texts:
I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial time just amazes me.

The only real knowledge I have about the model is stuff I picked up from the blog and from recent youtube video's where Aaronson discusses the subject. I have also recently read that the first quantum computer was sold.

Now I am wondering, and I hope this is not a stupid question, is quantum computing a turing complete computational model?

Also, how come there is an efficient factoring algorithm and not, say, an efficient algorithm for the graph isomorphism problem? What are the boundaries?

I hope answers will give me a more clear image of quantum computing.


texts: Programming languages for efficient computation

texts:
It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard complexity class. In particular, we can define a language in which we can express all efficient computations and only efficient computations.

For instance, for something like $P$: take your favorite programming language, and after you write your program (corresponding to Turing Machine $M'$), add three values to the header: an integer $c$, and integer $k$, and a default output $d$. When the program is compiled, output a Turing machine $M$ that given input $x$ of size $n$ runs $M'$ on $x$ for $c n^k$ steps. If $M'$ does not halt before the $c n^k$ steps are up, output the default output $d$. Unless I am mistaken, this programming languages will allow us to express all computations in $P$ and nothing more. However, this proposed language is inherently non-interesting.

My question: are there programming languages that capture subsets of computable functions (such as all efficiently computable function) in a non-trivial way? If there are not, is there a reason for this?


texts:
Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane.  In general the edges of $G$ may be represented as arcs rather than straight line segments; let $\overline{cr}(G)$ be the crossing number of $G$ when edges must be drawn as straight line segments.  Fáry's Theorem says that
$$cr(G) = 0 \iff \overline{cr}(G) = 0,$$
 but it is known that equality doesn't hold in general.  So, my question is whether there are any weaker constraints on the drawing where equality does hold in general:

  What restrictions can we place on the edge arcs of graph drawings without affecting the crossing number?

For example, can we always achieve minimum crossing number while drawing each edge curving monotonically in some direction?  What about drawing each edge as an algebraic curve?  I'd be interested in any results along these lines.


texts: Fast sparse boolean matrix product with possible preprocessing

texts:
What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)?

Actually, I have the advantage that when I'm multiplying A by B, the B's are predefined and I can do arbitrarily complex preprocessing on them. I also know that the results of products are always as sparse as the original matrices.

The "rather naive" algorithm (scan A by rows; for each 1 bit of the A-row, OR the result with the corresponding row of B) turns out very efficient and requires only a couple thousand of CPU instructions to compute a single product, so it won't be easy to surpass it, and it's only surpassable by a constant factor (because there are hundreds of one bits in the result). But I'm not losing hope and asking the community for help :)


texts: Bob's Sale (reordering of pairs with constraints to minimize sum of products)

texts:
I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well.

Someone has already asked a question related to this problem here - Minimum weight subforest of given cardinality - but as far as I understand it doesn't help me with my problem. The highest-rated answer on StackOverflow is also worth looking at.

Here's the verbatim copy of my StackOverflow question. It's probably inadequately formulated for this site (heck, I feel inadequately uneducated just asking it here), so feel free to edit it:

Note: this is an abstract rewording of a real-life problem regarding ordering records in a SWF file. A solution will help me improve an open-source application.

Bob has a store, and wants to do a sale. His store carries a number of products, and he has a certain integer quantity of units of each product in stock. He also has a number of shelf-mounted price labels (as many as the number of products), with the prices already printed on them. He can place any price label on any product (unitary price for one item for his entire stock of that product), however some products have an additional restriction - any such product may not be cheaper than a certain other product.

You must find how to arrange the price labels, such that the total cost of all of Bob's wares is as low as possible. The total cost is the sum of each product's assigned price label multiplied by the quantity of that product in stock.

Given:

N – the number of products and price labels
Si, 0≤i<N – the quantity in stock of product with index i (integer)
Pj, 0≤j<N – the price on price label with index j (integer)
K – the number of additional constraint pairs
Ak, Bk, 0≤k<K – product indices for the additional constraint

Any product index may appear at most once in B. Thus, the graph formed by this adjacency list is actually a set of directed trees.

The program must find:

Mi, 0≤i<N – mapping from product index to price label index (PMi is price of product i)

To satisfy the conditions:

PMAk ≤ PMBk, for 0≤k<K
Σ(Si × PMi) for 0≤i<N is minimal

Note that if not for the first condition, the solution would be simply sorting labels by price and products by quantity, and matching both directly.

Typical values for input will be N,K<10000. In the real-life problem, there are only several distinct price tags (1,2,3,4).

Here's one example of why most simple solutions (including topological sort) won't work:

You have 10 items with the quantities 1 through 10, and 10 price labels with the prices $\$$1 through $\$$10. There is one condition: the item with the quantity 10 must not be cheaper than the item with the quantity 1.

The optimal solution is:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

with a total cost of $\$$249. If you place the 1,10 pair near either extreme, the total cost will be higher.


texts:
I am writing a paper for a TCS conference and wondering what the community's opinion is on how abstracts in TCS should be written, good practices, or rules of thumb. I thought that I had read enough papers to be able to answer this question on my own, but after thinking about it a bit, I'm stumped.

Some specific questions I do not know the answer to:

What is the purpose of the abstract? Is it to help those who do not want to read the paper figure this out as early as possible? To help a future researcher understand whether the paper contains a result of use to them? To communicate the key novelty/results/advancement of the paper? Something else?
Who is the intended audience of the abstract? General computer science researchers, general TCS researchers, or researchers who specialize in the topic of the paper?
Similarly, to what extent should technical terms be introduced/defined in the abstract?
Does motivation belong in the abstract? Sometimes if I am not careful I find my abstracts turning into introductions.
What is the value of listing precise results versus outlining the general question addressed? In other words, how specific should the abstract be regarding the results? It seems hard to hit multiple levels of specific/general without being redundant.
When is it appropriate to mention/summarize prior work and background?

I was looking over responses to this question on examples of good TCS papers. There did not seem to be enough samples for me to learn, however :). The approaches to abstract-writing seem to vary widely.


texts:
Consider the undirected graph $G=(V,E)$ example below.
More precisely, the vertices in $V$ are labelled with $(x,y)$-coordinates and there is an edge between every vertices sharing the same $x$ and $y$ (not shown on the figure). For instance: $(1,1)-(1,2)$, $(1,1)-(1,3)$ and $(1,1)-(1,4)$

First question: Does this graph structure has a name?
Note that the sketch is only an example and can be generalized, but I am not sure whether the generalized graphs would still be planar.

(1,1) --- (1,2) --- (1,3) --- (1,4)
  |         |         |         |
  |         |         |         |
  |         |         |         |
(2,1) --- (2,2)       |         |
  |         |         |         |
  |         |         |         |
  |         |         |         |
(3,1) --- (3,2) --- (3,3) --- (3,4)
  |         |
  |         |
  |         |
(4,1) --- (4,2)

Second question: I'm interested in finding short-cycle covers of this graph (length 4 or 6 typically). Two solutions of the problem for cycles of length 4 would be:

(1,1)-(1,2)-(2,1)-(2,2)
(3,1)-(3,2)-(4,1)-(4,2)
(1,3)-(1,4)-(3,3)-(3,4)

and

(1,1)-(1,3)-(3,1)-(3,3)
(1,2)-(1,4)-(3,2)-(3,4)
(2,1)-(2,2)-(4,1)-(4,2)

And one solution for cycles of length 6:

(1,1)-(2,1)-(2,2)-(3,2)-(3,4)-(1,4)
(1,2)-(1,3)-(3,3)-(3,1)-(4,1)-(4,2)

I know that the general case for 3-cycle cover is NP-complete, but does the special structure of this graph enables to get a simple algorithm solving the cycle cover problem?


texts: Asymmetric metric TSP when many edges have equal costs in both directions

texts:
I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for $O(log(|E|)$ edges, or something close/related to that (in fact when this holds for the 'small-cost' edges).
Thank you


texts:
The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and Visibly Pushdown Automata?
For example, Dyck languages require parenthesis to be paired, but visibly pushdown languages merely require that stack movement is controlled by the input tape, without any requirement that "call symbols" and "return symbols" are matched one-to-one.
It is easy to imagine an intermediate class, e.g. the class of visibly push down languages where the removal of all level symbols from each word results in a Dyck language, but I'm not sure if any such classes have useful properties or have been the subject of previous study.


texts: On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

texts:
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.

MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time orientation algorithm.

  Is it possible to compute the determinant also in linear time?

Note that if we explicitly write down the matrix with Pfaffian orientation we need $\Omega(|V|^2)$ space to write down the matrix. But since number of edges is only $O(|V|)$ we might be able to get away with linear time algorithm for counting number of perfect matchings of a planar graph. Is this possible?

If $M\in\{-1,0,+1\}^{n\times n}$ be a matrix with only $O(n)$ non-zero entries and hadamard product $M\odot M$ being symmetric can we compute $Det(M)$ in $O(n)$ bit complexity?

Assume that the matrix is given in form a list where $1,-1$ locations are and so the presentation is only $O(n)$ sized.

The motivation comes from possibility of counting $\#$ of perfect matchings in planar graphs in linear time?

First of all $\#$ of perfect matchings can be written down in $O(n)$ bits for planar graphs.
Secondly given adjacency matrix $A$ we can find MST in linear time for planar graphs.
Thirdly from MST we can find a pfaffian orientation and find $M\in\{-1,0,+1\}^{n\times n}$ in linear time (So $M\odot M=A$).

So it seems highly plausible it should be the case that $\#$ of perfect matchings on planar graph should be computable in linear time with $O(n)$ bit complexity.

However if we use $Det(M)$ directly we cannot avoid $O(n^2)$ at best. But there may be an indirect way to compute $Det(M)$.


texts: Connectivity of graphs by edge and vertex removal

texts: Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the standard definition, is $(k-1,0)$-connected, according to the new definition. Is there a polynomial-time algorithm to decide if $G$ is $(a,b)$-connected? Here I consider that the input is $G$, $a$ and $b$.


texts: A possible error in the semantic chapter of the ISO standard for the Z specification notation

texts:
I may have found an error in the ISO standards document for the Z specification notation, namely ISO/IEC 13568:2002, "Information technology — Z formal specification notation — Syntax, type system and semantics".
The possible error is in chapter 15 "Semantic relations". This chapter describes the formal semantics of the Z notation. More specifically, the problem is in the following equation appearing in section 15.2.5.1 "Reference expression" on p. 75 that is meant to describe the meaning of a reference expression $i$, where $i$ is a variable name:
$$
[[i]]^{\mathcal{E}} = \lambda M : \text{Model} \bullet M\ i.
$$
This function is defined for every model $M$. But for those models whose domains don't contain the name $i$ the expression $M\ i$ is undefined.
Is this, in fact, an error, or do I overlook something? I'd appreciate an authoritative answer; I too can make speculations.


texts: (perfect fractional) matching in regular hypergraphs

texts:
I have been looking in general for results on matching for regular hypergraphs that are not uniform, but I could not find any. Papers I found by internet search seem to focus on uniform hypergraphs (sometimes in addition to being regular). The relative scarcity of results on regular hypergraph matching is somewhat puzzling, since uniform and regular hypergraphs are duals of each other and one would expect that matching may have been studied for both kinds.

I would appreciate if someone can point me to any sources. Of most interest to me are necessary and/or sufficient conditions for existence perfect matchings and closed form expressions or bounds for fractional matchings. I am also curious to know explanations (conceptual, historical etc) for the lack of results of this kind for regular hypergraphs.

Edit: A matching is a collection of pairwise disjoint hyperedges; a perfect matching is a matching that covers all vertices.


texts: Implications of a problem being in XP when parameterized by diameter

texts:
Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if it can be solved in $n^{f(k)}$ time). Does this imply solvability in XP time for other interesting parameters?

If so, is there maybe even some more or less "standard" list or web of parameters and how they relate documented somewhere?


texts:
Given an undirected graph and an integer $B$,
we ask to find the minimum set of nodes
whose removal partitions the generated graph into connected components,
each having at most $B$ nodes.

We can consider this to be a generalization of the minimum vertex cover,
where $B=1$, since deleting the vertex cover set of a graph $G$ gives an independent set,
i.e. partition G on connected component of no more than 1 node.

Are there similar problems in literature?
This problem is NP-complete on general graphs.
Which known problem on graph theory help to study its (in)approximation?
I want to study it on chordal graphs.
For which cases it may be polynomial and for which it is NP-complete?


texts:
Consider a connected random cubic graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined here, i.e. $3n$ is even and any two graphs have the same probability).

Of course there are $n$ possible Breadth First Searches, one for each starting node $s \in V$. A Breadth First Search $B_G$ starting at node $s \in V$ assigns a level $d(s, v)$ to each node $v \in V$, where $d(s, v)$ is the distance between $s$ and $v$ in $G$.

Let us say that such a Breadth First Search $B_G$ also assigns a level
$$ L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$$
 to each edge $e=\{u,v\} \in E$.

Given a specific Breadth First Search $B_G$, let $\alpha(B_G,i)$ be the number of edges that have been assigned level $i$, and let $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$. In other words $\alpha(B_G)$ is the number of edges of the level containing more edges than any other level. Finally, let $\alpha(G)$ be the maximum $\alpha(B_G)$ for any of the $n$ Breadth First Searches of $G$.

Let us call $\alpha(G)$ the amplitude of $G$.

  Question

  How does the expected value of $\alpha(G)$ grow as $n$ tends to infinity? Recall that $G$ is random cubic. More precisely, what I really would like to know is whether the expected value of $\alpha(G)$ belongs to $o(n)$.

Since $n$ is even, the limit is considered so that I don't care of odd $n$'s.


texts: Proving not NP-complete by non-existence of gadget

texts:
Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if the problem under consideration is NP-hard, then some widely believed complexity assumption fails (e.g.: Graph Isomorphism).
Is it possible to show that a problem $X$ is not NP-hard by showing the following?
(i) certain type of gadget must exist for a reduction from 3-SAT to $X$, and
(ii) the type of gadget asserted in point (i) cannot exist.
I am afraid such results are not there. Are there at least conjectures that take this direction?


texts:
Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned on the formula being satisfiable:

Q1: Can this be achieved efficiently by a classical computer (with random bits)?

Q2: Can this be achieved efficiently by a quantum computer?

I am also interested in the following two variants:

V2: You sample all the formulas w.r.t. a probability distribution that gives satisfiable formulas twice the weight of unsatisfiable formulas.

V3: you sample where the weight is the number of satisfying assignments (Here we care only about Q2).

Update: Colins' answer demonstrates a simple algorithm for V3. (I was wrong in assuming that this is classically difficult.) Let me mention another variant
of all the three questions:

You specify in advance $m$ clauses and you need to sample random satisfiable subsets of the input clauses.


texts: Applicability of Church-Turing thesis to interactive models of computation

texts:
Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere.  That is, it is presented as encompassing all computation when in fact it applies only to computation of functions, which is a very small subset of all computation.  Instead they suggest we should seek to model interactive computation, where communication with the outside world happens during the computation.

The only critique I have seen of this work is in the Lambda the Ultimate forum, where somebody lamented these authors for continually publishing what is obviously known.  My question then is, is there any more critique into this line of thinking, and in particular their Persistent Turing Machines.  And if not, why then is it seemingly studied very little (I could be mistaken).  Lastly, how does the notion of universality translate to an interactive domain.


texts: Complexity of topological sort with constrained positions

texts:
I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.

A topological sort of $G$ is a bijection $f$ from the vertices of $G$ to $\{1, \ldots, n\}$ such that for all $x$, $y$, if there is a path from $x$ to $y$ in $G$ then $f(x) \leq f(y)$. I wish to decide whether there exists a topological sort of $G$ such that for all $x$, $f(x) \in S(x)$.

What is the complexity of this decision problem?

[Notes: Clearly this is in NP. If you look at the graph of allowed vertex/position pairs, with undirected edges between pairings that conflict because they violate the order, you get a graph of disjoint cliques where you want to pick at most one pair per clique, at most one pair per position and at most one pair per vertex -- it seems related to 3-dimensional matching but I can't see if it is still hard with the additional structure of this specific problem.]


texts: Is qsort linear when sorting only two values?

texts: This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?


texts: Implementation that solves minimum set cover

texts:
Does anyone know of any tools that solve the approximate minimum set cover problem?

I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about more sophisticated algorithms/heuristic that do better on many problems in practice.  (e.g., Algorithms for the Set Covering Problem by Caprara et al.)  Are there any implementations generally available?  Any tools that others can use to find approximately optimal solutions, for large problem instances?  I'd prefer to use an existing tool, rather than try to understand and implement these sophisticated algorithms myself.


texts:
This is a followup to my followup to David's question.  This question admittedly leaves the original motivation far behind, but it might provide some useful intuition.

Suppose we are given a set of n non-vertical lines, each with a (possibly negative) real weight.  The lines partition the planes into convex polygonal cells; the cell complex is usually called an arrangement.  Define the weight of a cell to be the sum of the weights of the lines that lie above it.  Let p be a point that lies above every line, and let q be a point that lies below every line.

  Suppose there is a path between p and
  q that intersects only cells with
  non-negative weight.  Is there a path
  from p and q that intersects only
  cells with non-negative weight and
  crosses each line exactly once?

Equivalently: Suppose we are given a set of points in the plane, each with a (possibly negative) real weight.  Now imagine continuously moving a straight line, starting above all the points and ending below all the points, such that the line is never vertical.  Call the motion legal if at all times, the total weight of the points above the line is non-negative.

  If there is a legal motion, must there
  be a legal motion where the moving
  line passes over each point exactly
  once?

(It is easy to find such a path/motion or determine that none exists in $O(n^2)$ time.)


texts: How can you prove that a problem is not solvable in a certain time complexity?

texts:
One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable in polynomial time. However, I can't quite figure out how it would be possible to prove such a thing.

How can you prove that there is no better solution possible to a problem than a solution which has a certain time complexity?

I understand that there are no problems known in NP for which is proven that it cannot be solved in polynomial time, but are there problems known for which a proof does exists that it cannot be solved in for example constant or linear time? Perhaps an example of such a problem can help me understand this better.

EDIT: If you down vote this question could you please at least post a comment why you did so? I'd love to improve my question, but down votes alone don't tell me what I did wrong.


texts: How does Best Partition Communication Complexity behave under input transformations?

texts:
I'm looking for references about the behavior of communication complexity under input transformations. A specific toy example of the kind of question I'm interested in is the following.

Let $f(x_1,...,x_n)$ be a Boolean function over variables $\{x_1,...,x_n\}$ and $g(y_1,...,y_n,z_1,...,z_n)$ be a Boolean function over variables $\{y_1,...,y_n\} \cup \{z_1,....,z_n\}$ such that for each $a_1,...,a_n\in \{0,1\}^n$,
$$f(a_1,...,a_n) = 1$$ if and only if there exists $b_1,...,b_n\in \{0,1\}^n$ and $c_1,...,c_n\in \{0,1\}^n$ such that
$$g(b_1,...,b_n,c_1,...,c_n)=1 \mbox{ and } a_i = b_i \vee c_i \mbox{ for each $i\in \{1,...,n\}$}$$.

Question: Assume that the best partition communication complexity of $f$ is $d$. Is it true that the
best partition communication complexity of $g$ is at least $d$?


texts: About a pre-processing step for primal–dual weighted set cover problem

texts:
I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.
They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements($U$) and $m$ sets($S$). Each set has a positive weight. Let $E_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ weight(s). Let also $IP^*$ is the weight of an optimal set cover. It is easy to see, $IP^*\geq \beta$. Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that, "Since $\beta$ is a lower bound on $IP^*$, this cost is subsumed in the approximation. " And this is the statement I did not understand.


texts: Are quasi-polynomial sized circuits for 3-SAT trivial?

texts:
Suppose we consider 3-SAT with $v$ variables and $c$ clauses.  I am researching a method that appears to take $O(v^{2+\log c})$ time/space to solve any SAT problem fitting this description, to within an error that can be adjusted to an arbitrary amount.  However, there is a catch.

This method requires a set of precomputed values, after which it can solve an arbitrary 3-SAT problem fitting the above description.  The precomputed values are a set of size $O(v^{2+\log c})$ with each value taking $O(1)$ space.  The real problem is that each of these values could take $O(2^v)$ time to compute.  There is a chance that I can find a way to speed up these calculations.

I'm thinking that the bounds itself beats the upper bounds presented in this question (for small $c$).  So I'm wondering, is there a trivial way to reach the upper bounds I describe if we allow $O(v^{2+\log c})$ precomputations?

I'd like to continue this research and hopefully publish my results if everything works out, but first I'd like to know if there is a trivial way to do as well or better.

UPDATE

I have been studying related problems in addition to researching this algorithm.  I asked This question on StackExchange's IT Security site relating to password cracking and SAT, if you are interested.  At least one of the answers reflects this.


texts: Johnson Lindenstrauss for Random variables?

texts:
Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X_1,...,X_N)$ over $N$ uncertain states. If $\pi_i$ is the probability of state $i$, then this space has an inner product $\langle X, Y \rangle = E(XY) = \sum_{i=1}^n \pi_i X_i Y_i$ and a norm $\|X\|^2_{\pi} = \langle X, X \rangle = \sum_{i=1}^N \pi_i X_i^2$.

The standard JL lemma says that, if $S$ is a set of $m$ points in $\mathbb{R}^n$ and $n > C \frac{ln(m)}{\varepsilon^2}$ then there a (suitably scaled) random orthogonal projection $f:\mathbb{R}^N \to \mathbb{R}^n$
will satisfy

$$(1-\varepsilon)\|u-v\|^2_{N} \leq \|f(u) - f(v)\|_{n}^2 \leq (1+\varepsilon)\|u-v\|_{N}^2$$
where I have used $\|\cdot\|_{n},\|\cdot\|_{N}$ to denote the standard euclidean norms in $\mathbb{R}^n$ and $\mathbb{R}^N.$

Does there exist a version of the lemma with the weighted norm  $\|X\|^2_{\pi}$? What would the corresponding norm in the lower $n$-dimensional space look like?


texts: Does the awards budget cut problem support a sub $O(n\log n)$ time solution?

texts:
There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.
The problem gives you an input of $n$ integers called grants $g_1 ... g_n$ along with an integer budget $B$. We are then asked to find an integer $C$ (which we refer to as the cap) which has the following property:
$C$ minimizes the number grants $g_i$ that are greater than it WHILE also ensuring that $\sum_{g_i} \lbrace{ \min(g_i, c)\rbrace} \le B$
Note that the value $C$ is not necessarily unique, there are multiple values that satisfy the condition above. Any such value is desirable.
Now theres a pretty simple $O(n \log n)$ solution to this, which involves sorting the grants-array and then identifying the largest grant (usually through binary search or linear serach) such that the sum of all grants capped at this value end up being less than the budget.
Now the question is, is it possible to asymptotically do better? I'm reminded of the median problem which has a very similar "relative-cut" definition and whose optimal algorithm for a while always required sorting but then the exotic median-medians algorithm revealed that one could actually pull off $O(n)$ time.
I am very suspicious that a similar exotic awards grant algorithm should exist here.
See the following for more information:
https://kobejean.github.io/algorithms/2020/03/08/the-award-budget-cuts-problem/
https://codereview.stackexchange.com/questions/194272/award-budget-cuts-implementation-in-java
https://leetcode.com/discuss/interview-question/351313/Google-or-Phone-Screen-or-Salary-Adjustment


texts: Is this a known problem, and is it #P-complete?

texts:
Let $G=(V,E)$ be an undirected graph. What I call a selection function of $G$ is a partial function $f:V \to E$ such that for every node $v$, if $f(v)$ is defined then it is one of the adjacent edges to $v$. In other words, every node can either select no edge or select an edge that is adjacent to it. The image of $f$ is simply $\mathrm{Im}(f)= \{e \in E \mid \exists v \in V \text{ s.t. } e=f(v)\}$ i.e., the set of edges that are selected.

I am interested in the following counting problem:

INPUT: a graph $G$

OUTPUT: $|\{\mathrm{Im}(f) \mid f \text{ is a selection function of }G\}|$

Question 1: does it have an established name? (It seems to be to be rather natural so maybe it has already been considered)

Question 2: is this problem #P-hard? (Ideally, I would like it to be hard on bipartite graphs)

Note that this problem is in #P, which is not entirely obvious at first glance. To show this, it is enough to show that for every $S \subseteq E$, we can determine in PTIME if $S$ is the image of some selection function. This can be done as follows. First, construct the bipartite graph $G_S$ with nodes in the left partition being the nodes of $G$ and nodes in the right partition being edges in $S$, and connect $v$ in the left partition to $e$ in $S$ if $v$ is an endpoint of $e$. Then, compute the size $m$ of a maximum cardinality matching of $G_S$. Accept if $m=|S|$, and reject otherwise (observe that $m$ is always $\leq |S|)$. It is easy to check that this accepts iff $S$ is the image of some selection function.


texts: Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

texts:
What are some (not well-known) assertions that if true, the PH must collapse?

Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much luck.


texts: Building a decision tree to approximate a known function (not to learn an unknown function)

texts:
I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.

I would like to approximate $f$ using a decision tree.

Up to now I have only found literature in the context of machine learning, where $f$ is unknown, some samples $(x_i,\ y_i=f(x_i) + \mathrm{noise})$ are available and $f$ is estimated using a decision tree. That is a learning problem.

In my case I have a known (non trivial) expression for $f$ and I want to obtain the shortest binary decision tree for an arbitrarily good approximation (up to a specific error $\epsilon$). This seem to be a different problem than the learning problem (for instance, there is no regularization term to ensure generalization).

I suspect this problem to "hard". I assume some literature must exist on "no guarantees, greedy approaches" or similar, but I have not be able to find any.

Could any of you point me out some paper or book referring to this problem ?

Thanks for you answers.


texts: Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?

texts:
Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?

There is some known data for parity checks, CRC, Hamming encoding, but is there a theoretical limit?


texts:
Given two (deterministic) finite automata $A, B$ over $\Sigma$, a mapping $h:\Sigma\rightarrow \Sigma'$

Naturally $h$ can be extended to a mapping in $\Sigma^*\rightarrow \Sigma'^*$ which is denoted by $h$ as well.

Is the set
$$\{w\in L(A)\mid h^{-1}(h(w))\subseteq L(B)\}$$ regular?


texts:
Classic Problem:

Let a number $k$ be given.  The $k$-clique problem is as follows.

Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent?

Hypergraph Problem:

Let numbers $c$ and $k$ be given.  The $(c,k)$-hyperclique problem is as follows.

Given a $c$-uniform hypergraph $H$, does there exist a set $S$ of $k$ vertices so that any subset of $c$ vertices from $S$ forms a hyperedge.

Questions:

(1) What is the best known algorithm for solving $(c,k)$-hyperclique?

(2) What is its time complexity?

(3) Is there any connection between $(c,k)$-hyperclique and matrix multiplication?

For all I know, this might be a well studied problem.  Any references that investigate this problem are greatly appreciated.


texts: Williams' Method, Natural Proofs and Constructivity

texts:
I have some questions on the previous question which is written bellow.

Natural Proof and Constructivity : The topic of the previous question

Recently, Ryan Williams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.

Constructivity in Natural Proof is a condition that all combinatorial proofs in circuit complexity satisfies and that we can decide whether the target function in $\mathsf{NEXP}$ (or another "hard" complexity classes) has a "hard" property by a algorithm that runs in poly-time in the length of target function's truth table.

The other two conditions are: useless condition that require "hard" property can not be computed by any circuits in $\mathsf{TC}^0$ and largeness condition that the hard property is easy to find.

References:
* Ryan Williams, "Natural Proofs Versus Derandomization"

My Question

Breaking the largeness condition is formally stated as follows.

There is a property such that

$\mathop{Pr}_{f \leftarrow_{R} \{0,1\}^{2^{n}}} [f $ have the constructive property which is hard and useful against the class $\mathcal{C}] \leq \frac{o(2^{n})}{2^{2^{n}}}$

  If someone prove that the following statement , the statement have some meaning or shed light on this topic ?

  Statement:For some $f$, there exists  $n$-inputs circuit $C \in \mathcal{C}$ computing $f$ of size $m$ such that Circuit SAT on $C$ can be solved nontorivialy faster in the sence of the Ryan's technique, that is , $2^{n-l(m)}poly (m,n)$ giving a lower bound $2^{l(n)}$ against $NEXP$.

I am not sure whether this question is a good one, because in the Ryan's methods, the circuit which is given as an instance of CKT-SAT is yield through proof by contradiction. That is, Ryan shows that if $NEXP \subseteq P/poly$ then there is a circuit as an compressed representation of witnesses and the exsistance of such circuit is derived through proof by contradiction using derandomization and $NEXP \subseteq P/poly \Rightarrow NEXP=EXP=MA$.

  I am not sure the property which circuits as a compressed representation of witnesses have and the function $f_{C}$ which circuits as a compressed representation computes.
  If $f_{C}$ is very rare in the sence of largeness, can we break the largeness condition ?


texts: Constrained Topological Sorting with bounded number of chains

texts:
In general, constrained topological sorting is NP-hard.

Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair (u, v)such that there is a path from u to v -- that is, there can be maximum k number of chains.

I want to know, is it still NP Hard?

Edit: I have my answer. Decision version of this question is in NL which implies it is in PTIME.


texts: Bainbridge coauthored the paper `Functorial Polymorphism' with Freyd, Scedrov and Scott (DOI). What is his/her first name?


texts: Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

texts:
Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume  $H$ has  subgraphs $H_1, H_2... H_x$ (total $x$ vertex set).

Consider, a permutation $\pi_k \in \beta_k$ where $H_k^{\pi_k}=G_k$ such that $P= \pi_1 \times \pi_2...\pi_x$ (i.e. $P$ is  the direct product of permutations $\pi_1, \pi_2 ..... \pi_x$) and $H^P=G$.

$\pi_k$ is a local isomorphism and $P$ is global isomorphism of $G,H$.

$G_k, \forall k$ is not an $Independent$ $ Set$ .

Here, $\beta_k (k\leq x \leq n/2)$ is a set of permutations  for each $H_k$. Let, $\beta$ is a number and $\beta_k$ has maximum $\beta$ permutations.

Question  If All $\beta_k$ are given, how many steps are required to construct $P$, i.e. what is the computational complexity of finding $P$?

Brute force leads to $\beta^x$.

Does there exist  a  $\beta^c$ algorithm where $c$ is a constant?

Edit:
1. Consider that  all $H_k$ are ordered according to $G_k$.

A "sifting technique"  might help !
$G_k$ has the same vertices of $H_k$.
$G_k$ has no disconnected component.


texts: Connection strength in a weighted social digraph, based on weights of individual links

texts:
Given a network where edges represent entities and directed vertices represent relationships between entities, and each vertex has a strength between 0 (no relationship) and 1 (strongest).

I'm looking for a method to calculate the path strength between two entities.

For simple cases, I'm considering the following formulas:

Path: The strength of the connection is the multiplication of all weights of the links along the path.

Parallel direct links: The strength of the connection is 1-(1-w1)(1-w2)...(1-wn)

My questions:

Were these formulas suggested before?
How can this method be extended to more complex cases, such as the graphs given below:


texts: Are there enumerations of machines for all languages in  such that there exists a simulator that can efficiently run all the machines enumerated?

texts:
From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (encodings over (0,1)) of such machines provides an indexing of ...we have Theorem: No universal simulator for this indexing can run in ."
He then goes on to say: "can it be proved that  for any indexing of  requires more than  to compute? We have proved this for a wide class of indexings, namely counter indexings satisfying the succinct composition property."

 is the graph of the universal function  and represents the minimum power necessary to simulate  uniformly.

The counter indexing (or polynomial time counters) he is referring to is talked about in the answer here: https://cs.stackexchange.com/questions/126615/how-does-an-enumerator-for-machines-for-languages-work/126621?noredirect=1#comment266467_126621

I'm wondering what causes simulation of the enumerated machines to be difficult, and can it be circumvented--namely: does there exist an enumeration of machines for all languages in $$ that describes the machines in such a way that allows the machines, as specified, to be simulated efficiently by a simulator (with no more than  overhead) on any input--or (basically) as Kozen puts it "allow(s) easy construction of programs from (their) specification"?
Looking for any progress that has been made since Kozen asked ^ the above question ^.


texts: Reference request: Arithmetic circuit complexity

texts:
I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/video) for a gentle introduction? I found these two given below.
Determinant versus permanent by Manindra Agarwal https://pdfs.semanticscholar.org/6a05/a4fe63e409ba040b890bbf5da0f3b1ca7085.pdf
Arithmetic circuits by Amir Shpilka
https://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf
Is there any other material which can be more appropriate for a beginner?


texts:
Suppose that we have an EU-CMA or sEU-CMA signature scheme without random oracles. My question is if messages to be signed are in the form H(m), where H is a hash function (doesn't belong to the signature parameters). Does this affect the security of the scheme?

EU-CMA: existentially unforgeable under chosen message attack.

sEU-CMA: Strongly EU-CMA.

See digital signature forgery for more info.


texts: On a property of random rooted trees with $n$ nodes and of height $h$

texts:
I am working on a proof that require the result of the following problem:

Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of $T$ has degree (# of children) at most $d$. $T$ was picked uniformly at random from all possible such trees. We define a decent on $T$ as follows.  Start with root, for each of its children we decide with probability $p$ whether to decent the subtree rooted by that child. This decisions are made independently for each of the children of root. Then the process continues recursively.

Then, what it is the average number of nodes this procedure will visit?

Is there any known result for this problem for trees with $d$ > 2?


texts:
Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations:

Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z_{\geq 0}} \setminus  A.$
Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.

Disjoint set union comes into mind, but I can't think of a way to make it support mex-es.
Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.

Ideally, both of these should be polylog (on the size of the represented sets).

How about if the sets are from a bounded universe?


texts: Defining Mutually Recursive functions in Coq

texts:
This question is related to (but not the same as):

How to define a function inductively on two arguments in Coq?

In particular, I used those techniques (defining a second fixed point function) and Coq still complains.

Consider the following formalization of regular expressions.

Inductive symbol : Set := Zero | One.

Definition string := list symbol.

Fixpoint symbol_eq (a:symbol) (b:symbol) : bool :=
  match a with
    Zero =>
    match b with
      Zero => true
    | One => false
    end
  | One =>
    match b with
      Zero => false
    | One => true
    end
  end.

Inductive regexp : Set :=
    Symbol (s:symbol)
  | Concat (r1:regexp) (r2:regexp)
  | Union (u1:regexp) (u2:regexp)
  | Star (u1:regexp)
  .

Fixpoint rgm (r:regexp) (s:string) :=
  match r with
    Symbol ss =>
      match s with
        nil => false
      | a::nil => (symbol_eq ss a)
      | a::b::tl => false
      end
   | Union r1 r2 => (orb (rgm r1 s) (rgm r2 s))
   | Concat r1 r2 =>
       let fix f s1 s2 :=
         match s2 with
           nil => (andb (rgm r1 (rev s1)) (rgm r2 s2))
         | a::tl => (orb (andb (rgm r1 (rev s1)) (rgm r2 s2))
                         (f (a::s1) tl))
         end
       in (f nil s)
   | Star r1 =>
       match s with
         nil => true
       | a::tl =>
         let fix f s1 s2 :=
           match s2 with
             nil => (rgm r1 (rev s1))
           | a::tl => (orb (andb (rgm r1 (rev s1)) (rgm r s2))
                           (f (a::s1) tl))
           end
         in (f (a::nil) tl)
       end
  end.

Coq refuses to compile it for the following reason:

Error: Cannot guess decreasing argument of fix.

Question: how can we fix this?


texts: Algebraic account of Gaussian elimination?

texts:
For fun, I've been looking at the interpretation of linear logic in terms of finite-dimensional vector spaces, and ran into an interesting
question about the interpretation of double-negation-elimination in this category.

As is well-known, vector spaces have a natural notion of dual space -- given a vector space $V$,(over a field $R$) the dual space $V^\ast$ is
just the set of linear functions into $V \multimap R$. Furthemore, it is well-known (indeed, so well-known that I don't know who proved it) that every finite-dimensional vector space is isomorphic to its double-dual.

One direction of the isomorphism $V \to V^{\ast\ast}$ is easy (it's just the map $f : V \to V^{\ast\ast} \triangleq v \mapsto \lambda k.\;k(v)$). The other direction is trickier. The usual proof goes something like this:

The dimension of a dual space $V^\ast$ is the same as the original space $V$.
So the double-dual $V^{\ast\ast}$ has the same dimension as the original space $V$.
So if we can show that $f$ has a zero kernel, then we know that $f$ has a range of all of $V^{\ast\ast}$, and so is (one half of) an isomorphism.

But the only way I know of actually computing the inverse $f^{-1}$ requires choosing a basis and then inverting the matrix.

What I'd really like is an algebraic or categorial account of Gauss-Jordan matrix inversion (or Gaussian elimination or LU decomposition or
whatever), so that I can give a syntactic theory of inversion (and hence an operational semantics for double-negation elimination in FD vector spaces).

This seems like the sort of thing that must have been studied before, but my Google skills are apparently not up to the task....


texts:
Given $n$ coin denominations, with $c_1=1$ and $c_2<c_3<..<c_{n}$ being random numbers uniformly distributed in the range $[2,N]$. Asymptotically, for what fraction of coins does the greedy algorithm generate optimal change using this set of denominations?

The answer is known for  3 denominations ; but what about the general case?


texts: Finding the nearest node to a given set of nodes in a graph

texts: I am looking for an algorithm that, given a large weighted undirected graph, would find the node that has minimum average distance from a given set of nodes in the graph.


texts: Establishing causality under conditions of certainty

texts:
I'm currently reading "Causality: Models, Reasoning, and Inference" by Judea Pearl. Early on, he states that the development assumes that there are no certain entailments, no 1 or 0 probabilities -- that every assignment to variables in a causal model has nonzero probability.

I'm interested in applying some of these ideas to program analysis, where perfect entailment is the norm, and most combinations of assignments are impossible. How much of the theory of causality still applies in this scenario?

One interesting note is that he actually violates his own rule at one point when he talks about modelling a STRIPS-like planning language, and mentions in passing assigning 1 or 0 probabilities in that case.


texts: What are the general direction and target question in the field of quantum error correction?

texts:
After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in the quantum setting as well.
Of course, there was also the big break of stabilizer formalism, fault-tolerant computing and particular families of codes like Toric code and other surface codes.
What are the general directions and target questions in the area (like current status of decoding algorithms and codes with good parameters) and applications of it?
For example on the application side, one key area that we see nowadays is local codes and connections to qPCP or hamiltonian complexity. What are some (big or small) questions that we are trying to answer?


texts: Enumerating results of a variant of LCE queries

texts:
Let $\Sigma$ be an ordered finite alphabet.
Longest Common Extension (LCE) queries are the following problem:

Input: a string $w$ of size $n$
Query: two integers $i$ and $j$ such that $0 < i \leq n$ and $0 < j \leq n$
Output: $\max \{ k, w[i..i+k] = w[j..j+k] \}$

where $w[i]$ is the $i$-th character of $w$ (starting from $1$) and $w[i..j] = w[i] w[i+1] \dots w[j]$.
LCE queries are solvable in $O(1)$ for any $i$ and $j$ after a linear preprocessing of $w$.
I want to solve a variant of this problem (one might call it Mirror LCE queries):

Input (same as before): a string $w$ of size $n$
Query (same as before): two integers $i$ and $j$ such that $0 < i \leq n$ and $0 < j \leq n$
Output : $\{ k, w[i-k..i] = w[j..j+k] \}$

Are Mirror LCE queries enumerable in linear preprocessing constant-delay ?
Note: by linear preprocessing constant-delay, I mean the following: the algorithm is first given $w$ and has linear time to produce a data structure $D$.
This data structure can then be used with any $i$ and $j$ to enumerate all the corresponding $k$s with no duplicates with $O(1)$ time between two consecutive answers.


texts: Concatenative binary lambda calculus/combinatory logic

texts:
John Tromp defines a version of the lambda calculus that is encoded in binary:
https://tromp.github.io/cl/cl.html

a) Does there exist a concatenative version of this language (or its combinatory equivalent)?

b) Does there exist a concatenative version restricted to the primitive recursive functions (e.g. as per Combinators for the Primitive Recursive Functions)?


texts: What evidence is there that Graph Isomorphism is not in $P$?

texts:
Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$.

One such evidence is the $NP$-completeness of a restricted Graph Automorphism problem(fixed-point free graph automorphism problem is $NP$-complete). This problem and other generalizations of $GI$ were studied in "Some NP-complete problems similar to Graph Isomorphism" by Lubiw. Some may argue as evidence the fact that despite more than 45 years no one found polynomial-time algorithm for $GI$.

  What other evidence do we have to believe that $GI$ is not in $P$?


texts: Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?


texts: representation of concept classes and pac learning

texts:
I was reading the book of Kearns and Vazirani and I didn't completely understand the following:

Let C be a concept class and suppose we want to PAC learn C, they say first consider a larger hypothesis set $H$ such that $C\subset H$, where the output of the learner lies in $H$. Then, they go on to show that suppose the VC(H)=d, then it suffices to take $O(d)$ many labelled examples $(x,c(x))$ in order to PAC learn $C$ by outputting a hypothesis in H.

My questions:
1) why do we need this H? In particular, isn't there a second layer of optimization going on; I could possibly pick a H which is the set of all functions, for which the VC(H) would be super large and that doesn't seem to tell us a good upper bound at all, so we need to find a H that includes $C$ but yet not too large. I lack intuition on what's going on here.

2) Is there a nice way to just talk about VC(C) and say, VC(C) many samples suffice to learn C?


texts:
In Provably Secure Steganography by Hopper, et al, we  have the following definition

Cryptographic notions

Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let $A$ be an oracle probabilistic adversary:

Define the $prf$-advantage of $A$ over $F$ as

$$Adv^{prf}_F(A)= | Pr_{K \leftarrow U(k), r\leftarrow \{0,1\}^*}[A_r^{F_k(.)}=1]- Pr_{g \leftarrow U(L,l), r\leftarrow \{0,1\}^*}[A_r^{g}=1] |.$$

where $r$ is the string of random bits used by adversary $A$. Define the insecurity of $F$ as

$$InSec^{prf}_{F}(t,q) = max_{A\in \mathcal{A}(t,q)} \{ Adv_F^{prf}(A)\}$$

where $U(k)$ is a uniform distribution over $k$ bits, $U(L,l)$ is a uniform distribution on functions from $\{0,1\}^L$ to $\{0,1\}^l$, and $F_K$ is a function $F_K:\{0,1\}^k\times\{0,1\}^L\to\{0,1\}^\ell$. But honestly, I don't know how I'm supposed to understand or parse the definition. Intuitively, I get the adversary $A$ is outputting $1$ if it decides that $F_K$ is not sufficiently different from a sample $r$ drawn from the channel distribution. But can someone walk me through, like I'm an idiot, as to what role each part of the definition plays in the overall mechanism of prf-advantage?

Link to paper: https://www.cs.cmu.edu/~biglou/PSS.pdf


texts: The natural proofs barrier of Razborov and Rudich states that under credible cryptographic assumptions one cannot hope to separate NP from P/poly by finding combinatorial properties of functions that are constructive, large, and useful.  There are several well-known results that manage to evade the barrier.  There are also several papers discussing possible loopholes to the three conditions, such as a result of Chow showing the barrier is sensitive to weak violations of largeness, and a recent paper of Chapman and Williams suggesting how to potentially avoid the barrier by relaxing the usefulness condition.  My question is whether there are any examples, or even the possibility, of avoiding the natural proofs barrier not by violating constructiveness, largeness, or usefulness, but by falling entirely outside its scope.  That is, it is not at all obvious to me why every potential method of proof should need to be based on finding combinatorial "properties" and then partitioning all functions into those that do and don't meet the property.  Why must this framework of operation apply to all possible proofs, and if it doesn't then what would other types of proofs look like?


texts:
Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.

For those that don't know about succinct data structures:

  Given a combinatorial structure, with
  a(n) distinct configurations, and a
  known "useful" representation $R(n)$.
  Is there a "succinct" data structure
  that takes storage of around
  $\lg(a(n))$ bits yet lets us perform
  operations as fast as we can with the
  normal representation $R$?

The top ones I am interested in if anyone would like to entertain a discussion

Suffix Arrays. They are a subset of all permutations.
Ordered Trees. They are a subset of all binary "parenthesis" strings (the matched variety).
All nearest smaller values, as in the paper (1). Not only can you compress in both dimensions; the allowable "smaller value" arrays in one direction are a small subset of lists $\{0,...,n-1\}^n$ , and thus you need to store less than $n \lg(n)$ bits.


texts: What is the motivation behind defining Deterministic Looping Automata?

texts:
I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it!

I believe they are strongly related to DBWs. And i would like to see how.

My intuition:
since we can assume W.l.o.g that each non-accepting state $q$ in a DBW $A$ has a loop of non-accepting states containing q. Maybe one can look at the $strongly$ $connected$ $components$ of $A_{rej}$, Where $A_{rej}$ denotes $A$ restricted to non-accepting states, as looping automata.

Relevant papers could help.

Note: i am new to research. In particular i have few knowledge about DBWs. Its more a reference than a question.

thanks.


texts:
Is there a formalization, which from a proof that a system includes enough arithmetic extracts an arithmetic sentence in the language of PA, which is not provable in the given system? Imagine the following, given representation of FOL+axioms of ZF, in let's say Coq/Agda, I can run the proof to obtain the independent sentence, of course after proving the assumptions on there existing enough arithmetic in ZF.
Is there such a variant for Coq in Coq?


texts: Streaming Algorithms: Motivations for estimating frequency moments

texts:
The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:

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

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

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

There have been more work in this area which have improved upon the results of this paper:

For $F_k$, there is a matching upper and lower bound of $n^{1−2/k}$ for $k>2$. The upper bounds are by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.

There has also been some related work on approximating $F_\alpha$ where $\alpha$ is not necessarily an integer. http://www.stat.cornell.edu/~li/SODA09_CC.pdf

This question talks about the improvements: Bounds on approximating frequency moments

My question is regarding the motivations of this line of work. The AMS paper talks about the application of $F_2$ to compute the surprise index, the moments give the skewness of the data which helps to select appropriate algorithm for data partitioning of a database. Other sources and papers mention applications in databases.

Other than these, is there any motivation for using these moment estimating algorithms in statistics? What I am thinking about is how relevant is this line of work to the statistics community?
I was presuming a scenario that these moments may be useful to compute some statistic of the data for some statistical estmation or test of hypothesis, but if they use higher moments like k>6, the linear lower bounds on space motivate the approximation of such statistic using only lower moments or formulation of different statistic that uses only lower moments which can be computed in sublinear space. But, I am not aware of such scenario and couldnt find one. Can you please help me find?

[Though not sure, I presume using estimates of these moments,  one can also approximate central moments. Please comment and correct me on this as well.]

Also, if you add any motvation not mentioned here, it will be heplful.
Please dont hesitate to improve my question.


texts:
I have a question about page 9 in Proofs and Types.

The given $\rightarrow$Introduction rule says that $A \rightarrow B$ can be deduced from $B$ if the deduction of $B$ contains an arbitrary number of $A$s (0 or more).  How can this be true if there are zero $A$s in the deduction of $B$?


texts: What are the consequences of $L = \oplus L$?

texts:
Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard.  Informally, my question is, "How hard is that?"

We know that nonuniformly $NL \subseteq \oplus L$, see the answers to this question.  We also know that it is unlikely that $\oplus L = P$, see the answers to this question.  How surprising would it be if $L=\oplus L$?  I have heard many people say that $L=NL$ would not be shocking the way $P=NP$ would.

  What are the consequences of $L=\oplus L$?

Definition: $\oplus L$ is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space.


texts:
Let me define the following "grammar":

$$A_0 \leftarrow 1$$

$$A_{i+1} \leftarrow A_i \mid A_i \  K_{i+1} \mid A_i \ K_{i+1} \ A_i$$

where $1$ and $K_i$ are terminals (infinite amount of them: $K_1, K_2, \dots$ ), $A_0, A_1, \dots$ are non-terminals, $\mid$ means alternative, $\leftarrow$ defines a non-terminal, $i$ is an integer such that $i \geq 0$.

That is, it looks like a grammar composed of an infinite number of rules and terminals.

My questions are:

can I call such a construction a "grammar"?
in which grammar category can I include it?
have such structures been studied before, can anyone give links or bibliographic references?

Thanks a lot.


texts:
The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:

Instance:

  A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-1}$), each of which consisting of a finite sequence of Read and Write operations on multiple shared variables in program order.

  An important restriction here is that all the Read operations are on the process $p_0$.

Example:

   The above figure gives a trace example. Here, $W$ is for Write operation, and $R$ is for Read operation. $Wx1$ means updating the shared variable $x$ to 1. $Ry3$ means reading the shared variable $y$ and returning 3.

Problem:

  Is there some schedule (i.e., a sequence) of all the operations such that:

  the program order between operations is maintained;
  in the schedule, each Read should read the value from the latest preceding Write on the same variable.

Example (Cont.):

  For example, the trace in the above figure can be scheduled as follows:
  $$Wx1(p_1), Wx1(p_0), Rx1, Wx2(p_1), Wy3, Ry3, Wx2(p_0), Wx1(p_3), Rx1.$$

Now, I want to study the complexity issue of this decision problem. Specifically, is this decision problem NP-hard?


texts: Minimum amount of colors preventing an equilateral uniformly colored subtriangle

texts:
In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem:

For fixed $n$, find a minimal $k$ and a map  $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.

Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

In fact they asked for a reasonably small $k$ for $n=1000$ and in the solution (written in german) they noted that a greedy approach yields a coloring with $27$ colors for $n=1000$, which can be reduced to $15$ by randomizing colors until a valid solution is found.

I am interested into exact solutions (for smaller $n$). The solution says that backtracking yields that $2$ colors are sufficient for $n\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, where backtracking is already really slow for $n=17$.

First I tried to use an ILP formulation and Gurobi to get some results for $n>17$, but it was too slow (already for $n=17$). Then I used a SAT solver, because I noticed that there is a straight forward formulation as a SAT-instance.

With that approach I was able to generate a solution with $3$ colors for $n=18$ within $10$ minutes:

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

But to decide if $3$ colors suffice for $n=19$ it is already too slow. Is there some different approach that gives exact solutions for $n \geq 19$? Certainly we can't expect a polynomial algorithm.


texts:
While trying to prove some basic properties using coinductive types in Coq, I keep running into the following problem and I cannot get around it. I've distilled the problem into a simple Coq script as follows.

The type Tree defines possibly infinite trees with branches labelled with elements of type A. A branch need not be defined for all elements of A. The value Univ is the infinite tree with all A branches always defined. isUniv tests whether a given tree is equal to the Univ. The lemma states that Univ does indeed satisfy isUniv.

Parameter A : Set.

CoInductive Tree: Set := Node : (A -> option Tree) -> Tree.

Definition derv (a : A) (t: Tree): option Tree :=
  match t with Node f => f a end.

CoFixpoint Univ : Tree := Node (fun _ => Some Univ).

CoInductive isUniv : Tree -> Prop :=
  isuniv : forall (nf : A -> option Tree) (a : A) (t : Tree),
    nf a = Some t ->
    isUniv t ->
    isUniv (Node nf).

Lemma UnivIsUniv : isUniv Univ.
Proof.
  cofix CH.    (* this application of cofix is fine *)
  unfold Univ.

Admitted.

At this point I give up the proof. The current goal is:

CH : isUniv Univ
============================
isUniv (cofix Univ  : Tree := Node (fun _ : A => Some Univ))

I do not know which tactic to apply to eliminate the cofix in the goal to produce (Node something) so that I can apply isuniv.

Can anyone help prove this lemma?
What are the standard ways of eliminating cofix in such a situation?


texts: Constructing all digraphs without repetitions

texts:
I am interested in an algorithm that allows me to construct all inequivalent (non-isomorpic) digraphs of size n with self-loops allowed. For example, the output should look like this:

Even though it is trivial to simply construct all such digraphs, I believe that the requirement that non-isomorphic graphs should appear only once makes the problem very difficult. Of course, we can always construct all of them and drop the duplicates but this approach is too slow. Ideally I would like an algorithm that just creates the inequivalent ones by construction.

Does such a thing exist? Any ideas or references would be most welcome.
Descriptions of the algorithm either in a diagrammatic form or in terms of adjacency matrices are equally acceptable. Thanks in advance!


texts: Embedding distortion under group quotient

texts:
The high level question is as follows:  Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$.  Under what condition does the quotient of the group by a (normal) subgroup inherit this low-distortion embedding?

Formally:
Let $G$ be a group with a Cayley graph ${\cal G} = Cay(G,S)$ for some generator set $S\subseteq G$, that can be embedded into the hypercube $\mathbf{F}_2^n$ with low-distortion, i.e. there exists $i: G \hookrightarrow \mathbf{F}_2^n$
such that for any $x,y\in V({\cal G})$,
$\frac{1}{c} d_{\cal G}(x,y) \leq \Delta(i(x),i(y))\leq c d_{\cal G}(x,y)$,
where $\Delta(a,b)$ is the Hamming distance between $a,b\in \mathbf{F}_2^n$,
and $d_{\cal G}(x,y)$ is the length of a shortest path connecting $x,y$ in ${\cal G}$.

Suppose now that $N\subseteq G$ is a (normal) subgroup of $G$.
Is there a choice of generators $S_N\subseteq G / N$, for which the quotient group $G/N$ has a low-distortion embedding into $l_1$ as well ?


texts:
I've been reading the Handbook of Model Checking recently; I'm especially interested in probabilistic model checking, so have been led to the PRISM model checker. For background, I am very familiar with TLA+ and use of its model checker for safety & liveness properties. My goal is to specify & model-check a simple probabilistic consensus protocol like snowflake (pdf).

One thing which confuses me is the difference between Markov Decision Problems (MDPs), Discrete-Time Markov Chains (DTMCs), and Continuous-Time Markov Chains (CTMCs). I'd assumed probabilistic model-checking was just a way of assigning weights to nondeterministic steps; things like network messages being dropped, nodes crashing, random choice of nodes to send messages to, that sort of thing. Why are these different models necessary? What can you express in one but not the other?

I see on this page the documentation says:

  In every state of the model, there is a set of commands (belonging to any of the modules) which are enabled, i.e. whose guards are satisfied in that state. The choice between which command is performed (i.e. the scheduling) depends on the model type.

But aren't we model-checking it in some way where it doesn't matter which action is "performed", since both possible transitions are checked via some breadth-first search mechanism?


texts: Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

texts:
The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and  $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $.

I wonder the following statement holds.

  $ $    $\#\mathsf{P} \subseteq \mathsf{FP}^{\mathsf{PH}}$

If we prove this statement, $\# \mathsf{P}$ and $\mathsf{PH}$, that is, counting and alternation are $roughly$ $equivalent$ classes.


texts: What is the best text of computation theory/theory of computation?

texts:
In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression.  I borrowed that book and don't have one in my collection, so I need one.  So to the question, are there are any other books which could be seen as better and possibly more complete?

I didn't see a community wiki section here, so I couldn't note it as such.


texts: Testing for satisfiability of a system of linear equations over GF(2)

texts:
Consider a  system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$.

Is it easier to check satisfiability of the system without finding a specific solution $x$, in terms of time complexity? (A solution can be found in matrix multiplication time.)


texts: Is predicting (in the limit) computable sequences as hard as the halting problem?

texts:
Question:
Is predicting (as defined below) computable sequences as hard as the halting problem?

Elaboration:
"Predict" means successfully predict, which means make only finitely many errors on the task of trying to predict the n-th bit of the sequence given access to the previous n-1 bits (starting from the first bit and going through the entire infinite computable sequence).

There's a simple diagonalization argument (due to Legg 2006) that for any Turing machine predictor p, there's a computable sequence on which it makes infinitely many errors. (Construct a sequence that has as its nth term the opposite of what p predicts given the previous n-1 terms in the sequence.) So there is no computable predictor that predicts every computable sequence. A halting oracle would allow construction of such a predictor. But can you show that having such a predictor allows you to solve the halting problem?

More elaboration

Definition (Legg)
A predictor p is a Turing machine that tries to predict the n-th bit of a sequence S given access to the previous n-1 bits. If the prediction fails to match the n-th bit of the sequence, we call this a mistake. We will say that p predicts S if p only makes finitely many mistakes on S. In other words, p predicts S if there is some number M in the sequence s.t. for every m>M, p correctly predicts the m-th bit of S given access to the first m-1 bits.

Formally, we could define a predictor machine as having three tapes. The sequence is entered as input bit-by-bit on one tape, the predictions for the next bit are made on a second tape (the machine can only move right across this tape), and then there is a work tape on which the machine can move in both directions.

Simple results
By the above definition, there's a predictor that predicts all the rational numbers. (Use the standard zig-zag enumeration of the rationals. Start by predicting the 1st rational in the list, if there's a mistake, move to the next rational.). By a similar argument, there's a predictor s.t. given access to N, is able to predict all sequences of Kolomogorov complexity less than or equal to N. (Run all the N-bit machines in parallel and take the prediction of the machine that halts first. You can only make finitely many errors).

Citation
Shane Legg 2006
http://www.vetta.org/documents/IDSIA-12-06-1.pdf
(not the author of this post)


texts: Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?

texts: Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ complete $k_i$-partite graphs, where $p$ is finite (of course) and each vertex appears at most a constant number of times, satifying " the sum of such $p$ complete $k_i$-partite graphs is $G$ " ?  Moreover, such construction can be done in poly-time ?


texts: Base extension in residue number systems with low space

texts:
Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes if it helps).

I would like to compute $x \bmod{p^*}$ for some $p^* \not\in \{p_1, \ldots, p_m\}$, but with low space.

Of course I could reconstruct $x$ itself, but this would require $\log (\prod_i p_i) = \sum_i \log p_i$ bits of working space. Rather, I would like the computation to use something more like $\max_i \log p_i$ bits of space. Is this possible?

As a concrete example, suppose $\{ p_1, \ldots, p_m\}$ are the first $m$ primes and I would like to compute $x \bmod 4$. Or $\{ p_1, \ldots, p_m\}$ are the first $m$ odd primes, and I would like to compute $x \bmod 2$.


texts: I've just completed a short (5 page) paper on proving a certain combinatorial game NP-Complete. This is in no way a result of huge significance, yet it's one that I believe is publishable. What venues would be good for a paper like this? The only one I'm aware of is Information Processing Letters; are there other ones like this?


texts:
The maximum sum subarray problem involves finding a contiguous subarray with the largest sum, within a given one-dimensional array $A[1...n]$ of numbers. Formally, the task is to find indices i and j with $1<=i<=j<=n$ s.t. the sum $\sum_{x=i}^j A[x]$ is as large as possible.
It is well-known that this problem can be solved in linear time $O(n)$.
I'm trying to solve a variation of this particular problem. In addition to array $A[1...n]$ we are also given an array $W[1...n]$ where $W[i]$ gives the weight of the ith item. The items are ordered in increasing weight, so $W[i] \leq W[j]$ if $i<j$. Moreover, all values in $W$ and $A$ are larger than 0, and $A[i] \geq W[i]$ for all $i=1...n$. Objective: find a contiguous subarray that maximizes $\sum_{x=i}^j (A[x]-W[j])$.
Here's a numerical example
i  W  A
1  6  14
2  7  12
3  8  10
4  9  10
5  12 18
6  13 16
7  14 25
8  18 22
9  19 26
10 20 23

The solution to the above example would be: i=5, j=7, with a score of: $A[5]-W[7]+A[6]-W[7]+A[7]-W[7]=18-14+16-14+25-14=17$
To solve this problem, I came up with the following $O(n²)$ algorithm:
best_score= -1
best_i = best_j = -1

for j=n..1:
  score=0
  for i=j..1:
    score=score + A[i]-W[j];

    if score > best_score:
      best_score=score
      best_i = i;
      best_j = j;
    if score < 0:
      continue; //skip inner loop and continue with outer loop

Can this problem be solved more efficiently than O(n²)? In particular, can you prune part of the search by using the best score you found thus far?


texts: Can affine lambda calculus solve every problem in P?

texts:
In Advanced Topics in Types and Programming Languages it is mentioned, in the chapter on sub-structural type systems, that a "carefully crafted" affine lambda calculus with a recursion combinator for lists can only type terms which have polynomial running time (it does not present the proof due to complexity). This would be super interesting if we could also solve every problem in P. I could try to find a solution to a P-complete problem using the calculus presented by I'm not sure this would actually prove anything. It doesn't seem to me to mean that it can preform all the reductions necessary to use a solution to a P-complete problem (although it sure does seem likely).

If an affine lambda calculus is not known to be able to solve exactly the problems in P, is there any known calculus that can solve exactly the problems in P?


texts: CNF encoding of set cover - NExpTime-completness

texts:
Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.
I suspect that the following problem is NExpTime-complete:
-given two CNF formulas $A(X)$ and $B(Y,X)$, and an integer $K=2^k$, determine if there exist $K$ valuations $v_1,v_2,...,v_K : Y \to {0,1}$ such that $[A(X)] \subseteq \bigcup_{v=v_1,v_2,...,v_K} [B(Y/v,X)]$, i.e. are there K valuations of the variables in Y such that all the valuations that makes $A(X)$ true are covered by valuations that makes $B(Y/v,X)$ true.
So this can be seen as a succinct encoding of the set cover problem using CNF formulas. My guess is that this result should be a consequence of the NP completness of set cover and some general results about succinct encodings of problems using CNF formulas. Unfortunately, I was not able to locate such a result in the literature...


texts: the number of rational points of a curve modulo 2

texts: Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written as $\sum a_{ij} x^i y^j. $)


texts: Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions?

texts:
Possible Duplicates:
  Do many-one reductions and Turing reductions define the same class NPC
  Many-one reductions vs. Turing reductions to define NPC

Let $P,Q \subseteq \Sigma^*$ be languages such that $P$ and $Q$ are both in NP. Assume that $P$ is NP-complete under Karp reductions (there is a polynomial time many-one reduction from 3-SAT to $P$) and there is a Turing-reduction from $P$ to $Q$, i.e. there is a polynomial-time algorithm which decides $P$ when given oracle-access to $Q$. Intuitively this means that deciding $Q$ is as hard as deciding any problem in NP, while at the same time $Q$ is in NP, so Q cannot be ``harder'' than NP. Does this imply that $Q$ is NP-complete under Karp reductions, i.e. does this imply the existence of a polynomial-time many-one reduction from 3-SAT to Q? Any pointers are much appreciated.


texts: how to cover a set in a grid with as few rectangles as possible

texts:
In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate.  To get sufficient precision, how many rectangles are needed if the shape of the set is close to a rectangle?   I formalize the discrete version of the problem as follows.

Suppose we have a $N\times N$ grid (I assume it is a $N$ rows of squares, each row contains $N$ squares), and a set, say $S$, contains at least $r N^2$ squares, $r<1$. Now we wanna cover $S$ using rectangles approximately. (Pick several rows and several columns, all the crossing squares form a retangle)  The requirements are

1) all rectangles are disjoint with each other.

2) The number of misplaced squares (i.e. the squares outside $S$ but covered and the squares in $S$ but not covered) $\leq\epsilon |S|$, where $\epsilon$ is considered to be a small positive constant.
Question is how many rectangles are sufficient.

My guess is $poly(\frac{1}{r})$.


texts: Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

texts:
I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:

  Problem. For a given system of $m$ linear equations in $n$ unknowns modulo $k$, do there exist any solutions?

In the abstract to their paper Structure and importance of logspace-MOD classes on the classes ModkL,  Buntrock, Damm, Hertrampf, and Meinel claim that they  "demonstrate their significance by proving that all standard problems of linear algebra over the finite rings $\mathbb Z/k\mathbb Z$ are complete for these classes". On closer inspection, the story is more complicated. For instance, Buntrock et al. show (by a proof-sketch in an earlier and freely accessible draft found by Kaveh, thanks!) that solving systems of linear equations is instead in the complementary class coModkL, for k prime. This class is not known to be equal to ModkL for k composite, but never mind that — what I'm concerned about is the fact that they don't make any remarks about whether solving systems of linear equations mod k is even contained in coModkL for k composite!

  Question: Is solving systems of linear equations modulo k contained in coModkL for all positive k?

If you can solve systems of equations modulo a higher power q of a prime p, you can solve them modulo p as well; so solving systems of equations modulo q is coModpL-hard. If you could show that this problem is in ModqL, you would end up showing ModkL = coModkL for all k. That's likely to be difficult to prove. But is it in  coModkL?


texts: Natural graph class with five excluded subgraphs?

texts: I'm interested in hereditary graph classes characterized by a small number of excluded subgraphs. There are some well-known graph classes that are characterized by three or four obstructions -- examples are threshold graphs, chain grapns and trivially perfect graphs. My question is: are there natural graph classes characterized by five obstructions? (No relation to the eponymous movie). It may be possible to obtain some by considering the P4-structure of the graph.


texts: Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

texts:
Let $G=(V,E)$ be a graph.
Let $m(G)=|E|$ and $n(G)=|V|$.
There are two different density definitions for $G$:
$$d_1(G)=\frac{m(G)}{n(G)}$$
and
$$d_2(G)=\frac{m(G)}{n(G)-1}.$$
Let $H^* \subseteq G$ be a subgraph of $G$ such that
$$d_1 (H^*)\geq d_1 (H)$$
for any subgraph $H\subseteq G$.
My question is:
Is it true that for any subgraph $H\subseteq G$ we still have
$$d_2 (H^*)\geq d_2 (H)?$$
Any comment is welcome!
Update 1:
J.G showed that the statement is NOT TRUE by providing a counterexample.

Consider two disjoint triangles connected by a single edge. Without checking too formally, $^*$ is the full graph with value $7/6$ under the first definition, but either of the triangles has value $3/2$ under the second definition while the full graph only has value $7/5$.

Update 2:
I found that a maximum density subgraph (with the definition $d_1(G)=\frac{m(G)}{n(G)}$) can be found efficiently by using algorithms provided in references:

A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, University of California at Berkeley, 1984.
G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM Journal on Computing, 18(1):30–55, 1989.

However, I didn't find any reference for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$).
As pointed by J.G, a maximum $d_1$-density subgraph may not be a maximum $d_2$-density subgraph.
My new question is:
Is there any efficient algorithm for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$)?


texts:
I was wondering, is the bitonic sort algorithm stable? I searched the original paper, wikipedia and some tutorials, could not find it.

It seems to me that it should be, as it is composed of merge / sort steps, however was unable to find answer anywhere.

The reason why I'm asking - I was comparing this particular implementation of bitonic sort to the sort implemented in the C++ standard library, for array length 9 it requires 28 comparison / swap operations, while the standard library sort (which is unstable) requires 25. The three extra cswaps do not seem enough to make the sort stable.


texts: Maximum rows to partially distinguish all the columns

texts:
This is a problem I met in my work. I thought about it for about two weeks, no result. I don't know whether it has been studied before by others?

Problem Description: Given an $m\times n$ matrix $M$ with entries valued 0 or 1. Let $r_i$ denote the $i^{th}$ row,
$c_i$ denote the $i^{th}$ column and $t_{ij}$ denote the entry in the $i^{th}$ row and $j^{th}$ column. Find a $k \times n$ submatrix $A$ of $M$, such that in $A$
\begin{equation}
\forall_{r_i}{ \exists_{c_a,c_b}{ \forall_{r_j \ne r_i}{\left(  t_{ia} \ne t_{ib} \land t_{ja} = t_{jb} \right) } } }.
\end{equation}
$k$ is the parameter

The selected rows satisfy the following condition: For each row $r_i$, there exist two columns $c_a, c_b$, such that entries of the two columns at row $i$ are different, and at the remaining rows are the same.

Could someone give me any reference for it, if it has been studied before ? Thank you very much.

At first, I thought it was a special case of Minimum Test Set problem, however, it turns out not.


texts: Trivial upper bound for distribution testing

texts:
There is an obvious algorithm that tests any property of most discrete distributions. This algorithm works by learning the distribution. This is done by just learning the histogram for enough number of samples. In particular, I have the following analysis,
Let $p_x$ be the probability of item $x$ and $m_x$ be the number of occurrences of $x$ in $m$ samples. Then by Chernoff's bound, $Pr(|\frac{m_x}{m}-p_x|>\epsilon)<2.\exp(-2m\epsilon^2)$. Taking union bound over all $x$ in the sample space we can get $Pr(\sum_x|\frac{m_x}{m}-p_x|>\epsilon|\Omega|)<2|\Omega|\exp(-2m\epsilon^2)$. Scaling down $\epsilon$ by a factor of $|\Omega|$, we get $O(\ln |\Omega|\frac{|\Omega|^2}{\epsilon^2})$ samples are enough.

It seems there are folklore algorithm to do this in $O(\ln |\Omega|\frac{|\Omega|}{\epsilon^2})$ as well as in $O(\frac{|\Omega|}{\epsilon^2})$ samples. But I am unable to prove it. A similar question was asked here: Are there distribution properties which are "maximally" hard to test?


texts:
Let $S$ be a finite set. Following Lovasz (Matroid matching and some applications), let us define a polymatroid function over $S$ as a function $f : 2^S \rightarrow \mathbb{N}$ such that

(1) $f(\emptyset) = 0$,

(2) $X \subseteq Y \Rightarrow f(X) \leq f(Y)$,

(3) $f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)$.

The function $f$ defines a 2-polymatroid if $f({x}) \leq 2$ for every $x \in S$. My question is as follows: given two such functions $f,g$ over the same set $S$, and given two integers $r,s$, what is the complexity of counting sets $Z \subseteq S$ such that $f(Z) = r$ and $g(Z) = s$?

The $\# \mathsf{P}$-hardness of this problem is not clear to me, if by chance it was in $\mathsf{P}$ it would have some interesting consequences. Indeed, it encompasses natural problems such as counting the number of $k$-vertex trees in a graph, which complexity is open afaik.


texts:
Let $K=\frac{\mathbb{Q}[x]}{<f(x)>}$ where $f(x)$ is irreducible over $\mathbb{Q}$ and has even degree. I want to find $K_2$ such that $ \mathbb{Q} \subseteq K_2\subseteq K$ and $[K_2:\mathbb{Q}]=2$.

If K is a cyclic Galois extension over $\mathbb{Q}$ then discriminant of $f(x)$ solves the problem.

But what if $K$ is not a cyclic galois extension?

Or even particular when $K$ is not even a Galois extension.


texts:
See Translating SAT to HornSAT

It says in that post that it is impossible to translate SAT into HORNSAT. But it is known that HORNSAT is P-complete, so any language in P can be translated into HORNSAT. Then if it is impossible to translate SAT, which is in NP, into HORNSAT, then wouldn't this imply that P is not NP? What am I missing?