texts:
I am trying to understand some concepts about Modular decomposition and Clique-width graphs.

In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-number or chromatic-number using Modular decomposition.
Solving these problems by composing (using disjoint sum or disjoint union) two graphs G1,G2 is easy when you know the answer for G1 and G2. Since the prime-graphs on the decomposition of P4-tidy graphs are bounded graphs (i.e. C5,P5,etc.), it is easy to solve it for these "base case" and then solve it for compositions.
Hence by using the decomposition tree it is possible to solve these problems in linear time.

But it seems that this technique would work with any graph class such that graph-primes are bounded.
Then I found this paper "Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width" which seems to make the generalization I was looking for but I couldn't understand it very well.

My question are:

1- Is equivalent to say that prime-graphs of the decomposition tree are bounded (like in the P4-tidy graphs case) and say that a graph has the property "Clique-Width" bounded?

2- In case the answer for 1 is NO, then: Does exists any result about classes of graphs with graph-primes bounded (like in P4-tidy graphs) and thus optimization problems like clique-number solvable on linear time on all these classes?


texts: If the untyped language is terminating, can we still derive a contradiction from `Type : Type`?

texts:
Question

If a pure type system has a terminating proof language, can we have Type : Type at the logic level without causing paradoxes (i.e., without causing ∀ (x : *) -> x to be inhabited)?

Example

Suppose we take a pure type theory such as the Calculus of Constructions, restrict functions to be affine (at most 1 variable uses) and add constructs for stratified duplications - see here for details. That language - which we could call EACC (Elementary Affine Calculus of Constructions) has a normalizing untyped fragment. That is, the reduction of any term - even ill-typed ones - is guaranteed to terminate due to the reduction rules (and, in particular, the restriction that duplicated terms can not change their levels).


texts: Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

texts:
Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold?

Schwartz-Zippel lemma applies here since it holds for general fields and $\Bbb Z\subset\Bbb Q$ and there is an efficient randomized algorithm for this problem.

We expect this problem to have efficient derandomization.

What is the consequence if this problem does not have an efficient derandomization?


texts: How hard is it to compute an approximately optimal non-greedy CART tree?

texts:
The question itself is closer to the bottom of this post, and

is formulated without any rerefence to the term "CART".

Motivation:
In traditional CART (Classification and Regression Trees), one simply chooses the locally-optimal question at each step. $\:$ However, it is not obviously the case that doing so produces a

globally-optimal tree of questions. $\:$ In formalizing this problem, attributes with a canonical

total order do not pose any issues; the nodes are allowed order-comparisons and nothing else.

The two issues I see are attributes without a canonical total order (categorical attributes), and what trees are allowed. $\:$ One possibility for categorical attributes is to allow the nodes to apply a circuit of bounded size; however, the feasibility or lack thereof in that case is likely to depend on cryptographic assumptions. $\:$ Instead, I will require that the input come with an explicit list of the tests that a single node is allowed to apply to a given categorical attribute. $\:$ Since the number of values of each totally-ordered attribute is at most the number of data-points, one can in that case convert an instance so that all attributes will be categorical. $\:$ After doing that, the number of allowed tests per attribute is at most the total number of allowed tests, so one can convert an instance so that all attributes are binary (with the bits given by the responses to each of the allowed tests), and one no longer needs to worry about what tests are allowed.

The other issue was what trees are allowed. $\:$ Since I have no idea how one would weight
depth vs. number of nodes, I will keep things simple and require that the trees be perfect.

  Actual Question: $\:$ Is there an additive-error PTAS for the following minimization problem?

Inputs: $\:$ a positive integer S that is given in unary, a positive integer n,

and a non-empty list of binary vectors whose lengths are all n+1,

Well-Formed Outputs: $\:$ a perfect binary tree of depth d that has each non-leaf node labelled with an element of {0,1,2,3,...,n-2,n-1}, where d is the greatest integer that satisfies 2^d ≤ S

Value of a Well-Formed Output: $\:$ the conditional entropy of the last entry of V (which is V[n])

given the leaf-node that one ends at when going out from the root along the edges indicated

by V[current_node's_label], where V is chosen uniformly from the list of vectors in the input


texts: What are the classic papers from the recursion theoretic area of complexity theory?

texts:
Two papers I would include are:

D. Kozen, "Indexing of subrecursive classes", STOC, 1978.
R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.


texts: Quantum algorithms for QED computations related to the fine structure constants

texts:
My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like series $$\sum c_k\alpha^k,$$ where $\alpha$ is the fine structure constant (around 1/137) and $c_k$ is the contribution of Feynman diagrams with $k$-loops.
This question was motivated by Peter Shor's comment (about QED and the fine structure constant) in a discussion regarding quantum computers on my blog. For some background here is a relevant Wikipedea article.
It is known that a) The first few terms of this computation gives very accurate estimations for relations between experimental outcomes which are with excellent agreement with experiments. b) The computations are very heavy and computing more terms is beyond our computational powers. c) At some points the computation will explode - in other words, the radius of convergence of this power series is zero.
My question is very simple: Can these computations be carried out efficiently on a quantum computer.
Question 1

1):  Can we actually efficiently compute (or well-approximate) with a quantum computers the coefficients $c_k$.
2) (Weaker) Is it  at least feasible to compute the estimates given by QED computation in the regime before  these coefficients explode?
3) (Even weaker) Is it  at least feasible to compute the estimates given by these QED computation as long as they are relevant. (Namely for those terms in the series that gives good approximation to the physics.)

A similar question applies to QCD computations for computing properties of the proton or neutron. (Aram Harrow made a related comment on my blog on QCD computations, and the comments by Alexander Vlasov are also relevant.)  I would be happy to learn the situation for QCD computations as well.
Following Peter Shor's comment:
Question 2

Can quantum computation give the answer more accurately than is possible classically because the coefficients explode?

In other words

Will quantum computers allow to model the situation and to give
efficiently approximate answer to the actual physical quantities.

Another way to ask it:

Can we compute using quantum computers more and more digits of the
fine structure constant, just like we can compute with a digital
computer more and more digits of e and $\pi$?

(Ohh, I wish I was a believer  :) )
more background
The hope that computations in quantum field theory can be carried our efficiently with quantum computers was (perhaps) one of Feynman’s motivation for QC.  Important progress towards quantum algorithms for computations in quantum field theories was achieved in this paper: Stephen Jordan, Keith Lee, and John Preskill  Quantum Algorithms for Quantum Field Theories. I don't know if the work by Jordan, Lee, and Preskill (or some subsequent work) implies an affirmative answer to my question (at least in its weaker forms).
A related question on the physics side
I am curious also if there are  estimations for how many terms in the expansion before we witness explosion. (To put it on more formal ground: Are there estimates for the minimum k for  which $\alpha c_k/c_{k+1} > 1/5$ (say).) And what is the quality of the approximation we can expect when we use these terms. In other words, how much better results can we expect from this QED computations with an unlimited computation power.
Here are two related questions on the physics sister site. QED and QCD with unlimited computational power - how precise they are going to be?; The fine structure constant - can it genuinely be a random variable?


texts:
Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in $\mathsf{RNC}$. Is anything known about containment in either $\mathsf{L}$ or $\mathsf{NL}$?

Such a bound seems unlikely for the space-complexity of s-t minimum cut given that maximum flow is $\mathsf{P}$-complete.


texts:
In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be polynomial-time solvable if $k > \sqrt{n}$ and conjectured hard for $k< \sqrt{n}$.

My question is: what is known/believed about other values of $p$? Specifically, when $p$ is a constant in $[0,1]$? Is there evidence that, for every such value of $p$, there exists some $k=n^{\alpha}$ for which the problem is computationally hard?

References would be particularly helpful, as I haven't succeeded in finding any literature which looks at the problem for values other than $p=\frac{1}{2}$.


texts: Definition of matrix-multiplication exponent $\omega$

texts:
Colloquially, the definition of the matrix-multiplication exponent $\omega$ is the smallest value for which there is a known $n^{\omega}$ matrix-multiplication algorithm. This is not acceptable as a formal mathematical definition, so I guess the technical definition is something like the infimum over all $t$ such that there exists a matrix-multiplication algorithm in $n^t$.

In this case, we cannot say there is an algorithm for matrix-multiplication in $n^{\omega}$ or even $n^{\omega + o(1)}$, merely that for all $\epsilon > 0$ there exists an algorithm in $n^{\omega + \epsilon}$. Often, however, papers and results which use matrix-multiplication will report their cost as simply $O(n^{\omega})$.

Is there some alternate definition of $\omega$ that permits this usage? Are there any results that guarantee that an algorithm of time $n^{\omega}$ or $n^{\omega + o(1)}$ must exist? Or is the usage $O(n^{\omega})$ simply sloppy?


texts: How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?

texts:
In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July.
Several of the attendees argued that we should use GCT to attack easier problems than $\mathsf{P}$ vs. $\mathsf{NP}$ in order to build intuition and see if the method has potential.

The question that has been bugging me:

  Is it possible to use GCT to show known separations like $\mathsf{P} \neq \mathsf{EXP}$ or $\mathsf{L} \neq \mathsf{PSPACE}$?

Does something like $\mathsf{L} \neq \mathsf{PSPACE}$

Not even make sense in the GCT context, or
Is utterly trivial and uninteresting in GCT framework, or
Lead to conjectures just as hard as $\mathsf{P}$ vs. $\mathsf{NP}$  ?


