Is the running time of Boyer-Moore linear? With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?

Are there any sublinear expected-time string matching algorithms (on all alphabet sizes)?

Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question Kaveh posted. My question was: Is Boyer-Moore actually linear on small alphabets?

The log base below is $|\Sigma|$, and (ceiling of) $logM$ (often just one) is implied.

Preprocess the Pattern into a lookup table, with $M-logM+1$ keys, each key having size $logM$, and with associated key positions in the Pattern. Converting sequences of $logM$ letters into array indices is the only tricky part. The table size is $|\Sigma|$ raised to ceiling of $logM$, for easy indexing.  Each bucket is a short, possibly empty, list of key positions.  Run time: $O( MlogM )$.

Main: Skip through Text positions $k$ by $(M - logM + 1)$, constructing a $logM$ sized search key at Text positions $k$ thru $k + logM -1$. Look up the search key in the table. If found, naively attempt to match the Pattern at Text[$k$ - key position].  The naive attempt almost certainly fails in $logM$ comparisons. The only tricky part is that a key may occur in multiple Pattern positions.  The expected number of test positions is $O(1)$.  Expected run time: $O( (N/M)logM )$.

Post: Garbage collect the preprocessing space, $O(MlogM)$.

A proof that Main is optimal for $N>M^2$, on all alphabet sizes, is needed.


Why do computer scientists on the whole work under the assumption that P ≠ NP? Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either.

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP or https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/.

Update: Or the very recent Chapter 3 here: http://www.scottaaronson.com/papers/pnp.pdf

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.

There is a hidden difference between conjectures equivalent to a $\Pi_1^0$ sentence like Riemann hypothesis and conjectures equivalent to a $\Pi_2^0$ sentence like $P \neq NP$. We sort of already know some algorithms (i.e. universal search algorithms like Levin search or Hutter search) which would be polynomial time in case $P = NP$ (well, Levin search only works for syntactic subclasses of $F(NP\cap coNP)$=TFNP like PPA or integer factorization, and Hutter search ...), but that still doesn't settle the $P \neq NP$ conjecture.

  I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if P=NP was proven to be true, so why is this not assumed?

You probably mean that we should assume a non-zero probability that $P=NP$, for example by assuming that $P=NP$ with probability 0.01% and $P \neq NP$ with probability 99.99%. Many computer scientists will claim that this is more or less what they do, but they don't see how this assumption should alter what they write in their papers in any substantial way.

What they could do different would be to state the relation between runtimes achieved by reductions between problems more explicitly. But how much more explicit? Should they try to work less with $f(n)=O(g(n))$ and more with $f(n)\sim g(n)$ ($\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$) and $f(n)\lesssim g(n)$ ($\limsup_{n\to\infty}\frac{f(n)}{g(n)}\leq 1$) for stating resource estimates in theorems? The question is just whether this is realistically possible, since even basic tools like the master theorem are formulated in terms of $f(n)=O(g(n))$, and it is unclear how complicated they would become in terms of $f(n)\lesssim g(n)$ (or whether such a formulation would be useful at all).


Journals with quick reviewing Background: The motivation for this question is two-fold. First, I would like to get some hard facts to better understand the ongoing conferences vs. journals debate. Second, if this information was somewhere available, I could make a more informed decision when submitting papers for review; I would be happy to favour journals whose editors do a good job at selecting and shepherding referees.

Question: Are there any TCS journals that have consistently fast reviewing?

The rules:

I am not looking for any anecdotal evidence; I would like to see hard facts, such as "according to our statistics, during the last 3 years, 98% of our submissions were reviewed in at most 4 months".
Only time from the initial submission to the first decision counts. I do not care how long it takes to actually print a physical journal; it is beyond our control anyway.
A journal that is just a series of conference proceedings does not count. We all know that conference reviewing is quick.
Open-access on-line journals are perfectly fine.

