texts: May Boolean circuits be exponentially more concise than Boolean formulae?

texts:
Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest Boolean circuit $C_n$ describing $f_n$. Say we have $|F_n| = \Omega(g(|C_n|))$ for a certain function $g$.

What is the fastest-growing $g$ for which this is known to be possible, and the slowest-growing $g$ for which it is known to be impossible? (From the comments, it seems like there is still a gap here, but I'm trying to understand which one.)

This is the "simple" version of my question. What I am interested in is a multi-output, probabilistic (=weighted), variant of the problem, defined as follows. It is clear how to extend circuits to be multi-output, and I define a $k$-output formula to be just a $k$-tuple of formulas on the same inputs. I say that the input variables have a certain probability of being true (written in binary and accounted for in the circuit or formula size), each independently from the others, and I look at the probability distribution on the tuple of outputs (forgetting which input is yielding which output, just looking at the distribution on values), given this product distribution on the inputs, in the circuit and formula context. Here again the circuits are certainly more concise than formulae, but how much? Are there some distributions that can be exponentially more concise to represent with circuits, intuitively because of sub-expression reuse?

To give an example for this more elaborate version, consider the following distribution on $n$ outputs:

$000 \cdots 00$ with probability $1/2$,
$100 \cdots 00$ with probability $1/4$,
$110 \cdots 00$ with probability $1/8$,
...
$111 \cdots 10$ with probability $1/2^n$,
$111 \cdots 11$ with probability $1/2^n$.

There is a multi-output probabilistic circuit of size $O(n)$ which generates this (and reuses the draw of the $i$-th bit to draw the $(i+1)$-th). By contrast, the straightforward Boolean function encoding of this is quadratic, and I can't see how you could make it shorter but yet cannot prove it...


texts:
UPDATE

Now community wiki.  My new version of the question is: let's make a big list of classes of polygons.  We may be able to produce the most comprehensive list on the web, or in the literature. If there is community interest, after Jan 1st I will organize the information from all the answers into a post on the community blog.

ORIGINAL QUESTION BELOW

  Could you recommend a source, either in print or online, for a menagerie of polygons?  An extensive/exhaustive list of classes of polygon?

The Wikikpedia article on polygons provides a partial classification, but I would like something more complete.  Also, I am not concerned about how to name a 90-sided figure.  Rather, I am trying to find a list of classes that contain infinitely many figures each (examples: star polygon, isothetic polygon).

For example: actual words for "looks like a spider," "would look like a football if it were smoothed out," and so on.

I've already checked The Geometry Junkyard and several pages of a Google search, but perhaps I didn't know what to look for.

Thanks very much.


texts: Atomic snapshot algorithms on tree-structured shared registers

texts:
Background:
Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety.
The Gang of Six algorithm shows that such an atomic snapshot object has wait-free implementation with $\Theta(n^2)$ reads and writes to the component shared registers (when they are restricted to single-writer, $n$-reader registers) in the worst case. This time complexity is then reduced to $\Theta(n \log n)$ using a more clever algorithm.

Questions:
The two algorithms are both concerned with the most general structure of the underlying single-writer, $n$-reader registers. That is to say, they are simply an unorganized array of registers.

However, in many situations, they are in tree structures, like in a file system. For instance, in ZooKeeper, the in-memory znodes are organized in a hierarchical namespace referred to as the data tree. My questions are:

  Are there any atomic snapshot algorithms concerning the special tree structures of the underlying shared registers? (I found nothing closely related.)
  What are the advantages an atomic snapshot algorithm can take when the underlying shared registers are organized in trees, in hope of reducing the worst-case (or average-case) time complexity.


texts: Are there distribution properties which are "maximally" hard to test?

texts:
A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required to decide (w.h.p) if $D\in P$ or $d(D,P)>\epsilon$ ($d$ here is usually the $\ell_1$ distance). The most common measure of complexity is the number of samples used by the algorithm.

Now, in standard property testing, where you have query access to some object, a linear lower bound on query complexity is obviously the strongest lower bound possible, since $n$ queries would reveal the entire object. Is this the case for distribution testing as well?

As far as I understand, the "trivial" upper bound for testing properties of distributions is $O(n^2\log n)$ --- by Chernoff bounds, this is enough to "write down" a distribution D' which is close to D in $\ell_1$ distance, and then we can just check if there are any distributions close to D' which are in P (this might take infinite time, but this is irrelevant to sample complexity).

Is there a better "trivial" test for all distribution properties?
Are there any distribution properties for which we know sample lower bounds stronger than linear?


texts: Constant Width Max Sum Product Multi-objective Shortest path problem

texts:
This question is a follow-up on the question I asked three days ago here.

For convenience I restate it here.

I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1, which sum up to 1 (at most).
A path is first assigned a vector, which is the component-wise product of the weights of the edges along the path. The path is then assigned a value, which is the sum of the entries of this vector. I am interested in the maximum path.

More specifically, I consider the following decision problem: given a graph, a source, a target and a threshold c in (0,1), does there exist a path from the source to the target whose value beats the threshold c?

As @Denis has shown, this problem is NP-complete if the size of the vector is part of the input.

I am interested in the following restriction: now the size of the vectors (meaning, number of entries) is restricted to a constant K (not part of the input).
It is clear that the problem is polynomial for K = 1. Is it polynomial for K = 2? Is there K such that it is polynomial for K and NP-complete for K+1?


texts:
Consider the following integer program (general covering):

$\min c \cdot x$ subject to

$Ax \ge b$,

where all entries in $A, b, c$ are nonnegative and $x$ is required
to be nonnegative and integral.

In Vazirani, it is an exercise to show that an $O( \log n )$-approximation algorithm exists,
where $A$ is an $n$ by $m$ matrix.  Could someone give me a reference
on how to do this?

In particular, I am interested in the case when $x$ is required to be binary, and in the use of linear programming to approximate.


texts: What is conjunctive truth table reduction?

texts: What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?


texts: Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation?

texts:
The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is represented by a father-child link in this tree.

Similar trees can also be constructed for visualising the computations of probabilistic and quantum machines as well. (Note that it is better for some purposes not to view the related graph for quantum computations as a tree, since two nodes representing identical configurations at the same level of the tree can "cancel" each other out, due to quantum interference, but this doesn't have anything to do with the present question.)

Of course, deterministic computations are not like that; there is a single "branch" in the corresponding "tree" for any run of a deterministic machine.

In all the three cases mentioned above, what sometimes makes these computations "difficult" for deterministic computers is not really that there is branching going on, rather, it is a matter of how much branching is present in the tree. For instance, a polynomial-time nondeterministic Turing machine which is guaranteed to produce computation trees whose "widths" (i.e. number of nodes in the most crowded level) are also bounded above by a polynomial function of the input size can be simulated by a polynomial-time deterministic TM. (Note that this "polynomial width" condition is equivalent to restricting the NTM to make at most a logarithmically bounded number of nondeterministic guesses.) The same thing is true when we put similar width bounds on probabilistic and quantum computations.

I know that this issue has been examined in detail for nondeterministic computations. See, for example, the survey "Limited Nondeterminism" by Goldsmith, Levy, and Mundhenk. My question is, has this phenomenon of "limited branching" or "limited width" been studied in a common framework encompassing all of the nondeterministic, probabilistic, and quantum models? If so, what is the standard name for it? Any links to resources will be appreciated.


texts: PromiseBQP and expectation values of operators

texts:
This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,

  ... a difficult and unsolved meta-question is whether PromiseBPP = PromiseBQP
  implies SampP = SampBQP. Translated into “physics language,” the question is this: suppose we
  had an efficient classical algorithm to estimate the expectation value of any observable in quantum
  mechanics. Would that imply an efficient classical algorithm to simulate any quantum experiment,
  in the sense of sampling from a probability distribution close to the one quantum mechanics predicts?

I have trouble understanding this statement. From the definition of PromiseBQP I don't see how PromiseBPP = PromiseBQP means an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics. Any ideas how this connection can be made?


texts:
My graph is as follows:

I need to find a maximum weight subgraph.

The problem is as follows:

There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in different Vertex cluster, there is a weighted edge, and in the same Vextex cluster, there is no edge among vertexes. Now I want to find a maximum weight subgraph by finding only one vertex in each Vertex cluster. And the total weight is computed by adding all weights of the edges between the selected vertex. I add a picture to explain the problem. Now I know how to model this problem by ILP method. However, I do not know how to solve it by an approximation algorithm and how to get its approximation ratio.

Could you give some solutions and suggestions?

Thank you very much. If any unclear points in this description, please feel free to ask.


texts: List of NP-Complete graph problems/ properties?

texts: Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for finding them?


texts: Very simple question, for which I failed to find an explanation: what does "modulo" mean in the "Satisfiability Modulo Theories"?


texts:
The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.

People in parameterized complexity theory strongly believe that k-colooring is strictly harder than the k-clique problem, because k-clique problems can be solved by an exhaustive search of all ${n \choose k}$ potential cliques while k-coloring is NP-complete for a fixed k (k=3). k-coloring is also monotone function.

It seems to be natural that the approx method is appropriate for deriving lower bounds of the problem but I haven't seen a paper which justifies this intuition.

Is Razborov's method useful to derive the exponential monotone lower bound of k-coloring?


texts:
What is known about the relation between the class of regular lanuages and NLOGTIME? Is any class contained in another one?

You have some choice of how to define NLOGTIME to get one or both inlcusions; cf., e.g., Regan & Vollmer, Gap-languages and log-time complexity classes, TCS 188 (1997), pp. 101–116.


texts: Can typed lambda calculi express *all* algorithms below a given complexity?

texts:
I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming larger as the expressiveness of the type system grows. I recall that, e.g., the Calculus of Constructions can express at most doubly exponential complexity.

My question concerns whether the typed lambda calculi can express all algorithms below a certain complexity bound, or only some? E.g. are there any exponential-time algorithms not expressible by any formalism in the Lambda Cube? What is the "shape" of the complexity space which is completely covered by different vertices of the Cube?


texts: Max-Cut algorithm that shouldn't work, unclear why

texts:
OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:

Given an undirected graph $G=(V,E)$, give an algorithm that finds a cut $(S,\bar{S})$ such that $\delta(S,\bar{S})\geq |E|/2$, where $\delta(S,\bar{S})$ is the number of edges crossing the cut. Time complexity must be $O(V+E)$.

For some reason, I got a lot of the following solution. Now, it does use too much time, so it's not a matter of grading, but I got curious. It doesn't "seem" correct, but all my attempts at counterexamples have failed. Here it is:

Set $S\leftarrow \emptyset$
Let $v$ be a max degree vertex in the graph
Add $v$ to $S$
Delete all edges adjacent to $v$
If $\delta(S,\bar{S}) < |E|/2$ return to 2

Note that $E$ in step 5 refers to the original graph. Also note that had we skipped step 4, this would obviously be wrong (for example the union of a triangle with two isolated edges).

Now, any simple proof has the following problem - it might be that when we add a new vertex $v$ we actually remove $|S|$ edges from the cut while adding $d(v)$ new edges (where $d(v)$ refers to the graph with edges deleted). The thing is, that if this is detrimental to our cause, it means that this vertex $v$ "used to" have an ever higher degree, so it "should have been" selected earlier.

Is this a well known algorithms? Is there some simple counterexample for it?


texts: deciding $\beta$-equality of planar lambda terms

texts:
Mairson showed that the problem of computing the $\beta$-normal form of a linear lambda term (or equivalently, computing its principal type) is complete for polynomial time.

Harry Mairson. Linear lambda calculus and PTIME-completeness. JFP 14(6), 2004.

In particular, he showed PTIME-hardness by reduction from the circuit value problem.

My question is about the restriction of the decision problem to linear lambda terms which are planar in the sense that they can be typed without using the exchange law (e.g., $B = \lambda x.\lambda y.\lambda z.x(yz)$ is planar, but $C = \lambda x.\lambda y.\lambda z.(xz)y$ is not). Is this an open problem? I would suspect that it has lower computational complexity, since Mairson's encoding of boolean circuits uses non-planarity in an essential way to distinguish "True" from "False".

I'm specifically interested in $\beta$-equality of planar lambda terms, but the problem is related to deciding equality of proofnets for non-commutative multiplicative linear logic, so I'd also be interested in any results in that direction.


texts: What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?


texts:
Are there any applications of lattice-based algorithms other than those in cryptography and integer programming?

Could someone state a few papers where
the primary algorithms use lattice-based LLL algorithms?


texts: Higher order Quines - when do super Quines exist?

texts:
The normal Quine - a program that prints its own code - is a special case of an n-Quine.

An n-Quine is a program that prints code for a different program that after n iterations of printing and running will yield its own source (it has a period of n, and it does not repeat during the first n-1 iterations).

A "super Quine" is a (n>1)-Quine that is shorter than all the shortest n-Quines with smaller n (including the shortest 1-Quine = normal Quine).

When are super Quines possible? It's easy enough to think of a language where they are. But it is hard to think of an example in any general purpose language.

What factor determines the presence or absence of super Quines in a language?


texts: Is square removal easier than factoring?

texts:
It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i.e. some commonly believed hypothesis which would be violated if factoring could be reduced to square removal? But if square removal should indeed be easier than factoring (in the sense outline above), then the next question is whether it is an NP-intermediate problem (i.e. whether a polynomial time algorithm for it is known or not).

Here is a clumsy description of the square removal and factoring tasks:

Let $n\in\mathbb{N}^*$ be given in binary representation. Let $n=\prod_i p_i^{\alpha_i}$ with $p_i$ prime, $\alpha_i\in\mathbb{N}^*$, and $p_i\neq p_j$ for $i\neq j$ be the prime factorization of $n$.

For square removal, the binary representation of $m=\prod_i p_i$ is requested.
For factoring, finding (the binary representation of) a non-trivial factor of $n$ is requested, i.e. a number $q=\prod_j p_j^{\beta_j}$ with $1<q<n$, $\beta_j\in\mathbb{N}$, and $\beta_j\leq\alpha_j$.


texts: Hardness of Approximation for minimum path cover in an undirected graph?

texts:
Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path cover of $G$ having the least number of paths.

One can show the minimum path cover problem is NP-hard by a reduction from Hamiltonian path: a minimum path cover consists of one path if and only if there is a Hamiltonian path in $G$. This reduction is shown in wikipedia.

But is there any result showing the hardness of approximation for minimum path cover in an undirected graph? e.g., what is the best approximation ratio a polynomial-time algorithm can achieve?


texts: Problems of similar complexity for different measures

texts:
It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a poly-space lower bound (say for multi tape TM), i.e. is there a space-hard problem in $\mathbf{P}$?

Similarly, is there a problem in $\mathbf{P}$ with a good non-deterministic time lower bound? Is there a problem in $\mathbf{NP}$ with poly-space lower bound? ...


texts: What are current open problems in compiler theory?

texts: Compiler theory seems to be a pretty vetted subject. What are some open problems or current research happening in the field?


texts:
Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.

Denote $\mathcal P(a,c)$ to be the set of convex polytopes in $\Bbb R^n$ presented by $O(n^a)$ linear inequalities with $e/d=O(n^c)$.

Is it $\#P$ complete to find number of integer points in such polytopes?
Is it $NP$ complete to decide existence of integer points in such polytopes?

I am essentially asking if the polytope is reasonably round what is the difficulty of counting and decision problems. Here for quantifying roundedness I use width and max distance (but may be some other quantification which I do not know may be appropriate).

I think some strange partition of 0/1 cube with convex faces might suffice for 1.


texts: Can a hash preimage be used to amplify BPP probabilities?

texts:
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$.  A standard way to do this is to use a classical PRG to randomly sample a number $r$ uniformly from $[0,S]$; we can plug $r$ into $P$ to see if $P(r)=0$.  If we only perform the above test one time, we would be "fooled" into thinking the polynomial is $0$ when it's not only $d/S$ times.  However, we can rinse and repeat $k$ times to amplify our success probability, and our probability of being "fooled" is at most $(d/S)^k$.

As an alternative to rinsing and repeating, suppose instead we draw $r$ uniformly at random where we also know that $H(r)\le 2^{-m}$ for some cryptographic hash $H$ and some target $m$.  That is, $r$ is not merely chosen uniformly at random from $[0,S]$, it's also a special $r$ that is chosen from all $[0,S]$ that hash on to less than a small value.

  If we know that $H(r)\le 2^{-m}$, and we also know that $P(r)=0$, can we conclude that our probability of being "fooled" is at most $(d/S)^m$?

If we only choose one $r\in[0,S]$ whose SHA256 hash begins with a leading $0$, and test that $P(r)=0$, is that "the same" as testing if $P(r_1)=P(r_2)=0$ for two different $r_1, r_2\in[0,S]$?


texts: If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? If that is possible can it be generalized to all possible languages or just a subset?


texts: Neural Networks to classify accelerometer double taps

texts:
I'm building an application for Android devices that requires it to recognize, by accelerometer data, the difference between walking noise and double tapping it. I'm trying to solve this problem using Neural Networks.
At the start it went pretty well, teaching it to recognize the taps from noise such as standing up/ sitting down and walking around at a slower pace. But when it came to normal walking it never seemed to learn even though I fed it with a large proportion of noise data.
My question: Are there any serious flaws in my approach? Is the problem based on lack of data?
The network
I've choosen a 25 input 1 output multi-layer perceptron, which I am training with backpropagation. The input is the changes in acceleration every 20ms and output ranges from -1 (for no-tap) to 1 (for tap). I've tried pretty much every constallation of hidden inputs there are, but had most luck with 3 - 10.
I'm using Neuroph's easyNeurons for the training and exporting to Java.
The data
My total training data is about 50 pieces double taps and about 3k noise. But I've also tried to train it with proportional amounts of noise to double taps.
The data looks like this (ranges from +10 to -10):
Sitting double taps: http://i.stack.imgur.com/a7PDT.png

Fast walking: http://i.stack.imgur.com/ljRwp.png
So to reiterate my questions: Are there any serious flaws in my approach here? Do I need more data for it to recognize the difference between walking and double tapping? Any other tips?


texts: Zero error randomized communication complexity vs deterministic communication complexity

texts:
It is known that for $\Theta(1)$ error the worst case definition of randomized communication complexity and average case definition are equivalent. But when the error is $0$, the worst case randomized communication complexity is same as deterministic communication complexity.

Is any function known to have super-constant deterministic communication complexity but constant zero error randomized communication complexity?

More generally, what is a witness function that separates deterministic communication complexity and zero-error randomized communication complexity?

Any help is appreciated.


texts: Is there an algorithm that's "like" cross-validation for approximation algorithms of NP-hard problems?

texts: I normally do machine learning work, and when I'm evaluating an algorithm on a data set, I always use cross-validation to determine how effective the algorithm is.  Is there a similar method for evaluating approximation algorithms on specific instances of NP-hard problems?  If not, how do you determine which algorithm is best for a given problem domain in practice?


texts: Less known graphical representations of Boolean functions

texts:
A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other variants and derivatives such as zero-suppressed BDDs, algebraic and multi-terminal decision diagrams, as well as propositional DAGs.

The lattice or Boolean-algebraic structure of the set $\{0, 1\}^n$ might also serve as a foundation for a (not necessarily efficient) graphical representation of functions $f: \{0, 1\}^n \rightarrow \{0, 1\}$.

I just need to know about other graphical (or lattice-based) representations of Boolean functions (or, more generally, functions into finite sets) that may be less popular than BDDs, possibly because they turned out to be inefficient or because they apply only to restricted families of functions (e.g., isotone or linearly separable functions), etc.

The literature of these graphical representations (and their applications) is vast and it is really hard (but still very useful) to know about less popular ones (at least to avoid their pitfalls).


texts:
Consider a function $f : \mathbb R^m \rightarrow \mathbb R^n$.

Function $f$ can be written down as a simple arithmetic program. It uses addition, subtraction, multiplication and division - however, we condition the input to be such that no division by zero occurs.

Which algorithms do exist to simplify such a program, i.e., that produce an equivalent program of shorter (or shortest) length?


texts:
What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version asking whether there exists such a minor for given $k$) but I don't know of a published proof.

There are some papers on constant factor approximations to this problem, e.g.:

Demaine, E.D.; Hajiaghayi, M.; Kawarabayashi, K. (2005). Algorithmic graph minor theory: Decomposition, approximation, and coloring. FOCS, 637–646.
Gua, Q.-P.; Tamaki, H. (2011). Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time. Theoretical Computer Science 412 (32): 4100–4109.

Is it hard to $(1+\epsilon)$-approximate, for some $\epsilon>0$?


texts: Dynamic transitive closure with immediate new reachability facts

texts: The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, most works on time complexity provide separated estimations on update operation and reachability query evaluation. But what about the case when one wants to get new reachability facts immediately on the update? So, we have only update queries, and as a result of each edge insertion we want to get all new reachable pairs (for edge deletion --- all pairs that became unreachable, for example). Are there any results on the theoretical time complexity of such a case?


texts: Are the problems PRIMES, FACTORING known to be P-hard?

texts:
Let PRIMES (a.k.a. primality testing) be the problem:

  Given a natural number $n$, is $n$ a prime number?

Let FACTORING be the problem:

  Given natural numbers $n$, $m$ with $1 \leq m \leq n$, does $n$ have a factor $d$ with $1 < d < m$?

Is it known whether PRIMES is P-hard? How about FACTORING?
What are the best known lowerbounds for these problems?


texts:
In 1992 in the paper Imperative Functional Programming, Simon Peyton Jones and Philip Wadler write:

  So monads are more powerful than continuations, but only because of the types! It is not clear whether this is only an artifact of the Hindley-Milner type system, or whether the types are revealing a difference of fundamental importance (our own intuition it's the latter -- but it's only an intuition.)

There seems to be a lack of evidence for the Hindley-Milner side of the question. (Perhaps there is an interesting paper in this as well).

My question is: Are the types that show monads are more powerful than continuations revealing something of fundamental importance? (ie are there some papers that have addressed this since 1992).


texts:
There are protocols which make use of invoking an oracle or submitting queries to an oracle and getting response from that. There are many examples in which oracles are used to define security, like IND-CCA security and there are many examples of using the term oracle to just a procedure accepting input and providing some output, independent of the input, like non-information oracles of Canetti (you can refer to my previous question to read more about non-information oracles). My question is about the Random Oracle, that is an oracle with random output.

  When can we determine that we are using the random oracle model? For example, when we use the random output of a hash function, definitely we are in the random oracle model, but if we use one way property of hash function we are not using random oracle model. Can you provide more examples on this?

Let me clarify my ambiguity through an example. In this article the authors use a new oracle which is relatively unknown called linear oracle bilinear Diffie-Hellman (or in short LO-BDH) and security of their approach lies in the hardness of this assumption. How can I determine that using this assumption, we are not using the random oracle model (the authors claim that they are not in the random oracle). Here is another source of ambiguity:

  They are using commitments over UC framework which are impossible in the plain model thus they are at least using common reference string (CRS) model. How can I make sure that if I use such an oracle (LO-BDH) in the security proof of another protocol, I am still in the plain model or using it does not cause undesired shifting of models?

Edit: I found interesting material on RO methodology in the book Introduction to modern cryptography by Katz and Lindell. the rest is from the mentioned book.

  When defining pseudorandom functions, the authors have considered algorithms having oracle access to a random function. But usage of a random function there is very different from the usage of a random function in the RO methodology. In the pseudorandom functions, a random function is used as a way of defining what it means for a concrete keyed function to be pseudorandom. In the random oracle model, the random function is used as part of the construction of the primitive, so must somehow be instantiated in the real world if we want a concrete realization of the primitive.

BTW, the authors have noted that a random oracle is not a one way function because random oracle is not a fixed function, but in order to implement it in a real world, it must first be instantiated and description of it must be fixed. So a hash function is fixed before executing the protocol.


texts:
Can anyone recommend a good book(s) or journal article(s) on object-oriented program design patterns/principles and simulation modeling of diseases?

I received the above question this morning by email.  It was sent to a SIAM list service I belong to.  I don't know the asker, and I don't know a good answer either.  I figured, though, if some people here had good suggestions, either theoretical or practical, I could send him the link to this question.

Thanks.

Edit: I sent the asker a copy of this question, with Artem K's answer visible.  He responded, saying thanks.


texts: How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem

texts:
Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for simplicity, it can be a uniform distribution (50% probability for 0 and 50% for 1). And there is a set of constraints over the variables, thus in the constrained state space, the actual probability distribution of each variable will skewed. For example, if we have two variables a,b and a constraint a=0->b=1, the actually probability that b=0 will be 1/3 compared to 0.5 when unconstrained.

I am wondering if there are any results on estimating the probability distribution of the random variables under a set of constraints. The golden answer of the probability distribution could be derived by using the SAT solver to get all the solutions and then computing the statistics, which is prohibitively computationally expensive. Thus I am wondering if there is any way to do a fair estimation on that.


texts: The size of output in circuit complexity

texts:
In circuit complexity we have one circuit for each input size.
The size of the output is determined solely by the size of the input.
So it seems to me that taken in its strict sense there are functions computable in $\mathsf{P}$ over $\{0,1\}^*$ which are not computable in $\mathsf{P/poly}$.

This is partly caused by using $\{0,1,b\}$ in the Turing machine model
while in circuit model we only have $\{0,1\}$.

Is there a nice standard way to deal with this issue
that would work well for small complexity classes
(e.g. it shouldn't change the complexity of computing AND of inputs too much,
so encoding/decoding inputs/outputs is not a good solution)?

Is there a simple modification of Turing machine model or circuit model
which would make them correspond without this issue?


texts: Is there a algorithm for Max Cut on a Planar Directed Graph (MAX DIRECTED CUT ALGORITHM)?

texts:
Max Cut on a Undirected Graph has many algorithms when the Undirected Graph is Planar.
I have been wondering though if one could generalise this to Directed Planar Graphs?


texts: What is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)?

