texts: What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?

texts:
A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,

A  0  0  0

0  0  0  0

0  0  C  D

What are some effective heuristics that could be applied to find them - and particularly, techniques to trim/discard paths along the way?

Edit: Just to clarify, the edges are formed when elements are connected horizontally and vertically, but not diagonally. The problem also states that any element that is marked 0 can be used to form a path, but non 0 elements are "obstacles" that need to be avoided.

A-0-0-0
      |
0-0-0-0
|
0-0-C D

could be one path, for instance. Another may be,

A 0-0-0
| |   |
0 0 0-0
| | |
0-0 C D


texts: NP complete graph problems about structural properties

texts:
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.
An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.
Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.


texts: Is there a book/survey-paper outlining language class hierarchies, closure properties, etc

texts:
I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack counter machines, deterministic CFLs, etc.

I'm wondering if anybody knows of a good book or survey paper which outlines the properties of these languages. Most of what I'm looking at is too obscure or too new to be in my Hopcroft-Ullman book, even the 1979 edition.

Mainly I'm looking for which language classes are contained in one-another, the closure properties of these languages, and the decidability of basic problems (F-problems) on these languages.

Some example of things I'd look up in this reference:

Are all languages accepted by Reversal-bounded Multi-counter machines also accepted by non-reversal-bounded single counter machines?
Are the deterministic reversal-bounded MultiCounter languages closed under left and right concatenation?
Is universality decidable for single-counter machines.

These are just example questions, I have many others that come up in my day-to-day work.

As a starting point, I've tried tracing which papers cite Oscar Ibarra's  "Reversal-Bounded Multicounter Machines and Their Decision Problems", but haven't found much.


texts: Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

texts:
According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has linear-size circuits.) Note that it implies $\mathsf{P}\neq \mathsf{NP}$.

Kolmogorov's  conjecture, however, is viewed likely to fail. For example, Ryan Williams writes in a recent paper: "The conjecture would be surprising, if true. For languages in $\mathsf{P}$ requiring $n^{100^{100}}$
time, it appears unlikely that the complexity of such problems would magically
shrink to $O(n)$ size, merely because a different circuit can be designed for each
input length."

On the other hand, Andrey Kolmogorov (1903-1987) is widely recognized as one of the leading mathematicians of the 20th century. It is rather hard to imagine that he would have proposed a completely absurd conjecture. Therefore, to understand it better, I tried to find some arguments that might actually support his surprising guess. Here is what I could think up:

Assume $\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$. Then we can pick a language $L\in \mathsf{P}$, such that $L$ has superlinear complexity both in the uniform and in the non-uniform model. There are then two possibilities:

There is a known  explicit algorithm (Turing machine) that accepts $L$. From this we can construct an explicit function family that must have superlinear circuit complexity. However, this may be viewed  unlikely, since no one has been able to find such an example in more than 60 years of intense research on circuits.
There is no known explicit algorithm for $L$. For example, its existence is proved via non-constructive means, such as the Axiom of Choice. Or, even if the explicit algorithm exists, no one has been able to find it. Given, however, that there are infinitely many languages that can play the role of $L$, it is unlikely again that they all behave in this unfriendly way.

But then, if we dismiss both options as unlikely, the only remaining possibility is that such an $L$ does not exist. That means  $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$, which is precisely Kolmogorov's conjecture.

  Question: Can you think of any further argument for/against Kolmogorov's conjecture?


texts: Computing the class number using the prime factorization of the discriminant

texts:
i was wondering if there is a way to use the prime factorization of the discriminant $d$ when computing the class number $h(d)$. E.g., assume you have an integer $n = pq$ with $p \equiv 1\pmod{4}$ and $q \equiv 3\pmod{4}$, with known primes $p$ and $q$ and the imaginary quadratic field $\mathbb{Q}(\sqrt{-n})$. Then $d  = -n = -pq$ and you want to compute $h(d)$. Do there exists an algorithm the uses the knowledge of $p$ and $q$ or the class numbers $\mathbb{Q}(\sqrt{-p})$ and $\mathbb{Q}(\sqrt{-q})$ to compute the class number $h(d)$?

There is an answer to a complexity question on mathoverflow from 2013, which at least indicates that the best known algorithm ($\mathcal{O}(D^{1/4+\epsilon})$ with GRH or $\mathcal{O}(D^{1/2+\epsilon})$ without GRH) does not utilize this.

Regards,
Etsch


texts: Complexity: simulated annealing vs. quantum annealing

texts:
How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?

In Convergence theorems for quantum annealing by Morita and Nishimori, it has been shown that QA performs better than SA. Let's me quote from the Discussion section:

  We have proved strong ergodicity of the inhomogeneous Markov chains
  associated with Quantum Annealing using both Path Integral Monte Carlo
  and Green's Function Monte Carlo methods, mainly with the application
  to the Transverse Field Ising Model in mind, which covers a wide range
  of combinatorial optimization problems. Our proof is quite general in
  the sense that it does not depend on the spatial dimensionality or the
  lattice structure of the system. The convergence of QA is guaranteed
  if the transverse field decreases as $\Gamma(t) \approx
 \frac{const}{t^c}$ asymptotically. This annealing schedule for the
  transverse field is faster than the temperature-annealing schedule,
  the log-inverse law, found by Geman and Geman for Simulated Annealing.

Does this result settle the question of the performances for Simulated vs. Quantum annealings? I have a feeling that we should put a little more context here.

I assume to settle the question we need to find a quantum annealing schedule which is faster than all simulated annealing schedules. The problem can be reduced to finding a quantum annealing schedule which is faster than the fastest simulated annealing schedule. Now, to me, the fastest simulated annealing schedule makes sense only when we know what optimization problem we are talking about. We cannot find the fastest simulated annealing schedule for all conceivable optimization problems. That just doesn't make sense to me.

So, is the performance comparison between SA and QA settled? Is yes, how? If no, how can we do it?


texts: What is First-Order Rewritable (and FO-Query)?

texts:
I just wonder what FO Rewritable is, put an example to make it clearer for me. Also, I heard that a language that is FO Rewritable is very good, in what sense?

It is said as follow:

  A class C of TGDs is ﬁrst-order rewritable (or FO-rewritable) iff for every set of TGDs $\Sigma$ in C, and for every BCQ Q, there exists a ﬁrst-order query $Q_\Sigma$ such that for every database
  instance D, it holds $D\cup\Sigma\models Q$ iff $D\models Q_\Sigma$.

Since answering ﬁrst-order queries is in the class $\textrm{AC}_0$ in the data complexity, it immediately follows that for FO-rewritable TGDs, BCQ answering is in $\textrm{AC}_0$ in the data complexity.

Then my question can be extended into, what is a first-order query?

Link to the paper: http://portal.acm.org/citation.cfm?doid=1514894.1514897


texts: Splay tree potential function: why sum the logs of the sizes?

texts:
I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data structure. However, I cannot seem to find a solid intuition for the potential function that Sleator and Tarjan use in their analysis.

The analysis works by assigning each element in the tree an arbitrary weight $w_i$, then setting the size $s(x)$ of a node to be the sum of the weights of the nodes in the subtree rooted at $x$. They then take the log of this value to get the rank $r(x)$ of the node, so $r(x) = \log s(x)$. Finally, the potential function of the tree is defined as the sum of the ranks of all the nodes.

I understand that this potential function works correctly and I can follow the analysis, but I don't see why they would choose this potential. The idea of assigning a size to each node makes sense to me, since if you sum up the sizes, you get the weighted path length of the tree. However, I can't figure out why they decided to take the logs of the weights and then sum those up instead - I don't see any natural property of the tree that this corresponds to.