(And if a journal is so questionable that you would be embarrassed if your name was somehow associated with it, let's skip it entirely.)

Glencora Borradaile has an interactive graph with turnover time (among other information) for several journals from several sources.

However, not included is the first journal I think of with a fast turnaround time: Information Processing Letters (IPL).  I couldn't find any statistics, but rapid dissemination is their first goal.  When refereeing for a similar Elsevier journal with the same goal of rapid dissemination but with a slightly different scope, they requested my report within about 5 weeks.

I have heard that Theory of Computing aims to have quick reviews. I am not sure about the statistics though, I have not looked them up.


Partitioning a square for optimal queries I have a square plate of size 1x1, full of lots of skittles. I want to eat all of the skittles, but the only way I can get the skittles is through these two oracles:

$f(x, y, r)$ tells me how many skittles are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

$q(x, y, r)$ gives me all of the skittles that are in the circle of radius $r$ centered about the point $(x,y)$ on my plate

However, my plate is very big, and my oracles are very small. So the $r$ given to $f$ and $q$ must be less than or equal to a given value $R$.

Oracles don't come free these days: I have to pay a cost of 1 each time I call $f$. Each time I call $q(x, y, r)$, I must pay a cost of $f(x, y, r)/P$: 1 for each $P$ skittles that my oracle brings to me (rounded up). The $P$ is an input to this problem. Then those skittles are eaten.

There are $N$ skittles on my plate. What is a strategy that doesn't cost very much to eat all of my skittles, in terms of $N, R$, and $P$?

I'm curious about two cases:

If an adversary is placing skittles, what is the most they can make me pay?
If all the skittles are each independently placed according to a uniform distribution over the entire plate, what is a strategy that does "sorta well", and what is the expected amount I would need to pay?

A good idea seems to be to use nonoverlapping circles in the densest circle packing in 2d. Please check the corresponding Wiki-page: https://en.wikipedia.org/wiki/Circle_packing. This way you reach up to $C = 0.907$ coverage. Assuming the scittles are uniformly distributed and $N \gg \frac{1}{S_c}$, where $S_c$ is the surface of the cricles you use, we may estimate that you'll have to pay $\frac{CN\#circles}{P} = C^2N/S_cP$ for fetching and roughly $\#circles = C/S_c$ for looking in thustly covered area. We may cover the gaps, which cover about $1-C$ of the square, by correspondingly smaller cirlces again, the cost of looking should be just as before. The cost of fetching is hard to estimate, without delving into geometry to much at this point, but i guess it may be roughly $(1-C)N/P$. Also, you may terminate one you reach $N$.

A smart adversary would start placing the scittles in the gaps. I assume it's a good idea to pick a random reference for the lattice of circle placing. Also you could randomly pick the areas to  check for scittles from the main lattice (covering $C$) and from the minor lattice (covering $1-C$).

Now we are stuck with the decission which radius to pick in $[0,R]$. I assume as large as possible under the placed constrains makes sense. There is probably space for optimization by choosing some radius $r$ so that your main lattice has little overflow over your plate.

Alternatively you may use the densest packing, but with circles overlapping. This way all the gaps vanish and you skip the cost for lookups on the secondary lattice.

Hope this input helps you somewhat.

-I think ur plate (geometrically) will have a fixed no.  of circles of max.  radius R that needs to be checked no matter how or where did you start; So let us assume this number is X (= 1/(⚻R^2)) .... {if u divide ur plate to 1/R^2 squares and thus adjacent circles u'll miss tiny small places bet. the circles that may contain skittles}
.
- So, u have to loop from 1 to X  checking every circle & counting skittles till N is reached; to make it faster in average u may start from the center of the plate moving to the border
.
-If an adversary is placing skittles, that's another story because each circle may be visited more than once, and the idea would be to follow his movement checking the circle surrounding it


Is there a set theoretic way to look at SQL? I have been learning about SQL and at times it feels like set theory.  A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$.

A table could be defined as any subset of the Cartesian product.  We could define a table called zipcodes with a schema city STRING(30), state CHAR(2),  zip INTEGER(5)  then in set theory we could define the zipcodes stable as:
$$ zicodes \subseteq \text{cities} \times \text{states} \times \text{zips} \simeq \{a, \dots, Z\}^{30} \times \{a, \dots, Z\} \times \{1, \dots, 10^5\}$$
So any table is a subset of a cartesian product.

My theory has limitations, since you can't store all of $\mathbb{R}$ as a SQL database (e.g. by cantor diagonalization) since $|\mathbb{R}| > |\mathbb{Z}|$ in cardinality.

In any case, do any theories of SQL exist that compare it to set theory?

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle.

The structure of the basic building block - relation - is described in set language, but that's about it. This is not really very insightful, because the whole mathematics is written in set language. The fact that probably caught your attention is that the foundation of SQL - relational algebra - has distinct Boolean flavor.

Please also note that SQL actually operates not with relations but multirelations which are bags(multisets) of tuples(rows). Therefore, its algebra is not a [boolean] algebra of sets. There were various attempts at rigorous theory of multirelations, with provenance semiring being the most recent development

Consider doing a join operation on your data. You are doing nothing but a cross product on the data. This falls under relational algebra. Set operations are the most basic and vague way of looking at the query on hand.


Reducing the Height of Context-Free Grammars Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.

Say that a string $w\in L(G)$ has height $h$ if $w$ has a parse-tree of height at most $h$. Say that $G$ has height $h$ if each string $w\in L(G)$ has height $h$. Let $|G|$ be the number of production rules in $G$. I have the following problem, which I believe it is well studied in the field of parallel parsing, but with a somewhat distinct terminology.

Problem: Given a context free grammar $G$ in CNF accepting a language $L(G)\subseteq \Sigma^n$, construct a context free grammar $G'$ in CNF such that

$L(G') = L(G)$,
$h(G') = O(\log n)$,
$|G'| = |G|^{O(1)}\cdot n^{O(1)}$.

Does the problem given above has always a solution?
In other words, from $G$ we want to construct a context free grammar $G'$ accepting the same language as $G$ but such that every string in this language has a parse tree of logarithmic height. The size of the obtained grammar $G'$ is allowed to blow up polynomially in $n$ and in the size of the original CFG $G$.

I'm mostly interested in references dealing with the problem above or similar problems.

Obs 1: Without the requirement that $|G'|=|G|^{O(1)}\cdot n^{O(1)}$, we can construct a grammar $G'$ with size $2^{O(n)}$ by considering a distinct set of production rules for each string in $L(G)$.

Obs 2: I don't care about the time necessary to construct $G'$. The only important thing is its size $|G'|$.

Obs 3: Both grammars are required to be in Chomsky normal form. Also both are allowed to be ambiguous.

The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.

In simple words, you want to inline non-terminals.
given a rule like S -> a B d, B -> b,c, you want to inline B, just replacing it with its content means : s -> a,b,c,d what would reduce the height. You can do it only if there is no direct circular dependency in the rule, means, there is no : S -> ...S... because you can not inline that. If there is circular dependency on 2nd lvl, sutch as
S-> ... B... , B -> xxxSxxx this you can inline like : S -> .... ( xxxSxxx)...


Interesting programs on small machines I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1

INC ri   ; ri <- ri + 1
DEC ri  ; ri <- r1 - 1
JNZ  address    ; if (r0 != 0) then jump to <address>. Else, skip.
LDR ri, address  ; load value at <address> into ri
STR ri, address  ; store the value in <ri> to <address>

What interesting programs can I make using this instruction set using no more than 16 instructions (the range of my address space).

So far, the best I have is "check if memory contains an odd value in the range 0-7"

Also, does it help if I add the following instruction:

JLT address ; if (r0 < 0) then jump to <address>. Else, skip.

even many simple counter machines have been proven Turing complete and this result might be surprising to nonresearchers (or researchers who dont specialize in the area). suggest a more relevant research question would be to review the existing models (many listed on wikipedia), determine if yours fits into them anywhere, and if it does not, describe the precise difference with one of the "nearest" models analyzed in the literature.


Dimensionality reduction in machine learning This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).

Dimensionality reduction refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. PCA and Johnson-Lindenstrauss are the most common examples.

From an algorithmic perspective, the tradeoff is clear: lower dimensionality yields faster runtimes and reduced storage space, but compromises precision. I call this the dimension-distortion tradeoff.

From a statistical/information-theoretic perspective, the situation seems less clear. It is commonly believed that dimensionality reduction (PCA in particular) has a denoising effect and thus should actually improve the performance. On the other hand, dimensionality reduction does discard information, which might cause the performance to degrade. Thus, one must address the statistical question: is the information I'm discarding noise or potentially useful (and even if useful, might the benefits of lower dimension still outweigh the losses)?

There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our
ALT'13
 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.

Are there other formal analyses of the statistical benefits of dimensionality reduction? Perhaps other tradeoffs besides those mentioned above?

Information Geometry is a rigorous framework which combines statistical inference, information theory and differential geometry.

Several open problems in statistics (and geometry) have found a new formulation and solution.
Specificaly the concept of dual connections and dualy-flat spaces. It has been shown that various statistical inference methods (e.g maximum likelihood, EM algorithm etc.) can be formulated in terms of dualy-flat spaces in a statistical manifold (reference "Methods of Information Geometry", Amari, Nagaoka). The new formulation allows a unified view of previously un-related methods and algorithms.

The problem of dimensionality reduction and PCA has been formulated information-geometricaly as follows (with emphasis on information):

"Information-Geometric Dimensionality Reduction"
"An Information Geometric Framework for Dimensionality Reduction"
"The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"

agreed this is not studied in general so much. part of the theoretical challenge/ difficulty is its highly dataset- and algorithm-specific (in the sense that different datasets & ML techniques are more or less sensitive to the "dimension-distortion tradeoff"). often dimensionality reduction is regarded as a tunable/ optimizable parameter along with all the other ML parameters and some quality metric intrinsic to the problem (also measuring learning success/ "generalization") is used to determine how much to apply. typically the performance of the ML algorithm declines if either too little or too much dimensionality reduction is applied.

however re "formal analysis/ tradeoffs of dimensionality reduction," newly emerging, try this large paper, which looks at how the Johnson-Lindenstrauss reduction affects datapoint proximity wrt a distance metric & lays out a more general theoretical framework. 60pp

TOWARD A UNIFIED THEORY OF SPARSE DIMENSIONALITY REDUCTION IN EUCLIDEAN SPACE
 / BOURGAIN, DIRKSEN, NELSON

as mentioned in the comments, one great applied case study in this type of big data problem & the relevance of PCA/ dimensionality reduction with major statistical/ scientific analysis is in the Netflix prize for movie ratings prediction. prior to the contest, PCA type approaches were somewhat rarely applied to human ratings predictions. however they were found to be extremely effective in this contest combined with careful tuning/ conditioning. the winning solutions used large "blends" of many different techniques but PCA related algorithms composed many of them.

moreover, sometimes mostly PCA alone without further learning algorithms applied on top of this data was enough as an effective/ top performing prediction algorithm. in this case one could say that most of the statistical trends in the data were apparently "identified" by PCA and what was "left over" (the "residual") was either not substantial or noisy. this contest had a $1M prize awarded to collaborating teams and eventually Netflix decided to employ many of these techniques in their live production system.

see eg

The BellKor Solution to the Netflix Grand Prize / Koren
The BigChaos Solution to the Netflix Prize 2008 / Toscher & Jahrer


Circuity complexity: monotone circuit of Majority function As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).

  http://link.springer.com/chapter/10.1007/11830924_38

My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)

Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.

On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).

Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge.


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

I think Dijkstra's shortest path algorithm would be suitable for your problem. But since you want to find the shortest-path node from a set of nodes and not from just one node, you need to tweak it.

The algorithm is quite straightforward but a bit obtuse, try searching for animated expositions on YouTube.


Indications that strengthen the conjecture: NEXP ⊊ EXP^NP I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.

Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.

Some Examples:
1.  A paper by Shuichi Hirahara: “Identifying an honest EXP^NP oracle among many”, which states that “No instance checker for EXP^NP -complete languages exists unless EXP^NP = NEXP” https://arxiv.org/abs/1502.07258

A paper by Laszlo Babai, Lance Fortnow and Carsten Lund: “NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS” which states that we do not know whether NEXP provers are sufficient to prove any NEXP language to a verifier, but the best upper bound we know on the power of the provers for NEXP is EXP^NP
http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf

Are there any additional known results on the conjecture of NEXP ⊊ EXP^NP?
What are its implications on the separation of other classes?

Thanks

Being pulled down by the gravitational force from $\mathrm{BPP}$, hardly any convincing evidence can be lurking on the surface of $\mathrm{EXP}^{\mathrm{NP}}$ for you to see.

Only after proving $\mathrm{BPP}\subseteq \mathrm{P}^\mathrm{NP}$, this class would give up on $\mathrm{EXP}^\mathrm{NP}$. But then, $\mathrm{EXP}$ and $\mathrm{NEXP}$ would have their chances to thrive (on their own).


Algorithms to classify the geometrical relationship of two 3D-geometries I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if

volume A is inside volume A
volume B is disjoint of volume B

Also I am interested in the dimension of the intersection of A and B if they aren't disjoint.

Specific ideas for algorithms would be just as helpful as references to useful books or papers.

I'm assuming you mean

volume A is inside volume B
volume A is disjoint of volume B