texts:
The Idea is this:

The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS.

However Dense versions of Max Cut do have a PTAS!

This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up.

Does such a speedup exists in the complexity literature?

Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable!


texts: A theorem regarding statistically-hiding commitment schemes

texts:
Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends $C_n(m ; r)$ to the receiver. To decommit, he simply reveals $m$ and $r$. We let $C_n(m)$ denote the random variable obtained by uniformly and independently picking $r$ (of proper length) and computing $C_n(m ; r)$.

Finally, let $U_n$, $U_n'$, and $U_n''$ be i.i.d. random variables with uniform distribution over $\{0,1\}^n$. We assume that repeated use of a random variable results in the same sample. For example, $\langle U_n, U_n+1 \rangle$ means a pair, where we first sample $U_n$ to obtain an $n$-bit string $m$, and then let the pair be $\langle m, m+1 \rangle$.

I want to prove that the following distribution ensembles are statistically indistinguishable:
$$\mathcal {X} = \{\langle U_n, C_n(U_n) \rangle\}_{n \in \mathbb{N}} \enspace,$$
$$\mathcal {Y} = \{\langle U_n', C_n(U_n'') \rangle\}_{n \in \mathbb{N}} \enspace.$$


texts: Resource / book for recent advances in statistical learning theory

texts:
I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class Lemma, Covering Numbers, Chaining, Dudley's Theorem, Pseudodimension, Fat Shattering Dimension, Packing Numbers, Rademacher Composition, and possibly other results / tools that I'm not aware of.

Is there a website, survey, collection of articles, or, best of all, a book covering these topics?

Alternatively, I'm looking at examples of how to bound the Rademacher average for simple classes, in the same way that people use axis-aligned rectangles to show how to bound VC-dimension.

Thanks in advance.


texts: Lower Bound for the Parity Learning Problem

texts: What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, | \, \,\sum_{i=1}^n x_i = k \}$, and the hypothesis space $\mathcal H$ is $\{0,1\}^n$. Given a bitstring of length $n$ as input, the adaptive membership query oracle returns 1 if the parity of the $k$ effective bits is odd and 0 otherwise.