Does the potential function of the splay tree correspond to some natural property of the tree? Is there a particular reason, other than "it works," that they would choose this potential? (I'm specifically curious because this set of course notes mentions that the "analysis is black magic. [N]o idea how discovered")

Thanks!


texts: Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

texts:
I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such that the obvious greedy algorithm finds a clique of size $C_p \log n$ in $G(n,p)$ almost surely, then any results on finding a clique of size $(C_p + \epsilon ) \log n$ would be even better.

In particular, I am interested in whether we know how to find a $(C_p +\epsilon)\log n$ clique in $G(n,p)$ using $O(n^{\epsilon^2\log n})$ time and $O(n^{\epsilon^2\log n})$  space. Would a randomized algorithm that finds a $(C_p +\epsilon)\log n$ vertex clique with high probability under these time and space constraints constitute a publishable result? Any pointers to relevant literature would be greatly appreciated.


texts: Is any computational problem a search problem?

texts:
I was looking for a formal and general definition of a computational problem (and major subclasses thereof e.g. decision, function and search problems). But, given the definitions I have found thus far, I fail to see how the definition of a 'search problem' is any less general than that of a general 'computational problem', as both seem to correspond to an arbitrary binary relationship.

Concretely,

I have found the following definitions of a computational problem:

[source: http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf]

  In a computational problem, we are given an input and we want to
  return as output a solution satisfying some property: A computational
  problem is then described by the property that the output has to
  satisfy given the input.

[source: https://en.wikipedia.org/wiki/Computational_problem]

  A computational problem can be viewed as an infinite collection of
  instances together with a solution for every instance.

I interpret both to imply that a computational problem corresponds to a relation $R \subseteq X \times Y$ between (representations of) problem instances $X$ and (representations of) solutions $Y$.

Under this definition, the subclasses of decision (Y={yes,no}) and function problems (R is a function) make sense.

However, the definitions of a search problem (in the same articles) confuse me, as they seem to be equivalent:

[source: cs.stanford.edu]

  Thus, a search problem is specified by a relation $R \subseteq\{0,1\}^∗\times\{0,1\}^∗$.

[source: wikipedia.org]

  a search problem is a type of computational problem represented by a
  binary relation

[EDIT]

After some reflection, one candidate for being more general than search problems would be optimization problems that do not have to be solved optimally (otherwise they would reduce to 'finding an optimal solution', i.e. a search problem), as they, besides capturing the 'desirability' of a solution, also capture the'desirability' thereof (some preference relation on Y), a concept not corresponding to any $R \in X \times Y$.

In general, I would answer my own question as follows:
As long as you think of problems in terms of 'acceptable' outputs given inputs, we're dealing with search problems by definition.
Once we need to a more subtle ('fuzzy')/general notion than 'acceptability', such as 'desirability' (e.g. non-exact optimization problem above) a binary relation does no longer suffice.

Is this reasoning sound?

Also, do you know of any sources I can cite (beyond wikipedia, PlanetMath and handouts...) for definitions of 'computational problem' and 'search problem'?


texts: Max weight travel on a graph with deadline

texts:
Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we want to find a path $P$ so that $\sum_{e \in P}l(e) \le D$ and $\sum_{e \in P} w(e)$ is maximized.

Questions:

This problem can be solved using a pseudo polynomial algorithm by iterating over time $t=1,\cdots,D$.
Let $S_{v,t}$ be the weight of the optimal path until time $t$ ending at vertex $v$.
$$
S_{v,t}=\max(\max_u S_{u,t-l(e_{uv})},S_{v,t-1})
$$
Therefore, it seems a (weakly) NP-hard problem to me, but I have no proof for it yet. Do you have any idea?
In a more complicated version of the problem, the path can visit each vertex $v$ and each edge $e$ at most $h(v)$ and $h(e)$ times. The above algorithm does not work for this constraint version of the problem. Any better solution?

The problem can be modeled using ILP:
$$
\begin{align}
{\tt Maximize} \quad & \sum_i \sum_j w(e_{ij}) X_{ij} \\
&\sum_i \sum_j l(e_{ij}) X_{ij} \le D \\
& \sum_i X_{i0} = \sum_j X_{0j} = 1\\
& \sum_i X_{iv} = \sum_j X_{vj}, \quad {\tt for \; all \;} v = 1,\cdots,n
\end{align}
$$

Where $X_{ij}$ denotes the number of times the path goes through edge $e_{ij}$.
The first constraint enforces the deadline and the last two are the conservation law (number of times entering a node is the same as the number of times exiting it). $v_0$ is a virtual node that traveling to/from it has zero weight and zero time.

In the more complicated version of the problem,
we have the following additional constraints:
$$
X_{ij} \le h(e_{ij})
$$
$$
\sum_i X_{iv} \le h(v) \quad {\tt for \; all \; }v
$$


texts:
I am a physicist working in TCS in a new group. I would like to know, given a conference (imagine your favorite ones),  how can I know the quality of this conference and also the quality of the journal where the proceedings will be pusblished (in case they are). I heard something about CORE classification but found no link or more information about. Thanks

P.S.: I find TCS stack exchange very interesting for TCS discussions (obviously). I just wonder if there is any similar stack exchange academic site for physics/chemistry. I found physics.stackexchange, but some questions related with journals were instantly classified as offtopic


texts: Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

texts:
Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x(j)$ consecutive time-slots (the $j$th idle period), then a penalty of $p(j)=\lfloor x(j)/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties $p(j)$ (over idle periods $j$). There is one constraint: the budget $B$ of the machine should be respected.
I am trying to find an optimal online algorithm for the online version of this problem, i.e., at time-slot $t$, we only know the budget $B$, the set of $t$ time-slots, and the costs $c(1), c(2), \ldots, c(t)$ for all $i$.
Can you suggest a way to solve this online problem? Do you see any similarities with other online problems in the literature so I may use to start solving my problem?
Note that an offline version of this problem with incremental budget has a dynamic programming (DP) solution as shown here.
After analyzing the DP solution, I found that the optimal value of the problem can be found in an online fashion. In other words, as we construct the DP table $M(t,p)$, we calculate  $\min\{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$. At the last slot, we can found the least value and that would be the optimal number of truncated gaps. However, the optimal solution, the actual scheduling of the job in each slot, cannot be found in an online fashion using the DP solution.


texts: A natural problem in $\textrm{S}_2^\textrm{P}$?

texts:
The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from Wikipedia):

  A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that

  If $x \in L$, then there exists a $y$ such that for all $z$, $P(x,y,z)=1$
  If $x \notin L$, then there exists a $z$ such that for all $y$, $P(x,y,z)=0$

  where the size of both $y$ and $z$ must be polynomial in the size of $x$.

Also see Fortnow's post and the complexity zoo for more informal explanations and discussions.

While this class seems reasonably natural, I can't find an example of a problem that's in $\textrm{S}_2^\textrm{P}$ for a non-trivial reason (i.e., not just because it is in NP or MA or some class contained in $\textrm{S}_2^\textrm{P}$). Does anyone know a problem that fits this description?

If no one can think of a problem like that, I wouldn't mind a problem that's in a sub-class of $\textrm{S}_2^\textrm{P}$, but it's non-trivial to show this, whereas the problem is obviously in $\textrm{S}_2^\textrm{P}$.


texts: Classic Neural Network Layout for regression: is the score function derivable?

texts:
I need to solve an optimization problem based on a function f(X). This function is not known, but it can be estimated from a training set. So first I train a model, then I get the score function f(X), and then I can use this function to solve my optimization problem.

So far, in my problem, I used a simple polynomial regression, and hence the score function is a polynomial. With this score function, the optimization problem works very well since it is infinitely derivable.

Now I want to improve f using a more complex model, i.e. a classic neural network for regression. I wonder: what kind of properties does the score function have in neural networks? Is it at least continuous? Is it derivable?


texts: Describe Levins 'Tile Expansion' one way functon in layman terms

texts:
I'd like some explanation on the details of the 'Complete OWF' presented on this paper in 'layman terms'.

See page 13 of  https://arxiv.org/pdf/cs/0012023.pdf

I'd prefer that the answerer had 'initiative'. That is - the answer should cover all aspects that could be described without jargon, or to give the definition of those terms in layman terms, without me having to list all those aspects. Thats because, in order to properly explain my doubts, I'd have to explain my 'guesses' on all those items and why they seem not to be correct, and the question would be too long. Also, other users may have different doubts, and sticking to mine may make this question less useful to the community (I expect moderators intervene if this doesn't seem adequate).


texts: Generating graph for random walk given hitting time distribution

texts:
given a discrete distribution of hitting time probabilities, is it possible to generate a random walk that generates this hitting time distribution? More specifically I am interested in generating a finite graph so that a simple random generates the given hitting time distribution.

I guess it is not possible to generate the exact distribution, but maybe approximate it?

Any hints on papers etc. are welcome!

Thanks,
Chris


texts: Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard?

texts:
By the well-known self-reducibility of SAT we can obtain a satisfying variable assignment for a Boolean formula by a polynomial number of calls to an $NP$ oracle (delivering only yes/no answers). Thus, the computation of a satisfying variable assignment for a Boolean formula is in $FP^{NP}$.

On the other hand, it is not possible with only a logarithmic number of $NP$ queries to obtain a satisfying variable assignment of Boolean formula as shown by Gottlob and Fermüller.

Has it already been shown that the computation of a satisfying variable assignment is also $FP^{NP}$-hard?


texts: What was the original intent for the creation of Lambda calculus?

texts:
I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church extracted relevant things for his work on "effective computability" and abandoned his prior work on logic.

So as I understand it, the $\lambda$-system and its notations took form as part of something to do with logic. What was Church initially trying to achieve that he forked off from later? What were the initial reasons for creating $\lambda$-calculus?


texts:
Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:

$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ for $j=1\dots,r$.

Is it possible to derive the H-representation of the convex hull of the union of $P_j$s, i.e., ConvexHull$(\bigcup_j P_j)$, efficiently?


texts: Finding a Hamiltonian cycle from perfect matching of a bipartite graph

texts:
A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H,  constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original graph edges replaced by corresponding L-> R edges.

Is it possible to find a Hamiltonian cycle in G (assuming it exists) as one realization of the vertex-disjoint cycle cover from the bipartite graph, H, using a matching algorithm?


texts:
I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete problem language can be reduced to other problem(s) language(s). This is the picture from the book:

However, even after thinking for quite some time, I can't think of a reduction from Vertex Cover to Max-Cut. Nor could I find any resource online. My question is, is there any (non-trivial*) reduction? Or is it some kind of misprint?

*Non-trivial meaning that it's not of the forms: 1) Vertex Cover -> SAT -> ... -> Max-Cut using Cook-Levin Theorem, or 2) Vertex Cover -> L -> ... -> Max-Cut, where L is some really unrelated language to both VC and Max-Cut.

Note: Even though the arrow reads Ex 2.16, the actual Ex 2.16 just asks to prove that Max-Cut is NP-complete. Also, this is not a homework question.


texts: Non-Uniform Classes of Languages not Closed Under Complement

texts:
Most "normal" non-uniform circuit classes are closed under complement. Just add a negation gate to the output of a circuit, and if necessary, apply De-Morgan's law.

Now there are some natural non-uniform classes of circuits, such as skew circuits of polylog depth which are still closed under complement but under much less obvious proofs.

Are there natural non-uniform circuit classes that are provably not closed under complement?
If the above question is too hard, are there natural circuit classes inside P/poly which imply something unexpected if they happen to be closed under complement?

I expect that a class satisfying any of the above will be kind of weird, since if $C_1 \subseteq X \subseteq C_2$ are complexity clases and $X$ is not closed under complement then $C_1\neq C_2$. Since such separations are lacking, by "natural" I mean some class that has been studied before and not made up exclusively to answer this question. On the other hand, I think that it would be interesting to have ways of engineering complexity classes that are not closed under complement.


texts: Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

texts:
We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.

Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.

$\mathsf{PP}$ still seems like it would be of reach.

What evidence do we have that $\mathsf{P} \neq \mathsf{PP}$, under that assumption, i.e., evidence that does not apply to $\mathsf{P}$ vs. $\mathsf{NP}$?

$\underline{\mbox{Assumption}}$: Note if $\mathsf{SAT}$ is in linear time then perhaps $\mathsf{P=PSPACE}$ might follow as composition of linear time is linear time?

$\underline{\mbox{Following is only based on if above assumption follows}}$:

Perhaps the problem would be

1a. why believe $\mathsf{SAT}$ is in superlinear time

1b. and if there is reason to believe $\mathsf{SAT}$ is in superlinear time then why believe $\mathsf{PP}$ requires $\Omega(\log\log n)$ quantifications?
Do evidences provided by https://eccc.weizmann.ac.il/report/2018/107/ and http://arxiv.org/abs/1504.03398 still hold up in face of $\mathsf{P=NP}$ and $\mathsf{SAT}$ in linear time ($\mathsf{P=NP}$ seems to invalidate second)?


texts: Where does a C-like language without heaps belong in the automata hierarchy?

texts:
Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without malloc and free; thus,the concept of a heap is absent in C''. Is C'' fundamentally weaker than C'? (I have a sense that this is the case because I cannot create lists and trees in C'', but can't be sure.) Can we map C' and C'' to deterministic TM and PDA, or some other automata, respectively?

Is there a work(s) that explores the computational powers associated with different language features? Roughly speaking, the answer I am trying to get at from the above paragraph is how important is the heap in the design of C.


texts: Breadth first search and Eppstein K shortest paths algorithm

texts:
I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf

I have trouble particularly with this quote on page 7, paragraph 2.3:

"If G contains cycles, the path tree is infinite. By Lemma 3, the path tree is heap-ordered. However since its degree is not necessarily constant, we cannot directly apply breadth first search (nor Frederickson’s heap selection technique, described later in Lemma 8) to find its k minimum values."

Why can we not use breadth first search (BFS) here? I've tried to look for an answer and to come up with different graphs where the degree of the nodes varies, but so far I do not understand this. Could someone explain how the non-constant degree prevents us from using BFS?


texts: How to start learning formal language theory

texts:
I sincerely apologize if this is not appropriate in this stack Q&A, though it seemed the most fitting.

I want to learn formal language theory, as well as generating grammars etc. The purpose is primarily from a programming perspective (and from pure interest), not from academic requirements. My current state of knowledge includes basic college-level math (very far from good skills sadly), and of course programming skills.
Which math and logic fields should I explore. What is the best way to learn it (other than majoring in mathematics)?
Specific resources are welcome (as is general direction I should follow).

Also - what are skill requirements to properly learn the topic and understand it to the degree it may be useful in programming?

EDIT: my interest in this branch of mathematics started once I learned regular expressions and wanted to "delve deeper"


texts: CCCs, computational calculi and point-surjectivity

texts:
The models of some computational calculi are in a correspondence with Cartesian Closed Categories with an object $U$ that has some relationship to its exponential object $U^U$ e.g. a retraction between $U$ and $U^U$ gives $\lambda$-algebra whereas those with enough points and $U \cong U^U$ admitting extensionality
One possible relationship between $U$ and $U^U$ is (weak) point-surjectivity which is defined as there existing a morphism $\phi : U \rightarrow U^U$ such that for all points $p: 1 \rightarrow U^U$, there exists a point $u : 1 \rightarrow U$ and $\phi \circ u = p$.
This relationship is relevant to $\lambda$-calculi as the $F: D \rightarrow D^D$ sided arrow in the retraction for lambda models and in the isomorphism can be seen to be point-surjective. Furthermore point-surjectivity appears in Lawvere's Fixed Point Theorem which can be used to derive the First-Fixed-Point theorem for the (I have written a derivation here however it has been rushed so apologies for mistakes).
A question that I have been contemplating is whether point-surjectivity corresponds to any existing class of automata or combinatorial calculi. Longo and Moggi in "A Category-Theoretic Characterization of Functional Completeness" outline the categorical models associated with combinatory algebras however it is not immediately obvious to me whether we point-surjectivity corresponds to this formulation however my intuition says otherwise. I have managed to derive several combinators in an applicative structure induced  by a point-surjective $F: U \rightarrow U^U$ in the standard way as outlined in Chapter 5 of Barendregt's "The Lambda Calculus: It's Syntax and Semantics". These are the Mockingbird combinator $\textbf{M} x = x x$, the Identity combinator $\textbf{I} x = x$, and the combinator $\textbf{F} x y = y$. Derivations can be found here. I am unsure if this is an exhaustive list of the combinators that can be derived or if this set has any meaningful interpretation.
Any guidance or insights would be greatly welcomed!


texts: The randomized query complexity of the conjoined trees problem

texts:
An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of.  In this problem, we're given an exponentially-large graph like the one pictured below, which consists of two complete binary trees of depth n, whose leaves are connected to each other by a random cycle.  We're supplied with the label of the ENTRANCE vertex.  We're also supplied with an oracle that, given as input the label of any vertex, tells us the labels of its neighbors.  Our goal is to find the EXIT vertex (which can easily be recognized, as the only degree-2 vertex in the graph other than the ENTRANCE vertex).  We can assume that the labels are long random strings, so that with overwhelming probability, the only way to learn the label of any vertex other than the ENTRANCE vertex is to be given it by the oracle.

Childs et al. showed that a quantum walk algorithm is able simply to barrel through this graph, and find the EXIT vertex after poly(n) steps.  By contrast, they also showed that any classical randomized algorithm requires exp(n) steps to find the EXIT vertex with high probability.  They stated their lower bound as Ω(2n/6), but I believe that a closer examination of their proof yields Ω(2n/2).  Intuitively, this is because with overwhelming probability, a random walk on the graph (even a self-avoiding walk, etc.) will get stuck in the vast middle region for an exponential amount of time: any time a walker starts heading toward the EXIT, the much larger number of edges pointing away from the EXIT will act as a "repulsive force" that pushes it back toward the middle.

The way they formalized the argument was to show that, until it's visited ~2n/2 vertices, a randomized algorithm hasn't even found any cycles in the graph: the induced subgraph that it's seen so far is just a tree, providing no information whatsoever about where the EXIT vertex might be.

I'm interested in pinning down the randomized query complexity of this problem more precisely.  My question is this:

Can anyone come up with a classical algorithm that finds the EXIT vertex in fewer than ~2n steps---say, in O(2n/2), or O(22n/3)?  Alternatively, can anyone give a lower bound better than Ω(2n/2)?

(Note that, by the birthday paradox, it's not hard to find cycles in the graph after O(2n/2) steps.  The question is whether one can use the cycles to get any clues about where the EXIT vertex is.)

If anyone can improve the lower bound past Ω(2n/2), then to my knowledge, this would provide the very first provable example of a black-box problem with an exponential quantum speedup, whose randomized query complexity is greater than √N.  (Where N~2n is the problem size.)

Update: I've learned from Andrew Childs that, in this note, Fenner and Zhang explicitly improve the randomized lower bound for conjoined trees to Ω(2n/3).  If they were willing to accept constant (rather than exponentially-small) success probability, I believe they could improve the bound further, to Ω(2n/2).


texts:
I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R.  And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R.

Thanks.


texts: Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

texts:
The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it seems Unvollständigkeitssatz is more commonly used, and Entscheidungsproblem ("decision problem") is still understood, but not necessarily associated with das Halteproblem (which seems to be more common after Turing's work on automata). On the other hand, for English CS researchers, Entscheidungsproblem is usually the only word they are familiar with.

Note: the words are not the same, and it could be argued that Hilbert's question about deciding was answered in the negative for a particular case by Gödel's statements about incompleteness, so that incompleteness demolishes decision in general.

Interestingly, when looking at the German Wikipedia, there is no entry for Entscheidungsproblem, but there is one for Gödelscher Unvollständigkeitssatz, and the entry about Hilbert uses Gödelscher Unvollständigkeitssatz. When looking at the English Wikipedia, one readily finds an entry for Entscheidungsproblem.

How come Entscheidungsproblem is no longer used in German?


texts:
I was wondering if the JSON spec defined a regular language.  It seems simple enough, but I'm not sure how to prove it myself.

The reason I ask, is because I was wondering if one could use regular expressions to effectively pars JSON.

Could someone with enough rep please create the tags json and regular-language for me?


texts: Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However asking for counter examples here might be a reasonable extended formulations problem.


texts: Is there a gadget that reduces generalized geography to undirected graphs?

texts:
The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245 (thx to Marzio De Biasi for the link) it is posed as an open problem. Is it still open?

In fact, I wonder if there is a simple gadget that we can put in the place of every directed edge to make a straight-forward reduction from the directed version. Is it known that no such gadget can exist?


texts: Connection between nonmonotonic logic and type theory (lambda calculus)

texts:
There is known connection between classical and modal logics and type theory (lambda calculus), but are there connections between nonmonotonic logics (e.g. defeasible logic) and type theory (lambda calculus)? Maybe HoTT provides some generatlization where such connections can be found?

If such connections can not be established then widely available proof assistants (Isabelle, Coq) are not useful for nonmonotonic logics, aren't they?


texts: Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

texts:
Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression  operations (Kleene star, concatenation, reverse, set operations, etc). I was unsure about the worst case performance of my package.

A DFA has the same expressive power as an NDFA, because an n-state NDFA can be trivially converted to a DFA having 2^n states. However, are there any lower upper bound guarantees for such a conversion that do not require an exponential explosion in state?

I was unable to come up with examples mal-behaving regular expressions or NDFAs, but I didn't spend much time thinking about it. I am guessing a regular expression like ((((e|A|B|C)*(e|D|E|F))*(e|G|H|I))*(e|J|K|L|M))* which mixes a lot of alternations and Kleene stars would have a linearly sized NDFA but an expansive DFA.


texts: A clarification in Signature schemes for Strong Unforgeability.

texts:
Signature scheme is strongly unforgeable.
"making the message m being signed depend on the randomness r — we break
the proof of security for the underlying signature."

From Paper: Strongly Unforgeable Signatures Based on Computational Diffie-Hellman - Dan Boneh, Emily Shen, and Brent Waters.

Can some one point out how a scheme can be broken when the message being signed depends on the randomness?

Thanks. Please let me know if I am not clear. The paper has it all.


texts: When do cellular automata on non-abelian groups not offer a computational speed up?

texts:
Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally disconnected.

If $x\in A^{G}$ and $g\in G$, then define $gx\in A^{G}$ by letting $gx(h)=x(g^{-1}h)$.

We say that $F:A^{G}\rightarrow A^{G}$ is $G$-equivariant if
$F(gx)=g F(x)$ for each $g\in G$ and $x\in A^{G}$.

Then a cellular automaton is a function $F:A^{G}\rightarrow A^{G}$ which is both continuous and $G$-invariant.

We say that a language $L\subseteq A^{*}$ is accepted in polynomial time by a cellular automaton over the group $G$ if there exists some $B$ with $A\subseteq B$ along with some special elements $0,u,v\in B\setminus A$, a cellular automaton $F:B^{G}\rightarrow B^{G}$, an element $g\in G$ of infinite order, and a polynomial $p$ that satisfies the following property:

Suppose that $s\in A^{*}$. Then let $x\in B^{G}$ be the string where
$x[g^{i}]=s[i]$ whenever $i<|s|$ and $x[h]=0$ whenever $h\not\in\{e,...,g^{|s|-1}\}$. Then there is some natural number $n<p(|x|)$ such that
$F^{n}(x)(e)\in\{u,v\}$. Furthermore, if $n$ is the least natural number such that $F^{n}(x)(e)\in\{u,v\}$, then $s\in L$ if and only if $F^{n}(x)(e)=v$.

Is there a characterization of the groups which are computable in polynomial time such that a language $L$ is accepted in polynomial time if and only if
it is accepted in polynomial time by a cellular automaton over the group $G$?


texts:
Is it possible to build an explicit $N \times N$ $0/1$-matrix with $N^{1.5}$ ones such that every $N^{0.499} \times N^{0.499}$ submatrix contains less than $N^{0.501}$ ones?

Or probably it is possible to build an explicit hitting set for such property.

It is easy to see that random matrix has this property with probability exponentially close to $1$. Also, expander mixing lemma is not sufficient to derive this property.

I guess pseudorandom generators that fool combinatorial rectangles could help here, but they are designed for uniform distributions and I basically need $B(N^2, N^{-0.5})$ here.


texts: A simple(?) funny combinatorial problem!

texts:
Let we fix $0<E<1$ and an integer $t>0$.

for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$

  $A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \times t \}| \geq \binom{ E \times n}{ t }$

I don't know if the statament is true o false.
I think it's true.

My intuition come from the observation that for the vectors $\bar{c} \in \{0,1\}^n$ (with the desidered property about the sum) we have $A_{\bar{c}}= \binom{ E \times n}{t}$; in this case we can only select subset from the set $\{ i ~|~ c_i = 1 \}$.

In the others case we can create good subset (s.t. the sum is greater then $E \times t$) using the coordinate in $\{ i ~|~ c_i > E \}$ but also, maybe, using few coordinate from the set $\{ i ~|~ c_i \leq E \}$ we could create other good set!

So,Prove it or find the bug! hoping that it could be a funny game for you!

Motivation of the question:

Suppose you have a random variable $X\in \{0,1\}^n$, a typical measure of "how much randomness" there is in $X$ is the min-entropy

$H_{\infty}(X) = min_{x} \{ -log(Pr[X = x]) \}$

In some intuitive sense the min-entropy is the worst case of the famous Shannon Entropy (that is the average case).

We are interested to lowerbound the min-entropy of the random variable $(Z=X \wedge Y| Y)$ where $Y$ is uniformely distributed over the set $\{ y ~|~ \sum_i y_i = t\}$.

Loosely speaking if we are lucky we can catch the bits of $X$ that have "good entropy" and so we if $H_{\infty}(X)\geq En$ then  $H_{\infty}(Z|Y)\geq Et$

  What is the probability that we are lucky?

The problem is well-studied one and there exists a lot of literature,
for example see Lemma A.3. in Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model


texts: Solving an online problem without maximizing or minimizing an objective

texts:
You have a budget $B$ and a satisfaction level $L$. An indivisible product is available for sell and you are interested in buying. The product is divided into $n$ parts. Part $i$ of the product has positive value $v_i$.

On day $i$, you get to know $v_i$ and you have to decide how much price $p_i\geq0$ you would pay for this part of the product.

After $j$ days, given the values $v_1, v_2, \ldots, v_j$ and the prices you paid $p_1, p_2, \ldots, p_j$ for each value, you know that you can reach a satisfaction level of $(1+v_1p_1)(1+v_2p_2)\cdots(1+v_jp_j)$.

Your objective is to buy the product after $n$ days while you reach the satisfaction level of $L$ and pay no more than $B$.


texts:
I want to generate an infinite sequence of numbers between $0$ and $9$ such that the percentage of number $i$ appearing in the sequence is $p_i$. Let $p=\lbrace p_0,...,p_9\rbrace$.

Another agent $B$ will observe $k$ consecutive elements from the sequence. Then it will update its belief about the probability of $p_i$ using a belief update rule (let's say a simple frequentist, i.e., the number of occurrences of each digit divided by $k$).

The question is how can I generate the sequence such that $B$'s belief $q$ is close to $p$, i.e., $d(p,q)$ is minimized where $d(p,q)$ is the dsitance function of two distributions, e.g., $d(p,q)=(\sum_i (p_i-q_i)^2)^0.5$.

Note that I don't know how $B$ will choose the $k$ numbers. Let's consider the worst case (i.e., worst $p'$).


texts:
I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:

What is the status of approximating rank of a matrix in these models (e.g., communication complexity, query complexity, streaming etc)? Here the goal is to output a number which is approximately the rank of the matrix. Is there a paper(s) which presents the state-of-the-art regarding this?

A quick Google search points only to the papers involving low rank approximation. The exact rank problem, however, has high lower bound (in randomized communication complexity) which follows from a reduction from singularity problem (i.e., whether a matrix is of full rank or not).


texts: Is the longest trail problem easier than the longest path problem?

texts:
The longest path problem is NP-hard. The (typical?) proof relies on a reduction of the Hamiltonian path problem (which is NP-complete). Note that here the path is taken to be (node-)simple. That is, no vertex can occur more than once in the path. Obviously it is thus also edge-simple (no edge will occur more than once in the path).

So what if we drop the requirement of finding a (node-)simple path and stick to finding an edge-simple path (trail). At first glance, since finding a Eulerian trail is much easier than finding a Hamiltonian path, one might have some hope that finding the longest trail would be easier than finding the longest path. However, I cannot find any reference proving this, let alone one that provides an algorithm.

Note that I am aware of the argument made here:
https://stackoverflow.com/questions/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph
However, the argument seems flawed in its current form, as it basically shows you could solve the edge-simple case by solving the node-simple case on a different graph (so the reduction is the wrong way around). It is not clear that the reduction could easily be changed to work the other way as well. (Still, it does show that at the very least the longest trails problem is not harder than the longest paths problem.)

So are there any known results for finding longest trails (edge-simple paths)? Complexity (class)? (Efficient) algorithm?


texts: Types which correspond to sets of cardinality of continuum

texts:
Are types which correspond to sets with cardinality of continuum possible in MLTT (or in any other constructive theory)?

On the first sight, they aren't, since elements of types are terms and we have only countable number of terms.

Does it mean that sets with cardinality of a continuum really doesn't exist and just a nice abstraction which simplifies mathematics a lot?


texts: Bounds on the size of NFA for $r$-skip $k$-distinct language

texts:
This question is about an extension of a language discussed in this question.

We define the $r$-skip $k$-distinct language as follows:

$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \forall i\neq j\in [rk],i=j \mod r\implies \sigma_i \neq\sigma_j\}$$

That is, the set of letters whose distance is a multiplication of $r$ are different.

This language is finite and therefore regular. Specifically, if $|\Sigma|=n$, then $|L_{r,k}|=$$({n\choose{k}}\cdot k!)^r$.

For $r=1$ we get the language $L_{k-distinct}$ defined in the linked question.

A natural NFA build for $L_{r,k}$ uses the color coding scheme and for a $(|\Sigma|,k)$-perfect hashing family $\mathcal F$ (i.e. mapping the letters into $k$ indices) selects a hash function $f\in \mathcal F$ by an epsilon transition and then verifies that each set of letters $\Sigma_i = \{\sigma_j|i=j \mod r\}$ is distinct.

Such perfect hashing family build of size $O(e^{k+\log^3 k}\cdot n\log n)$ is known

The resulting automaton is of size $O((2e)^{r(k+O(\log^3 k))}\cdot n\ \text{polylog}\ n)$, which is the same as we would get for $L_{1,rk}$ (which is $L_{rk-distinct}$) by using the same approach.
(The reason for this size, at least in a naive build, is that the automaton state have to encode which of the $k$ colors we've seen for each of the $r$ letter sets).

A more careful build would give $O(4^{r(k+O(\log^2 k))}\cdot n\ \text{polylog}\ n)$ sized automaton (same goes for $L_{1,rk}$).

This sounds wasteful, as a lot fewer comparison are needed as $r$ grows larger (and $rk$ is constant).

What is the smallest automaton we can build for $L_{r,k}$?


texts: Node-weighted steiner problem with few terminals

texts:
Consider the node-weighted steiner problem:

Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \subseteq V\setminus T$ of vertices such that $G[T\cup S]$ is connected.

Is this problem polytime solvable when the number $|T|$ of terminals is a constant?


texts:
I am reading this article, and I need help with an apparently obvious proof.

The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real multilinear polynomial of degree at most $\sqrt{N}/7$, and suppose that $|p(X)| \leq \frac{2}{3}|p(0^N)|$ for all $x \in \{0,1\}^N$ with Hamming weight 1. Then there exists an $x \in \{0,1\}^N$ such that $|p(x)| \geq 6 |p(0^n)|$.

We need the following information:

We have that a polynomial $p$ approximates a boolean function $f$ if for every $x \in \{0,1\}^n$ we have that $|p(x) - f(x)|\leq 1/3$. Then the approximate degree of $f$, $deg'(f)$ is the minimum of the degree of $p$ over all polynomials $p$ that approximate $f$

I think that Aaronson means that the lemma immediately follows from the following result (that can be found here): If $f$ is a boolean function s.t. $f(0^n) = 0$ and for $x$ with hamming weight 1 $f(x) =1$, then $deg(f) \geq \sqrt{n/2}$ and $deg'(f)\geq \sqrt{n/6}$.

So how can we proof the lemma? I am already confused that we have that " $|p(X)| \leq \frac{2}{3}|p(0^N)|$" instead of " $|p(X)| \leq \frac{1}{3}|p(0^N)|$". You can perhaps assume that $p(0^N) = 1$ and then deduce that $1-p$ cannot approximate the OR function, because the degree is too low.  But I dont see how I get the rest.


texts: Are there poly time algorithms to determine if a graph is almost bipartite?

texts:
Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.

Are there poly time algorithms to determine if a graph is exactly or approximately almost bipartite?


texts:
Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of methods for constructing an "index" structure so that the following operations can be performed on the table and index in $O(k\log N)$ time (relative to $N$ and $k$):

Insert a new element into the table.
Remove a specified element from the table.
Given a set of values of the fields, obtain the first record that is in the table with field values greater than the given field values, when the table is sorted into the lexicographic order with field 1 first, field 2 second, etc.

We wish to generalize this construction so that when operation 3 is done, any of the $k!$ orderings of the $k$ fields can be specified to determine the ordering of the records in the table.

Clearly, this can be done by constructing k! indexes, one for each ordering of the fields.  Then the operations take $O(k!k\log N)$ time.

We want an algorithm whose operations are much faster (relative to $k$), preferably $O(k\log k \log N)$ time.

Does such an algorithm/data structure exist?  It seems likely that if it existed, someone would have published and implemented it by now, but I've found no signs that one exists.  Conversely, perhaps it can be proven that no such algorithm exists.  But I've found no signs that such a proof exists.


texts: Research about geometry negotiation in widget layout

texts:
It's very common to view GUI layout as an optimization problem.

I've uncovered a lot of research around linear constraint systems, but a lot of real world layouts can not be represented linearly. For example, a simple "Wrapping" layout introduces discontinuities at line or column breaks.

Some real world systems compute layout recursively. They alternate between measuring and positioning widgets, then iterate until a fixed point. I've seen this process called "geometry negotiation" in the documentation for several of these widget libraries. However, I can not find any formal treatment of this approach.

Outside of linear constraints, are there any other formalisms targeted at these sorts of layout optimization systems?


texts: Obfuscation transformation and code maintainability

texts:
This is more a software engineering question, but my interest is in the mathematical modeling of the problem.

While there seems to be some literature on the modeling of obfuscation transformation, I'm finding it difficult to locate papers that relates it to code maintenance - guess because they are inherently orthogonal. But its hard to imagine no study has been done by modeling this as an optimization problem. Can anybody point me to any thing that is helpful to get some insight into this?


texts: Entropy inequality of joint von Neumann entropy given some marginal inequalities

texts:
Assume that I have a pure, multipartite state $\omega_{ABCD}$ and a unitary $U(\omega_{ABCD})=\tau_{ABCD}$. The effect of $U$ on $\omega$ results in
$$
S(\omega_B)<S(\tau_B)
$$
and
$$
S(\omega_A)>S(\tau_A).
$$
$S$ is the von Neumann entropy and the states $\omega_A,\tau_A$ etc are the marginal density matrices (for instance, $\omega_A$= $Tr_{BCD}{\omega_{ABCD}}$). This effect of $U$ is an assumption, I don't say it always holds.

QUESTION:
Comparing the joint entropies $S(\omega_{AB})$ and $S(\tau_{AB})$, is this true
$$
S(\tau_{AB})-S(\omega_{AB})\leq S(\tau_{B})-S(\omega_{B})
$$
and if yes, why?

EDIT: Another assumption is that $S(\omega_{AB})\geq S(\omega_B)$.


texts: Quantum algorithms for generalizations of determinants

texts:
There are a wide variety of determent-like constructions.  Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like quasideterminants extend the theory of determinants to non-commutative rings.

At least permanents have a rich complexity theory, perhaps the others do to.

For any of these constructions, is there a quantum algorithm that asymptotically out preforms the fastest classical algorithms for computing it?

I'm asking because some post-quantum crypto systems like http://arxiv.org/abs/1407.1270 and code-based crypto suffer from extremely large key sizes due to representing public keys as matrices.  A priori, it might be possible to "compress" that large matrix into something like a characteristic polynomial but using some non-commutative analog of the determinant.  This approach sounds less viable if quantum computers could compute some analogs of the determinant more quickly.


texts: Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$

texts:
By "complement problems", I mean the two problems' objective functions are complement. For example, the vertex cover and its complement independent set in this sense. For a graph $G(V,E)$, their answers add up to $|V|$. Another example is a problem I am working on. The dominating set problem and its complement "packing as many edges as possible so that there is no path or circle whose length is more than 2". Dominating set is $W[2]$-complete in the sense, and the edge packing problem is in $W[1]$-complete( whether it is complete in $W[1]$, I am still looking).

So, I come to the following audacious conjecture.
If problem A and problem B are complement, then A and B are not in the same class in the parameterized complexity structure, i.e. $FPT \subseteq W[1] \subseteq W[2] \subseteq \cdots W[SAT] $. Of course, there is another condition : A and B are not $P$ in the classical complexity hierarchy.

I am not very familiar with parameterized complexity theory. So, any advice is welcome. Thank you very much.


texts: Maximum computational power of a C implementation

texts:
If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have?

Note that “C implementation” has a technical meaning: it is a particular instantiation of the C programming language specification where implementation-defined behavior is documented. A C implementation doesn't have to be able to run on an actual computer. It does have to implement the whole language, including every object having a bit-string representation and types having an implementation-defined size.

For the purpose of this question, there is no external storage. The only input/output you may perform is getchar (to read the program input) and putchar (to write the program output). Also any program that invokes undefined behavior is invalid: a valid program must have its behavior defined by the C specification plus the implementation's description of implementation-defined behaviors listed in appendix J (for C99). Note that calling library functions that are not mentioned in the standard is undefined behavior.

My initial reaction was that a C implementation is nothing more than a finite automaton, because it has a limit on the amount of addressable memory (you can't address more than sizeof(char*) * CHAR_BIT bits of storage, since distinct memory addresses must have distinct bit patterns when stored in a byte pointer).

However I think an implementation can do more than this. As far as I can tell, the standard imposes no limit on the depth of recursion. So you can make as many recursive function calls as you like, only all but a finite number of calls must use non-addressable (register) arguments. Thus a C implementation that allows arbitrary recursion and has no limit on the number of register objects can encode deterministic pushdown automata.

Is this correct? Can you find a more powerful C implementation? Does a Turing-complete C implementation exist?


texts: Number of connected partitions (or labelings) in a grid graph

texts:
Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, whether they are at a corner or border. Here is an example with $W=4$ and $H=3$ :
$$\begin{array}{ccccccc}
O & - & O & - & O & - & O\\
| &   & | &   & | &   & |\\
O & - & O & - & O & - & O\\
| &   & | &   & | &   & |\\
O & - & O & - & O & - & O\\
\end{array}$$
I wish to partition $G$ into $n$ subgraphs. Each vertex can be labeled with an integer from $1$ to $n$. I would like to count the number of possible "connected labelings" of $G$, as a function of $W$, $H$ and $n$.
In image processing, we would call this a segmentation, with non-empty and connected regions.
In my "connected labeling", two properties should be verified :

non-emptiness : have at least one vertex per label
connection : each subgraph made up of vertices labeled i should be connected

Without any constraint, there are $n^{WH}$ possible labelings. If we add the non-emptiness constraint, we should remove the labelings having only 1, 2, ... n-1 labels, which gives
$$n^{WH} - \sum_{k=1}^{n-1} {n\choose k}k^{WH}$$
But, then, how to handle the connectedness constraint?


texts: Linear programming optimization problems using parallel algorithms

texts:
I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches for solving LP problems in a parallel way, but I wonder if there are specific methods which are efficient for such (real-world, by the way) systems.

Thanks in advance.


texts: A maximization problem containing summation and multiplication

texts:
Are the following two problems NP-hard?

Problem 1

Given $n$ ordered pairs of integers $S=\{(a_i,b_i)\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a+\prod_{(a,b) \in A}b$ is maximized.

Problem 2

Given $n$ ordered pairs of real numbers $S=\{(a_i,b_i)| 0 \leq a_i \leq 1, 1 - a_i \leq b_i \leq 1\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a-\prod_{(a,b) \in A} b$ is maximized.

Or, equivalently:

Given $n$ ordered pairs of real numbers $S=\{(a_i,c_i)| 0 \leq a_i, c_i, \leq 1\}$, $1\leq i \leq n$, and an integer $k$, find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,c) \in A}a-\prod_{(a,c) \in A}(1-ac)$ is maximized.

The objectives can be taken as set functions defined on $2^S$. The objective of the second problem is submodular.

Any hint, reference to a book, a paper or related problems is appreciated.
I have tried finding a reduction from knapsack and set cover, but no luck so far.


texts: Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

texts:
Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) also tries to prove something non-trivial at the level of circuits, Jukna's remark 1.18 here http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf tries to attempt $P/poly$ is not strong enough etc.

Is there any known strategy to prove $P$ is not $NP$ that does not prove the stronger statement such as $NP\not\subseteq P/poly$?

Assume $NP\subset P/poly$ holds, assume $coNP=NP=RP\neq P$ holds and assume $VP=VNP$ holds and in this scenario is there any hope to prove $P\neq NP$?

Why negative vote (this is a perfectly reasonable query seeking whether there is any strategy known that can avoid 'circuit'ous route and also addresses one 'minuscule' probability cause of why known approaches fail (just because except $P\neq NP$ everything we assume is false - this probability is technically nothing yet there))?


texts: Cost of in-place partitioning integer arrays

texts:
Suppose we are given an array $a\colon[n]\to[m]$ of length $n$ (and each entry is between 1 and m). We will denote the $i$th entry of the array as $a[i]$.

Task: Permute the array $a$ in-place so that the elements of the same value are grouped together. To be explicit, the final array $a$ needs to satisfy
$$a[i] = a[j]\implies \forall i < k < j, a[k] = a[i].$$
Here we assume the randomized word RAM model with $\log m$ bit wide words (take $m > n$).

For the purposes of this question in-place means using $\mathrm{polylog}(n)$ words of space on top of the mutable array $a$, which can be changed arbitrarily but at the end of the algorithm must be a permutation of the original array.

Is there an in-place algorithm known with running time $o(n\log n / \log \log n)$?

Does the integer sorting literature offer anything for this?


texts:
In this answer it is shown we can encode inductive types in System F-omega using the church encoding:

$Fix F = \forall T : \mathsf{Type} \,.\, (F T \to T) \to T$

for some type constructor $F$.

It is also known that this encoding does not admit constant-time destructors for those datatypes.

If we add positive-recursive types to System F-omega then we can use the Parigot encoding to get efficient datatypes (when sharing correctly they can also be space efficient).

Can we also generalize the Parigot encoding to be of a form similar to the F-algebra style of datatypes?
My intuition says we'd have to modify the encoding to something like:

$Fix F = \forall T : \mathsf{Type} \,.\, (F (Fix F, T) \to T) \to T$

Only I am not sure this type will pass the positive-recursion check.


texts: Proof of a unique homomorphism from an initial object

texts: What is the proof that there is only one homomorphism from an initial object to another object?


texts: Shortest cycle separator for biconnected planar graphs

texts:
An $(s,f)$- balanced separator in a graph $G$ is a set $S$  of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is said to be a cycle-separator.

  Question: for which smallest value of $\frac{s}{\sqrt{n}}$ such that $f$ is a constant there exists (and one which can be found in
  polynomial time) an $(s,f)$-cycle separator for all biconnected
  planar graphs which are not "easy" - the notion of easiness being (for
  example) bounded tree-width. Probably the parameters $s,f$ will depend
  on the tree-width $w$ of the easy class.

Notice that I do not care about $f$ as long as it is a constant but $s$
(as a fraction of $\sqrt{n}$) is crucial for me.

Some background:
Lipton-Tarjan gave a $(c\sqrt{n},\frac{2}{3})$-balanced planar (vertex) separator for some constant $c$. Subsequently Miller gave a similar separator that is also a cycle but in triangulated planar graphs.

If we omit the triangulated condition (say replace it by $2$-vertex connected) there might not exist an $(O(\sqrt{n}),O(1))$-cycle separator - case in point being a cycle on $n$ vertices. We can choose to ignore such easy (e.g. all bounded tree-width) cases.


texts: Smallest known formula for the determinant

texts:
The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size).

Do you have any reference for this? In particular, what is this formula?


texts: Is there an extension to the stable roommates problem with multiple roommates per room?

texts:
The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to each other). There is an efficient algorithm which finds a solution, if there is one.

Is there an extension of this problem to rooms which can take more than two people?

Such an extension does seem challenging, because so much of the definition of the problem rests on the fact that roommates are in pairs, which means that each roommate only shares with a single other. This makes comparisons between potential pairings trivial - does the roommate prefer this partner or that one? Asking whether a roommate prefers one set of partners or another is much harder. Still, i'm interested in any approaches which have been taken!


texts: Subtyping rules for extension of System $F_\omega$ with subtyping and kind-level variance tracking

texts:
I need an extension of System $F_\omega$ with subtyping, and where the variance of type constructors is reflected in their kind. Unfortunately, System $F^\omega_{<:}$, as defined in chapter 31 of Pierce's Types and Programming Languages, doesn't address the latter requirement, so I decided to roll my own.

Here is the list of additions to $F_\omega$'s I've made so far:

Polarities

Ground forms: $+$, $-$.
Inversion: $+^\dagger = -$ and $-^\dagger = +$.

Variances

Ground forms: sets of polarities.
Inclusion: set inclusion.
Inversion: memberwise.

Kinds

Ground forms: $\Omega/V$ and $K \rightarrow K'$.
Inclusion:

Given $V_1 \subseteq V_2$, we can derive $\Omega/V_1 \subseteq \Omega/V_2$.
Given $K_2 \subseteq K_1$ and $K_1' \subseteq K_2'$, we can derive $K_1 \rightarrow K_1' \subseteq K_2 \rightarrow K_2'$.

Types

Kinding:

$\Gamma \vdash \top, \bot : \Omega/V$.
$\Gamma \vdash (\rightarrow) : \Omega/V^\dagger \rightarrow \Omega/V \rightarrow \Omega/V$.
The remaining rules are as one would expect.

Inclusion:

Given $\Gamma \vdash T : \Omega/V$ and $\{+\} \subseteq V$, we can derive $\Gamma \vdash \bot \subseteq T \subseteq \top : \Omega/V$.
Given $\Gamma \vdash T : \Omega/V$ and $\{-\} \subseteq V$, we can derive $\Gamma \vdash \top \subseteq T \subseteq \bot : \Omega/V$.
Given $\Gamma \vdash T_1, T_2 : \Omega/\{+,-\}$, we can derive $\Gamma \vdash T_1 \subseteq T_2 : \Omega/\{+,-\}$.
The remaining rules are as one would expect.

And here I ran out of imagination. Now I have the following questions:

Is what I've sketched so far sound? What sanity checks can I use to make sure I'm not doing something wrong? Perhaps something akin to automated testing in computer programming?
A type system with polymorphism and subtyping must have bounded quantification. How hard should it be to add?
A very important desideratum in type systems with subtyping is that the inhabitants of each kind form a lattice. How hard should it be make sure that each kind is a lattice?
What's the most convenient tool for mechanizing formal systems like the one I sketched? Preferably, I'd like a library or framework that already does the “boring stuff”, like implementing variable substitution and handling contexts.


texts: Problems that can be used to show polynomial-time hardness results

texts:
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed require $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems that can be used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X such that I can show it is X-hard and leave it at that?

Update: This question originally asked for families of problems. Since there aren't that many families of problems, and this question has already received excellent examples of individual hard problems, I'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a bounty to this question to encourage more answers.


texts:
I'm finding is there any range summable hash function.

ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of approximating the frequency moments.

Improved range-summable random variable construction algorithms gives one for any k-wise independence,
but its author Martin J. Strauss shows it is incorrect from his homepage.

The only one I can find is from One-Pass Wavelet Decompositions of Data Streams, where a 4-wise one is given. It used second-order Reed-Muller hash functions.

Are there any other range summable hash functions with 4 or more independence?


texts: "Context" understanding in tree grammars

texts:
The Context-Free tree grammar has rules of the form:

$A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$,

where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ means a set of all possible trees with labels from $Z$.

where $N$ is a finite unranked set of non-terminals and $T$ is a finite unranked set of terminals, $x_i$ are free-variables.

It is clear, that this form of rules is definitely context-free.

The thing which I doubt about is: would the following form of rules

$x_1(A)\rightarrow x_1(A_1,\dots,A_2)$, where $A_i\in(N\cup T)$,

be context-free?

(More generally: $x_1(A)\rightarrow x_1(t_1,\dots,t_2)$, where $t_i\in T(N\cup T)$).

(Obviously it is not context-free according to the definition, but why not?). I don't see any context here. Such kind of rules may be useful for describing changing of the branch without growing tree down. $X$ here is a free-variable, and it points to the arbitrary parent node of the terminal $A$.

The only one theoretical objection here against "context-free-ness" of this form of rules, is that this kind of rules implies, that non-terminal $A$ is not a root of the current derivation tree. From other hand, conventional rules of the form $A(X_1)\rightarrow\dots$ can not be applied for the case when $A$ is a leave in the current derivation.

UPD: For those who asked me for an example of Context-free tree grammar, please refer this link: http://research.nii.ac.jp/~kanazawa/Courses/2011/Kyoto/cft.pdf

Though it describes CFTG for ranked trees, obviously the same rules in the same semantics can be applied for the case of unranked trees.


texts: Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?

texts:
Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA?

The existence of $L$ would imply that linear-space-bounded cellular automata are more powerful than linear-time cellular automata: All deterministic CSL's can be recognized by linear-space-bounded cellular automata and linear-time cellular automata can be simulated by LBA's in $O(n^2)$ steps.

By using crossing-sequences, it is shown that unbounded LBA's are more powerful than linear-time-bounded LBA's. In particular the context free language $\{ ww^R\: | \: w \in \Sigma^* \}$ cannot be recognized by a turing machine in $O(n)$ steps, but can be recognized in $O(n^2)$ steps.


texts: SAT solvers & SAT solving methods admitting minimal satisfying assignments

texts:
I'm in need of a SAT solver that outputs minimal assignments - that is, a set of assignments to a subset of all propositional variables such that substitution into the CNF formula makes each clause true, and such that the satisfiaction fails when any of the variables in the solution set is removed.
One possible application area is All-SAT, where one can take a standard incremental SAT solver and continually add minimal blocking clauses by negating the solutions, essentially converting the problem to a reduced form of DNF.
I've found two general methods for deriving minimal assignments. The first is to apply a minimal hitting set/set cover algorithm (or a heuristic) to the substituted CNF clauses (discussed here). The second is to apply an approach with unsatisfiable cores (discussed here).
Do any SAT solvers have strategies for minimal assignment extraction built-in? Are there any modifications to the CDCL procedure that take into account variable ordering/subsumption to make it all in one process?


texts: Verification: how 'formal' is a tool like Java Modeling Language (JML) compared to certified libraries and model checking?

texts:
(note: this is probably a beginner question, and English is not my first language)

Recently, I have read a paper that used the “Java Modeling Language” (JML), see for instance:

http://www.eecs.ucf.edu/~leavens/JML//index.shtml
http://www.eecs.ucf.edu/~leavens/JML/fmco.pdf

a) certified Software
To my understanding, a sorting algorithm proven correct in the theorem prover Coq (and possibly extracted to an ocaml program) is "certified software" or formally verified software, as a mathematical proof of the correctness can be extracted and possibly manually verified.

b) model checking
software verified via model checking is not certified or formally verified software, as the model checker has to be trusted.

How does the "Java Modeling Language" (JML) compare for verification purposes?

Okay, I think I get it. It is not about software verification, as it is stated that:

The contracts are defined by program code
in the programming language itself, and are trans-
lated into executable code by the compiler. Thus,
any violation of the contract that occurs while the
program is running can be detected immediately.

I cannot find a real example of verification in the above paper, at least not in the sense of model checking or certified software, so I guess they just don't have an emphasis on formal methods.


texts:
Church numerals $\overline{0} = \lambda fx. x$ and $\overline{n} = \lambda f x. f^n x$ are provisions for applying a function $n$ times to an argument. An alternate system of numerals, possibly attributable to Kleene, is $\overline{0} = \lambda x. x$ and $\overline{n+1} = [F, \overline{n}]$, where $[\,,\,]$ represents pairing and $F$ is the boolean value $\textit{false}$.

Can these numerals also be viewed as $n$ applications of a function? More concretely, without using the $Y$ combinator, is it possible to construct a lambda term $t$, such that $t$ applied to the Kleene numeral $\overline{n}$ and lambda terms $f$ and $x$ reduces to $f^n x$?


texts: Help in NP-Hardness proof of a certain type of Class Cover problem

texts:
Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) required to cover the Point Set (S).