Then it's really simple. Pick the volume you expect to be a superset, or $A$. Each polygon defines a plane. Use these points to solve for $ax+by+cz+d=0$, for every polygon of $A$.
Then it would help if you had a point that you know is inside a volume.
find the closest polygon to your inner point, and check whether that point is greater or less than the plane. let that number be $k_{P_n}$ (either 1 or -1).
take a polygon that is next to your initial polygon. find the folding edge of the two.
take a point of the new polygon that is not on the folding edge ($l$).
extend a point from the folding edge orthogonal to the initial plane above the initial plane ($a$). second point on the initial plane, but outside of the line of intersection ($c$). (above with respect to your k of the initial plane)
if $l$ is on the initial plane, then adjust your new k so that $a$ is above the new plane.
if $l$ is above (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is below the new plane.
if $l$ is below (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is above the new plane.
keep doing that until you have your complete shell mapped for k. if you have more than one shell (like a hollow object) you need to track all unmapped polygons and do the same thing for them.
then you can compare your volumes.
take any point from B, and find the closest polygon from A, and check whether your B point is above the plane of the A polygon. do this for every point in B.
you also need to check whether any A point is in B, for the special case in which a sharp spike from one volume penetrates the other.
If all points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $B$ is inside $A$
If some but not all points of $B$ are inside $A$, then $A$ and $B$ intersect.
If no points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $A$ and $B$ are disjoint.
Further reading:
Look at computing volume of convex polytopes. Alternatively to the above, you can look at the union volume to draw your conclusions. if $V_U=V_A$, then $A\subset B$. if $V_U<V_A \wedge V_U<V_B \wedge V_U \neq 0 $ then $A$ intersects $B$. If $A_U=0$ then they don't intersect.


Are there any open problems left about DFAs? After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original unmodified DFAs we study in undergrad.

This is a vague question but I hope you get the idea. I want to understand if it is fair to say that we completely understand DFAs. So I really mean questions that are inherently about DFAs, not problems artificially made to look like a problem about DFAs. Let me give an example of such a problem. Let L be the empty language if P=NP and some fixed non-regular language if P is not NP. Can L be accepted by a DFA? This question is about DFAs, but it isn't about them in spirit. I hope my point is clear and I don't get pedantic non-answers from people.

In short is it fair to say

  We essentially completely understand DFAs.

I am sorry if it turns out that this is a huge area of research that I was not aware of and I have just insulted an entire community of people.

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit.

  Let $u$ and $v$ be two distinct words with $|u|=|v|=n$.  What is
  the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa?

Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{2/5}(\log n)^{3/5})$.  The best known lower bound in $\Omega(\log n)$.

For a survey see this.

("thinking outside the box"...) this is a somewhat contrived problem involving DFAs (have not seen it studied elsewhere) but manifests a theme in TCS that even many apparently "simple" computational objects (like DFAs) can have complex properties, also an aspect/theme embodied in Rices theorem. (in some ways the ultimate "complexity" is "undecidability" aka Turing completeness.)

consider a family of DFAs and an "exponentiation" operator "↑". this operator takes a regular expression (RE) "x↑n" and repeats it $n$ times. ie for any RE $x$ and finite $n$, $x↑n$ is a RE (and therefore also a DFA). this operator is considered in various contexts and in some important problems eg one of the first problems proven EXPSPACE-complete.[1][2]

now consider a family of DFAs $DFA_n$ which is built from a single RL expression $DFA'$ (not exactly/strictly a DFA) with embedded instances of the exponentiation operator in the form "↑n" where here "↑n" is a symbol (but otherwise $DFA'$ is a RL/DFA). then for every finite $n$, $DFA_n$, constructed by replacing/substituting the instances of "x↑n" in $DFA'$ by n repeated instances of x, is also a RL (and a DFA).

(now as usual let $\Sigma$ be the language symbol set/alphabet.) claim:

  the problem "does there exist an $n$ such that $DFA_n ≠ \Sigma*$" is undecidable.

the claim follows from constructions in [1] where basically a regular expression is constructed using exponentiation that simulates a TM computation on a specific input iff it is not equal to the "full language" $\Sigma*$. the exponentiation is used to reflect the maximum tape width used in the TM computational tableau accepting the word in the language. this construction can also be found in [3]. a halting computation can be found iff there is a finite $n$ tape width for that computational tableau accepting the word.

now, to tie this in more with the question, while this is not widely noted (considered trivial by some), many open problems in TCS/mathematics are tightly connected with undecidability in that given an oracle for the halting problem, they can be "solved".

therefore, in a sense, tying this all together using this basic problem about DFAs that is undecidable, there will always be open problems about DFAs, because there will always be "open" problems about DFAs (such as this one) equivalent to undecidable problems. in fact using Rices theorem in reverse as this construction does in some ways, basically any relatively "simple" yet nontrivial computational property in TCS can be used to construct undecidable problems.

[1] Word problems requiring exponential time / Stockmeyer & Meyer

[2] Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

[3] Introduction to languages, automata and computation / Hopcroft/Ullman.


Space-time tradeoff and the best algorithm Consider some language $L$ such that:

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

and so that

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

In other words, the fastest machine $M$ computes $L$ in time $O(f(n))$ and the most space efficient machine $M'$ computes $L$ while using space $O(g(n))$.

What can be said about the space efficiency of M or the time efficiency of M'? Or more precisely, if $\mathbb{M}_T$ is the set of all machines that compute $L$ in $O(f(n))$ then what can we say about the most space efficient machine in $\mathbb{M}_T$? What about the same thing for the obvious space version: $\mathbb{M}_S$.

Alternatively, can $f(n)$ and $g(n)$ be used to define some good space-time tradeoffs? Under what conditions is $TS \in o(f(n)g(n))$ or more generally for some space-time tradeoff $h(T,S)$ under what conditions is $h(T,S) \in h(o(f(n)),o(g(n)))$.

The prototypical f and g here would probably be poly-time and polylog space.  The interesting problem here is connectivity (in directed graphs) which can be solved in polynomial time (using linear space) or in polylog space (using super-polynomial time).  It is a famous open problem whether it can be solved in TIME-SPACE(poly,polylog), a class known as SC.

I.e. your question is a well-known open problem.  I don't think that anything non-trivial is known here.

this question turned up on "similar questions" when I just posted this other question https://cstheory.stackexchange.com/questions/9677/deterministic-time-space-separation-via-space-compression.

there I cite hopcroft,paul,valiants 1977 result (apparently best known acc. to rj lipton in his blog) that seems to apply to your question ie $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$


Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers? Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent models) for studying computers?
What is the point of studying these much stronger models with respect to real computers?
Why is the finite automata model not enough?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata.
Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the state space infinite. This infinity can be perceived as an abstraction of "very big in front of the size of the data". When writing a computer program, you try to save space for efficiency, but you generally assume that you won't be limited by the total amount of space on the computer. That is part of the reason why Turing Machines are a better abstraction of computers than finite automata.

Real computers have limited memory and only a finite number of states. So they are essentially finite automata.

Turing machines are derivatives of finite automata. Turing machines are practically von Nuemann architecture.


minimizing size of regular expression for finite sets It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.

What are the results if the language is finite?

One can consider this problem in two models:

The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.
The input is a DFA, and we measure the input size by the number of states of the DFA.

Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression.

Edit: As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP.

The following argument is essentially from (1): The decision versions of the two problems are contained in the second level of the polynomial hierarchy (more precisely: in the complexity class $\Sigma^P_2$), as follows. Guess a regular expression of size at most $k$, and check if it is equivalent to the given deterministic finite automaton (respectively: to the language given as a list of words).

I believe that no further results regarding your problems are known. For a similar-looking optimization problem, where the objective is to find a minimum equivalent nondeterministic finite automaton instead of a regular expression, the following results are known:

For input described as DFA, the minimum equivalent NFA problem is ${\bf DP}$-hard, see (1). Here, ${\bf DP}$ stands for "difference polynomial time"; this is the "Sigma" complexity class at the second level of the Boolean hierarchy.
For input described as a list of words, the minimum equivalent NFA problem is ${\bf NP}$-hard, see (2).
For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see (2).

Beware: Unlike the setting of infinite languages, I do not see a straightforward reduction from the NFA minimization case to the problems from your question.

References:

(1) Hermann Gruber and Markus Holzer. Computational Complexity of NFA Minimization for Finite and Unary Languages. In: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber and Markus Holzer. Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP. In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

Edit:
I think that grammar based codes are not so closely related: in that setup, the given language is a singleton set. But for such a singleton language $L=\{w\}$, the minimum size regular expression is (trivially) given by $w$.

apparently lacking an exact known answer or a better one than this, heres a near/recent ref on research specifically on the subj of minimizing REs (which is an apparently uncommon angle):

