12:01 AM
Ah. Now I get it.

I think I missed a joke there. Time to go to bed, at last!

No real joke. Mindless banter. Bed for me too.

Goodnight then :)

Banter is hard via chat.
good night,see you in public beta! (fingers crossed)

4 hours later…
3:58 AM
1

Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa. \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(\langle 1, R_A\rangle, K) \\ A \to B: &\quad E(\langle 2, R_A+1, P_A\rangle, K) \\ \end{align*}...

@Gilles any comment on my comment for ^^^^^^^ ?

4:17 AM
well i think we all agree that it's time for public beta

4 hours later…
8:28 AM
@ComputerScience posted something. It's still incomplete and not very clear, but there's a time you gotta hit the Post button
@RanG I think it's true

Morning Gille
@Gilles "In addition, colist contains infinite ." you accidentally a word there
off to work, read you later

1 hour later…
9:39 AM
@AlextenBrink I think I can do your über-queue if you allow O(log v) with v the largest key for insertion. No?

10:17 AM
No, sorry - you can do it without assuming anything about your keys :)
@Raphael (just giving you a notification)
Although that is probably good enough for practical applications at least

10:37 AM
Is log(n) in the number of nodes currently in the queue, or in the number of all keys seen?
We could not get threaded AVL trees to work, but we suspect that threaded Splay trees could do the job

n is the number of items currently in the tree
'We'? :)
Oh, that doesn't have anything to do with my question, does it?
I mean, the threaded trees don't

my advisor, a PhD student of and me
sure it does
we thread a search tree with in-order pointers

Ah, like that :)

that allows to find and delete in O(1)
only problem: keep invariants somehow

10:41 AM
Splay trees may allow us to do the splay operation when inserting and to be find
nono
(by the way, my advisor has apparently proven years ago that rotatins in AVL tree can not amortise properly; he was happy that the result finally found an application :D)

(he also accused you of Forschungskraftzersetzung)

Uh oh :P
I don't know that word :P

Forschung = research; it is originally Nazi lingo: en.wikipedia.org/wiki/Wehrkraftzersetzung

It took me a few years to come up with a situation in which my heap was of use at all myself :P

10:45 AM
hahaha
yea, we have been struggling to come up with examples where you might have an advantage over many operation (towards a counter-proof)

The heap I came up with actually supports quite a lot of operations, one of which is that you can construct it in O(n) time on sorted input
Which then implies the use I mentioned in my question

I don't know what "intersection" means there

And I imagine you can use it to speed up more sweepline-based algoritms

can you merge them in o(n log n)?

Ah, it's a geometric problem
Given n lines, find their intersections

10:48 AM
ahh

You use a sweepline algorithm that works in O(n log n + k log n) time, where k is the number of intersections

and you pre-sort them according to what?

You sweep a line perpendicular to the x-axis (though y-axis is fine as well)
And if your endpoints are sorted on their x-coordinates, you can use my structure to get O(n + k log n) time
Really a world-shocking improvement! :P

^^
did you publish it?

No :P
I have no idea how fast you can merge my structure

10:51 AM
I take it you don't use some kind of search tree?

It looks like you can do it in O(n1 + n2) time, or O(n1 log n2) time
Possibly faster, let's see
I don't usually consider the running time of merge operations, it's not an operation that is used a lot I believe?
"I take it you don't use some kind of search tree?" - do you really want me to answer that question? :)

@AlextenBrink only with "yes" or "no" ;)

Then the answer is "no", have fun with the double negative ;)

@AlextenBrink I remember one instance where merging heaps would have been cool. Of course, there are variants that allow fast merges.
@AlextenBrink Ach...

You can merge fib heaps in O(1) time IIRC

10:58 AM
right

Resolving the double negative: I do use some kind of search tree

@AlextenBrink that's comforting

Hmm, there may be a chance you can merge in O(n1 + log n2) time...

morning @DaveClarke! I tried to use the tools I linked to on some music with a similar scenario as yours, but all they did was spew out numbers (I expected nice pictures, naive me). Without reading their papers it is probably hard to extract something useful.