Well, covering by Rectangles is proved to be NP-Hard and now, I want to consider a different shape say L-shape and now find out covering by it.

So, can somebody help me in proving that this problem is NP-Hard too. I've worked on it a bit, tried reducing it from known NP-Hard problem but couldn't quite get it.


texts: How many distinct vertices does a random walk visit until it mixes?

texts:
Consider an arbitrary undirected simple connected graph having vertex set $V$ and edge set $E$, and a lazy simple random walk on it.

How many distinct vertices does the random walk visit until it mixes?
(We define the mixing time to be the time the random walk needs to get close to stationarity ($\forall v\in V, \pi(v)=deg(v)/|E|)$).

When a random walk traverses the vertices of a graph it may occur that goes back to already visited vertices. This gets more likely when the walk is trapped in a subset of $V$ with low conductance.

It seems to me that the number of distinct vertices visited by a random walk should be related to the graph's conductance.

The question seems important and preliminary but I can not find anything about it.


texts:
One of my Java projects is a fork of parboiled, and unlike, say, Antlr or JavaCC, parsers are generated at runtime. Grammars generated are Parsing Expression Grammars, or PEGs (I hear another term for them is "packrat").

While the runtime generation adds complexity (bytecode generation involved), another aspect relates to parser theory itself. As I have, unfortunately, no solid background in computer science, I lack theoretical knowledge to map existing code to existing concepts -- in this case, parsers.