Minimizing NFA's and Regular Expressions (2005)
by Gregor Gramlich, Georg Schnitger

  We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's). We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, resp. symbols within the factor o(n), unless P = PSPACE. Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least poly(log n) . Our setup also allows us to analyze the minimum consistent dfa problem.


Set optimization problem - is it np-complete? Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective function:
$$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$$.

Is the problem NP-hard?

Since the objective function seems weird, it is helpful to explain an application of the objective function.

Suppose we have n items $e_1$ to $e_n$ and there are $c_i$ copies of each object $e_i$ in our inventory. We have some customers and they are interested in these objects in proportion with their weight $w_i$, which means the object with greater $w_i$ is more popular. We have an online sale system and we need to answer our customer's requests correctly. We cannot recognize objects by their shapes (They all look the same!). But we have some classifier to find them. Each classifier can be used for detecting copies of an object. We aim to run k classifier in order to maximize our customer's satisfaction.

P.S: It may be useful to think about the case that $w_i c_i=p$ for all $i\leq n$; however, I'm not sure.[I was wrong about this! It is in P by this assumption]

The answer below observes that a special case of the problem is solvable in polynomial time.  This does not fully answer the question in the post, but may give some insight on what might be needed for an NP-hardness proof, and may provoke additional interest in the post...

Observation. The problem in the post has an algorithm that, given any instance where each $c_i$ is an integer, runs in time polynomial in $n$ and $D = \sum_i c_i$.

Proof sketch.
Fix any input $(S, w, c, K)$ where $w,c\in\mathbb{R}_+^n$ and (WLOG)
$S=\{1,2,\ldots,n\}$.  Rephrasing the problem slightly, the goal is to find $M\subseteq S$ of size $K$ maximizing $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$.

Consider the following dynamic program.
For any integers $(d_1, d_2, k, m)$ with $0\le d_1 \le d_2 \le D$, $0\le k \le K$, and $k\le m\le n$, define
$$\textstyle\phi(d_1, d_2, k, m)
= \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~
M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$$
The desired solution is $\max_d \phi(d, d, K, n)$.

Partitioning the possible solutions for $\phi(d_1, d_2, k, m)$ into those that contain $m$ and those that don't, we get the recurrence
$$\textstyle\phi(d_1, d_2, k, m)
= \max\begin{cases}
\phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\
\phi(d_1, d_2, k, m-1).
\end{cases}$$
We leave the boundary cases as an exercise.

The number of subproblems is $O(n^2 D^2)$, and for each the right-hand side of the recurrence can be evaluated in constant time, so the algorithm runs in time polynomial in $n$ and $D$. $~~\Box$

Corollary. Unless P=NP, any reduction showing NP-hardness will reduce to instances where $D$ is not polynomial in $n$.

Remark. Unless I am mistaken, there is also a PTAS for the problem in the post, based on rounding the $w_i$'s then using dynamic programming. However, the existence of a PTAS has no direct bearing on whether the problem is NP-hard, as asked in the post.

I am also curious --- does anyone know whether the special case when $w_i=c_i$ (for each $i$) has a poly-time algorithm? (EDIT: it does, per Willard Zhan's comment this seems to be optimized by taking $M$ to contain the $k$ largest elements.)

Your are asking about the maximization of a function with no restrictions?

It is really simple. If M is the biggest set, then it is the best solution. No need to calculate anything.

This problem seems similar to the knapsack problem, which is NP by the way.


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

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

Here is a possible alternative to a padding argument, based on Schöning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many):

  Uwe Schöning. A uniform approach to obtain diagonal sets in complexity
  classes. Theoretical Computer Science 18(1):95-103, 1982.

We will apply the main theorem from that paper for $A_1$ and $A_2$ being languages and $\mathsf{C}_1$ and $\mathsf{C}_2$ being complexity classes as follows:

$A_1 = \varnothing$ (or any language in $\mathsf{P}$)
$A_2 = \text{SAT}$
$\mathsf{C}_1 = \mathsf{NPC}$
$\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

For the sake of clarity, the fact we will prove is $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ implies $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

Under the assumption that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ we have $A_1\not\in\mathsf{C}_1$ and $A_2\not\in\mathsf{C}_2$. It is clear that $\mathsf{C}_1$ and $\mathsf{C}_2$ are closed under finite variations. Schöning's paper includes a proof that $\mathsf{C}_1$ is recursively presentable (the precise definition of which can be found in the paper), and the hardest part of the argument is to prove that $\mathsf{C}_2$ is recursively presentable.

Under these assumptions, the theorem implies that there exists a language $A$ that is neither in $\mathsf{C}_1$ nor in $\mathsf{C}_2$; and given that $A_1\in\mathsf{P}$, it holds that $A$ is Karp-reducible to $A_2$, and therefore $A\in\mathsf{NP}$. Given that $A$ is in $\mathsf{NP}$ but is neither $\mathsf{NP}$-complete nor in $\mathsf{NP} \cap \mathsf{P/poly}$, it follows that $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

It remains to prove that $\mathsf{NP} \cap \mathsf{P/poly}$ is recursively presentable. Basically this means that there is an explicit description of a sequence of deterministic Turing machines $M_1, M_2, \ldots$ that all halt on all inputs and are such that $\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$. If there is a mistake in my argument it is probably here, and if you really need to use this result you will want to do this carefully. Anyway, by dovetailing over all polynomial-time nondeterministic Turing machines (which can be simulated deterministically because we don't care about the running time of each $M_k$) and all polynomials, representing upper bounds on the size of a Boolean circuit family for a given language, I believe it is not difficult to obtain an enumeration that works. In essence, each $M_k$ can test that its corresponding polynomial-time NTM agrees with some family of polynomial-size circuits up to the length of the input string it is given by searching over all possible Boolean circuits. If there is agreement, $M_k$ outputs as the NTM would, otherwise it rejects (and as a result represents a finite language).

The basic intuition behind the argument (which is hidden inside Schöning's result) is that you can never have two "nice" complexity classes (i.e., ones with recursive presentations) being disjoint and sitting flush against each other. The "topology" of complex classes won't allow it: you can always construct a language properly in between the two classes by somehow alternating between the two for extremely long stretches of input lengths. Ladner's theorem shows this for $\mathsf{P}$ and $\mathsf{NPC}$, and Schöning's generalization lets you do the same for many other classes.

(NPI $\nsubseteq$ P/poly) $\implies$ (P$\neq$NP)


Small steps for better TCS conferences? Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already forgotten it.

Hence the question: Which small steps we could easily take to improve TCS conferences?

Hopefully, this question could become a resource that we could double-check whenever we are organising conferences, to make sure that we do not repeat the same mistakes again and again...

I am here interested in relatively small and inexpensive details – something that conference organisers could have easily done if only they had thought about it in time. For example, it might be a useful piece of information that could be put on the conference web page well in advance; a five-dollar gadget that may save the day; something to consider when choosing the restaurant for the banquet; the best timing of the coffee breaks; or your ideal design of the conference badges.

We can cover here all aspects of conference arrangements (including paper submissions, program committees, reviews, local arrangements, etc.).

This is a community wiki question. Please post one idea per answer, and please vote other answers up or down depending on how important they are in your opinion.

Keep prices down: you can get lovely hors d'oeuvres at a $750-per-seat hotel-hosted conference, it is true, but it tends to detract from the intellectual atmosphere you can get with a $100-per-seat university-hosted conference.  Also, you don't just get the people attending who deliver talks.  Allow students at the university to attend for free;
Space parallel sessions, so that people can really move between them;
But also encourage interaction between speakers and attendees at parallel sessions beforehand, so that parallel sessions are also autonomous communities.  This encourages interaction, and the sense that parallel sessions are moving the discussion in their subfield forward.  Some conferences (e.g., the German linguistics conference, DGfS) have taken this to the conclusion of having all parallel sessions be independent workshops.

Discourage audience laptop usage during presentations.

Of course I cannot say for sure which laptop users are listening to the talk and which ones are reading email, but I always find it discouraging (if not rude) as a speaker to be speaking to a wall of heads buried in laptops.

Naturally some people are looking up definitions or related work and so forth, to enhance their listening experience. But having I seen plenty of people reading email or facebooking, I really wonder why they are even in the room.


Generating points uniformly distributed over the SURFACE of a standard simplex I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices).

One way to efficiently generate points that are uniformly distributed over the ENTIRETY of the $k$-simplex is to generate samples of $k$ iid exponential random variables, $E_i$, $i\in \left[1,k\right]$, then normalize, and $\vec{X}=\frac{\left\langle E_1,E_2,\dots,E_k\right\rangle}{\sum_{i=1}^k E_i}$, will be uniformly distributed over the entire $k$-simplex.

My problem is that the probability that one of these points lands on the surface (i.e. at a vertex, or along a hyper-edge, or on hyper-face, etc.) is nearly $0$, so that in practice all of the points end up being in the INTERIOR of the $k$-simplex.

In an attempt to sample the SURFACE of the $k$-simplex I have considered each hyper-edge, hyper-face, etc. separately and generated uniformly distributed samples on each (since they are themselves lower dimensional simplices). However, the problem becomes computationally unfeasible as $k$ increases because the number of hyper-edges, hyper-faces, etc. blows up.

Does anyone know of a method to explicitly generate samples that are uniformly distributed over the SURFACE (or BOUNDARY) of a standard $k$-simplex?

I created an algorithm for that. for detail see
    http://www.sciencedirect.com/science/article/pii/0098300493900457

briefly speaking, you can use following recursive formula to generate:

x_1=1-R_1^{1/n-1}
x_k=(1-\sum_{i=1}^{k} x_i)(1-R_k^{1/n-k}),    k=2,…,n-1
x_n=1-\sum_{i=1}^{n-1} x_i

Best wishes


Cheap online selection with weighted comparisons Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$.  We do not have access to the values of these elements, but we can compare any two elements of $S$ to see which one is smaller.  For any indices $i$ and $j$, there is an associated cost $C_{i,j}$ to compare the $i$th and $j$th elements of $S$.  The complete cost matrix $C_{i,j}$ is given to us in advance.

It is well known that $n-1$ comparisons are necessary and sufficient to find the smallest element of $S$.  However, since each comparison may have a different cost, we also want to keep the total cost of the comparisons as small as possible.

Is there an online algorithm that finds a sequence of comparisons of small total cost that finds the smallest element of $S$?  There is no online algorithm that finds the set of comparisons with minimum total cost, even when $n=3$, but perhaps there is an online algorithm with small competitive ratio.

In particular, does allowing the online algorithm to perform more than $n-1$ comparisons help?  Is it better to make several "extra" cheap comparisons instead of a few expensive comparisons?

I am especially interested in the case $C_{i,j} = 4^{d(i,j)}$, where $d$ is a discrete metric over the set $S$, and $0 \le d(i,j) \le k$, for all $i,j$.  An optimal online algorithm is still impossible in this setting.

Any references to similar problems are appreciated. I'm not searching for someone to solve my problem (although some ideas may help and are appreciated).  I just want to know if this problem is known. (I couldn't find anything.)