texts:
This is probably pretty simple, but consider the standard Post Correspondence Problem:

Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find a sequence of indices $i_1, \ldots, i_K$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$. This is, of course, undecidable.

Now, I call this a 'variant', but it's not really--it essentially throws away 'correspondence'. Anyway, consider the following variant:

Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find two sequences of indices $i_1, \ldots, i_K, j_1, \ldots, j_{K}$ such that $\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$. What can be said about this variant? If this is trivial, my apologies!


texts: Girth of graphs that decompose into two disjoint union of spanning trees

texts:
Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees.  In particular, $G$ has $2n-2$ edges.

It is not hard to show that the girth of $G$ is at most $O(\log n)$.  However, I don't have an example with girth bigger than $4$.

  Do we have an example of such graph whose girth is $\Theta(\log n)$, or is there a way to prove an even better upper bound?

I wonder if there are constant degree expanders that, after removing an appropriate number of edges, can be decomposed into two disjoint union of spanning trees.


texts: Fast extraction of pairs overlapping an interval

texts:
I am trying to find a fast algorithm to extract pairs that overlap with a specified interval.

Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 <= x2, (you can imagine them two points on the x-axis or on a timeline to visualise the problem better). Provided 2 other values V1, and V2, also assuming V1 <= V2, I want to extract the set of all pairs that satisfy at least one of the following criteria.

V1 <= x1 <= V2
V1 <= x2 <= V2
x1 <= V1 <= V2 <= x2

So intuitively what I need to extract is all interval pairs that overlap with V1 and V2, either partially (criteria 1 and 2) or completely (criteria 3).

I wish to find a fast way to extract them (I know this depends on how large the interval between V1 and V2 is). The solution I came up with so far is organising the pairs in a balanced binary search tree sorted with just x1 and traversing it for items that are x1 <= V2, and then checking the rest of the criteria as I am traversing the tree. I could also enhance it by adding another binary search tree sorted by x2 of the same pairs, and traversing similarly for pairs x2 >= V1, and maybe using this tree instead when the V1, V2 interval is biased towards the right of the midpoint of the whole range of values of the pairs.

Is there any better idea how I could achieve this? It seems I can only get O(n) complexity.


texts: putting objects in buckets -- optimization problem

texts:
Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let
$$
E: \mathcal O \times \mathcal B \to \mathbb{R}_{>= 0}
$$
be a function.  Is there an algorithm that, given a partition of $| \mathcal B |$,
$$
| \mathcal B | = \sum_{b \in \mathcal{B}} \mu_b
$$
returns a function $\varphi: \mathcal O \to \mathcal B$ maximizing the quantity
$ \sum_{o \in \mathcal O} E(o, \varphi(o))$, subject to the constraint that $| \varphi^{-1} (b)| = \mu_b$ for all $b \in \mathcal B$?

Motivation: all objects need to be put into a bucket, but the buckets have different sizes.  The function $E$ gives the value of placing a given object in a given bucket.  If the buckets each have a certain capacity, how can an optimal distribution of objects in buckets be found?


texts:
Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$.

The question is to decide, given $\{A_1, \dots, A_m\}$ and a natural number $k$ in binary, whether there exists a word $w$ over $\{1, \dots, m\}$ whose length is bounded by $k$ such that
$[A_w]_{1,1}>0$.

This problem is decidable, but its complexity is not clear to me. In particular, is it in PSPACE? (Note that because $k$ is given in binary, one cannot just guess a word $w$ in PSPACE.)


texts: Can machine learning algorithms be trained to discard nonsense?

texts:
Afaik, the problem with many machine learning algorithms is that they will often label nonsense into some categories.

What measures can one take to discard nonsense results?

Eg. if you have a bot that is supposed to label stuff as either orange or an apple, how can you gurantee that it won't label a random image of noise as either of the two?

Or label a car as either of the two?

Do you have to train your neural network to have 3 categories, "apple", "orange" and "neither"?


texts:
Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$.

Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \leq k$.

How many locally sorted sequences of degree $k$ are there for $n$ elements? Hopefully, there will be a better approach than "enumerate all possible sequences and check each one".

I wasn't sure how to approach this problem, so I tried proofing results for various values of $k$. I solved this for $k=1$; it's just a Fibonacci sequence. $k=2$ is a lot more difficult to me. I keep overcounting.

For handiness, here's some Python code to use when checking results:

from itertools import permutations
def check(seq, k):
    for i in range(0, len(seq)):
        index = i+1
        if abs(seq[i] - index) > k: return False
    return True
n = 5
k = 2
orig = [ i+1 for i in range(0,n) ] # easier if we use sequences of integers
check_count = 0
for perm in permutations(orig):
    if check(perm,k):
        check_count += 1
print(check_count)


texts: Average-degree Bounded Graphs are no harder than Maximum-degree Bounded Graphs (for distance oracles with purely multiplicative stretch)