texts: Is there a relationship between computational complexity theory and complex systems theory?

texts:
Computational complexity theory classifies problems according to their inherent difficulty.

Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts.  Examples include chaotic systems, complex adaptive systems, or nonlinear systems.

Is there any formal bridge between these fields?

For what it's worth, the notion of performing cryptography with cellular automata is not new, and earlier this year
Applebaum, Ishai, and Kushilevitz identified "complexity" with computational intractability.


texts: Tradeoff between running time and depth in neural network

texts:
I might not be in the good stack-exchange site, so please forgive me.

Let consider a neural network that we want to train to a certain task. For the purpose of my research, I am wiling to reduce the number of operations during the training process within my encrypted neural network (homomorphically encrypted). However, I'm definitely not an expert in this domain and I would need some insights.

The weights inside my neural network are all encrypted in a way that allows normal computations (and hence proper training phase). However, encrypted operations are much more costly than operations on clear data.

Practically, if we want to reach a certain value for the error function (let's say $E < 0.01$) for instance, does there exist a tradeoff between number of operations and depth of the neural network.

As far as I know, people tend to find the accurate size of a neural network by trials and intuition but maybe some people made some theoretical results on this kind of tradeoff (even for only one specific kind of NN) ? If you have any paper to recommend I would gladly take them!


texts: The polynomial languages and ordered syntactic monoids

texts:
A polynomial language is a languge which could be represented as the finite union of languages of the form:
$$
 A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X
$$
Such an expression is called a monom and it's degree is the value $k$.
Equivalently it could be defined as the smallest class containing the finite languages, languages of the form $A^*$ for $A \subseteq X$ and closed under union and concatentation.

The degree of a polynomial language is the maximum degree of the monoms in a minimal (with regard to the degree) representation of the polynomial language in the form of unions of monoms.

An ordered monoid $(M, \le)$ is a monoid $M$ together with a partial order which is compatible with multiplication. A set $D$ is called downward closed if $p \in D$ and $q \le p$ implies $q \in D$. An ordered monoid recognized a language $L$ via a morphism $\varphi : X^* \to M$ if
$$
 L = \varphi{-1}(\downarrow\varphi(L))
$$
where $\downarrow D$ denotes the smallest downward closed subset containing $D$.

For the syntactic monoid $Syn(L)$ there is a natural order given by $u \le_L v$ iff
$$
 \forall p,q \in X^* : pvq \in L \Rightarrow puq \in L.
$$
Then for $[u], [v] \in Syn(L)$ it is $[u] \le [v] :\Leftrightarrow u \le_L v$.

  Let us consider a polynomial language $L$ of degree $k$ and words $u,v$ with $\mbox{alph}(v) \subseteq \mbox{alph}(u)$. Then for all $p,q$ we have $pu^{k+1} q \in L$ implies that $pu^kv u^k q\in L$, too. Thus, the syntactic orderd monoid of $L$ satisfied an equation of type $u^{\pi}vu^{\pi} \le_L u^{\pi}$

Remark: $u^{\pi}$ denotes the unique idempotent associated with $u$, for example $\pi = n!$ where $n$ is the size of the finite monoid.

The shaded paragraph I do not understand, the relation
$$
 pu^{k+1}q \in L \Rightarrow pu^k vu^k q \in L
$$
for $\mbox{alph}(v) \subseteq \mbox{alph}(u)$ and $k$ the degree of the polynomial is clear cause a monom of degree $k$ can "fix" just $k$ letters, and so some $u$ lies in some $A_i^* \subseteq X^*$ and so also $v$. But why does this order relation for the syntactic monoid follows? Is there any simple relation between the idempotent powers and the degree I do not see?


texts: Bidirectional A*: is an update of the distance estimation feasible while searching?

texts:
The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal.

The bidirectional case of A* is not as simple as the bidirectional Dijkstra as the finish condition is a bit tricky, of course you can manage to implement it if you work with "consistent potential functions" (see paper reference below).

Now to my question: when implementing a special distance estimate for A* (landmarks/ALT) this works also in the bidirectional case. In some papers they say one can change the active set of landmarks while the search is going on. This makes sense as the estimates will get better and still only a subset is involved for the estimate.

But will changing/improving the distance estimate while the search is going influence the optimality?

Unintuitive things can follow from this, e.g. a distance update to a node lowers the distance from source to this node but could increase the distance from this node to the goal due to the better distance estimate but I'm unsure if this violates the 'consistent potential' definition and could result in suboptimal paths. (E.g. in my latest trial to implement this I sometimes get suboptimal results but this could be also other bugs.)

The paper "Computing Point-to-Point Shortest Paths from External Memory" says I can do so but I'm unsure if I misunderstood something:

  6.1 Restarting. As we shall see below, we sometimes need to change the way lower bounds are calculated in the middle of an ALT computation,
  e.g., by replacing the current potential functions p f and p r by
  another consistent pair.


texts:
Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that

The rank of the sub matrix $M[A, V\setminus A] \leq k$
$|A|\geq |V|/c$, $|V \setminus A|\geq |V|/c$, for some constant $c>1$.

where  $M[A, V\setminus A]$ denote the submatrix $(m_{ij};i \in A, j \in V \setminus A)$.

Note: Assume that existence of such a subset $A$ is guaranteed. .


texts: Succinct circuit representation of graphs

texts:
The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:

END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0n) = 0n != S(0n), find an input x in {0,1}n such that P(S(x)) != x or S(P(x)) != x != 0n.

