Computer Science - 2014-11-28

« first day (996 days earlier) ← previous day next day → last day (3429 days later) »

12:11 PM

I ve just coming here to thank all people that have helped me identify flaws in my paper. I ve just uploaded the final draft of the paper to here dropbox.com/sh/c3t3fj3zgvuahd5/AABx8qFqz_1dEW3hukuZvHCca?dl=0 i corrected the size of images, reduced the number of pages and simplified the proof. I'm going to try to upload it to arxiv, if someone wants to be in the acknoledgement section, say it to me and i'll put you there.

2 hours later…

1:51 PM

@rotia Looks better (on first glance), even though the lack of LaTeX is still felt acutely. Good luck!

3 hours later…

4:52 PM

rotia your paper has some interesting/ worthwhile aspects & was glad to see the real peer review that came about in the chat room with your introducing it. engaged group dialogs on here are not always so common. plz keep us informed of the arxiv reponse, am curious how they treat "amateur" & "university-unaffiliated" submissions. have had some frustration with their opaque policies in the past & others have reported it also. hopefully more only in the physics section.

fyi re arxiv, & its occasional restrictive-and-concealed submission policies, there is some alternative. see comments on here also for more bkg

-7

A: "The Solution Problem" - How to get credit for your work as an undergrad?

several other answers have mentioned submitting to arxiv which is indeed a sometimes prestigious and elite site occasionally containing some work/papers submitted by undergraduates. you appear to be affiliated with a university. fyi this is a semiofficial requirement of arxiv submissions, sometim...

2 hours later…

7:02 PM

lol. reskimmed the new draft. agreed, improved. alas, still mixing up backquotes and apostrophes. so thats the flip side of ppl complaining about lack of feedback, and a big part of the real frustation with "cranks". lack of attentively incorporating feedback.

dude, to be brutally candid, it comes off as dyslexic.