texts:
I'm trying to understand a specific part from an article of Agarwal and co.
It is about Distance Oracles but there is a specific explanation of How to convert from average-degree graph to maximum-degree bounded graph with linear complexity.
I can't understand it so I need a simple language explanation...
This is the link to the article: http://arxiv.org/pdf/1201.2703.pdf and the specific explanation is in section 5.
From the article: (I don't understand the reduction)

Let G = (V, E) be a connected graph with average degree ∆. Given G, we
will first create a ∆-degree bounded graph G∆ = (V∆ , E∆ ). Then, we
show how can be used on G∆ to return stretch-s paths on G.
The Reduction: For each node v ∈ V , create α v = ⌈deg(v)/∆⌉ nodes v1 , v2
, . . . , vαv in V∆ . For each edge e = (u, v) ∈ E, if deg(u) ≤ ∆ and
deg(v) ≤ ∆, create an edge e = (u1 , v1 ) in E∆ . For each node v ∈ V
, we arbitrarily distribute N (v) in G to the nodes corresponding to v
in G∆ such that for i = 1, 2, . . . , (α v − 1), |N (v) ∩ N (vi )| = ∆
and |N (v) ∩ N (vαv )| = (deg(v) − (α v − 1) · ∆). Finally, for each
pair vi , vi+1 , we create an edge in E∆ of weight 0.
In order to answer an approximate distance query for any pair of nodes u, v ∈ V , we use D to answer approximate distance queries between u1 , v1 ∈ V∆
in G∆ and let the length of the path returned by the data structure be
δ′ . We output the distance δ′ as an approximate distance for the pair
of nodes in G.

Thanks!


texts:
The following fact seems to be used implicitly in cs theory, particularly algorithms. Given a RAM machine $M$ running in time $O(f(n))$, another RAM machine $M'$ can simulate $M$ in time $O(f(n))$. This differs from the case for Turing machines, where $M'$ may require $O(f(n) log(f(n))$ time.

I say this is often used implicitly because many papers will simply say something like "run $M$, but keep track of certain auxiliarily information as you do so". This is really simulating $M$, but for RAM machines the distinction is not so important because running times are not (asymptotically) affected.

Is there a reference for this theorem? I am summarizing the situation correctly?


texts: What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

texts:
I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson.  Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$.  They define a family of functions $G = \{G_n : B^{l(n)} \to B^n\}$ to be pseudorandom in case for every circuit of size $n$ we have

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(where $x \in B^{n},y \in B^{l(n)}$ are uniform random variables).

I understand that I am to think of $x$ and $y$ as random variables, and that I want to compare the distance between $x$ and $G(y)$ as random variables.  I get the intuition that circuits are being used as sort of "tests" in to see if $G$ can be "figured out."  What I am really struggling with is why the condition $(*)$ is the right one.  Does anyone have any advice on how to think of this definition?


texts:
I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be proved using quantum tools. A survey Quantum Proofs for Classical Theorems (A. Drucker, R. Wolf) gives a nice list of such problems, but surely there are many more.

Particularly interesting would be examples where a quantum proof is not only possible, but also "more illuminating", in analogy with real and complex analysis, where putting a real problem in the complex setting often makes it more natural (e.g. geometry is simpler since $\mathbb{C}$ is algebraically closed etc.); in other words, classical problems for which quantum world is their "natural habitat".

(I'm not defining "quantumness" here in any precise sense and one could argue that all such arguments eventually boil down to linear algebra; well, one can also translate any argument using complex numbers to use only pairs of reals - but so what?)


texts: Typing relations terminology – how do I read typing relations?

texts:
I am currently trying to read up on type theory and have some quick questions on terminology.

In the following rule,

$$
\frac{x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$

How would you write that in English? Would the following be correct?

  If we have established that under the assumption that $x$ has type $T_1$, $t_2$ has type $T_2$; then we can derive that under the empty set of assumptions, $\lambda x.t_2$ has type $T_1\to T_2$.

Is this just a shorthand for the following?

$$
\frac{\Gamma,x:T_1 \vdash t_2 : T_2}{\Gamma\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$

Would this be read as If we have established that under the assumptions of the type environment $\Gamma$ and the binding $x:T_1$, that $t_2$ has type $T_2$; then [$\ldots$]?


texts: Improved lower bounds or upper bounds on union-find structures since Tarjan?

texts:
In 1979, Robert Tarjan published "A Class of Algorithms Which Require Nonlinear Time To Maintain Disjoint Sets", which proved an upper bound of $O(m \alpha(n))$ time on the time complexity of performing $m$ operations on a disjoint-set forest with union-by-rank and path compression, assuming there are $n$ nodes. He also proved a matching lower bound on any data structure for this problem in a pointer machine.

Since this paper was published, has anyone devised an data structure that runs in $o(m \alpha(n))$ for this problem? (Such a data structure would have to rely on techniques that don't work on a pointer machine.) Or are there any new lower bounds on non-pointer-machines?


texts: Under what conditions is the Dining Philosophers Problem unsolvable?

texts:
The wikipedia article for the Dining Philosophers Problem lists some solutions which are dependent on external information, i.e.:

Numbering of forks
A waiter to act as mutex
Messaging between philosophers

If we restrict the problem to the bare essentials, i.e.:

No information encoded in the table/forks
No prior meeting between philosophers, and hence no ordering/numbering
No communication between philosophers at the table

Is it provably impossible for every philosopher to have a strategy that avoids deadlock/starvation?  Is there a good understanding of the "minimal" conditions necessary for a solution to exist?


texts: Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an approximation.


texts: Has there been a study of circuits operating on arrays?

texts:
Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any boolean function). One can consider families of these for different input sizes as opposed to general Turing machines, and consider the languages they accept or functions they compute (if they have multiple outputs); one can reason regarding their size and depth as a function of the input length; define the classes of languages acceptable by them with certain restrictions; study their composition; etc.

I've also been introduced to the Blum-Shub-Smale computational model, where the constituent operations of a program have elements of a field (e.g. the Rationals or the Reals) as inputs and outputs; and such a machine can be likened to a circuit if it has no loops or similar control structures. It's been the subject of much less theoretical literature, but I can still find tens of thousands of papers referring to the "BSS Model". And there are arithmetic circuits (with only + and * gates) which I vaguely recall from my Complexity Theory class as an undergrad (proofs about #P and PSPACE where boolean circuits get "arithmetized" -  AND into * and OR into +, with the inputs still being boolean).

But - what about circuits which operate on more complex units of data? That is, arrays of unbounded finite length - with the individual elements either all of some single type or from some vocabulary of types? Obviously, you might want to constrain the nodes in such circuits, as otherwise they would just be Turing machine or circuit families in themselves, but this is still a relevant kind of automaton to study these days - with programming models such as CUDA and OpenCL which apply these kinds of operations on very large amounts of data, controlled at the level of the entire kernels and their dependencies.

So - have circuits-operating-on-array seen any theoretical study? I've failed to find any such work so far.

Note: RAM/register machines in which registers or individual memory cells contain arrays would be a next best thing.


texts: Any resources describing an OS assigning process priority via distance to HD head?

texts:
During the introductory computer organization class I recently took, the professor described the limitations of seek time in reading or writing to the disk. He suggested a solution whereby the operating system would prioritize the process whose sectors were then closest to the head. In that case, it could move smoothly back and forth rather than jerking to an arbitrary track where the process' data lies. (I guess this assumes a full drive or an even distribution.)

Warford's Computer Systems doesn't mention anything similar and the professor is on vacation. I am curious whether this is just a thought experiment (like bogo sort) or has someone attempted this strategy? Any resource welcome; thanks


texts:
My questions:

What are other names for this and similar problems and their fields? ("equivalence of varieties in universal algebra", "equivalence of algebraic structures", "rewriting systems for searching equivalence"?)
what algorithms do you know solving this kind of problems?
What papers/books do you recommend?

Problem

I'm interested in approaches of finding, whether two computations are equivalent?

I try to find my way between rewriting systems, automated theorem proving, logic programming, varieties, or just visiting graph of all possible basic block transformations (in order to find corresponding vertices (with some luck ;) ) ).

Of course. In finite domains, I could enumerate all possible inputs for all possible symbols permutations, check whether computations gives same results, and do this in finite time. I am looking for other approaches.

Computations

Computations are given as basic blocks represented in SSA - static single assignment form. We can assume finite number integer arithmetic (for example 64bit numbers). Computations run in RAM model.

For those not familiar with compilers theory and design, Basic Block has no jumps, no loops, no function call, one exit, and one entry etc. So we can say, that each execution of BB has O(1) complexity.

SSA - static single assignment form of basic block is DAG (Direct Acyclic Graph). In that sense, there is similar question on TCS.SE about unification theory and DAG isomorphism, while my context, focus, purpose and approach is different.

Equivalence

Let me be more specific what I mean by equivalence of computations. Let's take following setup:

two computations $f$ and $g$ and treat them as functions.
$P$ is a vector of $f$'s parameters $p_1, p_2, \ldots, p_n$
$P' = \operatorname{perm}(P)$ is permutation of parameters.

By equivalence, I mean, there exist permutation $P'$ that for any inputs $P$ , we have $f(P) = g(P')$ same (vector of) results in both computations.

Another equivalence definition

I've just found, definition of basic block equivalence, very similar to mine. I hope it might clarify, what I mean by that.

Let me cite from C Decompilation: Is It Possible? by Katerina Troshina, Alexander Chernov and Yegor Derevenets:

  Let $f$ be an object renaming transformation (...) $f(C_1) = C_2$ if there exists a renaming of named objects such as registers, labels, etc, preserving program semantics and making the programs $f(C_1)$ and $C_2$ syntactically indistinguishable. Existence of such an f transformation is a sufficient condition of program equivalence. (...) Equivalence of basic blocks may be checked by reducing them to a RISC-like representation. Let $h$ be a basic block reduction transformation. Let $B_1$ and $B_2$ be basic blocks, let $B'_1 = h(B_1)$ and $B'_2 = h(B_2)$ be the corresponding basic blocks in the RISC-like representation. Let $g$ be an instruction reordering transformation preserving the program semantics. If for the basic blocks $B_1$ and $B_2$ there exist transformations $f$ , $g$ and $h$ making $g(f(h(B_1))$ and $h(B_2)$ syntactically indistinguishable, basic blocks $B_1$ and $B_2$ are equivalent.

Although, their approach is more focused on assembly code, my approach is more in direction of path-algebra for algorithm pattern matching. What it implies, I'd like to take into account, not only instruction reordering, but equations they represent as well. (Simple example : $(a + b) / 2$ is different to $a / 2 + b / 2$ on $k$-bits integer computations - modular arithmetic. When $a + b \ge 2^k$ results are different. While algorithms, authors/implementators intentions might be the same. That's why I'd like to mix approaches from different fields).


texts:
Two related questions about bounded depth computing:

1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem simpler we can assume that all p(i)s are 0,1, or 1/2. or even that all of them are 1/2.)

Now you make a bounded number of computation round. In each round you apply reversible classical gates on disjoint sets of bits. (Fix your favorite set of universal classical reversible gates.)

At the end you get a probability distribution on strings on n bits. Are there results on restriction of such distributions?

I am looking to something analogous to Hastad switching lemme, Boppana result that the total influence is small or LMN theorem.

2) The same question as 1) but with bounded depth quantum circuits.


texts: Trace minimization with an orthogonality constraint

texts:
For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:

that $X$ is orthogonal.

All the matrices have real entries and $A,B$ are square while $X$ is rectangular. Thanks.

This is what I have:

Define $B=F^{T}F$. Define $Y=FX$. You get the above problem as
\begin{align}
\min_{Y}~ \text{trace}(AY^{T}Y)
\end{align}

But now I want $X^*$ that minimizes the original problem. This is what is confusing me!


texts: Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

texts:
Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such isomorphic subtree in $T_2$.

  What is known about the complexity of this problem?


texts: Calculate Huffman code length having probability?

texts:
Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will the longest encoded symbol have? How many encoded symbols will have same length?

I try to imagine a Huffman tree for it, but it does not appear to make much sense, as trees for Huffman encoding aren't always balanced (so I can't use tree's height to calculate this I guess). I know that at least two least-probable symbols will have longest codings, but how to relate element's probability with its Huffman code length? Or maybe there is some other way to calculate it?


texts: Counting the number of satisfying assignments in a POSITIVE CNF-SAT

texts:
We know the problem of counting the number of satisfying assignment in a given general boolean formula (CNF-SAT), a given DNF formula, or even a given 2SAT formula is a #P-complete problem.

Now, consider a CNF-SAT with no negative literal (no $\neg A$, always $A$). The decision problem is very easy (set all of the variables to TRUE and check if the assignment is satisfying the formula), but what about counting the number of satisfying assignments? Does this have a polynomial time algorithm? Or it's a #P-complete problem.


texts:
How does hardness plays role in testability?

Intuitively, it seems that for the problems which have exact efficient algorithm, there is more hope to get constant query (or, relatively a small number of queries) testing algorithm (in property testing framework).

But here is the counterexample, testing if a graph is $k$-colorable
(which is a hard problem) there is a constant query testing algorithm (see paper), while for testing if given numbers are sorted $O(\frac{1}{\epsilon}\lg n)$ queries are required (see paper) .

So, does hardness plays any role in testability, or is completely orthogonal to it?


texts: Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

texts:
Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability.

Result 2: The $\mathsf{PARITY}$ has its fourier weight concentrated on the co-efficient of degree $n$.

Question: Is there a way to prove(if provable) $\mathsf{PARITY}$ is not computable by $\mathsf{AC}^0$ circuits via/using the results 1 and 2 ?


texts: Generating set of a group and relation to diameter?

texts:
Is there an efficient algorithm to test if a given subset of symmetric group generates the symmetric group?
Drawing the Cayley graph and testing for all pairs reachability is one way however that scales in the size of the group.
Is there a relation between maximum distance between generating elements where distance betwee two elements of generating elements is with respect to transpositions and diameter of Cayley graph of the group with respect to the generating set?


texts: Approximation ratio for covering n points in d dimensions

texts:
What is best known approximation ratio for the following problem :

Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a point , if the point lies on the line .


texts: Recovering a rank-one matrix from its eigendecomposition after randomized rounding

texts:
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ with probability } A_{ij} \\ 0 & \mbox{ with probability } 1-A_{ij} \end{cases} $$

Is it possible to recover $x$ by looking at the principal eigenvector of $A_{\rm rounded}$? In other words, suppose $v$ is the principal eigenvector of $A$; is it true that, after rescaling $v$ and $x$ to have unit norm, the two vectors are nearly the same? In particular, can one show that $P( || \frac{x}{||x||_2} - \frac{v}{||v||_{2}} ||_{\infty} \geq \epsilon)$ goes to zero for any $\epsilon > 0$ as $n \rightarrow \infty$?

I wrote a quick MATLAB simulation that suggests the answer is yes. Here is my code:

  n=20000; %matrix size

  %generate matrix;

  x = rand(n,1);

  y = rand(n,1);

  A = x*y';

  %generate rounded matrix

  B = zeros(n,n);

  for i=1:n

for j =1:n

    if rand>A(i,j)

        B(i,j)=0;

    else

        B(i,j) =1;

    end

end

  end

  %eigendecomposition of B

  [v,d]=eig(B);

  %figure out the index of the principal eigenvector;

  m = max(abs(d));

  mm = max(m);

  i = find(m==mm);

  %compare principal eigenvector to true answer

  y = v(:,i)/norm(v(:,i)) - x/norm(x);

  norm(y,inf)

Running this code with matrix size of 20,000 took me a few hours and returned $|| v/||v||_2 - x/||x||_2 ||_{\infty} \approx 0.02$, suggesting that the answer is positive. Since the answer is likely yes, is this something that is present in the literature? And is there a simple argument to see that recovery is possible, in this or a related model?

(I previously asked this question on MO without receiving an answer.)


texts: Why is there an enormous difference between SAT solvers?

texts:
SAT solvers are very important in algebraic attacks, for example walksat and minisat.

However, when solving the benchmark problems available here there is an enormous performance difference between the two - Walksat is much faster than minisat for these problems. Why is this?

This implementation of walksat appears to have some performance improvements - is there any reason it wasn't included in the international SAT Competitions?


texts: Assignment problem with sum replaced by max

texts:
In the assignment problem, one tries to find $f$ such that the cost function
$$
\sum_{a\in A} C(a,f(a))
$$
is minimized. Here $f$ is a bijection between sets $A$ and $B$ of equal finite cardinality, and $C$ is a cost function $A\times B \to \mathbb R$.

My question: is there a name for the problem to minimize
$$
\max_{a\in A} \, C(a,f(a))
$$
over bijections $f$ as above?

Thanks in advance for any replies or references.


texts:
In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019.
The open problems are being submitted and peer reviewed, which makes this list reliable (in the sense that the problems are well-defined, motivated and "accessible").
In the area of sublinear algorithms and property testing, there is this wiki page, which similarity includes a list of open problems.
My question is: are there similar lists for other areas in TCS (e.g. complexity, cryptography etc.)? I didn't find such a list in common conferences, and I wonder if there are blogs/websites with a list of known open problems (which are accessible in some sense, i.e. not just "p,np" and problems at that level)


texts: Languages that lack contraction, weakening or exchange

texts:
When learning about generalized arrows, a question arised to me: Are there any languages (or potential languages) that lack one or more of the structural rules: contraction, weakeing and exchange?
Under Curry-Howard isomorphism, these rules, used frequently in logic, map into programming concepts. If we denote $A, B, C \vdash D$ a program (corresponding to a natural deduction proof) that computes a value of type $D$ from inputs of types $A$, $B$ and $C$, we get:

Contraction: $\Gamma, A, A\vdash B$ can be transformed into $\Gamma, A\vdash B$.
That is, a single input can be used twice.

Weakening: $\Gamma\vdash B$ can be transformed into $\Gamma, A\vdash B$.
That is, it's possible to add arbitrary, unused inputs.

Exchange: $\Gamma_1, A, B, \Gamma_2 \vdash C$ can be transformed into $\Gamma_1, B, A, \Gamma_2 \vdash C$.
That is, the order of inputs doesn't matter.

An example for language lacking contraction would be quantum computing. There the allowed operations can be described with unitary matrices, and duplicating a value can't be expressed as such.
It also seems to me that weakening isn't an admissible rule for quantum computing, at least in the above form, as we can't forget a value with a unitary matrix. But we could have a weaker rule such as $\Gamma\vdash B$ can be transformed into $\Gamma, A\vdash A\otimes B$, and the $A$ in the output can be dropped when extracting the results of such a computation.
The exchange rule is clearly permissible in quantum computing.
Are there any other examples, in particular a language that doesn't allow exchange, or where weakening isn't allowed even in such a weaker form?


texts: Quantum algorithm of graphs: How to create superposition of paths?

texts:
Let us allow path to have same vertexes in it. (defining)

So suppose we have a graph of $N$ vertexes and we want to separate it into some superposition of paths that have $N$ vertexes (so if the number of vertexes is $N$, there would be like $N^N$ paths.)

Is this possible? If it is, how can this be done?


texts: Approximating a monotone submodular function using a concrete coverage function

texts:
Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e.

Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to find another ground set, $V$, and map each element from $U$ to a subset of $V$ ($m:U \to 2^V$) such that $f(S) \leq g(S) \leq \alpha f(S)$ for every $S \subseteq U$, where $\alpha$ is the approximation ratio (hopefully a constant) and $g(S) = c|\bigcup_{e \in S}m(e)|$ for some constant $c$.

An approximation that uses a weighted ground set, $V$, is also very welcomed (I guess we can't avoid that).

Thank you


texts:
I was going through Fagin's Theorem (summary on wiki) and if I understood correctly Existential Second Order Logic (ESO) can be used to represent any NP problem, the same can be said for a Non-deterministic Turing Machine.
Now I have a few questions about that:

If ESO logic is enough to characterise all the NP problems, what does the full Second Order Logic (SOL) characterise more?
If the answer to the first question is "nothing more", does that mean that any SOL can be reduced to ESO logic (it is true already that Higher Order Logics can be reduced to SOL for instance...)?
Perhaps I am missing and confusing something to have such questions in mind. Would it be possible to have some papers' link to fill in the gap?


texts: Which cryptographic protocols are secure against quantum computer attacks?

texts:
Are there any cryptosystems that we know that would be secure against an attack by a quantum computer?

Are there problems which are known or suspected to be hard for quantum computers, and can these be utilized to yield cryptographic protocols which are secure against quantum computers?


texts: Complexity of counting 3-colourings of planar bounded degree graphs

texts:
The following are known:

It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
For all $d\geq 3$, it is #P-complete to count the number of 3-colourings of a graph with maximum degree $d$ [2].

Correction (27-04-21): Result 1 is only with respect to randomized reductions (NOT deterministic reductions) in both Barbanchon [1] and Hunt et al. (unpublished work I think; details of construction appears in other papers).
What about the complexity of counting the number of 3-colourings of a planar bounded degree graph $G$?
(say, $\Delta(G)\leq 3$ or $\Delta(G)\leq 4$)
It is a bonus if bipartiteness (or girth) also comes into the picture. Counting 3-colouring of a bipartite graph is #P-complete [3]. Result 2 above is improved to triangle-free graphs of maximum degree $d$ by Greenhill [4].
References
[1] Barbanchon, Régis, On unique graph 3-colorability and parsimonious reductions in the plane, Theor. Comput. Sci. 319, No. 1-3, 455-482 (2004). ZBL1043.05043.
[2] Bubley, Russ; Dyer, Martin; Greenhill, Catherine; Jerrum, Mark, On approximately counting colorings of small degree graphs, SIAM J. Comput. 29, No. 2, 387-400 (1998). ZBL0937.05041.
[3] Linial, Nathan, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods 7, 331-335 (1986). ZBL0596.68041.
[4] Greenhill, Catherine, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Comput. Complexity 9, No. 1, 52-72 (2000). ZBL0963.68082.


texts: What are the criteria for inviting conference papers (e.g. SODA) for special issue?

texts: This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA conference. Also would be good to know about the selection criteria and the panel which selects it.


texts:
I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. going down a Slope

Examples for algorithms that i cannot use: Newton's method, Quasi-Newton method, Finite difference, Approximation theory, and Numerical analysis

However on a cube those do not work. My problem size is $n=20$ and higher, so a breadth first search is out of the question.

What is a working optimization strategy for optimization on a cube? What would be its running time? I hope to get better than just a brute-force optimization that needs me to iterate through all possible combinations.

Edit:
Here is my problem fleshed out. I am interested in a theoretical analysis and would like to have - as stated in the question - an algorithm that tackles this along with the runtime analysis.

I have a combination of lightwaves. Each lightwave $L$ has a interaction with all other lightwaves. Meaning there is a relation $REL_{L_i,L_j} = func(Li,Lj)$ matrix. What i can do now is remove lightwaves, to remove interactions between waves. I would like to have the most lightwaves possible, while keeping the sum of the relations low.

The problem turns into a $(0,1)^n$ optimization, where $0$ is exclusion of a lightwave, $1$ is inclusion.

I hope this clarifies the problem up a bit and made sense.

Edit 2:
I am optimizing for the term $\sum$ of relations divided by the number of lightwaves since a full pareto optimization would be useful, but impractical to display as a solution. (thanks  Tsuyoshi Ito)


texts:
Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a single edge. That is there is an edge $(T_1, T_2)$ if there exists two edges $x, y \in G$ such that $T_1 - x = T_2 - y$.

My question is this: are there some non-trivial lower or upper bounds on the degree of the vertex with minimum degree in $T(G)$?

Note: I edited the question (last line) a bit to make it less ambiguous
.


texts: What are the morphisms of Adj(C,T) - the category whose objects are the adjunctions of a given monad?

texts:
The Wikipedia page for Monad says just that for a monad $(T,\eta,\mu)$ we can define the category of all adjunctions that define the monad:

  Let ￼$\textbf{Adj}(C,T)$ be the category whose objects are the adjunctions ￼$(F,G,e,\varepsilon)$ such that $(GF,e,G\varepsilon F)=(T,\eta,\mu)$￼ and whose arrows are the morphisms of adjunctions which are the identity on ￼$C$. Then this category has

  an initial object $(F_T,G_T,\eta,\mu_T) : C\to C_T$￼, where $C_T$￼ is the Kleisli category,
  a terminal object $(F^T,G^T,\eta,\mu^T) : C\to C^T$￼, where ￼$C^T$ is the Eilenberg-Moore category.

What are the morphisms of adjunctions in $\textbf{Adj}(C,T)$ and what is meant by ... which are the identity on $C$?


texts: What's the relevant CS theory for CodinGame challenges?

texts:
CodinGame challenges are basically extremely large decision trees, where your program is trying to find the node with the highest possible score. Greedy algorithms don't work because picking a locally optimal path (such as the highest-value child of the current node) can lead to a globally suboptimal result. Nor do any other straightforward algorithmic approaches, such as dynamic programming.
I'm wondering what's the relevant CS theory for this kind of problems. I'm not even sure what to call them, except maybe "non-linear optimization problems".
I'm also interested in approaches to solve them. Would some sort of machine-learning work?  It seems like it should, since the ML approach of AlphaStar was successful in tackling the Starcraft game, which seems to be the same class of a problem.
EDIT:
An example of a CodinGame challenge is their Fall Challenge 2020 which essentially is writing an agent to play the board game Spice Road against another agent.


texts: Difference between a cyclic and a left-recursive context-free grammar?

texts:
I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:

  The original purpose of the LC transform is to allow
  simulation of left-corner parsing by top-down parsing,
  but it also eliminates left recursion from any noncyclic
  CFG.
  (from page 5 of http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf)

Note the second part of this quote:

  it also eliminates left recursion from any noncyclic
  CFG.

I though that a cyclic grammar and a left-recursive grammar go hand in hand? What's the difference?

Thanks for any hint on this!


texts: Matching of points in two discrete linear sequences with potentially missing points

texts:
This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up.

Anyway, the game is as such: my friend John has a sequence of letters that are mapped to a sequence of numbers (the letters are unique but the numbers are not necessarily unique). John now hides the letters from the sequence and sends me only the numbers in the same order as the sequence. My job is to guess the letters of this sequence. The only information available to me is a database that contains all letters of the alphabet and a rough numerical mapping.

So, for example, John computes the following:

(a : 5, b : 10, c : 1, e : 15, f : 4)

Then john sends me (5, 10, 1, 15, 4). I now have to guess which letters those numbers belong to. As I said above, I have some rough estimate of what number each letter in my database should be mapped to.

This problem is not hard with this domain. The Hungarian algorithm for lowest cost assignment would work fine. However, what about arbitrarily large string sizes? Suppose I have a gigantic database of strings (ranging from a few letters all the way to 20 letters) to number mappings. The database is ordered lexographically. John chooses a subset of this database, changes the numbers of each entry a certain amount (different for all) and then asks me to guess that sequence.

Any leads?


texts:
I came across the No Free Lunch Theorem via Jürgen Schmidhuber's paper on Universal Search and there were a couple remarks on NFL which stood out
to me. The first was that we can't define a uniform distribution on an infinite number of objects. Second, Schmidhuber argues that there's nothing inherently natural about the uniform distribution and I'm inclined to agree on this point as well.

Although I'm aware of maximum-entropy arguments in favour of uniform distributions, on an infinite number of objects it's more natural to observe an exponential distribution. Might there be a well-known counter-argument in the optimisation literature
to the points raised by Jürgen Schmidhuber?

Optimal Ordered Problem Solver
No Free Lunch Theorem


texts:
Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set?

To be clear, I'm not interested in quick sort per se, but in constructing a measure of difference between two sets (of equal size), the elements of both of which have been assigned integer ranks. I'd like a measure of what is the minimum effort to to transform the order of one set into that of the the other using a quick sort-like procedure; presumably assuming one set has already been sorted is a harmless simplification of the problem.

Is there a known algorithm w/ asymptotic time bound to compute the shortest partition sequence?


texts: First-order multi arity functions in dependent type?

texts:
(cross posted from Reddit https://www.reddit.com/r/dependent_types/comments/b1ts8b/firstorder_multi_arity_functions_in_dependent_type/?

Take Agda for example, functions of multi arity is "encoded" as functions of one argument returning functions. In the same sense one can "encode" a record type as iterated Sigmas, but Agda has primitive first-order record type.

Then the problem is, in the encoded case, one can talk about functions of multiple arities generally, like function extensionality https://github.com/agda/cubical/blob/master/Cubical/Core/Prelude.agda#L105 . to apply function extensionality to functions of multiple arity, one just iteratively apply it multiple times.

It turns out Sigma type has also some general properties like this: https://github.com/agda/cubical/blob/master/Cubical/Foundations/HLevels.agda#L66 . So if record type is also encoded, then one can use this to a record type of multiple fields, just iterate it multiple times. But in case of Agda one cannot do this, because record type is primitive to Agda.

So is there a dependent type theory that has primitive multi-arity function types?

Also can we extends such a theory so we can talk generally of functions of multiple arity and records of multiple field? One goal is to write down a definition of "isContrRecord" in this new theory.

Any related reference?


texts: References to learn more about graph laplacian.

texts:
I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces.

Can someone give a pedagogic reference which helps learn this subject?
Also is there something called "free probability theory" which is somehow equivalent to random matrix theory?
Would you call the usual QFT of Hermitian matrices a random matrix theory?


texts: Question about "typical set" in Shannon's source coding theorem

texts:
I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on asymptotic equiparition' principle:

  For an ensemble of $N$ $i.i.d$ random variables $X^N=(X_1,X_2....X_N),$ with $N$ sufficiently large, the outcome $x=(x_1,x_2...x_N)$ is almost certain to belong to a subset of $|A_x^N|$ having only $2^{NH(x)}$ members, with each member having probability  "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that typical set doesn't necessarily contain the most probable element set.

Because the "smallest-sufficient set" $S_{\delta}$ which is defined as:

  the smallest subset of of $A_x$ satisfying  $P(x\epsilon S_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $  In other words, $S_{\delta}$ is constructed by taking the most probable elements in $A_x$, then the second probable......until the total probabily is  $\ge1-{\delta}$.

My question is, as $N$ increases, does $S_{\delta}$ approaches typical set such that these two sets will end up being equivalent of each other? If the size of the typical set is identical to the size of $|S_{\delta}|$,  then why are we even bother with $S_{\delta}$? Why can't we just take the typical set as our compression scheme instead?


texts: How is it proven that Key Exchange implies OWFs?

texts:
Page 38 says that Key Exchange implies the existence of one-way functions.

When I try to work out the proof myself, I get that in the hypothetical case

where there is Key Exchange but no one-way functions, an eavesdropper

would have a non-negligible probability of obtaining a random bits that would

have produced that communication actually observed, and then I get stuck.

As far as I can see, it could be that when the eavesdropper finds such bits,

the probability that the bits found would give the same key as

the parties get from the random bits actually used is negligible.

Does the existence of a secure Key Exchange protocol imply the existence of one-way functions?

If yes, how is that proven?


texts:
It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$. However, the proof doesn't seem to generalize to $\mathsf{P}/\text{poly}$ so the possibility $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ i.e. $\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$ seems open.

  Assuming $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ (or even that the polynomial hierarchy doesn't collapse on any level), is $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ known to be true or
  false? What evidence can be put for and against it?


texts: Proof assistant usage in complexity theory research?

texts:
Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most people wouldn't use such tools because the proofs would be too low level. Is anybody using these proof assistants in a way that is critical to their research, as opposed to a nice supplement?

I am interested because I might start learning one of those tools and it would be fun to learn about them in the context of proofs of reductions, correctness, or run time.


texts:
$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$.

A no-brain approach is to calculate distances between $x$ and $y$ for all $y \in S$ and then sort them using any fast algorithm.

Is there any way to store or preprocess $S$ so the sorting process becomes faster?


texts: Counting/Enumerating Minimal Edge Covers

texts:
A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.

  Questions

   Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial upper bound on their number? Is there any clever algorithm in literature to enumerate them?

  Empirically, I'm observing that the number of Minimal Edge Covers seems to be always odd: so far in my experiments I've never met a graph having an even number of them. Is this a theoretically proven fact? If not, has their parity been investigated in literature?


texts:
We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$.

The DAG subset sum problem (might exist under a different name, a reference will be great) asks whether there are vertices $v_1,v_2,...,v_k$, such that $\Sigma_{v_i}g(v_i) = T$, and $v_1\to..\to v_k$ is a path in $G$.

This problem is trivially NP-Complete, as the complete transitive graph yields the classical subset sum problem.

An approximation algorithm for the DAG subset sum problem is an algorithm with the following properties:

If there exists a path with sum T, the algorithm return TRUE.
If there is no path summing up to a number between $(1 − c)T$ and $T$ for some $c\in (0,1)$, the algorithm return FALSE.
If there is a path summing to a number between $(1 − c)T$ and $T$, the algorithm may output any answer.

Subset sum is known to be approximable in polynomial time for all $c>0$.

Does the same hold for DAG-Subset-Sum?


texts: General Results for Complicated Constraint Satisfaction Problem

texts:
Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of certain coloring configurations. The color configurations take forms like: there exists a vertex with color $a$ so that all vertices in the row of that vertex have colors in the set $\{a,b,c\}$ and all vertices in the column have colors in the set $\{c,d\}$; or they could be something like: there does not exist a column of vertices all with color $b$.

The number of dimensions in my problems is always fixed (e.g., 2-dimensional grid, 3-dimensional cube, and so forth) and the number of colors is fixed, but the constraints can change and I can vary the size of "graphs" I use. Given a problem, I need to determine whether there exists a colored graph (which will look like a hypercube in general) so that the existence and nonexistence constraints (coloring configurations) are satisfied.

I need to make general claims about problems of this kind (e.g., a graph always exists to solve problems with coloring configurations of a specific form; or, such a graph never exists for coloring configurations of a certain form, etc...). It would also be nice to know some properties about the graphs I need (e.g., the maximum size of the smallest graph that solves a particular class of such problems; or properties about the color patterns in such a graph, etc...).

Are problems of this type studied anywhere? Best I can tell right now, they are just complicated constraint satisfaction problems, but I can't find what I need out there. I need to read more about the mathematics behind these problems. I am most interested in understanding the general properties of such problems, and not so much in algorithms (though I don't mind learning about algorithms). Any references would help. References to subjects I need to read about, theorems, articles, and so forth would be great.


texts: Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?

texts:
Sorry for not-precise question. :-(

There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of them is $O(1.23^n)$. But the algorithms do not use the specific information of comparability graphs.

So I wonder whether there exists more powerful(faster) exact algorithm for counting independent sets in comparability graphs?


texts: Maximum number of triangles in a constrained delaunay triangulation

texts:
I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number of vertices.

Is there any papers or theorems that show that constrained delaunay triangulations have fewer or more triangles than normal delaunay triangulations?

http://www.cs.ucdavis.edu/~amenta/pubs/HiDeeDel.pdf


texts: Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

texts:
Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string for this alphabet.

Usually, as long as $\Sigma$ contains more than 1 element, the exact number of elements in $\Sigma$ doesn't matter: at best we end up with a different constant somewhere. In other words, it doesn't really matter if we use the binary alphabet, the numbers, the Latin alphabet or Unicode.

  Are there examples of situations in which it matters how large the alphabet is?

The reason I'm interested in this is because I happened to stumble upon one such example:

For any alphabet $\Sigma$ we define the random oracle $O_{\Sigma}$ to be an oracle that returns random elements from $\Sigma$, such that every element has an equal chance of being returned (so the chance for every element is $\frac{1}{|\Sigma|}$).

For some alphabets $\Sigma_1$ and $\Sigma_2$ - possibly of different sizes - consider the class of oracle machines with access to $O_{\Sigma_1}$. We're interested in the oracle machines in this class that behave the same as $O_{\Sigma_2}$. In other words, we want to convert an oracle $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ using a Turing machine. We will call such a Turing machine a conversion program.

Let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2, 3 \}$. Converting $O_{\Sigma_1}$ into an oracle $O_{\Sigma_2}$ is easy: we query $O_{\Sigma_1}$ twice, converting the results as follows: $00 \rightarrow 0$, $01 \rightarrow 1$, $10 \rightarrow 2$, $11 \rightarrow 3$. Clearly, this program runs in $O(1)$ time.

Now let $\Sigma_1 = \{ 0, 1 \}$ and $\Sigma = \{ 0, 1, 2 \}$. For these two languages, all conversion programs run in $O(\infty)$ time, ie there are no conversion programs from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ that run in $O(1)$ time.

This can be proven by contradiction: suppose there exists a conversion program $C$ from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ running in $O(1)$ time. This means there is a $d \in \mathbb{N}$ such that $C$ makes at most $d$ queries to $\Sigma_1$.

$C$ may make less than $d$ queries in certain execution paths. We can easily construct a conversion program $C'$ that executes $C$, keeping track of how many times an oracle query was made. Let $k$ be the number of oracle queries. $C'$ then makes $d-k$ additional oracle queries, discarding the results, returning what $C$ would have returned.

This way, there are exactly $|\Sigma_1|^d = 2^d$ execution paths for $C'$. Exactly $\frac{1}{|\Sigma_2|} = \frac{1}{3}$ of these execution paths will result in $C'$ returning $0$. However, $\frac{2^d}{3}$ is not an integer number, so we have a contradiction. Hence, no such program exists.

More generally, if we have alphabets $\Sigma_1$ and $\Sigma_2$ with $|\Sigma_1|=n$ and $|\Sigma_2|=k$, then there exists a conversion program from $O_{\Sigma_1}$ to $O_{\Sigma_2}$ if and only if all the primes appearing in the prime factorisation of $n$ also appear in the prime factorisation of $k$ (so the exponents of the primes in the factorisation doesn't matter).

A consequence of this is that if we have a random number generator generating a binary string of length $l$, we can't use that random number generator to generate a number in $\{0, 1, 2\}$ with exactly equal probability.

I thought up the above problem when standing in the supermarket, pondering what to have for dinner. I wondered if I could use coin tosses to decide between choice A, B and C. As it turns out, that is impossible.


texts: What can i learn about a graph about which only certain properties are known

texts:
1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts?

The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable,
The degree of each vertex, and
The number of paths of length $j$ in the graph for all $j \in \{1,...,n\}$.

Keep in mind that graph is not given (so in particular the neighbors of each vertex are not known).

2) What computations can be performed on a graph given in this manner that are more efficient than the corresponding computations on a general graph?

Thanks!


texts: I am looking for a good relatively complete and up-to-date book or survey about heuristic algorithm design techniques.


texts: Proof for Upper Bound of Sum of Square Roots Problem

texts:
In [1], Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP.

  Given integers $a_1, a_2, \ldots, a_n$ and $L$, determine if $\sqrt{a_1} + \sqrt{a_2} + \cdots + \sqrt{a_n} < L$

They observe that it is not even apparent that this problem is in NP since it is not clear what the minimum digits of precision are required in the computation of the square roots to sufficiently compare the sum to $L$. However, they do cite a best known upper bound of $O(m2^n)$ where $m$ is "the number of digits in the original symbolic expression". Unfortunately, this upper bound is attributed merely to a personal communication from A. M. Odlyzko.

  Does anyone have a proper reference to this upper bound? Or, in the absence of a published reference, a proof or proof sketch would also be helpful.

Note: I believe that this bound might be inferred as a consequence of more general results by Bernikel et. al. [2] from around 2000 on separation bounds for a larger class of arithmetic expressions. I'm mostly interested in more contemporaneous references (i.e.: what was known circa 1976) and/or proofs specialized to just the case of the sum of square roots.

Garey, Michael R., Ronald L. Graham, and David S. Johnson. "Some NP-complete geometric problems." Proceedings of the eighth annual ACM symposium on Theory of computing. ACM, 1976.
Burnikel, Christoph, et al. "A strong and easily computable separation bound for arithmetic expressions involving radicals." Algorithmica 27.1 (2000): 87-99.


texts: (How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

texts:
From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to reason about them in any meaningful way with just the functional point of view? Would it even be possible?

I've been mulling on this question purely from a point of self inquiry as part of learning the lambda calculus model of computation. I understand that it's "non-intuitive" and that's why Godel favored the Turing model. However, I just wish to know what are the known theoretical limitations of this functional style of computation and how much of a hindrance would it be for analyzing the NP class of problems?


texts: Keyed queues with depth queries and delete

texts:
I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations:

empty is a DMV containing no keys.
enqueue(q,k) adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.
dequeue(q) deletes the key at the front of the DMV q, if one exists, and returns it.
delete(q,k) removes the key k from the DMV q.
depth(q,k) returns an natural number indicating the approximate number of keys between the key k and the front of the DMV q. Let $k_q$ denote the exact number of keys between k and the front of q. Then there must be some c such that for all k and q, $k_q/c$ < depth(q,k) < $ck_q$.

I think I know how to provide the queue operations in $\Theta(1)$ time and delete and depth in $\Theta(\lg n)$ time (all expected amortized). Is it possible to do better?

My proposed solution is as follows: Maintain a balanced tree with $O(1)$ operations at the ends. Nearly any finger tree will do. This tree will store the keys in queue order at its nodes. Also, annotate every non-spine node with its number of descendants.

Keep a hash table mapping keys to pointers to nodes in the tree.

To enqueue a key k, add k to the back of the tree. This invalidates $O(1)$ node pointers and creates $O(1)$ new node pointers, so we need only perform $O(1)$ hash table operations. Dequeue is similar.

To delete a key, we look it up in the hash table and find its location in the tree, then delete it from the tree. This takes $O(\lg n)$ time in the tree, and invalidates $O(\lg n)$ slots in the hash table. We must also maintain non-spine node size annotations in the tree, but this also only takes logarithmic time.

To find the depth of a key, we first annotate the spine nodes of the tree with their number of descendants. This takes $O(\lg n)$ time. We then look up the key in the hash table and find its location in the tree. We then follow parent pointers until we reach the root, summing the annotations at left siblings. Note that this is the exact depth.


texts: Categorical semantics for non-monotonic logics?

texts:
Are there any categorical semantics for non-monotonic logics?

It appears that the simple answer to this is "No" since the obvious notion of composition fails for any model of a non-monotonic logic. But is there a model that actually works with an appropriately defined notion of composition?


texts: Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

texts:
Assume you are given:

A list of N (not necessarily distinct) memory ranges of the form [x,y], where x and y are non-negative integers representing the lower and upper bounds of the range, and
A list of N memory access modes (read or write),

where the $i^{th}$ entry in the memory range list is accessed (either read from or written to) according to the $i^{th}$ entry in the data access modes list.

How do you efficiently generate a data dependency DAG representing the dependencies between subsequent accesses to possibly overlapping memory ranges?

The DAG should not have redundant dependencies. And ideally the algorithm should have running time quadratic in N (or better, if possible).

UPDATE: To clarify, a dependency between two memory accesses exists if

The two memory ranges being accessed overlap (i.e., have at least one byte in common), and
At least one of the access modes is a write (concurrent reads from the same memory range are ok).


texts: Bound the number of rounds in the sampling

texts:
Suppose we have a sequence $a_1,a_2,\ldots, a_n$, each $a_i$  is sampled uniformly and independently from $[0,1]$.
Define

$$
    J_1=1,\\
    \text{for}~i>1, ~J_i = 1 \iff a_i < \min \{a_1,a_2,\ldots,a_{i-1}\} \\
    \text{otherwise}, J_i=0
$$
By some sort of calculation, we can get
$$
    E[J_i] = \frac{1}{i}
$$
Thus if we let $J=\sum_{i=1}^nJ_i$, we have
$$
    E[J] = \sum_{i=1}^n \frac{1}{i} \approx \ln(n)
$$

Now, my question here is can we bound the probability $P(J-E[J] > \delta)$?

With Azuma's inequality, if we define $Y_i = E[J|J_1,J_2,\ldots,J_i]$, we can get
$$
    P(J-E[J]>\delta)=P(Y_n-Y_0>\delta) < e^{-\frac{\delta^2}{2n}}
$$
But this bound does not make much sense since when $n$ is large, it actually tends to be $1$.

The bound given by Markov inequality is also useless in our case. Any suggestion is welcome and highly appreciated.

Thanks so much!


texts: Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

texts: Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974).  I am wondering if it is also known whether the Presburger arithmetic decision problem remains intractable with quantum computation or even just randomized computation, and specifically whether it falls outside of BQP or BPP.  It would be profoundly humbling if such a seemingly weak mathematical theory, which doesn't even allow multiplication, gives rise to provably intractable problems.


texts: Example of a hardness-of-approximation proof which improves the approximation factor?

texts: Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so far, the bound is usually degraded in the reduction.


texts: Can one reverse a hash with partial plaintext knowledge?

texts:
First off, please forgive my ignorance because I am not as well versed in cryptography and mathematics as I would like to be. I may say something obviously wrong/dumb; please point it out!

Is there any technique which may reduce the difficulty of recovering plain text from a hash if the attacker knows part of the plain text?

Here is an example.
Alice writes this letter:

Dear Bob,
   Run!
Yours Truly,
Alice

Alice sends the plaintext to Bob over channel X and the hash over channel Y.

Eve intercepts the hash but not the plaintext.

Eve knows Alice starts the message with "Dear Bob," and ends with "Yours Truly, Alice".
Eve also knows that Alice sends messages in fixed blocks and will pad the body content with whitespace to meet the required block length.

Can Eve use her knowledge of 1)fixed message size and 2)partial plaintext knowledge to reduce the computational difficulty of reversing the hash?

I would appreciate any help on this topic, even if your answer is just "read this whitepaper".


texts: The only definition of "calculus" I'm aware of is the study of limits, derivatives, integrals, etc. in analysis. In what sense is lambda calculus (or things like mu calculus) a "calculus"? How does it relate to calculus in analysis?


texts:
Is there a generalization of the GO game that is known to be Turing complete?

If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete?  The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?


texts: Ground Reachability in String and Term Rewriting Systems

texts:
I have two questions concerning ground reachability in string and term rewriting systems.

String Rewriting Systems:

Let $\Sigma$ be a finite alphabet.

I have a set of rules $R$ of the form $a_ib_i = c_id_i$ where $a_i,b_i,c_i,d_i$ are symbols in $\Sigma$.

Problem 1: Given strings $u$ and $w$ in $\Sigma^*$ of size $n$ can $u$ be transformed into $w$ by the application
of rules in $R$?

Question1: Can Problem 1 be solved in time polynomial in $n$? Note that in this case
the problem is trivially decidable since the rules do not increase the size of the strings.

Term Rewriting Systems:

Now I have a ranked alphabet $\Sigma$ with function symbols of arity $0$, $1$ and $2$.

I have a set $R$ of rules of the form (where $x,y,z$ are variables and $f,g,h,k$ are function symbols)

$f(x,y) = g(y,x)$
$f(x,g(y,z)) = h(x,k(y,z))$

Problem 2: Given ground terms $u$  and $w$ over $\Sigma$ with $n$ leaves,
can $u$ be transformed into $w$ by the application of rules in $R$?

Question 2: Can Problem 2 be solved in time polynomial in $n$? Note that
decidability is also trivial here, since the rules do not increase the size of a term.


texts:
One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$.  I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.

Clearly a random DFA with sufficiently many states separates strings with high probability.  Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.

Can we do better?  Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)?  A brief search didn't turn up many results on the properties of random DFAs; all I could find was http://arxiv.org/abs/1311.6830.


texts:
I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that.

But I could not find anything on Weighted furthest point voronoi diagrams !! But it is very unlikely that this version of voronoi diagrams are not studied before.

So, any link / reference will be helpful.


texts: Uses of algebraic structures in theoretical computer science

texts:
I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (and to a lesser degree, other sub-fields of computer science).

Under group theory I've come across syntactic monoids for formal languages and trace and history monoids for parallel/concurrent computing.

From a ring theory standpoint, I've come across semiring frameworks for graph processing and semiring based parsing.

I have yet to find any uses of algebraic structures from module theory in my research (and would like to).

I'm assuming that there are further examples and that I'm just not looking in the right place to find them.

What are some other examples of algebraic structures from the domains listed above that are commonly found in theoretical computer science (and other sub-fields of computer science)? Alternatively, what journals or other resources can you recommend that might cover these topics?


texts: Does randomness buy us anything inside P?

texts:
Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.

Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in \mathsf{DTIME}(n^k)$?
Is its non-existence proven?

This question was asked on cs.SE here, but did not get a satisfactory answer.


texts: Exact exponential-time algorithms for 0-1 programs with nonnegative data

texts:
Are there known algorithms for the following problem that beat the naive algorithm?

Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.
Output: an optimal solution $x^*$ to $\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$.

This question is a refined version of my previous question Exact exponential-time algorithms for 0-1 programming.


texts: Can $f^{2^N}(x)$ be computed in polynomial time when $f$ is linear?

texts:
Linear functions: definition

Let's define a linear function as one expressible as an untyped λ-calculus term with the added restriction that no lambda argument can be used twice.

Linear functions: example

Many functions can be defined that way. For example, the successor of a binary string (interpreted as an integer) could be defined as (in Idris):

data Bit = O | I

succ : List Bit -> List Bit
succ bits = case bits of
  b :: bs => (case b of
    O => \ bs0 => I :: bs0
    I => \ bs1 => O :: succ bs1) bs
  [] => []

That function is linear in the above sense because it could be translated to the linear untyped λ-calculus. Pattern-matching could be expressed with Scott-encodings, and we avoided using the argument bs twice with extra lambdas. Of course, recursion isn't expressible on that language (the Y-combinator and similar require non-linear arguments), so this definition is actually illegal, but, if we unrolled that function a few levels deep, we could still implement a succ : Vect K Bit -> Vect K Bit, for bit lists of bounded depth K. That's OK for the purpose of the question. Let's assume a fixed finite K and abbreviate Vect K Bit as Bits.

The question

Given an arbitrary linear (in the sense above) function f : Bits -> Bits, can the non-linear function repeatF : Integer -> Bits -> Bits, which applies f n times to a bit-string, always be implemented in polynomial (or at least sub-exponential) time with respect to the size of the binary integer n, and such that its code size grows at most polynomially when we increase K?  In other words, is the running time of computing $f^n(x)$ polynomial in $n$? I care only about the dependence on $n$; you can think of the size of $x$ as fixed.

Example

For the example function defined above, succ, the answer is yes. Of course, if we define repeat(n,x) naively, then it'll take exponential time with respect to n:

repeatSucc : Integer -> List Bit -> List Bit
repeatSucc 0 x = x
repeatSucc n x = succ (repeatSucc (n - 1) x)

But by noticing that repeatSucc n x is equivalent to addition, we can implement it in polynomial time and space with known addition algorithms. This makes me wonder whether something similar is true for all functions f defined in the style above (or, of course, how we can prove that's not the case).

Note:

I'm analyzing the complexity of repeatF(n, x) with respect to n, which is a binary non-negative integer and could be potentially infinite. The input x has constant size, but that is irrelevant, it is just the initial state of the iteration. You can't build a finite size lookup table for a potentially infinite argument. Even if you could, the size of repeatF is limited by a polynomial function of the constant depth K, so you can't fit a lookup table for the entire image. I'm, less formally, in essence, asking if, for any "simple" linear function like succ, there is a succinct algorithm to compute its repeated application quickly. Please, consider this informal intuition if my concrete formalization has further issues.


texts:
Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language?

Instead, the fact that the language is in $NP$ would be proven by reducing it to another language in $NP$, where the link between the two is not trivial and needs careful analysis.

More generally, are there some interesting examples of problems in $NP$ so that it is hard to see that they are in $NP$?

A semi-answer would be the problem of deciding the winner in parity games: to show that it is in $NP$ (even $NP\cap coNP$), we need the positional determinacy theorem which is deep and non-trivial. However this answer is not ideal, because it still boils down to the existence of a polynomial witness for this exact problem (the positional strategy), and does not reduce to another different $NP$-problem.

Another one would be the AKS primality algorithm: deciding whether a number is prime is polynomial, while there is a priori no small witness for this fact. Let's say we rule out the "surprising polynomial algorithms", since many of them would fit the description above. I'm more interested in surprising $NP$ algorithms which are not deterministic.


texts: Difference between self-information and entropy

texts:
I get a bit confused about different definitions of entropy and/or self-information.

Entropy?

$$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$

Self-information?

$$ I(x) = - \log{P_X(x)} $$
$$ I(X) = - \sum_{x \in X} \log{\left(P_X(x)\right)} $$

When do I use which formulate to calculate what? Generally, I am interested in the average information content of a text. Here I would calculate the frequency of each word, the probability, sum up the negative logarithm of this probability and average it by the number of words.

What am I missing here?


texts: What is the contribution of lambda calculus to the field of theory of computation?

texts:
I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/reductions (crudely speaking). Some questions keep nagging at me though:

What's the point of lambda calculus? Why go through all these functions/reductions? What is the purpose?
As a result I'm left to wonder: What exactly did lambda calculus do to advance the theory of CS? What were it's contributions that would allow me to have an "aha" moment of understanding the need for its existence?
Why is lambda calculus not covered in texts on automata theory? The common route is to go through various automata, grammars, Turing Machines and complexity classes. Lambda calculus is only included in the syllabus for SICP style courses (perhaps not?). But I've rarely seen it be a part of the core curriculum of CS. Does this imply it's not all that valuable? Maybe not and I maybe missing something here?

I'm aware that functional programming languages are based on lambda calculus but I'm not considering that as a valid contribution, since it was created much before we had programming languages. So, really what is the point of knowing/understanding lambda calculus, w.r.t. its applications/contributions to theory?


texts: How is proving a context free language to be ambiguous undecidable?

texts: I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a decision? Perhaps I'm wrong and it can be done?


texts: Recovering the slope of a digitized line

texts:
Has there been any work on recovering the slope of a line segment from its digitization?
One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized line an interval of possible slopes.

(The notion of a digitized line that I am using is Rosenfeld's: the set of pairs $(i,nint(ai+b))$ where $i$ ranges over the integers (or a block of consecutive integers) and $nint(x)$ denotes the integer nearest to $x$ (if $x=k+1/2$, we take $nint(x)=k$).)

I've done some work on this on my own (see http://jamespropp.org/SeeSlope.nb) but I have
no formal background in computational geometry so I suspect I may be reinventing the wheel, since the question seems like such a basic one.

In fact, I know that the linear regression method of estimating the slope is in the
literature, but I haven't been able to find my $O(1/n^{1.5})$ result anywhere.  (This
result says that if one chooses $a$ and $b$ uniformly at random in $[0,1]$, then the
difference between the slope $a$ of the line $y=ax+b$ and the slope $\overline{a}$ of
the regression line approximating the $n$ points $(i,nint(ai+b))$ ($1 \leq i \leq n$)
has standard deviation $O(1/n^{1.5})$.)

Any leads or pointers to relevant literature will be greatly appreciated.

Jim Propp (JamesPropp@ignorethis.gmail.com)


texts: In the lambda calculus, are there commonly accepted names for $x$ and $M$ when they appear in $\lambda x [M]$  ? Something along the lines of "binder" and "bindee"?


texts: Probability of a $k$-path in a random graph

texts:
Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:

\begin{eqnarray}
Pr [G\mbox{  has a Hamiltonian cycle}]=
  \begin{cases}
    1 & (c(n)\rightarrow \infty) \\
    0 & (c(n)\rightarrow - \infty) \\
 e^{-e^{-c}} & (c(n)\rightarrow c)
  \end{cases}
\end{eqnarray}

That is, a probability $p=\ln n (1+o(1)) / n$ is enough to get an Hamiltonian cycle.

For a given parameter $k\in\{1,\ldots,n\}$, I'm wondering what is the critical probability $p$ for which it's likely that the graph will have a $k$-path.

It seems that $p=\ln k(1+o(1)) / k$ is too high, as we only need one simple path of length $k$ in an $n$-nodes graph.


texts: Log Rank Conjecture Collaborative Approach

texts:
Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects.

I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-polymath-projects/219639#219639 which has been well received so far

I feel that this is a good project for collaborative approach.

I know this is a fundamental open problem in CS.

1. Is there a list of possible avenues of research that could open up if progress comes on this topic? For example, I know there are connections to Matrix Rigidity.

2. Could we have a list of possible impact of Log Rank Conjecture and related research in CS?


texts: Trade-off between number of spheres and wasted space in covering a 3d object by spheres

texts:
Consider the following optimization problem:

Input: a 3-dimensional "object" $O$.

Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing the volume of $(\bigcup_i S_i) - O$.

Increasing $k$ results in better optimum (smaller wasted space).
I am interest in the trade-off between $k$ and the optimum wasted space.
Has this problem been studied before?


texts: Have results from the calculus of variations been used previously in TCS?


texts: Efficient algorithms for searching a collection of trees

texts:
I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset.

Are there efficient algorithms to do so?

I was thinking of something like suffix arrays, however, naively encoding the trees as strings (by a fixed traversal ordering of their nodes) won't work, since the search treelet can be of any arbitrary shape.

UPDATE:

Some details about the typical instances I expect:

The dataset will consist in at least tens of thousands trees, each consisting in about twenty to thirty nodes.
The trees will not be not binary, but the typical children number per node will be small (usually no larger than four or five, although in some degenerate cases it can reach about thirty). The number of labels will be in the tens of thousands.

I need that for NLP applications: each tree will be the dependency parse of a sentence, each node representing a word occourrence and each label a dictionary word (with some decoration).


texts: Can three stacks be implemented in one array, with O(1) push/pop time?

texts:
Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the same possible for three stacks?

More specifically, is it possible to implement three stacks given the following conditions:

You have a fixed size array that can hold N objects.
As long as the sum of the three stack sizes is < N, push() should not fail.
Both push() and pop() operations should take O(1) time.
In addition to the array, you can use only O(1) additional space.

Here are examples of solutions that do not satisfy these requirements:

Splitting the array into 3 fixed parts and using each part for a stack (violates 2).
Similar to the above but with movable boundaries between stacks (violates 3).
Simple linked-list based implementations (violates 4).

I'll accept non-trivial algorithms or impossibility proofs even if they don't meet all the conditions (1)-(4) exactly, for example, an algorithm where push/pop take O(1) amortized time, or where the additional memory is smaller than O(N), eg O(log N). Or an impossibility proof that shows that for example, accessing fewer than 5 elements of the array per push/pop is impossible.


texts: Intersection of two unsorted sets or lists

texts:
Suppose you are given two lists $L_1$ and $L_2$, each of which contains pairwise distinct elements from some set $S$.

What is the complexity of computing the intersection $L_1\cap L_2$ of the two lists?

If you have an order on $S$, you can sort your both lists and then compute the intersection in linear time, achieving $O(n\log n)$ complexity where $n=\max(|L_1|,|L_2|)$. More specific questions are then:

Can you compute the intersection in linear time, or at least faster than $O(n\log n)$?
If there is no natural order on $S$, what complexity can you achieve without using a sorting algorithm?

The second bullet point is quite vague. What I want to understand is whether sorting the lists (or one of them) is necessary though the answer does not need to be sorted.


texts: Using a probability distribution in the fooling set technique for communication complexity

texts:
I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition:

  Let $\mu$ be a probability distribution of $X\times Y$. If any $f$-monochromatic rectange $R$ has measure $\mu(R) \leq \delta$, then $D(f) \geq \log_2 1/\delta$. [Prop. 1.24]

I understand the idea of a fooling set (find a set which takes the same function value everywhere, but mixing and matching $x$ and $y$ coordinates will change the function value). I understand that $\mu$ maps $X\times Y$ to $\mathbb{R}$, and that $\mu(X\times Y) = 1$. But I don't understand why we should be allowed to use a probability distribution at all. There's no randomness here, and even if their likelihoods of being chosen were not uniform, each pair $(x,y)$ should in theory be possible, and we need to take this into consideration because communication complexity deals with the worst-case.

I'm obviously missing something. Any help here would be appreciated.

(Also, the use of any in the proposition is ambiguous. I assume that it means "for all", but it could also possibly mean "there exists"...)


texts:
I just found the following sentence from the #P wiki page:

"Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[3]"

http://en.wikipedia.org/wiki/Sharp-P-complete

the referece [3] is
Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science (Elsevier) 32: 169–188.

I took a quick look at [3]. But it seems to me that the results of [3] do not contain anything similar to what is in the wiki page. Is there a mistake in the wiki page? Thanks.