Brute-force case analysis reveals that the optimal competitive ratio for the special case  $n=3$, with no other restrictions on the cost matrix, is the golden ratio $\phi = (\sqrt{5}+1)/2$.  Thus, no online algorithm can achieve a competitive ratio better than $\phi$.

Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$.

Without loss of generality, the algorithm starts by comparing $S_1$ to $S_2$, at cost zero.
The adversary declares $S_1 > S_2$.
If the algorithm compares $S_1$ to $S_3$:

The adversary declares $S_1 > S_3$.
The algorithm must compare $S_2$ and $S_3$.
The adversary declares $S_2 < S_3$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $1+\phi$.
The adversary reveals the total order $S_2 < S_3 < S_1$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_2<S_3$) is $\phi$.

If the algorithm compares $S_2$ to $S_3$:

The adversary declares $S_3 > S_2$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $\phi$.
The adversary reveals the total order $S_2 < S_1 < S_3$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_1<S_3$) is $1$.

In either case, the algorithm's comparisons cost a factor of $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$ more than the optimal set of comparisons for the revealed total order.

More generally, the competitive ratio is $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$, where $a\le b\le c$ are the three comparison costs.  (There are more cases to consider here, because there are optimal algorithms that do not perform the cheapest comparison first, but the case analysis is still elementary.)  Tedious calculations imply that the expression $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ is maximized when $a=0$, $b=1$, and $c=\phi$.

In particular, if $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.

A start is:

Sort all elements of your cost matrix C
Perform the lowest cost comparison first, putting the loser in set NOPE
For each subsequent cost comparison, if either of the the two elements is in NOPE, don't perform the comparison
You have to keep going until all but one element is in NOPE, which is n-1 comparisons.

Is this a decent algorithm?  Depends on the relative cost of sorting C vs. doing the comparisons in S:

For any item you are evaluating, if there were a comparison cheaper than the current one being performed, it has already been performed, and the current item won that comparison
Cost == n^2 numeric comparisons to sort C, plus n-1 comparisons of S

-t.


Is Biological Computation a theme covered by the Theoretical Computer Science? I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an empirical theory of computation in the natural world than applications of biological systems in the industry of the computation.

Reference:
MITCHELL, Melanie. Biological Computation.

Yes there is some overlap, for instance the conference Unconventional Computation and Natural Computation (UCNC) covers theoretical computer science topics related to biological computation.

From the call for papers, UCNC topics of interest include (but are not restricted to):

  Molecular computing
  Quantum computing
  Optical computing
  Chaos computing
  Physarum computing
  Collision-based computing
  Self-assembling and self-organizing systems
  Super-Turing computation
  Cellular automata
  Neural computation
  Evolutionary computation
  Swarm intelligence
  Ant algorithms
  Artificial immune systems
  Artificial life
  Membrane computing
  Amorphous computing
  Computational systems biology
  Computational neuroscience
  Synthetic biology
  Cellular (in-vivo) computing

valiant proposed the PAC framework for learning which is the fundamental theory behind almost all algorithms in computational learning theory


How to automatically generate indexes and preaggregations from queries This question might be a little ill-specified, but the idea I want to explore is:

User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)
The schema for the data is specified

Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.

For a really simple example, say I have a table of logs:

(URL, IP address, user agent, response code)

And I input a queries like:

select * where URL = http://foo

Then it should know to automatically generate an index on the URL field.

If I also specify:

select count(*) from table group by IP_address desc limit 20

or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).

I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. http://scholar.google.com/scholar?cluster=1230153639822613926&hl=en&as_sdt=0,5

Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.

Hmm...

You could use undirected multigraphs or alternative graph structures stacks (epicly space inefficient).


Learnability of constraint satisfaction problems CSPs? This may sound more like a soft question but I am struggling to find an answer for it.

While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of machine learning and learning theory, there is almost nothing on learning CSPs. Given that CSP is a well known constraint formalism, I found this very weird. Am I missing something here?

You are probably looking for this paper:

Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003.  doi:10.1016/S0304-3975(03)00342-6

In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms.  This includes CSPs as a special case of more general quantified formulas (since a CSP instance is just an existentially quantified conjunctive formula).

For the Boolean case and also for two broad classes of non-Boolean formulas, there is a dichotomy between polynomially learnable (via the Generating Set algorithm, if the clone contains a "nice" operation) and not, subject to the hypothesis that there exists a public key cryptosystem secure against chosen ciphertext attacks.

there are many old SAT search, variable ordering, backtracking etc heuristics that can be regarded as verging on learning algorithms and many are applicable/generalizable to CSPs, and exact boundaries here may be blurring. possibly these have generally traditionally been two different fields, machine learning and constraint satisfaction, but with increasing intersection in more recent times. here are a few research leads. this appears to be an emerging area with some crosspollination with big data/datamining eg:

May 15 – 20, 2011, Dagstuhl Seminar 11201 / Constraint Programming meets Machine Learning and Data Mining

The second goal was to study the use of machine learning and data mining in constraint programming. Practitioners of constraint programming have to formulate explicitly the constraints that underly their application. This is often a difficult task. Even when the right constraints are known, it can be challenging to formalize them in such a way that the constraint programming system can use them efficiently. This raises the question as to whether it is possible to (semi)- automatically learn such constraints or their formulations from data and experience. Again, some initial results in this direction exist, but we are away from a complete understanding of the potential of this approach.

Learning Adaptation to Solve Constraint Satisfaction Problems Yuehua Xu, David Stern and Horst Samulowitz

Abstract. Constraint-based problems are hard combinatorial problems and are usually solved by heuristic search methods. In this paper, we consider applying a machine learning approach to improve the performance of these search-based solvers. We apply reinforcement learning in the context of Constraint Satisfaction Problems (CSP) to learn a value function, which results in a novel solving strategy. The motivation underlying this approach is to solve previously unsolvable instances.

Learning cluster-based structure to solve constraint satisfaction problems Xingjian Li · Susan L. Epstein

Abstract The hybrid search algorithm for constraint satisfaction problems described here first uses local search to detect crucial substructures and then applies that knowledge to solve the problem. This paper shows the difficulties encountered by traditional and state-of-the-art learning heuristics when these substructures are overlooked. It introduces a new algorithm, Foretell, to detect dense and tight substructures called clusters with local search. It also develops two ways to use clusters during global search: one supports variable-ordering heuristics and the other makes inferences adapted to them. Together they improve performance on both benchmark and real-world problems.