Is there a good reference book on parsers which I can purchase and read, or even links on the Internet, which can help me build such a "mapping", accounting for my poor theoretical knowledge?


texts: Row/column overlay problem for filling in a matrix

texts:
I was wondering if the following problem has been studied/has a name:

Given a matrix of numbers (may assume to be integers), find the smallest number of rules which define the matrix. Three kinds of rules may be used:

row rules:     row[i, x] - the value of any cell in row i is x
column rules:  col[j, x] - the value of any cell in column j is x
cell rules:    cell[i, j, x] - the value of cell at [i,j] is x

The rules have a precedence order: first cell rules are considered, then row rules, then column rules.

Example:

Given the 3 x 3 matrix:

2 2 2
1 2 3
1 3 3

one set of rules which describe the matrix is:

row[1,2], col[3,3], col[1,1], cell[2,2,2], cell[3,2,3]

Edit: I would be interested in getting opinions on what the complexity is of this problem. I have a polynomial time algorithm which does well enough for my use cases, but it would nice to know if the general case is not in P.


texts: Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

texts:
Definitions:

Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $B$.

Furthermore consider a lattice $L$ to be all points spanned by positive integer linear combinations of a basis set of vectors $\mathbb{B} = V_1, V_2, ..., V_b$ where $V_i \in \mathbb{R}^n$, so that $L = \{\sum_{i}{c_i \times V_i} | c_i \in \mathbb{Z}^+\}$.