Circuits or algorithms such as S and P implicitly define an exponentially large graph that is only revealed on a query-by-query basis (to keep the problem in PSPACE!), e.g. Papadimitrou's paper.

However, I don't understand how one would design a circuit that enables arbitrary graphs (if there is a systematic structure to the graph, it appears much easier to find the circuit). For instance, how would one design a polynomially-sized circuit that represents an exponentially-long directed line, with an all-0 label for the source vertex and randomly assigned binary labels to all other vertices? This seems to be implicit in the PPAD-related papers.

The closest I've come from a search online is Galperin/Widgerson's paper, but the circuit described there takes two vertex labels and returns a Boolean answer to "Are these vertices adjacent?"

So, how would you design a polynomially-sized circuit of an exponentially-sized graph that takes an n-bit input and outputs the n-bit label of its predecessor or successor, respectively? Or even, does someone know of a resource that explains this well?


texts: Greedy Backpropagation: has anyone researched it?

texts:
Backpropagation is computationally expensive. Has any research been done on a partially greedy implementation of it?

Intuition: at the beginning of training, big rough learning steps can be taken, so do we really need to tune each individual weight?

If we were to plot time series of every parameter as its value changes over training time, might we get correlations between certain parameters, particularly at the beginning of training?

For example, since the gradient propagates backwards, we might get correlations between the parameters of neurons behind one another. Such correlations could suggest that it's a waste of time to compute partial derivatives for all parameters, i.e we can use the partial derivative for a neuron in front to approximate the partial derivatives for the neurons behind it?

Has anyone seen any articles exploring anything like this?


texts:
Suppose we have an ID-based encryption (IBE) (Setup, Extract, Enc, Dec) scheme which is IND-ID-CPA (resp IND-ID-CCA) secure, and we want to construct threshold version of this scheme.
My question is: how to define the IND-ID-XXX security game for the new scheme.


texts: Is there any language for which a perfect optimization is decidable?

texts:
Is there a programming language L where it is possible to write an optimizer O, that, receiving a program in L and a set of cost for every low-level operation in L, returns the equivalent program with the least total cost possible?

Practical example:

(optimize '(* a a) [['* 2] ['pow 1]])

Should return:

(pow a)

For a hypothetical language where '*' and 'sqrt' are the only primitive operations, as the cost of the 'sqrt' operation (1) is lower than the cost of the '*' operation (2).


texts: Internal Regret in Online Convex Optimization

texts: Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and gives good "external regret".  Is there a similar generalization for internal regret?  (I'm not totally sure even what exactly that would mean.)


texts: A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?

texts:
Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)?

In greater detail:
given the well known definition of a grammar $G = (N,\Sigma,P,S)$ with $N$ being a finite set of nonterminal symbols, $\Sigma$ being a finite set of terminal symbols with $N \cap \Sigma = \emptyset$, $S \in N$ being the start symbol and $P$ being a finite set of production rules $P = \{(l_0,l_1,…,l_i)\times(r_0,r_1,…,r_j)^{*}\} \subset \alpha N \beta \rightarrow \gamma$ with $(l_i)\times(r_j) \in (\Sigma \cup N)\times(\Sigma \cup N)$ and $\alpha, \beta, \gamma \in (\Sigma \cup N)^{*}$, does there exist a set of further conditions on $\alpha$, $\beta$ and $\gamma$ only dependend on any of the $l_i$ and $r_j$(in other words, it is a purely syntactic restriction) such that $L(G) = \mathbf{PR}$?

Clearly, since $\mathbf{CSL} \subsetneq \mathbf{PR} \subsetneq \mathbf{RE}$ and both $\mathbf{CSL}$ and $\mathbf{RE}$ admit a grammar formalism (namely the noncontracting or monotonic grammars and the unrestricted grammars), I wondered whether such a formalism might exist for $\mathbf {PR}$ as well.

Contrary to the classes of $\mathbf{CSL}$ and $\mathbf{RE}$, the only known definitions of $\mathbf{PR}$ seem to either use nested functional equations or abstract programming language constructs instead of formal grammars. Extensive search in the academic literature, forums and online didn't gave any answers. It seems this question is an open problem bare of any interest.

I know that many arithmetic functions over the natural numbers can be defined using $\mathbf{PR}$ nested functional equations and that such arithmetic functions can also be defined using string rewriting or formal grammars. However, given the potential complexity by applications of either definitions of $\mathbf{PR}$ and the additional complexity arising by trying to delimit them from $\mathbf{RE}$, it seems unclear to find a phrase structure grammar formalism which generates exactly $\mathbf{PR}$.


texts: Are query-dependent ranking algortihms for web search doomed to be impractical?

texts:
Algorithms like HITS and SALSA are query dependent, and I've been given the impression that this makes them able to retrieve more accurate results. However, the query-dependent nature of these algorithms makes them unusable for practical implementation. For example, I have read that HITS is impractically slow.

Are query dependent methods doomed to fail the practicality test? I've seen some papers that have tried to speed up the computations involved. Is adoption of query-dependent methods, or some hybrid, something we could see in future?


texts: Which algorithms have been proposed to learn the architecture of a deep neural network?

texts:
Yoshua Benhgio's Learning Deep Architectures for AI book mentions that

  we should [...] strive to develop learning algorithms that use the data to determine the depth of the ﬁnal architecture.

Would anyone know of any algorithms proposed thus far to achieve this?

So far I have come across:

The tiling algorithm for building a feed-forward network to learn a Boolean function. It adds layers as well as units, but Boolean functions aren't too relevant for applied problems.


texts:
I was reading a set of notes where it says

  It can be shown that $\Omega(n^2)$ space is needed for one-pass algorithms to determine if an (unweighted, undirected) graph $G$ with $n$ nodes contains a triangle, even with randomization.

I've seen communication complexity results like that randomized protocols for disjointness require $\Omega(n)$ space, but what's a sketch or reference for the result above?


texts: Most optimal parallel method for calculating the integral of a 2D function

texts:
I posted already this question to SO but got no answer so I try it now here:

In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance the function, but I need to know the total "surface" of the function which is equal to zero. In a similar problem I could draw a rectangle over the 2D representation of the map of United Kingdom. The function is equal to 0 at sea, and 1 at the earth. I need to know the total water surface. I wonder what is the best parallel algorithm or method for doing this.

I thought first about the following approach; a) divide 2D map area into a rectangular grid. For each point that belongs to the center of each cell, check whether it is earth of water. This can be done in parallel. At the end of the procedure I will have a matrix with ones and zeroes. I will get the area with some precision. Now I want to increase this precision, so b) choose the cells that are in the border regions between zeroes and ones (what is the best criterion for doing this?) and in those cells, divide them again into successive cells and repeat the process until one gets the desired accuracy. I guess that in this process, the critical parameters are the grid size for each new stage, and how to store and check the cells that belong to the border area. Finally the most optimal method, from the computational point of view, is the one that performs the minimal number of checks in order to get the value of the total surface with the desired accuracy.