Automatic proofs or model checking in an extremely simplified functional language Imagine a stripped down functional programming language, that has the following properties

The only value type is an integer
There are no side effects
Functions are defined as a single expression, value of which becomes the return value of the function.
Program consists of zero or more function definitions and an expression. The expression can be defined in terms of the previously defined functions. Value of that evaluated expression is the result of the program.
Aside from simple arithmetic, there is only an if then else fi expression
The only way to do looping is through recursion

A program can then look like

f(x) = r(x+1,1)
r(x,y) = if x-(y*y) then r(x,y+1) else y*y fi

f(2)

so f() computes the second power of the given argument.

My question is, whether it is possible with current automated tools to prove theorems about such programs without human assistance. And what exactly?

Is it for example possible to automatically say for sure that for two functions f and g for every x: f(x) = g(x) ?

The ACL2 system includes all of the features of your language, and supports impressive automated theorem proving about program in that language.

In ACL2, you would write the theorem you describe as:

(defthm f-g-equal (equal (f x) (g x)))

having previously defined f and g.

Your language would be crippled for these reasons:

It has no aggregate data structures, making compositions impossible
It is not optimally minimalistic: You should consider integrating the lambda calculus to your language from which you can derive numbers and conditionals among other constructs
A program defined as 0 or more definitions does not return; you can define programs as the application of values on anonymous function arguments, so that programs are applied closures, and definitions could then be represented as the binding of a function's arguments to the values returned by the enclosing environment (just before arguments get applied, they are bound to their corresponding values)

You should definitively learn Scheme...


What is the computational complexity of "solving" chess? The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work backwards to all the possible moves/positions that would allow White to move in to one of those positions. If White ever found herself in such a position she could win by moving to the relevant checkmating move. Now we work backwards another step and so on. Eventually we get back to all the possible first moves White could make. The point is, once we've done this, we know that we have White's best response to any move Black makes.

Recently (last five years or so) Checkers was "solved" in this way. Obviously Noughts and Crosses (what the colonials might call "Tic-Tac-Toe") has been solved for ages. At the very least since this xkcd but presumably long before.

So the question is: what factors does this sort of procedure depend on? The number of possible legal positions, presumably. But also perhaps the number of legal moves at any given node... And given this, how complex is this sort of problem?

Bonus question: how long before a $2000 PC can solve checkers in a day? Chess? Go? (Of course for this you also have to take into account increasing speed of home computers...)

I've added the graph-algorithms tag because you can represent these games as trees, but if I'm abusing the tag please add something more appropriate

As @Joe points out, chess is trivial to solve in $O(1)$ time using a lookup table.  (An actual implementation of this algorithm would require a universe significantly larger than the one we live in, but this is a site for theoretical computer science.  The size of the constant is irrelevant.)

There is obviously no canonical $n\times n$ generalization of chess, but several variants have been considered; their complexity depends on how the rules about moves without captures and repeating positions are generalized.

If a draw is declared after a polynomial number of capture-free moves, or after any position repeats a polynomial number of times, then any $n\times n$ chess game ends after a polynomial number of moves, so the problem is clearly in PSPACE.  Storer proved that this variant is PSPACE-hard.

For the variant with no limits on repeated positions or capture-free moves, the number of legal $n\times n$ chess positions is exponential in $n$, so the problem is clearly in EXPTIME.  Fraenkel and Lichtenstein proved that this variant is EXPTIME-hard.

These estimates are way too high.

You're focused on branching based on legal moves. This makes lots of sense if you are trying to make a fast chess computer, but it's not how you would write a program to "solve" chess.

There <<<<< 13^64 possible game states in chess. Each square can only contain one of the chess pieces or nothing. You can iterate though them all and mark them as black win or white win in no more than 2^256 or so operations.

A more realistic guess of the number of reasonably achievable game states is around 2^100


What is some important work in fractals? Relating to the discussion on whether fractals are part of TCS, my question is:

  What are some important work/results in fractals in TCS?

The work/results may be focusing on fractals or it may use fractal concepts as a secondary analysis of some primary topic.

Mark Braverman has written quite a bit about Julia sets. See, e.g. Computability of Julia Sets

yrs ago when I asked about this elsewhere, there was an assertion that "fractals are not technically defined". think there is some validity to that. since then Ive been thinking that maybe fractals are best defined as a computational sequence or "computation tableau" eg via a turing machine. this would be a very broad definition but seems to fit & dont see obvious alternative. (worthy of another question here maybe) or at least there seem to be multiple plausible definitions of fractals.

also in line with this def of fractals in terms of computational tableaus, one major contribution to study of fractals is via cellular automata patterns, heavily studied by Wolfram in New Kind of Science.[1][2]

[1] New Kind of Science/wikipedia

[2] New Kind of Science/Wolfram online version


Is there a formal proof that quantum computing is or will be faster than classical computing? Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?

This is a question that is a little bit difficult to unpack if you are not familiar with computational complexity. Like most of the field of computational complexity, the main results are widely believed but conjectural.

The complexity classes typically associated with efficient classical computation are $\mathsf{P}$ (for deterministic algorithms) and $\mathsf{BPP}$ (for randomized). The quantum counterpart of these classes is $\mathsf{BQP}$. All three classes are subsets of $\mathsf{PSPACE}$ (a very powerful class). However, our current methods of proof are not strong enough to definitively show that $\mathsf{P}$ is not the same thing as $\mathsf{PSPACE}$. Thus, we do not know how to formally separate $\mathsf{P}$ from $\mathsf{BQP}$ either — since $\mathsf{P \subseteq BQP \subseteq PSPACE}$, separating those two classes is harder than the already formidable task of separating $\mathsf{P}$ from $\mathsf{PSPACE}$. (If we could prove $\mathsf{P \ne BQP}$, we would immediately obtain a proof that $\mathsf{P \ne PSPACE}$, so proving $\mathsf{P \ne BQP}$ has to be at least as hard as the already-very-hard problem of proving $\mathsf{P \ne PSPACE}$).  For this reason, within the current state of the art, it is difficult to obtain a rigorous mathematical proof showing that quantum computing will be faster than classical computing.

Thus, we usually rely on circumstantial evidence for complexity class separations. Our strongest and most famous evidence is Shor's algorithm that it allows us to factor in $\mathsf{BQP}$.  In contrast, we do not know of any algorithm that can factor in $\mathsf{BPP}$ — and most people believe one doesn't exist; that is part of the reason why we use RSA for encryption, for instance.  Roughly speaking, this implies that it is possible for a quantum computer to factor efficiently, but suggests that it may not be possible for a classical computer to factor efficiently.  For these reasons, Shor's result has suggested to many that $\mathsf{BQP}$ is strictly more powerful than $\mathsf{BPP}$ (and thus also more powerful than $\mathsf{P}$).

I don't know of any serious arguments that $\mathsf{BQP = P}$, except from those people that believe in much bigger complexity class collapses (which are a minority of the community). The most serious arguments I have heard against quantum computing come from stances closer to the physics and argue that $\mathsf{BQP}$ does not correctly capture the nature of quantum computing. These arguments typically say that macroscopic coherent states are impossible to maintain and control (e.g., because there is some yet-unknown fundamental physical roadblock), and thus the operators that $\mathsf{BQP}$ relies on cannot be realized (even in principle) in our world.

If we start to move to other models of computation, then a particularly easy model to work with is quantum query complexity (the classical version that corresponds to it is decision tree complexity). In this model, for total functions we can prove that (for some problems) quantum algorithms can achieve a quadratic speedup, although we can also show that for total functions we cannot do better than a power-6 speed up and believe that quadratic is the best possible. For partial functions, it is a totally different story, and we can prove that exponential speed ups are achievable. Again, these arguments rely on a belief that we have a decent understanding of quantum mechanics and there isn't some magical unknown theoretical barrier to stopping macroscopic quantum states from being controlled.

this is nearly the same core question that is driving something like hundreds of millions, or possibly billions of dollars of QM computing research initiatives both public and private worldwide. the question is being attacked at the same time both experimentally and theoretically and advances on each side carry over to the other side.

the question does attempt to neatly separate the theoretical and pragmatic/ experimental aspects of this question, but an experimentalist or engineer would argue they are tightly coupled, inseparable, and that historical progress so far on the challenge is evidence/ proof of that.

the following point is certainly not going to win any popularity contests (possibly due somewhat to the well-known/ observed bias that negative results are rarely reported scientifically), but it is worth noting that there is a minority/contrarian opinion promoted by various credible, even elite researchers that QM computing may or will never materialize physically due to insurmountable implementation challenges, and there is even some theoretical justification/analysis for this (but maybe more from theoretical physics than TCS). (and note that some may have doubts but are not willing to go on record questioning the "dominant paradigm".) the main arguments are based on inherent QM noisiness, the Heisenberg uncertainty principle, and the fundamental experimental messiness of QM setups, etc.