@Raphael At least it's nice to know I've stumped three people at least :D

11:02 AM
@AlextenBrink I think I will write down our idea after lunch

'stumped' may be too strong a word though
Ok :)

@AlextenBrink I can tell you enjoy yourself

Entirely appropriate xkcd :P

we have it taped to our office door :]

I do enjoy this, if only because it means it rightly took me quite a lot of time to find the answer myself :)

11:04 AM
And directly below this one:
@AlextenBrink fair enough
so long, afk

Cyas :)
Nope, I can't think of a faster merging strategy

11:26 AM
Meh, I'm supposed to be working on this parser, but thinking about merging is more interesting...

12:18 PM
@Raphael: Wow.

12:28 PM
@DaveClarke Hm?
@AlextenBrink Parsing is a solved problem, so... ;)

@Raphael: A delayed reaction to the fact that you'd been applying some tools to Eagles songs (or equivalent).

@DaveClarke I only have few Eagles songs. It was Sentenced, a now discontinued metal band. I have a live recording of their last concert where a former vocalist performed some songs. So I figured that that would be a good scenario try and detect the change of a band member.
Would have loved to include some results in the answer, but well -- only numbers.

@Raphael Not sure whether that was sarcasm (chat and stuff), so just in case you really think that: parsing is far from a solved problem ;)

@AlextenBrink Well, it is, but not for all types of grammars. ;) (it was loaded sarcasm)

As a matter of fact, I think I just found a method to parse NLR(k) grammars, I'm just not sure whether it's linear time...
The things I think up to do to avoid working on my parser...

12:43 PM
been there

12:53 PM
Why is no one (else) accessing the site?

We're not in public beta yet, so there's only about 30 people that visit the site right now, and I think most of the questions we can think of have already been asked
There's only so much seeding we can do - most of our users are answerers, not questioners

has anyone seen suggested edits to tag wikis in the past few minutes?

in The Assembly, 23 hours ago, by Grace Note
@Raphael The plans are actually about the be discussed, now that we're approaching your second week of private beta.
@Gilles nope

I just submitted a few, which have all been rejected with no indication of who did the rejecting

I did see something in my status bar, but they had disappeared before I could look at them

1:04 PM
it wasn't me, so @AlextenBrink, @DaveClarke, @Janoma or @Suresh.
or community mods

I haven't rejected any today.

except it normally says “Rejected by”, e.g. 102 was “Rejected by Raphael”. These are plain “Rejected”

Weird.
Maybe @RebeccaChernoff knows why this can happen. *pinging people*

I didn't think that could happen. Even in weird cases, Community accepts or rejects the edits.

SE has had some glitches last week; maybe the name is going to be synced in soon?

1:14 PM
@Raphael I'm pretty sure splay trees work indeed, nice idea :)
However
Hmm

Hm, I would like to put a bounty on this question of mine once we go public. However, if nobody proposes a good answer during the periode, Jeffe automatically is awared half of it, despite him not answering the question. Wicked system.

Now try to do the same, but with log n insert, and O(1) extract-min, extract-max, and extract-mean

@Raphael only answers posted during the bounty period are eligible for the auto award

extract max is easy. Mean?! You mean median?

Yes :)

1:17 PM
@Gilles Oh, indeed, my mistake. Thanks.

I just made a suggested edit to a tag wiki on SO and it was silently rejected after a few seconds. So I'm positing a network-wide bug

I could be wrong, but I think extract-median is quite hard using splay trees

@AlextenBrink Hm, I guess we can maintain a median pointer if we have double-linked threading. We know wether we insert/delete to the left or right and we can also count how many nodes are left or right from the current median. Once the counts are 2 apart, move the pointer by one.

Which tree variants have you already tried?
Ah, yes, of course, you can simply compare your element to the median pointer...

as we incrementally build up the tree, this should work out nicely.
bring it on! er

1:20 PM
Ok then, log n worst-case search ;)

now you're silly
if your structure can do all this, you should a) show us in an answer and b) publish it ASAP