texts: Are there temporal logics linear time properties that only have counterexamples that are more complex than a lasso?

texts:
Are there linear time temporal logics that can express some property $P_{nonlasso}$ that does have a counterexample, but none that is a lasso (or finite)?

Details:

One advantage of model checking over other formal methods is their ability to return a counterexample, a (finite path or a) path in form of a lasso. This is sufficient up to (extended) Büchi automata, since an infinite accepting path can be transformed to a lasso that infitely visits some accepting state.

But is this still the case for more complex linear time logics? Or a non-linear time logic that does have counterexamples, e.g. ACTL*? Can the $\mu$-calculus or MCRL2 express such a linear time property $P_{nonlasso}$?

For instance, having the Kripke structure $s_1 \leftrightarrow init \leftrightarrow s_2$, can I express the counting property "repeat $(init \rightarrow s_1 \rightarrow init)^i \cdot (init \rightarrow s_2 \rightarrow init)^i$ for infinitely increasing $i$"? This path does have a very simple schema...

Update: I am looking for linear time temporal logics without any relationship between multiple paths (see Makus's answer for other logics).


texts: Reasoning about non-deterministically terminating loops

texts:
Here's a "track B" question if there ever was one. Summary: the first thing I think of when I try to give a semantics to non-deterministic programs results in a semantics where I can't prove things about loops that only terminate non-deterministicaly. Surely someone has worked out what to do in this situation, or at least pointed out that it's hard, but I don't know how to go about looking for it (hence the "reference request" tag).

Background

I want to model an while-language with non-determinism. I think this is the obvious (or at least the naive) way to model such a language with a Smyth powerdomain, but correct me if I'm wrong. We will model the meaning of a command in this language is as a function whose domain is the set $S$ of states and whose codomain is the set ${\cal P}(S)_\bot = \{ \bot \} \cup {\cal P}(S)$, where $\bot$ is a least element representing non-termination and ${\cal P}(S)$ is the powerset of states.

We interpret commands as maps from states $\sigma$ to either the non-termination event $\bot$ or to sets of states $\{ \sigma_1, \sigma_2, \ldots \}$ which represent possible outcomes. $P \circledast Q$ is non-deterministic choice.

$⟦\mathbf{skip}⟧\sigma = \{ \sigma \}$
$⟦x := E⟧\sigma = \{ \sigma[(⟦E⟧\sigma)/x] \}$
$⟦\mathbf{abort}⟧\sigma = \bot$
$⟦\mathbf{if}~E~\mathbf{then}~P~\mathbf{else}~Q⟧\sigma = ⟦P⟧\sigma$ if $⟦E⟧\sigma = \mathit{true}$, otherwise $⟦Q⟧\sigma$
$⟦P \circledast Q⟧\sigma = \bot$ if $⟦P⟧\sigma = \bot$ or $⟦Q⟧\sigma = \bot$, otherwise $⟦P⟧\sigma \cup ⟦Q⟧\sigma$
$⟦P; Q⟧\sigma = \bot$ if $⟦P⟧\sigma = \bot$ or $⟦Q⟧\tau = \bot$ for some $\tau \in ⟦P⟧\sigma$, otherwise $\bigcup_{\tau \in ⟦P⟧\sigma} ⟦Q⟧\tau$

There's a directed complete partial order $\sqsubseteq$, where $\bot \sqsubseteq S'$ for any $S' \in {\cal P}(S)_\bot$ and $S_1 \sqsubseteq S_2$ if both $S_1$ and $S_2$ are proper sets and $S_1 \supseteq S_2$, and we can extend this to functions $f$ from $S$ to ${\cal P}(S)_\bot$ pointwise: $f_1 \sqsubseteq f_2$ if $f_1(\sigma) \sqsubseteq f_2(\sigma)$ for every $\sigma$, and $f_\bot$ is the function that maps every state to $\bot$.

The meaning of a loop is $⟦\mathbf{while}~E~\mathbf{do}~P⟧\sigma$ is the least upper bound of the chain $f_\bot \sqsubseteq f(f_\bot) \sqsubseteq f(f(f_\bot)) \sqsubseteq \ldots$, where $f(g)(\sigma) = \{\sigma\}$ if $⟦E⟧(\sigma) = \mathit{false}$, otherwise $\bot$ if $⟦P⟧\sigma = \bot$ or $g(\tau) = \bot$ for some $\tau \in ⟦P⟧\sigma$, otherwise $\bigcup_{\tau \in ⟦P⟧\sigma}g(\tau)$. (This definition assumes that the $f$ I just defined is Scott continuous, but I think it's safe to leave that aside.)

Question

Consider this program:

$x := 0;$
$b := \mathsf{true};$
$\mathbf{while}~b~\mathbf{do}$
$\qquad x := x + 2;$
$\qquad b := \mathsf{false} \circledast b := \mathsf{true}$

Intuitively, this is a loop that can return any positive even number or not terminate, and that corresponds to what we can prove about this loop using the weakest liberal precondition (it is possible to show that $\exists n. x = 2n$ is a loop invariant). However, because the loop has the ability not to terminate (we can refine the non-deterministic choice by the program that always takes the right-hand branch), the meaning of this program given any initial state is $\bot$. (Less informally: the function that maps any state where $b$ is false to itself and any state where $b$ is true to $\bot$ is a fixed point of the $f$ used to define the loop.)

This means that the naive semantics I proposed doesn't correspond in the way I expect to be able to reason about programs. I blame my semantics, but don't how to fix them.


texts: Is there an efficient algorithm to find the i-th dearrangement?

texts:
Here is the background for this question. Friends and I were playing a game where everyone needs to give another people some gift. In order to determine who should give gift to whom, we decide to drew lots. But the problem is, someone might end up giving him/herself gifts, which is not funny. You can see that the expected number of such unfortunate people is 1, so this happens quite frequently.

For this purpose, dearrangement seems to be a great fit. If I can fairly generate a dearrangement, then I can just pick one dearrangement and use it to decide who give whom gifts.

Randomized dearrangement generation could be done with Las Vegas method. But the problem is,
it only has expected polynomial running time. So I came to this problem of finding i-th dearrangement. If I can randomly pick an i in [1, D_n], and use some worst case polynomial time (efficient) algorithm to obtain the i-th dearrangement, then it's done.


texts:
Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree.

I cam across this page http://cs.anu.edu.au/~bdm/plantri/ which implements a program to do the above but the algorithm was not clear to me.

Any idea to design algorithm for the above problem will be helpfull.
Any link/paper to easier discussion is also welcome.


texts: Generalizing Brzozowski's DFA minimization algorithm to finite automata with different classes of accepting states?

texts:
Brzozowski's algorithm for converting a DFA into an equivalent minimum-state DFA is remarkably simple: if $R(D)$ denotes the NFA formed by reversing all the edges in a DFA $D$, making the old start state an accepting state, and making the old accepting states start states, and if $P(N)$ denotes the result of applying the subset construction to the NFA $N$, then $$P(R(P(R(D))))$$ is a minimum-state DFA with the same language as $D$.

We can think of a DFA as a computational device that accepts an input string $w$ and then outputs 0 if $w$ ends in a rejecting state and 1 if $w$ ends in an accepting state. A natural generalization of DFAs associated each state in the DFA with some natural number between 0 and $k-1$, inclusive.

To the best of my knowledge, it's possible to minimize these modified classes of DFAs by using a distinguishability-based minimization algorithm, such as the canonical one by Hopcroft. However, I can't see how it would be possible to adapt Brzozowski's minimization algorithm to this new class of automata because the key step (reversing the automaton) no longer has a clear interpretation in this generalized setting.

Is there a known generalization of Brzozowski's algorithm for minimizing these sorts of automata? If not, are there any theoretical reasons why we'd expect that such a modified algorithm wouldn't exist?


texts: Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P

texts:
I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance.

There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By definition $\mathsf{A}$ $\subseteq$ $\mathsf{B}$ but then it can be easily seen that $\mathsf{A}$ is truth table reducible to $\mathsf{B}$. Furthermore, $\mathsf{B}$ $\subseteq$ $\mathsf{coC_{=}P}$ (Zoo) and $\mathsf{FewP}$ $\subseteq$ $\mathsf{A}$ (Zoo).

1)What are the consequences of a Quasi Polynomial Time Algorithm for $\mathsf{B}$ ?
a)Does it put $\mathsf{A}$ in $\mathsf{QP}$ as well?
b)Other than proving that $\mathsf{P}$ $\neq$ $\mathsf{PSPACE}$ and $\mathsf{P}$ $\neq$ $\mathsf{PP}$ does it also show that $\mathsf{P}$ $\neq$ $\mathsf{NP}$?
2)What are the consequences of a Polynomial Time Algorithm for $\mathsf{A}$?
a)Does it put $\mathsf{B}$ in $\mathsf{P}$ as well?
b)Since $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{FewP} \subseteq \mathsf{A}$ we will have $\mathsf{P} = \mathsf{UP} = \mathsf{FewP} = \mathsf{A}$ . Then can it still be the case $\mathsf{P}$ does not equal $\mathsf{NP}$?
c)Does it also show that $\mathsf{NP} \subseteq \mathsf{RP}$ since now  $\mathsf{RP}^\mathsf{UP} = \mathsf{RP}$?


texts: Intersection between register automata and pushdown automata over infinite alphabet

texts:
I'm not an expert in automata theory, this is a reference request.
As far as I have understood it is known in the automata comunity that register automata by Kaminski are closed by intersection with pushdown automata over infinite alphabet.
Unfortunately I'm not able to find any reference about this.

Thanks in advance!


texts:
I'm seeking an efficient algorithm for the problem:

Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.
Output: The number $n$.

Question: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

This is a theoretical question motivated by my answer to a math.SE question How to find a formula for this bijection?.  In this question, the author wanted to find a bijection from $$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$ and the natural numbers $\mathbb{N}=\{1,2,\ldots\}$.  I proposed $$2^m 3^n \mapsto 2^m(2n+1)$$ as a solution.  Another answer there asserted "there is no simple formula", which makes me wonder how (computationally) simple my proposed solution is.
With my proposed solution, if we know $n$ and $m$, we can easily compute $2^m(2n+1)$ (write the binary digits of $n$ followed by $1$ followed by $m$ zeroes).  This takes $O(n+m)$ time.
Finding $m$ from the bits of $2^m 3^n$ amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving $3^n$ in memory).  This takes $O(m)$ time.
However, we also need to find $n$, which might be more difficult.  It would be possible to find $n$ by repeatedly dividing by $3$, but this seems wasteful.  It requires $n$ division operations, each of which will take $O(n)$ time, so this is $O(n^2)$ time in total.  [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in $O(n^2)$ time.]
It seems like we should be able to exploit knowing the input is a power of $3$.


texts: Checking if all products of a set of matrices eventually equal zero

texts:
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.

This means exactly what you think it does: we will say the set of matrices $\{A_1, \ldots, A_k\}$ has the property that all of its products eventually equal zero if there does not exist an infinite sequence $i_1, i_2, i_3\ldots$, all in $\{1, \ldots, k\}$, such that $$ A_{i_1} A_{i_2} \cdots A_{i_l} \neq 0$$ for all $l$.

Has the problem of deciding whether every product eventually equals zero been studied before? Is it decidable?

Seems like it might be related to matrix mortality, which is undecidable, but I do not see a clear connection.


texts: Can Lexicographic BFS be implemented in logspace?

texts:
Input: Given graph $G=(V,E)$ vertex labeling in some order

Output: Change the labeling of vertices's such that
labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ according least index given in input. Next labeling the neighbors of least index neighbor of $v_1$.
I.e. $v_1=u_1$ and neighbors of $v_1$ as $u_2,u_3,...$. so .. on

For example:
input: $G=(V,E)$ and $V=\{v_1,v_2,v_3,v_4,v_4,v_5,v_6\}, E=\{v_1v_3,v_1v_5,v_1v_6,v_2v_3,v_2v_4,v_2v_5,v_2v_6\}$

Output: $G'=(U,E')$ and $U=\{u_1,u_2,u_3,u_4,u_4,u_5,u_6\}, E'=\{u_1u_2,u_1u_3,u_1u_4,u_2u_5,u_3u_5,u_4u_5,u_5u_6\}$

Can there be a algorithm for above process in logspace?
I trying with BFS but not working in logspace. Can any one help me out.

See for defination of Lexicographic BFS(en.wikipedia.org/wiki/Lexicographic_breadth-first_search)


texts: Are there established cryptographic hardness assumptions for chaotic systems?

texts:
I found this paper of Cuomo and Oppenheim, where they use a Lorenz system to define an encryption scheme for signals. There is also this blog post describing and implementing the technique. The technique uses an interesting property of the Lorenz system known as "synchronization," which as far as I know occurs in other dynamical systems as well. Moreover, the chaotic nature of these systems intuitively makes guessing the parameters of the system infeasible, so a natural shared secret key is the set of constants used to define the system.

I was wondering if there has been any theoretical work in cryptography that deals with dynamical systems. Specifically, are there established cryptographic hardness assumptions for specific dynamical systems? It seems like it would be a different flavor of hardness assumption from the usual ones, because the methods naturally introduce some noise into the decrypted message.


texts: What are good approximation algorithms for the subset sum problem so far?

texts: By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.


texts:
I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal combinators include:

size 23: λf.f(fS(KKKI))K
size 18: λf.f(fS(KK))K
size 14: λf.fKSK
size 12: λf.fS(λxyz.x)
size 11: λf.fSK

where S = λxyz.xz(yz) of size 6 and K = λxy.x of size 2 are the combinators of the SK combinator calculus. The first 4 examples are described in this paper.

My questions are:

Are there any universal combinators that are smaller in size?
What is the smallest possible universal combinator?

EDIT: See also https://math.stackexchange.com/a/180263/76284, which has λazbc.bc(a(λy.c)) (which would be of size 8, matching the sum of sizes of the SK basis). Does anyone know how to express S and K from this combinator?


texts: Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

texts:
Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$ leaves so $c$ must be at least $1/2$. I assume that the leaves can only be labeled by variables (without negations), but it would be also interesting to know the answer if we allow also negated variables and constants.

Two examples of such formulas are given below.

$n=7$, $m=5$:

$n=9$, $m=7$:


texts: Understanding MA protocol as a variant of TM for small space setting

texts:
MA protocol is one of the most basic models of interactive proofs.

Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier  who verifies if $w$ is a positive witness of $x$ using  random bits $r$.  We say that $L$ is decided by MA protocol $\mathcal{P}$, if the following two conditions hold.

$x\in L\Rightarrow \exists w\,\Pr_r[\mathcal{P}(x,w,r)=1]>2/3$,
$x\notin L\Rightarrow \forall w\,\Pr_r[\mathcal{P}(x,w,r)=1]<1/3$.

  My question is:  What is the formal description of Turing Machine exactly simulating MA protocol with space $S(n)$?


texts: Rectangular constraints in Delaunay Triangulation without edges within

texts:
I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside of the rectangles that define the constraints.

I want to be able to create a graph without the edges within any of the rectangles that are the constraints (with the exception of the large boundary of course) but removing these edges in the triangulation that is given to me takes longer than O(nlog(n)) time at least and that's not good for what I need.

What I'm asking is, is there any quick way to get a CDT to keep edges from appearing within some polygon? I want the rectangles to be empty of edges but I'm not sure how to quickly do that.

In case this helps, the library I'm using is TriPath by Marcello Kallmann (http://graphics.ucmerced.edu/software/tripath/).

Here's an image to help you visualize what I'm trying to describe. This CDT is built with the black lines being constraints. As you can see, each constrained edge is part of a rectangle. The blue lines are unconstrained Delaunay edges. I am trying to remove any blue unconstrained Delaunay edges from within the black constrained rectangles.


texts:
What evidence is there that $coRP \neq NP$?

$coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.


texts: If an abstract machine can simulate itself, does that make it Turing complete?

texts:
For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e.g. simulating Conway's Game of Life in Conway's Game of Life).

So my question is: is a system being able to simulate itself sufficient to prove it's Turing complete? It certainly is a necessary condition.


texts: Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

texts:
SAT solvers give a powerful way to check the validity of a boolean formula with one quantifier.

For instance, to check the validity of $\exists x . \varphi(x)$, we can use a SAT solver to determine whether $\varphi(x)$ is satisfiable.  To check the validity of $\forall x . \varphi(x)$, we can use a SAT solver to determine whether $\neg \varphi(x)$ is satisfiable.  (Here $x=(x_1,\dots,x_n)$ is a $n$-vector of boolean variables, and $\varphi$ is a boolean formula.)

QBF solvers are designed to check the validity of a boolean formula with an arbitrary number of quantifiers.

What if we have a formula with two quantifiers?  Are they any efficient algorithms for checking validity: ones  that are better than just using generic algorithms for QBF?  To be more specific I have a formula of the form $\forall x . \exists y . \psi(x,y)$ (or $\exists x . \forall y . \psi(x,y)$), and want to check its validity.  Are there any good algorithms for this?  Edit 4/8: I learned that this class of formulas is sometimes known as 2QBF, so I am looking for good algorithms for 2QBF.

Specializing further: In my particular case, I have a formula of the form $\forall x . \exists y . f(x)=g(y)$ whose validity I want to check, where $f,g$ are functions that produce a $k$-bit output.  Are there any algorithms for checking the validity of this particular sort of formula, more efficiently than generic algorithms for QBF?

P.S. I am not asking about the worst-case hardness, in complexity theory.  I am  asking about practically useful algorithms (much as modern SAT solvers are practically useful on many problems even though SAT is NP-complete).


texts: What is the difference between non-determinism and randomness?

texts:
I recently heard this -
"A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for transitions are not known".

I feel as if I get the point but I really don't. Could someone explain this to me (in the context of machines or in general)?

Edit 1:
Just to clarify, the quote was in context of finite automaton, but the question is meaningful for Turing machines too as others have answered.

Also, I hear people say - "... then I choose object x from the set non-deterministically". I used to think they mean - "randomly". Hence the confusion.


texts: Jukna's book Extremal Combinatorics explains basic results about sunflowers.  Is there a more thorough survey of various sunflower results?


texts:
I'm self-studying turbo codes for a graduate course in coding theory. I understood how turbo codes works by directly reading Berrou' paper and some of the following works on this topic. Given that, there is a simple question that i canno't answer with my self...
Turbo code relies on the fundamental principle of message passing during iterative decoding, more formally speaking the extrinsic information produced by one decoder is passed as a-priori information to the next (companion) decoder. This is my problematic point: why extrinsic information, that is an a-posteriori computation (given from the Log-likelihood-ratio) should be passed as an a-priori information the next decoder?