there are now a fairly solid 2 decades of both theoretical and experimental research and the minority faction would argue that the results so far are not encouraging, lackluster, or are even now verging on a definitive negative answer.

one of the most outspoken proponents of the negative view (bordering on extreme/ scathing!) is Dyakonov but who nevertheless argues the case passionately based on all the angles:

State of the Art and Prospects for Quantum Computing / Dyakonov
Prospects for quantum computing: extremely doubtful / Dyakonov

one may accuse Dyakonov of near polemicism but it serves as a nearly symmetric counterpoint to some QM computing proponents who have a fervent belief in the opposing position (that there is nearly absolutely no question of its future/eventual/inevitable viability). another major theoretician arguing for inherent limitations in QM computing (based on noise) is Kalai. here is an extended debate between him and Harrow on the subject.

Perpetual Motion of The 21st Century?

it is also natural to draw some at least loose analogy to another massive/complex physics project that so far has not achieved its ultimate goal after decades of attempts and optimistic early predictions, that of energy-generating fusion experiments.


Linear time algorithm for finding shifted max Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order.
We want to compute
$$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.

  Is it possible to do better? Can we compute $m$ in linear time?

My main question is the one above.
But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$
and $f$ a function given by an oracle.
Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case?

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?

We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$.
We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$.
Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have
$$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$.
We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$
which are in the range $[max-n, max]$ in linear time and
use the sorted list to compute $m$.

If the array $A$ consists of distinct integers, then $m = \max(A) + 1$, since the distance between adjacent entries in $B$ is at least $1$; the situation is more interesting when they need not be distinct.

For your more general question, imagine a situation in which $f(B[i],j)$ is only "interesting" when $i = j$. It seems possible to construct an adversary argument which forces you to query $f(B[i],i)$ for all $i$ before you can know $\max_i f(B[i],i)$, hence you need to sort $A$ in order to find the answer, which takes $\Omega(n\log n)$ comparisons. (There are some complications since it might be the case that we can test whether $A[i] = B[j]$ in constant rather than linear time by querying $f(A[i],j)$.) This is the case even if $f$ is a (high-degree) polynomial.


(Cryptographic) problems solvable in a polynomial number of arithmetic steps In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper of Borwein and Hobart [2] in the context of straight line programs (SLP).

Since I was rather surprised to read this, I have the following question: Are there any other cryptographic problems or maybe also other relevant problems, that can be solved in a polynomial number of steps with a SLP and that are currently not known to be solvable efficiently on a "normal" classical computer?

[1] Adi Shamir, Factoring Numbers in $O(\log n)$ arithmetic steps. Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs,
The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592

I did not read the paper as well but the abstract seems to say that an exponenial number of bit operations are required.

Chebyshev's work on congruences and its reformulation in the AKS algorithm show that prime generation is in P. Therefore trial division yields non-trivial factors. In that case, for some number N, you can expect a density of primes of 1/ln(N).

Furthermore, you can have a look at Turing's 1937 PhD thesis on the subject.


A search problem and no algorithm for it I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.

Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight function $w(s)$. We start at some element $s_0 \in S$ and want to find an element with very low $w$-value.

How can we traverse this search space? For each element $s_1 \in S$, there exists a set of keys $K_S$, and we have some function $a : S \times K_S \rightarrow S$, that computes a new element $s_2 = a(s_1,k)$ for some $k \in K_S$.

We can evaluate the weight of some element $s$ only once it is given. But computing the weight is expensive, and should be minimalized. In order to find a good choice how to traverse throughout this graph, we are given a heuristic $h(s)$, that is supposed to compute a "good" key.

We know for small changes of the key (say, in Hamming distance), the weight of $w(s)$ does not change to much.

Question: Is such a problem known in theoretical computer science, and does there exist theory for it? In particular I am looking for algorithms for problems like these, and conditions on the heuristic $h$ to provide a "good" heuristic.

The description is deliberately vague, in order to allow for wider range of answers. I think many search algorithms do not apply, because they are too generous with search space evaluation. Maybe the problem is even too ill-posed to be accessible to CST tools.

Thank you very much!