:P
It can do this:

but yea, because we use search trees we can search efficiently. That's got have some uses.

@Raphael I've suggested an edit here
Can you wait a bit (don't accept or reject it for a couple of minutes) and tell me the link?

Search in worst-case O(log n) time, which returns a pointer to the tree, and in O(1) it can return a pointer to the minimum, maximum and O(1) other order statistics (such as the mean)
And given a pointer it can do this:
Remove in O(1) time, return successor and predecessor pointers in O(1) time

1:24 PM
Cc @DaveClarke since you're a mod on CSTheory: can you hold still on the suggested edit here and see if it gets auto-rejected after a while?

And you can insert in O(log n) time

And you can build it from presorted input in O(n) time

@Raphael oh, well, never mind. At least it wasn't auto-rejected during the first minute and a half

@Gilles Jup.
@AlextenBrink sounds almost too good to be true. So you have to ensure some kind of height-balancing; I am curious how you maintain that during deletiong in (wc?) O(1) time.

1:27 PM
@Raphael Can you confirm that you don't see anything below the red "Rejected" here (no indication of who or why)?

@Gilles Copy that, nothing there

@Raphael Yeah, that is the entire trick, to maintain balancing under deletion in O(1) time :)
@Gilles I don't see anything either

Hmm, maybe a bug introduced by this

did you try and edit an orphan's wiki?

@Raphael Which tree variants did you investigate?

1:32 PM
@AlextenBrink AVL, Trie, Treap, Splay, Leftist

Then you missed at least one ;)

@AlextenBrink no doubt
must be a non-standard one (hopefully). My boss has made a habit of counting trees, so if he does not know anything else, it must be pretty exotic. :)

Shall I give you the answer, or do you want to give it some more thought?

in The Assembly, 2 mins ago, by Grace Note
@Raphael You're going to head to public beta this week.

Wohoo :D
throw new Party();

1:36 PM
@AlextenBrink Uncaught exception, site halted

@AlextenBrink Well, at this point in time I don't know any more search-tree variants so I'd had to research. So don't hold back because of me. :)

0

I just submitted a few suggested edits to tag wikis on Computer Science, (137–146). All of them were newly created excerpts or wikis. They have been rejected silently: there is no indication of who did the rejection, not even Community. None of the users in the CS chat saw the edits, though one r...

@AlextenBrink Oh, we also briefly considered Red-Black and I excluded B-trees quickly.

@Gilles That would be bad, wouldn't it? :S
@Raphael Have you ever heard of Scapegoat trees?

@AlextenBrink Oh, did not know that one. *chuckle* I guess it is decades old?
@AlextenBrink I feel like I heard it somewhere, but I could not say what they are.

1:38 PM
No idea. It has a Wikipedia page, but it's not very well known
1993 apparently
It's a very simple tree, and the reason it's so cool is that it doesn't need additional info in the nodes to maintain balance

is it in Okasaki?

@AlextenBrink It is not listed as search tree variant

On insertion, you check the depth of the path you take, and if it's too deep, you go back up the tree, figure out where the unbalance is, and then you reform that subtree into a perfectly balanced tree
@Gilles No idea, I can check
It doesn't seem to be categorized very well
Deletion is even simpler: you delete the node... and do nothing! Unless you have deleted too many nodes since the last rebalance, at which point you rebalance the entire tree
So that's an O(n) operation every O(n) deletions, and hence O(1)
If you use a threaded tree, or as I did it, store predecessor and successor pointers in every node, you get everything I mentioned above

So it is basically the same idea we have on scapegoat trees which push you the rest of the way, right?

Yup, pretty much

1:43 PM
sweet

I ended up at Scapegoat trees as I realized you didn't have time to update any kind of information stored in nodes
If you have predecessor and successor pointers, you can actually do the rebalancing (a constant factor) faster than the method described in the paper (which involves a lot of rotations)
Shall I make an answer out of this?

and then a paper ;P

:P
I don't think this is worth a paper :P

@AlextenBrink If the original scapegoat tree was worth a paper and you improved it, it certainly is. Extracting order statistics is definitely sweet.

Extracting order statistics is really nothing more than maintaining pointers just like the median thing
You can do that with any threaded binary search tree

1:53 PM
Right; but maintaining the invariants of the underlying structure while deleting min in O(1), that is cool.
basically, you can do anything about as fast as possible

what can you lose? write it up, submit it. No pressure, no stress.

Too bad you'll have spent O(n log n) operations before you have n elements in your structure
It would have been really cool if you could insert elements in O(1) given a pointer to their predecessor/successor
Hmm, maybe you can do that...

inserting works; don't know how the balancing holds up, though

Maybe you can support insertion of elements that are larger/smaller than anything in the tree in O(1) time amortized, using a similar trick to deletion
That is, you save them up in a 'linked list' by just not balancing, and if you perform some other operation, you balance them all at once

2:00 PM
@AlextenBrink They call it The Sledgehammer
(users of Isabelle/HOL rejoice)

Oh? :)

@AlextenBrink Sledgehammer may take n log n time which won't amortise I'm afraid
Isabelle/HOL is a proof assisstant. sledgehammer brute forces search for a proof using a cluster of servers.

I just looked it up :)
If you can maintain the depth of the minimum, then I think you can insert elements smaller than anything in the tree in O(1) time I believe
Basically, if you have a pointer to a newly inserted node and the depth of that newly inserted node, you can balance it in O(1) time amortized
No, that last bit is not true

I don't follow you anymore. :>
(btw, you should get a gravatar; this funky pattern is not too recognisable)

2:16 PM
Hmm, good point
But what to choose...

2:26 PM
Hmm, what if you just forget about balancing at all, and only balance if you search? Only allow insertions given a pointer, and let search return the pointer closest to the key you searched on...
That would make everything O(1), except searching
And arbitrary insertions (which need a search first)
That might actually work

2:47 PM
hm. I see the charme of the idea, but the proofs, oh the proofs...
@AlextenBrink Guess where my avatar comes from (w/o Google inverse search) and do sth similar ;)

I have no idea where it's from :P
It looks like a flying squirrel or something

not quite

2

Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual Programming allows developers to write programs by manipulating graphical elements. I guess using Visual Programming sh...

Anyway, I have to go, it's been great chatting :D

3:06 PM
@AlextenBrink Dito, let's repeat that!

1 hour later…
4:15 PM
1

A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis: Any reasonable model of computation can be efficiently simulated on Turing machines How...

4:39 PM
0

I like to quote the tooltips of the UP- and DOWN-vote buttons here: UP: “This question shows research effort; ...” DOWN: “This question doesn not show any research effort; ...” I interpret “research effort” not in terms of science, but simply that the person who is asking should state what he ...