Referenced work:

Random points and lattice points in convex bodies I Bárány et al

Sampling Lattice Points R Kannan et al

Problem:

The above referenced work illustrates how one might randomly sample integer lattice points within the body of a polytope and use the results to approximate the size of the polytope, which is known to be $\#P$ hard to calculate in the general case. Furthermore they give sufficient conditions for when the sampling procedure will output a reasonable approximation (within polynomial factors).

These two papers assume the input lattice is the integer lattice $\mathbb{Z}^n$. For my application, I want lattice points spanned by a separate basis set.

Question:

While the general procedures used in the above papers to sample random integer lattice points seems adaptable to other lattices, the bounds necessary for nearly-uniform sampling may not. Do the same bounds and sampling procedures hold immediately for other basis vectors?

More directly, I am seeking a quick (polynomial time) nearly-uniformal sampling procedure that can output points in $P \cap L$ with inputs $A, B, n, $ and $\mathbb{B}$.


texts: Algorithm to compute distance between powers

texts:
Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$

Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? Also, how do we quickly compute the minimizing $x, y$?


texts:
Let $(A, \leq)$ be a totally ordered alphabet.

The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an inversion of a word $u$ of length $n$ is a pair $(i, j)$ such that $1 \leq i < j \leq n$ and $u_i > u_j$; since permutations are words with some constraints, this definition also works for permutations).

For instance, let $A$ be the alphabet $\{a_i : i \in \mathbb{N}\}$ where $a_i \leq a_j$ if and only if $i \leq j$ and $u := a_3a_1a_4a_2a_5a_7a_4a_2a_3$. Then, we have ${\tt std}(u) = 416289735$.

To compute ${\tt std}(u)$, an obvious and naive algorithm consists in scanning $u$ from left to right $n$ times and assigning during the $i$th run the letter $i$ to the smallest not yet considerer letter. Applying this to the above example, we obtain
\begin{array}
  & & a_3 & a_1 & a_4 & a_2 & a_5 & a_7 & a_4 & a_2 & a_3 \\
    &     & 1   &     &     &     &     &     &     &     \\
    &     & 1   &     & 2   &     &     &     &     &     \\
    &     & 1   &     & 2   &     &     &     & 3   &     \\
    & 4   & 1   &     & 2   &     &     &     & 3   &     \\
    & 4   & 1   &     & 2   &     &     &     & 3   & 5   \\
    & 4   & 1   & 6   & 2   &     &     &     & 3   & 5   \\
    & 4   & 1   & 6   & 2   &     &     & 7   & 3   & 5   \\
    & 4   & 1   & 6   & 2   & 8   &     & 7   & 3   & 5   \\
    & 4   & 1   & 6   & 2   & 8   & 9   & 7   & 3   & 5   \\
\end{array}
showing, assuming that $\leq$ is computable in constant time complexity, that the time complexity of ${\tt std}$ is $\mathcal{O}(n^2)$.

We can do better by using any stable sorting algorithm. The question is what is the best time complexity to compute the standardization of a word ?


texts: Optimization problems with good characterization, but no polynomial-time algorithm

texts:
Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings $x$?

Let us say that such a problem has a minimax characterization, if there is another polynomial-time computable function $g$, such that
$$\max_x f(x) = \min_y g(y)$$ holds. Here $x$ runs over all $n$-bit strings, and $y$ runs over all $m$-bit strings; $n$ and $m$ may be different, but they are polynomially related.

Numerous natural and important optimization problems have such minimax characterization. A few examples (the theorems on which the characterizations are based shown in parenthesis):

   Linear Programming  (LP Duality Thm),   Maximum Flow   (Max Flow Min Cut Thm),   Max Bipartite Matching   (Konig-Hall Thm),   Max Non-Bipartite Matching   (Tutte's Thm, Tutte-Berge formula),   Max Disjoint Arborescences in directed graph   (Edmond's Disjoint Branching Thm),   Max Spanning Tree Packing in undirected graph    (Tutte's Tree Packing Thm),    Min Covering by Forests   (Nash-Williams Thm),   Max Directed Cut Packing   (Lucchesi-Younger Thm),   Max 2-Matroid Intersection   (Matroid Intersection Thm),   Max Disjoint Paths   (Menger's Thm),   Max Antichain in Partially Ordered Set   (Dilworth Thm), and many others.