The LLR can be expressed as:
$$L(u_i)=\log\frac{P(u_i=1|\text{observation})}{P(u_i=0|\text{observation})}=\log\frac{p(obs.|u_i=1)}{p(obs.|u_i=0)}+\log\frac{P(u_i=0)}{P(u_i=1)}$$

What if the apriori knowledge of the source is known? For example...suppose a indipendent binary source, so that $P(0)=P(1)=1/2$. In this case there is no need to update the apriori knowledge because it is exactly equal to $0$, and extrinsic information is, in general, different from $0$, so the estimate is wrong at each step.

Thanks in advance


texts: Definition of a prefix-free Turing machine

texts:
A prefix-free function is one whose domain is prefix-free.
  Similarly, a prefix-free (Turing) machine is one whose domain is
  prefix-free. It is usual to consider such a machine as being
  self-demiliting, which means that it has a one-way read head that halts when the machine accepts the string described by the bits read
  so far. The point is that such a machine is forced to accept strings
  without knowing whether there are any more bits written on the input
  tape.

From Downey and Hirschfeldt, Algorithmic Randomness and Complexity, page 122.

I don't understand why such a device would ensure that the domain of the function is prefix-free. Take a word $\omega$ accepted by the machine. Then, as the next bits won't be read, $\omega \eta$ is also accepted. So $\omega$ and $\omega \eta$ are in the domain, which is not prefix-free.

Where am I wrong ?


texts: How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?

texts:
I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time.

Camerini's algorithm does this by splitting the edges by weight into heavy and light halves in O(|E|) time, then building a maximal forest from the light edges. If there is only one tree, then it recurses on the lighter half of edges, but if there are multiple trees, it reduces each tree to a super-vertex, then recurses with the new set of vertices and the heavy edges.

I don't understand how this can run in linear time. If the forest-finding runs in O(|V|+|E|) time, and |V| is not guaranteed to decrease in any predictable fashion, then the algorithm should be bounded by O(|V| log |V| + |E|).

What do I misunderstand about this algorithm?


texts: $\mathsf{NP} \cap \mathsf{coNP}$ as oracle

texts:
Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold?

Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true.

Is there a simple proof (or maybe just by definition)?


texts: Is the D-Wave architecture a close implementation of quantum interactive proof?

texts:
A very high level architecture is, as mentioned here, shown in this picture.

The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is BQP. Here the classical component is always in BQP if we are not too restrictive. On the other hand, the D-Wave box although don't have unbounded computational resources is not violating any law of quantum mechanics. Let's consider this as not-so-strong Merlin.

Can we say that this architecture is an restricted implementation of quantum interactive proof system? My motivation for this question is that if we want to do the complexity analysis of the D-Wave architecture should we model it as QIP?


texts: Semantic vs. Syntactic Complexity Classes

texts:
In his "Computational Complexity" book, Papadimitriou writes:

  RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the basis of defining a language in RP. For a machine N to define a language in RP, it must have the remarkable property that on all inputs it either rejects unanimously, or it accepts by majority. Most nondeterministic machines behave in other ways for at least some inputs ... There is no easy way to tell whether a machine always halts with a certified output. We informally call such classes semantic classes, as opposed to the syntactic classes such as P and NP, where we can tell immediately by a superficial check whether an appropriately standardized machine indeed defines a language in the class.

Several pages later, he points that:

language L is in the class PP if there is a nondeterministic polynomially bounded Turing machine N such that, for all inputs x, $x \in L$ iff more than half of the computations of N on input x end up accepting. We say that N decides L by majority.

Question 1: Why Papadimitriou concludes that PP is a syntactic class, while its definition is only slightly different from that of RP?

Question 2: Whether being "semantic" for a complexity class is equivalent to NOT having complete problems, or the lack of complete problems is thought of as a property that we GUESS semantic classes possess?

Edit: See related topic Do all complexity classes have a leaf language characterization?


texts: Pathwidth of planarized drawing of $K_{3,n}$

texts:
The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process:

Draw it in the plane such that no edge contains a vertex in its interior, and such that no more than 2 edges cross at any point.
Replace every crossing point of two edges by a new vertex of degree 4.

Then the resulting graph is clearly planar. While $K_{3,n}$ has constant pathwidth, some preliminary investigations suggest that regardless of the drawing you use to planarize $K_{3,n}$, you cannot guarantee that the planarized graph has constant pathwidth independent of $n$; I believe the pathwidth of the planarized graph must grow with $n$. Is this known, or implied by some existing result?

On the other hand, I have a family of graphs of constant degree and bounded pathwidth, which I can planarize without increasing the pathwidth by more than a constant. Is there a general result saying that this is always possible for graphs of bounded degree and pathwidth?


texts:
Is it known that permanent of a $0/1$ $n\times n$ matrix $M$ is computable in polynomial or randomized polynomial time with access to a ${\Sigma_{(\log n)^c}^P}$ oracle where $0<c$ holds and $\Sigma_{f(n)}^P$ means the number of alternations is $f(n)$?
If not known what is the consequence if it is possible to do so?


texts:
Krivine in his book (Lambda-calculus: Types and Models) introduces the grammar of lambda-terms and then abbreviations to denote them. The grammar itself is not ambiguous:  Lambda-terms are
obtained by applying, a finite number of times, the following rules :

any variable x is a λ-term ;
whenever t and u are λ-terms, then so is (t)u ;
whenever t is a λ-term and x is a variable, then λx t is a λ-term.

Then: "the term $(...(((t)u_1)u_2)...)u_k$ will also be written "$(t)u_1 u_2 ...u_k$". But let us consider the two following different $\lambda$-terms:

$v_1 = ((x)\lambda y. (y)z)w$
$v_2 = (x)\lambda y. ((y)z)w$

($w, x, y, z$ are variables)
and now it seems that I have two ways to interpret the notation $(x)\lambda y. (y)z w$:

either $t = x$, $k = 2$, $u_1 =\lambda y. (y)z$ and $u_2 = w$
or $t = x$, $k= 1$ and $u_1 = \lambda y. ((y)z)w$

It seems that the notation "$(t)u_1 u_2 ...u_k$" is ambiguous. Which rule am I violating in my interpretation?


texts:
I am intrigued by compression techniques and I'd like some recommendations about books to study, specifically, on lossless compression algorithms and data structures.

I don't know if there is a comprehensive book (or books) that deals with both compression of general sources (stream of bytes), and known inputs (e.g., integers, strings).

Thanks for your references!


texts:
Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:

1) Minimizing the number of balls that are required to cover all the points.

2) Maximizing the inter-clusters separation between clusters, which is define as follows:

For clusters $C_i$  and $C_j$ (with centroids $c_i$ and $c_j$), their inter-cluster separation $R_{ij}$ is  $$ R_{ij}=\frac{d_{ij}}{(S_i+S_j)},$$ where $S_i=\Sigma_{p\in C_i} dist(c_i,p)$ and $d_{ij}=dist(c_i,c_j)$. (Here, $dist$ is the usual $l_2$-norm.)

The exact algorithm of the problem should output optimal centers ${c_1, c_2, ..}$ of the clusters.

I have following two questions regarding the problem:

1) What is the inherent complexity of the problem.

2) If the above problem can be solved in sublinear query/time (in a similar spirit of the learning problem in the PAC model)? More precisely, by querying $poly(\frac{1}{\epsilon}, logn)$ many positions from the input the algorithm should output approximated clusters, i.e. $\Sigma_i dist(c_i, c_{opt_i})<\epsilon$. (Here $c_{opt_i}$ is the center of $i^{th}$ optimal cluster.)

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

Thanks!


texts:
I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid:

https://gist.github.com/4542999

1) Is this a known result?

2) If not, any suggestions of a niche journal that might be interested in such a submission?

3) Any known results on the space complexity of finite monoid elements?
I have yet to come across a monoid representation with efficient parallel computation that took more than O(log N) space, with N being the number of elements being "added"/"multiplied". Useful monoid data structures seem to be a constant number of counters or a member of a transformation semigroup of constant size; i.e. a fixed length array of size K with elements in 0...(K-1).


texts: Are there any books containing collections of automata problems?

texts: You can find specialized books consisting entirely or problems from particular math domains (e.g. linear algebra, polynomials, combinatorics), but I've yet to find such a book for automata of any kind.


texts: Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?

texts:
We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case.
But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is exponential, it could work very well in practice.

Are there any (deterministic) examples to this situatation other than Simplex algorithm?


texts: $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$ calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$?

texts:
This is question is related to this past question.
I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following:

1.4 Constraint Based Analysis
The purpose of Control Flow Analysis is to determine information about what "elementary blocks" may lead to what other "elementary blocks". This information is immediately available for the $\mathrm{While}$ language unlike what is the case for more advanced imperative, functional and object-oriented languages. Often Control Flow Analysis is expressed as a Constraint Based Analysis as will be illustrated in this section.
Consider the following functional program:
let f = fn x => x 1;
    g = fn y => y + 2;
    h = fn z => z + 3
in (f g) + (f h)

It defines a higher-order function f with formal parameter x and body x 1; then it defines two functions g and h that are given as actual parameters to f in the body of the let-construct. Semantically, x will be bound to each of these two functions in turn so both g and h will be applied to 1 and the result of the computation will be the value $7$.
An application of f will transfer control to the body of f, i.e. to x 1, and this application of x will transfer control to the body of x. The problem is that we cannot immediately point to the body of x: we need to know what parameters f will be called with. This is exactly the information that the Control Flow Analysis gives us:
$$\text{For each function application, which functions may be applied.}$$
As is typical of functional languages, the labelling scheme used would seem to have a very different character than the one employed for imperative languages because the "elementary blocks" may be nested. We shall therefore label all subexpressions as in the following simple program that will be used to illustrate the analysis.
Example 1.2 Consider the program:
$$[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$$
It calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$).