can you tell the difference between a left and right parenthesis? if so then with a "teeny bit" )( more effort you can master the challenge of the backquote vs the apostrophe. did you notice in chat? its screwing up your chat writing because backquotes format as typewritten text using the chat markup language....

7:17 PM

re crediting "us" for peer review. think it would be great to include a ref to this chat room & url in the ref section. also sometimes these are expressed as "acknowledgement/ thank yous" at the end of the paper.

now, wrt citing/ link rot. this chatroom has been around years & is not likely to disappear, however that is possible via se mechanisms where if another room arises and this one goes dormant, it can be frozen. alternative: use main se chat link, or the cs main site link & mention chat section.

do you have any interest in learning latex? there are very many resources for this, & there is an excellent web site called "writelatex" where you dont even have to install it locally, its entirely web-based. havent heard anyone else using this, am curious how others regard it.

again, nice crediting demaine & working from one of his proposed/ open problems. his paper on computational complexity of tetris you cite is online at his web site. it would be convenient to link the url in your paper.

Erik D. Demaine (born February 28, 1981) is a professor of Computer Science at the Massachusetts Institute of Technology and a former child prodigy. == Early life == Demaine was born in Halifax, Nova Scotia. His parents are the artist sculptor Martin L. Demaine and Judy Anderson. Demaine was a child prodigy. At age 7, he spent time traveling North America with his father, and was home-schooled until he entered college. Demaine entered Dalhousie University in Canada at the age of 12, completed his bachelor's degree when only 14 and completed his PhD when only 20 years old. == Professiona...

alas, havent seen him around se, dont think he's signed up. (does anyone know how to search all stackexchange site users? site users, not chat users?)

erikdemaine.org

user image

lol

7:45 PM

he's very "high profile" eg with a macarthur genius grant & in two documentaries... have had the one on origami in my appletv watchlist for months =D

user image

8:43 PM

@vzn lol, i'm sorry about the apostrophes backquotes thing, i'm spanish by the way

@vzn I have to say that on my defense, english is not my native language

@vzn And my keyboard is spanish too, thanks for the kind words

@vzn i'm trying to learn latex, by the way tex.stackexchange.com/questions/213327/… ,i do the paper with word, because i can save pdfs with it

plz do not apologize—unless youre gonna fix it.

afaik there is little difference between english/ spanish punctation esp wrt backquotes & apostrophes.

anyway you dont even seem to use it internally consistently in any way. its somewhat random

afaik writelatex may allow pdf export somehow. (wondering that myself.)

that se site for tex is indeed a very great resource for it (some "regulars" in this room have contributed substantially to it & have written glowingly about it.)

@vzn i've sent my paper to an author of tetris is easy,a week ago, he is reviewing it, he will correct the grammar if he ilikes it i think

no, of course not, nobody else is going to correct your grammar or punctuation and if you think so, you're mistaken, esp about the the actual concept of peer review.

only a collaborator/ coauthor would possibly stoop to that low level :p

what "author of tetris" are you referring to? who?

8:59 PM

walter kosters, why?

do you know him?

no. this guy? walter kosters?

what do you mean "author"? writer of papers on subj?

Yes that one, yes he wrote "Tetris is hard, made easy", one of my references

fyi, long ago met dude going to stanford. they were using tetris in a intro CS class. they had to write code for "the annoyer" routine that would send down ill-fitting blogs, lol

oh, ok, didnt recall WK in your refs.

it would really be nice/ helpful if you hyperlinked your refs to actual pdfs.

although admittedly that is not done so often.

just googled it, Kosters is not the main author on that paper.

ok, checking, looks like you cited it correctly.

ah, simple google search turns up this interesting/ important ref you seem to have missed.

Tell me

Tetris is hard, even to approximate by Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-nowell

seems to be a later combined paper with combined results of the two papers you already cite & mix of all the co authors.

9:10 PM

Yes, that's why i didn't include it

?!?

I thought that that wuld be repeating myself

it is highly relevant.

presumably its more complete/ comprehensive/ recent than either one of your current refs.

it also shows the researchers are aware of & connected with each other's works and collaborated later.

I ll include it then, and i will try to correct the apostrophes, backquotes thing, but that will take me longer

lol, welcome to science

computer science

9:13 PM

My english is pretty bad, when written, but its worse still when talking

imagine scientific papers that take many times the time/ effort/ results of your own...

again, asked this already, plz answer... what do you hope to accomplish with your paper?

do you have a CS job? are you done with community college for now? is this just a personal project? did you take CS classes in community college?

No, i never went to college, i studied programming in vocational formation, all practical, nothing theoretical

ok, working at all?

IThe little theoretical things that i know are by looking on it

even practical classes typically have some theory behind/ embedded in them.

do you have a software-related job? something else?

9:16 PM

No, im unemployed, i worked a while ago in a bussiness but only three months, the unemployment in Spain is very high, and the economy is struggling

sorry to hear that. what kind of business work?

I programmed in node in a big company in Valladolid, my town

←have enjoyed long periods of unemployment also

node.js, interesting, friend was telling me about that awhile back.

why do you want to publish a scientific paper? this will be your 1st presumably

I hope that people will look at my paper and hire me, but i think that that will be very hard

Node is all javascript, so if you understand node, you understand javascript

or vice versa

ah ok. that is not easy & does happen re hiring wrt papers. suggest you put in on your resume & answer questions about it in the interview. it can indeed help. nice idea!

9:20 PM

I hope so

it would be cool to show the employer the paper on arxiv even :)

Yes

Tetris is a very popular game, so it will have visibility

coincidentally just ran across a great link on tetris creator, have always wondered about him, trying to dig it up. re popularity, tetris is one of the most viral games of all time.

the author worked at MS in early days before xbox attempting to build some games there. very colorful guy.

he invented tetris in soviet russia, it was a while ago

aha found it!

man who made tetris, alexey pajitnov motherboard/ vice

^^^ star it!

colorful writing, history, great story.

he never made much $ off tetris afaik. others made massive $$$...

9:24 PM

i wasnt even born when tetris was invented

one of those so-called cautionary tales

lol

one of the classics. retro style, man =D

The curious thing of all this is that im very bad playing tetris

many of my favorite games are retro-style....

lol

do me favor & star the link, you know how to do that dont you?

cannot star the link myself.

done

=) thx man

geek admiration society

so kosters agreed to review your paper?

9:27 PM

he told me that he is looking at it

cool

this morning

its really amazing how few ppl around this chat site actually write papers!

it is very time consuming

i understand it

there was another dude from months back who was quite talented, but rather secretive, he told me he was working on a paper with someone, but then disappeared. have not seen him around in ages :\

he was also interested in the complexity of video games.

9:29 PM

