I voted on every question, lol I still have votes to cast.
I lied. I just went through and I reached the limit :)
@gilles I'm still confused as to what I can ask, lol. I have a bunch of time complexity questions I could ask from recent quizzes and homeworks I was confused on. But again, I don't want them to be closed as being too simple...
In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).
She shows that if you are trying to learn a minimal DFA with $n$ states, and your largest countexample is of length $m$, ...
Initially, Matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy algorithms to find optimal solutions. The concept of Greedoids was later introduced to generaliz...
In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? Could someone explain this?
In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing machine (QTM) that can actually benefit from quantum effects, namely, perform on high-dimensional...
Does SQL need subqueries?
Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL SELECT statement is actually pretty important for this to make sense, I don't appeal directly to relational algebra, but ...
We know that DFAs are equivalent to NFAs in expressiveness powers, there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states.
My question is: what is determining t...
@OghmaOsiris: I'm a bit late to the party, but my suggestion would be to just try it out and see what happens. I did the same with my question about EPAL: I was testing how interested people are in very theoretical questions, and as it turns out I think that one was a bit too theoretical.
In an answer to this question I wrote the following LaTeX code:
$$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the $n$-th symbol from the last one is 1}\}.$$
The output of this code should include four different curly brackets (two opening, two closing), but they are not being rendered.
Inline LaTeX...
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given workload will take is given by a known random variable $X$. Assume that there are $n$ such workloads...
According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator).
Is there an extension of SQL (implemented and used in the industry) which captures polynomial time computable que...
@Gilles I did this the day before yesterday; can confirm that answering questions at 4am is suboptimal. :D
@AlextenBrink I like the question about EPAL. But as I don't see why the language can not be parsed by recursive descent I am apparently not suited to answer (or, in case I am right, your question is moot).
Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, i.e. with uncountably infinite...
@Raphael Did you read my comment on the EPAL question regarding recursive descent? It does indeed look like it wasn't too theoretical after all, if I look at the number of upvotes.
@AlextenBrink Regarding your EPAL question: I read what you wrote, but the statement alone did little to convince my gut. Oh, wait... now I see. I had $a^nb^n$ in mind for some reason. Doh, my bad.
@AlextenBrink Regarding your heap automata answer: Not too sure about your use of $\cal{O}$ and $\omega$ there. What goes to infinity, as $n$ is fixed where you use them?
@Gilles Huh. I have been reluctant to invite people who did not sign up themselves (privacy). Once we hit public beta I will spread the word actively.
Maybe we should design flyers, posters, slides or something like that?
I am not too concerned about the number of questions. We have good ones, and knowledgeable members. I think quality will prevail and eventually attract quantity.
The D-CON workshop is on these days here in Kaiserslautern. I was thinking wether I should say something there, but have decided to just annoy people with Stackexchange stories instead. ;)
@Gilles Do you think the amount of questions is important for new members? I always figured that they were most likely to come so SE to ask a question, and might hit one or to recent questions. The backlog never seemed that important to me.
@Raphael depends who you're trying to recruit, true. It wouldn't be good to have a sudden influx of students asking homework questions before we have enough other content to balance them and enough manpower to answer them
@Gilles I have had succes with two strategies: a) "You have a problem with X? No idea, maybe go to SE?" has worked wonders with tex.SE as they are magnificent at answering weird questions. b) "Hey, look at this question. You know this stuff, right?" done that on math.SE, cstheory.SE
Type b) rarely sticks to the site as far as I can tell
@Gilles LOL. Chances are that many even speak French around here. Some even come from France, e.g. Bouajjani. Myself, I don't even speak a word French (besides "merci" and some I can't type)
I was told about then infant cstheory.SE by a very enthusiastic grad student who told me the site slowed down her dissertation. Moved around from there. And, obviously, you find Stackoverflow when googling for programming problems.
@Kevin I like the outdoors but get there not often enough. Never been to the site.
Well, we have some hard questions, too. I like that, actually; it also can be an incentive for people to join, if they perceive a need of their expertise.
@Gilles I could swear I have heard somewhere about a protocol that converges towards synchronised clocks with few assumptions. Can't remember where, though.
I expect D-CON to prompt some questions for me as I am not really part of that community (concurrency theory). Won't be too practical, I'm afraid.
Have a nice exam question I have no nice and simple answer for, too. Gotta write it up over the weekend or on Monday.
It is hard for me to estimate what part of computer science is interesting for practitioners. Never been one, really.
@Raphael it's hard for me too… As a former scientist doing program analysis, I think all programmers should know more about this. As a programmer now, I see that we don't have time or social acceptance to adopt anything other than C (in my line of business).
@Raphael About the 23%, I don't think we should worry too much about it. For instance, I could answer my own EPAL question by summing up which algorithms can't parse EPAL, but that wouldn't be a very good answer I think.
@Raphael I've made a minor edit to my answer that hopefully clarifies things, but the answer is getting so big I'm starting to get a bit embarrassed by the number of edits I made... It is a brilliant question though.
The first talk today showed how the provably (and apparently standard) mutex algorithm by Dekker failed if implemented in C as it should be (using volatile on the important variables). Very intrigueing. C++ compiler can fix it, but in a dumb way. They do it a lot better.
EPAL is not NLR(k) for any k, and NLR(k) is just about the most general unambiguous-grammar only parsing algorithm known, and it gets beaten by such a simple parser :)
@StéphaneGimenez Weekend coming up. Guess our target group is hard working. Even now, I should be in bed, resting for that workshop tomorrow and cuddling the beautiful girl that is already there (and probably sleeping by now :()
In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? Could someone explain this?
Sites in beta usually have a little 'site stats' box on the side so one can monitor the site health. How come this site doesn't have one ?
In an answer to this question I wrote the following LaTeX code:
$$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the $n$-th symbol from the last one is 1}\}.$$
The output of this code should include four different curly brackets (two opening, two closing), but they are not being rendered.
Inline LaTeX...
According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator).
Is there an extension of SQL (implemented and used in the industry) which captures polynomial time computable que...