I'm unsure about this part:

It calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$).

Looking at the program $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$, aren't the statements $\text{fn} \ x => [x]^1$ and $\text{fn} \ y => [y]^3]$ executed separately, the former first and then leading to the latter? So what do the authors mean when they say that "it calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$)", because this sounds like something different? Am I misunderstanding this?

EDIT:
This chapter's slides from the textbook's website.


texts: Is there a better than linear lower bound for factoring and discrete log?

texts:
Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and its variant over group of points of elliptic curves (and their higher dimensional abelian varieties) and the general hidden subgroup problem?

Specifically do any of these problems have more than a linear complexity lower bound?


texts:
Helly's Theorem states the following. Suppose $X_1,X_2,...,X_N$ are convex sets in $\mathbb{R}^d$, such that for any index-set $I$ with $|I| \leq h(d) := d+1$, we have $\bigcap_{i \in I} X_i \neq \varnothing$. Then $\bigcap_{i=1}^N X_i \neq \varnothing$.

Let $f: \mathbb{R}^d \times \mathbb{R}^n \rightarrow \mathbb{R}$ be such that for all $x \in \mathbb{R}^d$, $y \mapsto f(x,y)$ is convex, and for all $y \in \mathbb{R}^n$, $x \mapsto f(x,y)$ is convex. Suppose $n \leq d$.

Define the sets
$$ X_i := \{ x \in \mathbb{R}^d \mid f( x, y_i ) \leq 0 \}, \ \forall i = 1, 2, ..., N,$$
where $y_1, ..., y_N \in \mathbb{R}^n$ are given vectors.

I am wondering if Helly's Theorem holds true with Helly's number $h$ depending on $n$, not on $d$.


texts: Computing the permanent with polylog size matrices

texts:
The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$.

We know that the problem is not in $\mathsf{P}$, unless $l = \mathcal{O}(\log_2 n)$. What can we say about the complexity of the problem when $l = \mathcal{o}(n)$ as well as $\log_2 n = \mathcal{o}(l)$ ? For example, if $l = \text{polylog}(n)$ ?

Does the problem remain $\#\mathsf{P}$-complete ? Or is it complete for a class in some level of the polynomial hierarchy ?


texts:
I have a system for tagging articles. Each editor ads different tags to each piece of content. For example:

for A: George Washington, first president
for B: first president, Washington George
for C: George Bush, USA

Is there any way I can generate "possible similar tags". For example I need to suggest to the editor that "George Washington" and "Washington George" are similar and I should merge them.


texts: Lower bound on the largest restrained cubic subset

texts:
Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:

Each row in the cube (in any of the three directions) has exactly 2 or 0 points.
If two points are in the same row (any of three), connect them with an edge. The subset must be connected by these edges.

It is easy to build such a set which is $\Omega(n)$, for instance a staircase, or stacking squares. Is it the case that these structures are also $O(n)$? Or is there an $\Omega(n^2)$ bound?

Building such a set would require adding a linear number of points for each added dimension, which is hard due to the first restriction.

This problem may also be reformatted graph-theoretically. We may express points in the cube as 3-edges in a 3-uniform tripartite hypergraph. In this case our restraints become that each set of 2 points contained in a 3-edge is contained in exactly two 3-edges, and the 3-edges are connected.


texts: Clique-width expressions with logarithmic depth

texts:
When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree decomposition where the tree is binary and its height is $O(\log n)$. This can be achieved while keeping the width of the decomposition at most $3w$. (See e.g. "Parallel algorithms with optimal speedup for bounded treewidth", by Bodlaender and Hagerup). So, logarithmic depth is a property of a tree decomposition which we can get almost for free.

My question is if there exists a similar result for clique-width, or perhaps a counter-example. In other words, given a clique-width expression for $G$ using $k$ labels, does there always exist a clique-width expression of height $O(\log n)$ for $G$, that uses at most $f(k)$ labels? Here, the height is defined naturally as the height of the parse tree of the clique-width expression.

If a statement similar to the above is not known, is there an example of an $n$-vertex graph $G$ with small clique-width $k$, such that the only way to construct $G$ with $f(k)$ labels is to use an expression with large depth?


texts: Reference for (odd-hole,antihole)-free graphs?

texts:
X-free graphs are those that contain no graph from X as an induced subgraph.  A hole is a cycle with at least 4 vertices.  An odd-hole is a hole with an odd number of vertices.  An antihole is the complement of a hole.

The (odd-hole,odd-antihole)-free graphs are precisely the perfect graphs; this is the Strong Perfect Graph Theorem.  It is possible to find the largest independent set (and largest clique) in a perfect graph in polynomial time, but the only known method of doing so requires building a semi-definite program to compute the Lovász theta number.

The (hole,antihole)-free graphs are called weakly chordal, and constitute a rather easy class for many problems (including INDEPENDENT SET and CLIQUE).

  Does anyone know if (odd-hole,antihole)-free graphs have been studied or written about?

These graphs occur quite naturally in constraint satisfaction problems where the graph of related variables forms a tree.  Such problems are rather easy, so it would be nice if there were a way to find a largest independent set clique for graphs in this family without having to compute the Lovász theta.

Equivalently, one wants to find a largest independent set for (hole, odd-antihole)-free graphs.  Hsien-Chih Chang points out below why this is a more interesting class for INDEPENDENT SET than (odd-hole, antihole)-free graphs.


texts: How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?

texts:
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f).$$
If $f:X^{2}\rightarrow X^{2}$ satisfies the Yang-Baxter equation and $B_{n}$ denotes the braid group, then define a group action
$\pi_{f,n}:X^{n}\times B_{n}\rightarrow X^{n}$ by
$$\pi_{f,n}(x_{1},...,x_{n})\cdot\sigma_{i}=(x_{1},...,x_{i-1},f(x_{i},x_{i+1}),x_{i+2},...,x_{n}).$$

Define $x^{+}=\max(x,0)$. Define a mapping $f:\mathbb{R}^{4}\rightarrow\mathbb{R}^{4}$ by letting
$f(a,b,c,d)=(a',b',c',d')$ where

$$a'=\max(a,a+b,b+c),$$
$$b'=d-(a-b-c+b^{+}+d^{+})^{+},$$
$$c'=a+c+d-\max(a,c,a+d),$$
$$d'=\max(b,a-c+b^{+}+d^{+}).$$

Then the function $f$ satisfies the Yang-Baxter equations. Therefore the braid group $B_{n}$ acts on $\mathbb{R}^{2n}$ and this action restricts to an action on $\mathbb{Z}^{2n}$. See 1 for more information about this group action.

We say that a positive braid $b\in B_{n}$ is simple if $b$ cannot be factored as $b_{1}\sigma_{i}^{2}b_{2}$ for positive braids $b_{1},b_{2}$ and some $i$. The simple braids are in a one-to-one correspondence with the permutations in $S_{n}$, so these simple braids are sometimes called permutation braids.

Given a simple braid $b\in B_{n}$, the mapping $\mathbb{Z}^{2n}\rightarrow\mathbb{Z}^{2n},\mathbf{x}\mapsto\mathbf{x}\cdot b$ may be computed using $O(n^{2})$ $+,-,\min,\max$ operations. Can the mapping $\mathbf{x}\mapsto\mathbf{x}\cdot b$ be computed using only $O(n\cdot\log(n))$ of these $+,-,\min,\max$ operations?

http://iopscience.iop.org/article/10.1070/RM2002v057n03ABEH000519/pdf


texts: What is the best reduction we know from flavors of $SAT$ to $MCSP$?

texts:
Consider $\mathcal P(n,m)$ to be a class from the set $\{k\mbox{-}\mathsf{SAT}(n,m),\mathsf{CIRCUITSAT}(n,m)\}$ where $k$ is fixed, $n$ is number of variables and $m$ is number of clauses.
Denote $\mathsf{MCSP}[s(t)]$ to the class of problems which have a circuit of size $s(t)$ when input a truth table of size $t$
What is the best reduction that we know from a member in $\mathcal P(n,m)$ to $\mathsf{MCSP}[s(t)]$ when $t=f(n)$ for a function $f:\mathsf{Z_{\geq0}}\rightarrow\mathsf{Z_{\geq0}}$?
I am looking for the correct parametrization between the problems that we know (best $s(t)=s(f(n))$).
I know some reductions provide separation such as $\mathsf{EXP}\neq\mathsf{ZPP}$ or $\mathsf{PSPACE}\neq\mathsf{ZPP}$ or $\mathsf{NP}\not\subseteq\mathsf{P/poly}$. Literature says these are $\mathsf p$, $\mathsf{LOGSPACE}$ or $\mathsf{AC}^0$ reductions respectively and the question is what would the parameters of $f$ and $s$ be?


texts: Is the transducer version of BPP closed under complement?

texts:
Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this true generally for BPP languages, i.e. can generating random words in a BPP language (and it's complement) be done in probabilistic polynomial time?

Specifically, given a probabilistic polynomial time algorithm which outputs strings in $F_2^n$ by computing the functions $g_i(x_k)$, where $i = 1 .. n$ and $x_k$ are random bits, is it possible to output (uniformly or otherwise) strings from the complement of the image of $g_i$, $F_2^n \setminus Im(g)$ in probabilistic polynomial time?

If so, is there a known practical algorithm to find the complement and what is its computational complexity and is that complexity bound optimal? If only an approximate complement can be computed efficiently, what are the upper bounds on approximation? Could there be a PCP theorem?


texts: Intuition: Odd-cycle transversal in triangle-free graphs

texts:
I conjecture that if $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

For more information, see the 1988 paper by Erdös et al., How to Make a Graph Bipartite.

Question 1: Is this conjecture true by your intuition?

Question 2: What is the complexity of counting the number of odd cycles in a graph? Is there any efficient algorithm to do that?