1

Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \stackrel\alpha\rightarrow q$ for $(p,\alpha,q)\in\to$. The labelled transition $p\stackrel\alpha\t... 3 hours later… 7:59 PM REJOICE REJOICE THE BETA IS PUBLIC 6 I was just about to say something to that effect 10 minutes and not a question yet Perhaps not as celebratorily as you. What Area 51 proposals should we inform? Various AI ones? at least two AI-based proposals have made it into private, but not out. 8:07 PM Congrats yay, public! @MichaelMrozek has pledged to ask 6 questions I said joining the chat room should get me equivalent respect as if I'd asked 6 questions. I barely have 6 SO questions 0 Are we really this inactive, or are the stats broken (again)? On other sites, the stats seem to work fine... 0 visitors per Day? @MichaelMrozek I'm just 5 short of 6 on SO. So close. 8:19 PM @Kevin That's practically halfway. Almost Almost halfway to halfway. cu in an hour or so,don't burn down the site!;) well, looks like a lot of other sites probably need to update their FAQ now especially cstheory and SO 8:48 PM 1 A day or two ago, I was able to see upvote- and downvote-counts here on meta. That Feature is gone now. Was it a bug that it was available or is it a bug that it is missing now? 9:02 PM time until first question: 1 hour quality of first question: not much ): I hate caps in questions… @StéphaneGimenez So Do I, But I Don't Like The Question Much At All @StéphaneGimenez CAPS ARE OK IF THEY'RE AT THE BEGINNING OF SENTENCES or on bottles I'm Would Be Interested In The Answers :-) But I Doubt We'Ll Find SomeOnE ThaT Can AnsWer. What's Wrong With Title Case? @Kevin I was going to answer nothing with the letters set to random case. And my rand(128) call returned 0. 9:11 PM I dOn'T likE iT! whY noT usinG capS aT thE enD oF wordS alsO? @StéphaneGimenez fIXEd tHAt fOr yOu @Gilles: your random function is clever :) Have you ever tried exec /dev/urandom? Package managers are for users who haven't figured out how to pipe /dev/urandom into a file yet @StéphaneGimenez very low probability of an interesting result Sure, and the probability of a disaster is much higher (still very low). 9:18 PM 1 This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar? 9:37 PM Patience, guys. Good news travel slowly. @Raphael Link to A*? It's pretty basic compared with the level of the question, has its article on WP and is linked from WP:Pathfinding 0 cstheory.SE and math.SE have a link cite in the link popin that offers BibTeX and amsrefs for proper citing of questions and answers. Can we please get that, too? Sigh, no retag button until I get 2k @Gilles What do you want retagged? @Gilles We have linked other basic stuff; a link does not cost anything. @Raphael this was the latest one 9:53 PM Well,looks like you successfully retagged.:) user-interface, could have thought of that one Only about 9% of the comitters lived up to their word yet. :( Apparently this is not an unusually low figure,though. @Raphael Oh, I can retag, but only through the edit button, which is annoying @Gilles I don't see "retag" either but I got it on SO with <1k rep. Maybe it's not there in beta? I do most of my retagging on U&L, SFF and French, and I have access to the 10k tools on all 3, which include a “hidden” retag button @Raphael there's a retag button if you don't have enough rep to edit and there's a different retag button if you have 10k (2k in beta, 1k in private beta) ah, I see. And you can show it with a userscript,I assume? @Gilles Is that the hidden one right next to the tags? 9:57 PM @Raphael there used to be one, but it stopped working a while ago. I don't know if someone's made another @Kevin yes @Raphael On CS, hover your mouse immediately to the right of the tags of a question Ok, we don't have the worst stats among all sites despite being new. Only 200 questions till we catch the first gold site! Gogo! @Gilles O.O Oh good lord... sneaky! Thanks! I imagine most of our PP beta users sitting in frontof their PCs,furiosly hitting F5 on cs.SE main :D @Raphael ? the smallest gold site is Bicycles at ~1800 questions Lego is Beta? it got its own logo! @Raphael most sites get letters, like CS for Scicomp and CS for CS, but some get a logo stackapps does not count, I guess. Then cstheory. I see 10:05 PM 0 Is there a formal/academic connection between an imperative program and algebra, and if so where would I learn about it? The example I'm thinking of is: if(C1) { A1(); A2(); } if(C2) { A1(); A2(); } Represented as a sum of terms: (C1)(A1) + (C1)(A2) + (C2)(A1) + (C2)(A2) = (C1+C2)(A1+A2) ... ^^^^ do we want this question on CS? @Gilles I am not sure about "algebra", but I think he asks for formal semantics. That we can give him. @Raphael he's a programmer, he wouldn't need to ask if he knew the correct terminology So: do we want the question migrated? Anyone for? Anyone against? without the answer that should be a comment For the question, against the answer. although the best answer is probably a good book reference and a small example. Hoare triples? for instance; I would start (with) small(-step), though. 10:15 PM 0 I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples. The definition of Primitive Recursion is: h(x,0)=f(x), h(x,s(y))=g(x,y,h(x,y)). The short hand is h=Pr[f,g]. ... this one should be on CS now :) (posted 3 min ago) @StéphaneGimenez no, it's on-topic on Math too @Gilles It should be on CS, anyway ;) What does that question have to do with logic? @sepp2k I remember this being taught in my year 3 logic class, in the Math department 6 This is a follow-up to some comments at this question If the new cs-theory-lite site is created (it is still in pre-beta), a tricky issue is which questions here might be migrated there. I want to ask the moderators to show restraint, especially at first, in migrating questions. One area where... @StéphaneGimenez ^^^^^ @Gilles For me, it was recursion theory in a CS course. 10:22 PM @Raphael yes, it depends, which is why this question is on-topic on both sites @Gilles I should have said "should also" Anyway, I broadcasted links to cs.SE over all available channels. @Gilles, are we allowed to talk posters and slides now?:> @Raphael we've always been allowed, but now it's useful Yay for public beta! Let the 'stampeding hordes from SO' come, as Suresh put it :) @Gilles I do not want to dig for the quote,but you told me to wait. Anyone else lying in wait with a tab open on 'Newest questions', refreshing every so often due to being too paranoid to trust autorefresh? :P 10:37 PM @AlextenBrink the autorefresh is off today @AlextenBrink Guilty. Apparently we are correct to mistrust. I even use CTRL+F5 :P Now that is paranoid :P :> There are three questions on TCS that have been closed for being of rather low level in the past few ours, might it be worth pointing them in our direction? Not sure which of them would be suitable 10:42 PM I made it a habit when caches skrewed me. I don't use vanilla F5 anymore. @AlextenBrink In general, yes. I have not followed any SE much over the last two weeks, though. @AlextenBrink most questions on TCS that are basically decent are CS material -2 OK, so I am trying to prove that the following language is undecidable. The language is$EQ_{CFG} = \{M_{1}$and$M_{2}$are context free grammars and$L(M_{1})$=$L(M_{2})$The book the "Theory of Computation" by Michael Sipser provides the following proof for showing that the similar la... That's the one I'm thinking of @AlextenBrink I think it's ok, but Kaveh doesn't like migrations @Gilles dito A migration may be a bit much for the moment anyway - I didn't see the comment pointing him to us 10:59 PM A question! And quite a good one as well and tailored for you, Alex. No multis here, mind you! ; @Raphael Sorry, what do you mean by 'multis'? It's tailored for me indeed, and I don't have an answer readily available :P @AlextenBrink multiple accounts to push your stats. A common scam online games, and not a serious remark. @AlextenBrink I @Raphael You're assuming the input string doesn't contain any nonterminals then? That's probably a harder problem thpugh @AlextenBrink I'm disappointed! 11:05 PM @Raphael @Raphael Ah, ok :) that's how I read the question; he wrote$xay \in L(G)$@Raphael Well, it's certainly possible, but I can't say my method is very clean you'd have to parse xay and look at the position where a was derived. I wonder wether it is fair to assume any normal form... Trouble is, you don't know x or y :) I read is such that you know x,y,a 11:09 PM I don't think normal forms will help you much, could be wrong 3 Say I have a string$a \in \Sigma^+$and some CFG$G$such that$x a y \in \mathcal{L}(G)$where$x,y\in \Sigma^*$. Given the CFG, I'd like to determine a set of characters$C = \{ b \mid xaby \in \mathcal{L}(G)\}$. For my application, the string$a\$ is not much longer than the right hand side ...

Greibach Normal form should help
The pook guy probably went to bed and is in for a surprise tomorrow. :)

Yeah, probably :P

I'm off to bed, anyway. Have a good night, see you tomorrow!

Good night :)

11:14 PM
@Raphael at 5pm?

Ah, he's Canadian, good catch :)
Or, to be more precise, he is located in Canada

@AlextenBrink no, his profile claims that he's in Canada

There, answered in 21 minutes :)

Raphael has been automatically appointed as owner of this room. (What does this mean?)

@StackExchange It must mean that he speaks too much, right?

11:26 PM
Raphael 633, Gilles 601. It was a close call

Hmm, wow, my answer is just plain wrong...

11:52 PM
But, I think I have a better one