how so? how he disappeared?

he spent massive effort on one impressive NP reduction. let me dig it up for fun. its easily a paper, but written as a se answer. he edited it so much on the site it inadvertently became community wiki! ouch

vanished! hes around maybe. doesnt visit chat any more. after being quite manic about chat for months. miss him.

Sorry about that, maybe he is just very busy

he has wicked latex/ graph skillz! o.O

then, you know that he is not me, lol

18

A: Is Dominosa NP-Hard?

${\rm D{\small OMINOSA}}$ is NP-hard Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? Obvi...

7

A: Is Dominosa NP-Hard?

Note: This is a continuation and revision of my other answer. Problems with the reduction Recall the decision problem: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But: ...

those are 2 of the most amazing answers on the site, imho.

begging to be written up as a paper. hes already done 90% of the work.

quite a remarkable dude. there you can get an idea what is possible with latex. it is easy to learn. you right-click on any latex on the site & it will display the code. how way cool is that?

se has some incredible technology behind it at times. luv it

9:37 PM

aha i see it reminds of the proof that minesweeper is np complete, it had wires and circuits too

yeah that minesweeper proof is classic & got signficant media attn at the time.

Realz Slaw, $$F^{A^{R^{R^{R^{R^{A^{W^{A^{Y}}}}}}}}}$$

3.5k 12 43

algorithms complexity-theory graphs reference-request satisfiability np-complete data-structures

he seems to have last been active around here around last dec or so. coming up on almost a yr or so. he seems to dink around other places on se but lost interest in cs for the moment.

in fact, the little i know about reductions, is by looking papers about game complexity

will ping him just for fun he might get a kick of of some of this stuff lol

ehh try it, see what happens why not?

did you hit my website/ blog yet? re video games vs TCS/ computational complexity? it was a link on that page about 2012 game. think you will find it interesting.

9:40 PM

yes, there was a paper, where you mentioned me, but i havent looked your blog in detail

blog post*

something about grothendieck i think

wrote up a big post on video games vs TCS/ computational complexity last spring let me dig it up.

Mar 31 at 22:42, by vzn

cs/theory angle on video games etc Tmachine blog

^^^ star plz

thx man =D

done

somehow almost makes it all worth it lol

oops rats it doesnt fmt well in the starred column, sigh oh well

have been following this small slice of TCS a few yrs now. its nice to see a playful side of the field. they can be really humorless at times over on the cstheory site. have you visited it?

ah see you have. 1pt :)

yes i didi, they are all experts, it's not a place for a noob like me

im still learning

you are far from a noob in some ways, the paper "proves" it ;)

youre not gonna get many jobs with that low self-esteem thing going on :p

9:49 PM

as i told you, i like game complexity because its more about having a good idea than knowing a lot of math

the only math i know is graph theory and first order logic

it requires significant math & you have it in your paper. eg defn, thm, lemma, proof, etc.

have you heard of conways proof of the Turing-completeness of game of Life?

no

one of my favorites in showing how very advanced ideas can be touched on via "game theory"...

id look at it

do you have a link?

holy cow just checked there is zilch mention of it on my blog. coulda sworn wrote about it once or cited it. maybe on se somewhere...

do you know what undecidability is?

Turing completeness?

9:57 PM

I know what undecidability is, more or less, it reminds me of godels theorem

0

A: What are the simplest turing-complete systems?

the Game of Life cellular automaton, which has very simple update rules and was an early scientific/mathematical/computational example that exhibits/demonstrates emergence, is Turing complete, with the proof initially credited to Conway but it seems to be unpublished. Paul Rendell has constructed...

^^^ plz upvote that, its begging

it is very rarely cited. deserves to be much better known.

we are going to fill the sidebar with updates, today lol

oops mean can you hit the question on cstheory.se & upvote

ahh okay, sorry

it is a very neat crosscutting aspect of TCS. undecidability, games, emergence, cellular automata, proofs, turing completeness, etc.

luv those crosscutting threads. try to collect as many as can.

10:00 PM