Your description is a bit vague, but the problem you describe seems very similar to the canonical problem defining the complexity class PLS (http://en.wikipedia.org/wiki/PLS_(complexity)). Problems in PLS can be described by an exponentially sized graph that you have access to using two polynomial time algorithms: one for evaluating the weight of a current vertex, and one for directing you to the neighbors of a current vertex. The goal is to find a local-minimum in the graph: any vertex such that none of its neighbors have lower weight.

Complete problems for this class include computing pure strategy Nash equilibria in congestion games (See e.g. here), and no polynomial time algorithms for such problems are known.

It sounds like what you need is the A* algorithm.  This is a good algorithm for traversing a graph using a heuristic to estimate the "distance" each node is from the destination.  In your case, the destination is any node which has a low weight.  The heuristic for "distance from a low weight node" would then be a guess as to how close a node is from a low weight node (it sounds like you already know this).  I would check out the wikipedia page I posted above for this algorithm and others like it.


Applications of representation theory of the symmetric group Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:

  Do you know of any applications of the representation theory of the symmetric group in TCS?

The symmetric group $S_n$ is the group of all permutations of $\{1, \ldots, n\}$ with group operation composition. A representation of $S_n$ is a homomorphism from $S_n$ to the general linear group of invertible $n \times n$ complex matrices. A representation acts on $\mathbb{C}^n$ by matrix multiplication. An irreducible representation of $S_n$ is an action that leaves no proper subspace of $\mathbb{C}^n$ invariant. Irreducible representations of finite groups allow one to define a Fourier transform over non-abelian groups. This Fourier transform shares some of the nice properties of the discrete Fourier transform over cyclic/abelian groups. For example convolution becomes pointwise multiplication in the Fourier basis.

The representation theory of the symmetric group is beautifully combinatorial. Each irreducible representation of $S_n$ corresponds to an integer partition of $n$. Has this structure and/or the Fourier transform over the symmetric group found any application in TCS?

Here are a few other examples.

Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions.
Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. Symmetric Groups and Expander Graphs.
Kuperberg, Lovett and Peled (2012) proved that there exist small sets of permutations which act uniformly on k-tuples. Probabilistic existence of rigid combinatorial structures.

an older example, but still with recent/ongoing research, some of this theory shows up in the mathematics of the "perfect shuffle", seen as an element of the symmetric group & which was a famous discovery at the time. [1] mentions applications of the perfect shuffle to parallel processing algorithms and also the connection to Cooley-Tukey O(n log n) DFT. [2] is more recent. the perfect shuffle shows up in parallel processing [3], memory design, and sorting networks.

[1] Mathematics of the perfect shuffle by Diaconis, Graham, Cantor. 1983

[2] Cycles of the multiway perfect shuffle permutation by Ellis, Fan, Shallit (2002)

[3] Parallel processing with the perfect shuffle by Stone, 1971

[4] Omega network based on perfect shuffling

[5] Parallel and sequential in-place permuting and perfect shuffling using involutions Yang et al (2012)


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

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

This problem is solved in the following paper, where more general problems are mostly addressed: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .

Har-Peled’s coreset paper shows the existence of an $\mathcal{O}(\log n)$-size coreset for the approximate sum problem. This seems trivial, and does not clearly imply any $\mathcal{O}(\log n)$ time algorithm for the approximate sum problem.

Assume that $\varepsilon > 0$. is fixed. For a sorted list $0\leq a_1 \leq a_2 \leq \dots  \leq a_n$, the following points form a trivial coreset for the approximate sum problem:

$\qquad a_n, \frac{a_n}{1+\varepsilon}, \frac{a_n}{(1+\varepsilon)^2}, \dots , \frac{a_n}{(1+\varepsilon)^k}$

for some $k \in \mathcal{O}\left(\frac{\log n}{\varepsilon}\right)$.

The main contribution of the approximate sum paper is an nontrivial $\mathcal{O}(\log n)$ time method to find a coreset of size $\mathcal{O}(\log n)$, which is different from the above construction. Thus, it brings an $\mathcal{O}(\log n)$ time algorithm.

With the above $\mathcal{O}(\log n)$ size coreset, one can do binary search for each point $a_n \cdot (1+\varepsilon)^{-j}$  to determine its weight, which is the number of points between $a_n \cdot (1+\varepsilon)^{-j}$ and $a_n \cdot (1+\varepsilon)^{-(j+1)}$ in the sorted list. This implies a trivial $\mathcal{O}((\log n)^2)$ time algorithm for the approximate sum problem.


Shortest number of editing move between two words I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes are

add a letter at one of the extremities (for example, AB -> ABC),
duplicate and concatenate the whole word (for example, ABC -> ABCABC),
cut a word in two (the dual of the duplication move, ABCABC -> ABC + ABC),
delete one of the letters (for example, ABC -> AC), and
repeat one of the letters (for example, ABC -> ABBC).

For example, a minimal sequence of moves from ABC to BCBC is ABC -> BC (delete A) -> BCBC (duplication).

I don't have a background in computer science. Perhaps this is a well-known problem, but my Google search gave me nothing.

Do you know some related, well-defined problem?

Edit: As suggested in the answer by Anthony Labarre, I read some papers about the poset permutation/arrangement problem which is similar to the problem described above. Does anyone know more about this problem? Is this relevant?

I don't know whether this exact problem has been studied, but  Chaudhuri et al. studied the related tandem duplication-random loss problem: you are given a permutation, and you want to transform it into the identity permutation by
 (1)  duplicating a segment of any length and appending the copy right after the original, then (2) deleting elements so that you obtain a new permutation instead of a string. Note that applying (1) then (2) accounts for one operation.

Different variants can be defined according to the weight given to each operation, which in their paper depends on the width of the duplicated segments.
They also study a similar problem with the whole genome duplication, which is exactly the kind of duplication you allow. I don't remember reading about work on this problem in the context of strings, but I hope this can at least give you a starting point for your searches.

Except for duplication, the Levenstein distance might be worth a look:
http://en.wikipedia.org/wiki/Levenshtein_distance


Designing a Transport network path suggestion tool I am working on a suggestion system to passengers on transits to take.
The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent stations as edges. The
weights on edges being the time it takes to reach between stations.

We are in search of route, a person should take if he/she desires
to go from node A to node B. I am aware that I can use the shortest path
problem to find a shortest route. But the complication is that the
shortest route may not be the fastest route to the destination. This is because
on the shortest route one of the leg of the journey has very low bus frequency and thus may take longer.

Let me elaborate it further. What I mean is that say A--C--B is the shortest route  but the frequency of buses is hourly. But A--D--B is another route which
is longer that A--C--B but has more frequency say once in 10 minutes.
Thus in this case A--C--B is the desired route. It is quite clear that the standard shortest path may not give the desired result.

Can you suggest a solution to this problem? I was thinking may be
detect all unique cycles involving node A & B. And compute actually required
time (taking into account bus frequencies) on that route. But I am not
sure how to go about this.

The obvious way of doing this is via time-dependent or time-independent graphs where you run a Dijkstra on it. This is also described in the lectures I mention below.

Also you should have a close look into transfer patterns (used at google) and RAPTOR (used at microsoft). There is a nice introduction into transfer patterns at university freiburg in lectures 9-11. RAPTOR is implemented in OpenTripPlanner and later this year probably also in my GraphHopper project.

  But the complication is that the shortest route may not be the fastest route to the destination.

Of course, but why not just use the time as weight instead of the distance? So 'shortest' and 'fastest' is not really a big difference ...


What are some theory problems in Information Retrieval and Search Engines which are not yet solved or can be bettered? I'm interested in IR and Search Engines and want to work on a theory problem in this space. Most thoughts that I get are focused towards implementation and would like to explore something not solved or can be bettered instead of implementing

Anaphor resolution:

  Since this type of understanding is still poorly implemented in software, automated anaphora resolution is currently an area of active research within the realm of natural language processing.

Speed
Relevence

These are two big problems that search engines have. Relivence is easy to explane. The search Engine is not a Neuro Interface yet, but it could be, there is your awnser, if a search engine such as google was operated by neuro-interface, with the write programing and the web cam to read the enviroment the search engine could bring back much more relivent results instead of 500 results of nonsense for the next spider.

Speed ou type the querry in, goes wizzing of across thosands of miles of fiber optic and possably up to satilites on its journey. Finaly it arives at Google Data Center, one of the largest Computer clusters in the world and a very secret location. that querry is sent around all those computers and when it comes out the other side it has gotten a bit larger because it now has the response to your origonal search term, and so it starts its return journey across thosands of miles of fiber optic, coper and those two satilites. Than you get your results.
Now this only takes a between 3 seconds to 2 miniutes your but while your waiting it is chuging your bandwidth and up your broadband bill. Wouldent it be faster to lay a global network of Fiber optic cable with repeaters ? Than Broadband would run at close to the speed of light.

Thats my take on the Speed part of the Question.


Open access journals With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research articles are behind paywalls. I am looking for journals and conferences (related to theoretical computer science, graph theory, combinatorics, combinatorial optimization) that make all accepted publications freely available to everyone.

Some such journals are Theory of Computing, The Electronic Journal of Combinatorics, Logical Methods in Computer Science

If you know more such journals (or) conferences, please mention them in your answers.

EDIT : As suggested by David Eppstein in his answer, I am adding one more constraint. Please write only those journals/conferences that do not charge authors exorbitant fees to publish.

Conferences with proceedings published in the LIPIcs series:

STACS
FSTTCS
CCC (since 2015)
TQC (Theory of Quantum Computation, Communication and Cryptography)
ICALP
APPROX/RANDOM
SoCG
SWAT
ESA
MFCS

Springer's International Journal of Parallel Programming offers authors the option to publish openly. They offer online first and open access articles, both with feeds available.

(I guess they have other journals with the same, but I have not checked.)


Evidence that PPAD is hard? There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "surprising" consequences (like the collapse of the polynomial hierarchy).

My question is, what is the basis for belief that the class PPAD is intractable? If there was a polynomial time algorithm for finding Nash equilibria, would this imply anything about other complexity classes? Is there a heuristic argument for why it should be hard?

PPAD is pretty "low" above P and not much would change in our understanding of complexity if it was shown equal to P (except that the few problems in PPAD would now be in P).  The main "evidence" that PPAD!=P is an oracle separation, which is essentially equivalent to the  combinatorial fact that no "black-box simulation" exists.

This paper is relevant to this, in that it attempts to show that PPAD = P: https://arxiv.org/abs/1609.08934


Ternary (and beyond) computation and quantum computing? Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved.  I have always thought that having more states could improve computing power (e.g. using a trit instead of a bit), but there is a seeming lack of attention being paid to the problem.

Some work has been done in the quantum computing area using qubits to achieve more than the normal two energy levels (see, for example, the recent effort at UCSB).

What advances have been made toward having ternary (or greater) computers, and what are the primary the implications of the extra states?

Actually the usual RAM model is just this approach taken into extreme: each "storage unit" has as many as $\textrm{poly}(n)$ possible states (instead of just 2 states). We assume that each memory word can store $O(\log n)$ bits and word-operations have unit cost.

Cf. this question.

why was my post deleted? I didn't do anything against the guidelines, i read the guidelines page!

I'll post this AGAIN. The only way to get ternary logic to work in a computer, is to first understand that you must have 3 magnetic fields, from a 3 terminal powersource. This is a simple negative>positive + a 3rd option.

But first, to whoever deleted my prior post, just because you do not enjoy reading the responses of people who can actually think for themselves and outside the box doesn't mean that person broke any rules. To others reading this, I posted a very good and informative response explaining how in theory a 3 state power system can work.

It's very obvious to me you can have a 3 terminal (but still 2 pole) battery. All you need is Zinc for negative and copper for positive (very common, of course) and the 3rd is aluminum. In order for me to explain how it's possible to have a 3rd type of electric current i first have to explain how we understand color scales. Take the green, red and blue color scale. Doesn't matter which color you want to with. So we will say in this case red is positive and blue is negative. What are these colors combined? Purple! So what is the opposite of purple? GREEN! This is how you figure out the other metal. Combine zinc and copper and guess what, you have brass, what the ancient greeks were very fond of at some point in their time. So, just like we take purple and look at it's opposite, we find that the opposite of brass is aluminum. Now you have your third terminal's alkaline.

Ok, so now that we have that out of the way. It is now possible to have a 3rd current. What will happen, due to the aluminum being weaker than the zinc negative, but stronger than the copper positive, if you place the aluminum 3rd terminal in a position that makes all three triangular in placement, the zinc's stronger energy will obviously flow to both of the terminals. But in the case of zinc to aluminum, the electrons will flow around the metal, creating a circular field, instead of a forward one. The reason for this is because of the aluminum's stronger magnetic field relative to the copper. So it's "pushing" on the copper and is being pushed by the zinc. If you put them in your battery correctly, the 3rd terminal will by default have a circular magnetic field, and so will the wire connected to it.

So why was my post deleted? Can you prove anything I just said wrong?


What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes? I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? Is there any previous work that can one cite in regards to this or any type of inclusion or exclusion like Toda's Theorem?

The number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula.  The inductive proof is quite elegant. So #P = #PSpace.