In all these examples, a polynomial-time algorithm is also available to find the optimum. My question:

  Is there any optimization problem with a minimax characterization, for which no polynomial-time algorithm has been found so far?

Note: Linear Programming was in this status for about 30 years!


texts: Is the following optimization problem (another variant to a previous problem) NP-hard?

texts:
This problem is a following up question on  this one. The only difference is the addition of $3^{rd}$ constraint "$\sum_{i} x_{ij} \le M$", where M is a constant number. This constraint essentially states that each "node" can only take M incoming edges at most.

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$ and is also a transitive closure, is given. E.g. $S=\{(1,2), (2,3), (1,3), (2,4), (1,4)\}$. For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$
$$\sum_{i} x_{ij} \le M$$

Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.


texts: Determination of maximum number of incoming transitions to a state in any trace-equivalent representation of an LTS

texts:
Suppose $L$ is a labelled transition system (LTS). Suppose that the function $maxIn(L)$ (LTS $\rightarrow$ integer) returns the number of incoming transitions to the state of $L$ that has the most incoming transitions of all states of $L$. So, for example, if $L$ is a tree with the root as its only initial state then $maxIn(L) = 1$.

Now suppose that $traceEq(L)$ denotes the set of LTS that are trace equivalent to $L$. So if $L1, L2 \in traceEq(L)$ and $L1 \neq L2$ then $L1$ and $L2$ are not topologically isomorphic but have the same set of traces as $L$. Note that $L \in traceEq(L)$.

Given an LTS $L$ is there any algorithmic way of determining the value of $min_{L' \in  traceEq(L)} maxIn(L')$ ? The case of interest is where all the members of $traceEq(L)$ are finite, so that a cycle in $L$ cannot be unwound and represented by an infinite sequence of states.


texts: Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

texts:
During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke.
In chapter 10 (pdf available on the above site), section 10.2.2. he shows a lower bound of $\Omega\left(n^{3/2}\right)$ on the number of guards needed in three-dimensional art gallery guarding. He says (bold marking is by myself):

  In fact, we describe in this section a polyhedron constructed by Seidel that has these two properties.

I believe that the construction, as presented in the book, is not fully correct and thus I tried to find the original work by Seidel.
Sadly there is no reference in this section and the only reference in the book with Seidel is Constructing Arrangements of Lines and Hyperplanes with Applications by H. Edelsbrunner, J. O’Rourke, and R. Seidel which does not include the construction.

I have looked through Seidels Google Scholar page but there seems to be nothing relevant.

Do you have a source or know anything more about this construction?
What could be a good and accepted way for me to obtain information? Contacting either of the two?


texts:
Let $F = C_1 \wedge C_2\; \wedge ... \wedge\; C_m$ be a unsatisfiable $k$-CNF on variables $x_1,...,x_n$, where $k$ is constant.

Let $x_j\rightarrow x_j^1\wedge x_j^2$ be a substitution that replaces each variable $x_j$ in with the conjunction $x_j^1\wedge x_j^2$, where $x_j^1$ and $x_j^2$ are two new variables. Let $G$ be the formula which is obtained from $F$ by applying the substitution above to all variables, and then converting it back to a CNF formula.

Clearly, $F$ is unsatisfiable if and only if $G$ is unsatisfiable. Additionally, $G$ is a $O(k)$-CNF with at most $2^{k}\cdot m$ clauses,
since intuitively each clause of F is expanded into at most $2^{k}$ clauses.

Question: Suppose we have a resolution refutation $P$ for $F$ of size $s$. Can $P$ be converted into a resolution refutation for $G$ of size $s^{O(1)}$?

I feel that there might be a standard trick for getting such conversion but I couldn't find any reference. The idea I had in mind was to apply the substitution on each clause appearing in the proof, and then use the fact that resolution is implicationally complete.  But this would only work for refutations of small width, since each clause of width $r$ may be get expanded into up to 2^r clauses.

References or suggestions are very welcome.


texts: True Bit Complexity of matrix multiplication is $O(n^{4})$

texts:
Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry of both matrices being multiplied) of size $m$ bits, the addition operation actually happens on $O(n^{3}nm) = O(n^{4}m)$ bits.

So it seems that the true complexity of matrix multiplication if measured via bit complexity should be $O(n^{4})$.

$(1)$Is this correct?

Supposing if one creates an algorithm which reduces the bit complexity to $O(n^{3+\epsilon})$ rather than total multiplications and additions, this might be a sounder approach than say reducing the total multiplications and additions to $O(n^{2+\epsilon})$ as attempted by researchers such as Coppersmith and Cohn.

$(2)$ Is this a valid argument?


texts: Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$

texts:
For each #$k$SAT instance one can build a matrix $A$ such that $\mathrm{perm}(A) = F(\Sigma)$, where $\Sigma$ is the solution count of the $k$SAT formula and $F$ an easy to invert function.

My question is whether there is a similar reduction in the opposite direction: given an integer valued matrix $A$ with $\mathrm{perm}(A)>0$, is there a systematic way to build a #$k$SAT formula such that $\Sigma=F(\mathrm{perm}(A))$, where $F$ an easy to invert function?


texts:
The problem of finding the pair of closest points in a set of points has been a classical example of divide and conquer technique for some decades now. But I could not find any results on finding $k$th closest pair of points; that is the $k$th pair $(p_i, p_j)$ in the list of pairs of distinct points from set $P$, sorted in increasing order of distance.

I could not find anything on that. Do we have any results? More particularly, I am interested in the case of points from a Euclidean plane.


texts:
Consider 2 graphs G1 and G2.
G1: Any non-regular graph.
G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the number of nodes in the graph).
We run a lazy random walk on G1, such that the random walk at a node $v$ either stays at $v$  with probability $1/2$ or moves out to a neighbor with probability $1/2d_{v}$, where $d_{v}$ is the degree of the node $v$. Consider, $t_{mix}$ as the mixing time of this random walk. Additionally, we maintain a queue where the starting node of the random walk is added to a queue, and thereafter each time the random walk jumps to a neighbor, the node it jumps to is added to the queue. Let the queue contain $k$ nodes when the random walk has mixed $(k<= t_{mix})$. Note that since the graph is non-regular the stationary distribution that it converges to is non-uniform.
Now, consider another random walk on G2, which chooses each edge with probability $1/d_{v}$, where $d_v$ is the degree of node $v$ including the self-loops. Assume that this random walk exactly follows the previous random walk (on G1) in the sense that each time there is a jump to the neighbor, it jumps to the same neighbor as the previous walk, i.e., it will push the exact same nodes to its maintained queue. When we consider time, of course, this would be slower as, in low-degree nodes, the random walk would have to undertake many self-loops before being able to jump to a neighbor.  What I want to show that, is when the queue contains $k$ nodes or ($O(k)$ nodes), then this random walk has also mixed. Note that, as opposed to before, the stationary distribution here with respect to which we want the mixing is uniform (due to the added self-loops).
Is there any existing work that shows this? Or if not, what can be a good coupling argument to prove this? Any reference or help would be greatly appreciated.
(Observe that, the random walk on G2, can also be considered as another (biased) random walk on G1 where the random walk stays at the current node $v$ with probability $1-(deg(v)/n)$ and, with probability $1/n$, moves to a uniformly at random chosen neighbor.)


texts: Complexity of convolution in the max/plus ring

texts:
We can do convolution in $O(n\log n)$ for plus/multiply polynomials with FFT.  However, the approach doesn't seem very generalisable to rings in general.
Has there been any progress over the naive $O(n^2)$ convolution for the max/plus ring?

I should note that one can transform soft-max/plus into plus/product by doing exponentiation. Here $\text{soft-max}(x,y)=\log(e^x+e^y) = \max(x,y)  + \log(1+e^{\min(x,y)-\max(x,y)})$.


texts: Are runtime bounds in P decidable? (answer: no)

texts:
The question asked is whether the following question is decidable:

  Problem  Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input length $n$ ?

A narrow answer of "yes", "no", or "open" is acceptable (with references, proof sketch, or a review of present knowledge), but broader answers too are very welcome.

Answer

Emanuele Viola has posted a proof  that the question is undecidable (see below).

Background

For me, this question arose naturally in parsing Luca Tevisan's answer to the question Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?

The question relates also to a MathOverflow question: What are the most attractive Turing undecidable problems in mathematics?, in a variation in which the word "mathematics" is changed to "engineering," in recognition that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Thus, the broad objective in asking this question is to gain a better appreciation/intuition regarding which practical aspects of runtime estimation in the complexity class P are feasible (that is, require computational resources in P to estimate), versus infeasible (that is, require computational resources in EXP to estimate), versus formally undecidable.

--- edit (post-answer) ---

I have added Viola's theorem to MathOverflow's  community wiki "Attractive Turing-undecidable problems".  It is that wiki's first contribution associated to the complexity class P; this attests to the novelty, naturality, and broad scope of Viola's theorem (and IMHO its beauty too).

--- edit (post-answer) ---

Juris Hartmanis' monograph Feasible computations and provable complexity properties (1978) covers much of the same material as Emanuele Viola's proof.