i need reputation of fifteen to upvote on cstheory, sorry :(, i once programmed the game of life for a classroom exercice in c#

its the kind of thing where a teenager might even be able to understand undecidability, in the form of Turing completeness, in that construction.

ok thx anyway.

re your rep on cstheory, if you can ask/ think of a nontrivial question sometimes about game reductions, etc, it could get some upvotes. as my grandfather used to say, "cant get hung for trying" lol

have been trying to get a ref for Conway proving life Turing complete for ages, never have found it, it seems to be near-folklore.

do you play any games in your free time? what do you do for fun?

do you understand godels thm?

do you understand the papers youve cited? the demaine writeup/ results seem very advanced in places.

the rule 110 is turing complete i think, i understand godels theorem, at least what is written on the wikipedia article, something about you cant "prove" some statement that is true or the logic system will become inconsistent

omega inconsistent

if i tell you the truth i understood better "tetris is hard made easy"

is what inspired me

do you understand why rule 110 is Turing complete?

to write my paper

so you somehow 1st found the tetris/hard/easy paper? how did you run across it?

10:09 PM

no, i dont understand why rule 110 is turing complete, i just found it in wikipedia

lol just kidding about the rule 110 question. the proof is very involved. its a few dozen pages.

probably few have gone thru the entire proof.

looking about a list of np complete problems in wikipedia

i found about tetris

cool

wikipedia is where i see everything

what (video) games do you play?

10:11 PM

i used to play call of duty a while ago, but my ps3 broke

bummer.

i liked braid a lot

have 2 ps3s around here. big fan, have spent a lot of $$$ on it over the yrs. there is a fun retro game called "gravity crash" on ps3. see what you think.

like the "neon-like" graphics. it reminds me of a very old game on atari called "caverns of mars".

some rough similarity.

i had the megadrive when i was little

re retro games, also a huge fan of Berzerk.

kill the humanoid, destroy the intruder

10:13 PM

do you know about a game called little big adventure2?

not little big planet2?

i loved that game when i was a little kid

i completed it like seven games

*times

havent heard of the 1st one. we have little big planet I/II & one particular kid has played the heck out of it around here. one of the best games around.

the creation mode is amazing, it has a lot of digital logic, have you played it? there are ppl who have implemented sophisticated electronics logic in it.

yes i played it too

have been meaning to blog about that sometime also.

in house of my brother

very good stuff. training the next generation of comp scientists without them realizing it lol

minecraft is pretty impressive too. havent played it but the kid has. lots

10:16 PM

yes, but i havent tried to do any level on it.some day

great

minecraft has been a surpise hit

its worth ~$2B to MS. stunning. reminds me of angry birds or flappy bird. viral hits.

shows the amazing power of assymetry in the game biz. ie small dev shops with big, massive hits.

angry birds is like a mini Disney. they had a new large animation group/ studio with dozens of employees.

yes, and candy crush too

oh yeah. dont know as much about it, but have heard.

10:19 PM

in my classroom everybody played it

yep

do you have any opinion on ps4?

i think is better than the xbox in my opinion, but very expensive

yeah

we have written more on this last hour than in the past two days, incredible

heres some more recent writing wrt game industry & a very impressive gamechanging AI experiment where google hired a new startup based on autonomous/ unsupervised game learning.

gaming update: Deepmind/Google, Minecraft/Microsoft, Oculus Rift / Tmachine blog

the chat rooms on se tend to be rather "sleepy" and "bursty".

have you heard of oculus rift?

10:27 PM

yes, larry page talked about the startup in ted 2014 i think

oculus rift is about virtual reality, no?

is like a helmet, i think

yeah. really? can you dig up that Ted link? how much did he say?

it looks like the oculus rift might easily surpass google glass in the early adoption. glass really is running into some difficulty with early adoption.

im going to look it up

youtube.com/watch?v=mArrNRWQEso here it is

cool thx man

no problem

gotta go eat. nice chatting. see you around. good luck with the paper. moving right along.

10:32 PM

okay see you next time

:)

10:47 PM

re the 2SAT vs 3SAT question, SG just signed up & asked it on Theoretical Computer Science

4

Q: Properties expressible in 2-CNF or 2-SAT

How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)? Are there any games, such as pebble games? It seems that the classical black pebble game and the black-white pebble game are unsuitable for this (they are PSPACE complete, according to Hertel and Pitassi, SIAM J of ...

sat lower-bounds combinatorial-game-theory

« first day (996 days earlier) ← previous day next day → last day (3429 days later) »

Transcript for

Nov '1428

Computer Science

General discussion for cs.stackexchange.com

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile