Comp-sci is so cool
and I am so smart
and I can pick a paper
and totally understand
everything it says
and all that's new
and processes anew
all of it, within my grasp
since, of course,
I'm so smart
Or so I feel,
until I attend,
just a single,
complexity class :-(
Physics was easy
and math was nice,
graphs were obvious
like playing dice
circuits was fine
logic in silicon
it was all right
but all this crazy
hierarchy of time
expanders and extractors
and quantum dice
its all slowly
screwing my mind
I tell you I was
feeling all fine
until I took this
complexity class :-(
A Bit Named Qu
There was a bit named Qu
Who couldn't decide between states one and two
He spent his days in a superposition
Waiting to be measured by a photon emission
Life between states is quite a lonely place
But along came Sue with her beauty and grace
After what seemed like an eternity but was infact just a second
Qu proposed entanglement, and Sue was quite taken
From then on they transformed together
Jumping from gate to gate, nothing could be better
There must come a time when every bit be measured
Lucky for Sue and Qu, their bond will eternally be treasured
-Shirley Zhe Chen
But the collapsing saddens
So I wrote down a bunch of words related to theory
But none of them rhymed which seemed awfully eerie
Does anything really rhyme with permanent?
Assuming of course we discount determinant
Or maybe we don't need to make this thing rhyme
I can just drop concepts like expander, entropy, and time
Maybe I can talk about cookies on the last day
Or how a super position is a high dimensional ray
Or perhaps I can just do a meta poem
That would be annoying
If only those in Inception knew
Just what their device could do
Tunnel through the dream line
All the while saving time
With it we could be content
With unbounded computation in a single moment
Going back to a previous rhyme
We'll find space becomes the new time
Never Ever Never
Violets are blue, roses are red
Life is hard, never rest
Quantum theory, not so easy
Tensor product, feel uneasy
God's particle, spin left and right
Schrodinger's cat, both dead and alive
Weird bits, still can be flipped
Ever entangled, never impossible
Finish this sh**, fly to NYC!
it is NL-complete, that's quite nifty
but reduce SAT to it
and you'll make much profit
though you probably can't, what a pity.
Computational Complexity Theory
'twas the fall of '11, it's the first week of class
We give introductions, the first day goes fast
We're assigned homework groups, I'm with Ryan and Ben
You could say I was lucky, not so much for them
We learned 'bout computing algorithms efficiently
I think I'm understanding the concepts sufficiently
P and NP, classes time and space
At this point I'm managing to keep up the pace
Cook-Levin tells us computation is local
I don't ask any questions, I'm not very vocal
Discussions were great, I feel less like a dummy
Once Mary brought cookies and they were quite yummy
The lectures get longer, concepts more complex
Extractrators, entanglement, and other subjects
Thanksgiving break reminds us what weekends were like
Before complexity homework earlybird bonus point hike
Fast forward a bit, it's the last week of class
Dr. Shi is lecturing, students just hoping to pass
Now I'm writing this poem, maybe it wasn't so bad
We'll see soon enough, by the week that I've had
I learned much this semester, I'm glad I was here
The homeworks were tough, we all deserve beer
And with that note I say, for goodness sake
"Happy holidays to all, and to all a good break!"
P and NP
How hard is it to find the answer for
the truth and false without assigning crap?
How long does it consume to use no more
than red and green and blue to paint the map?
They seems so far away, they're so unlike,
Like this is in the sea, and that in space.
There's no one knows a way to take a strike
unless the nondeterminism takes place.
Let's call for nondeterminism! You say.
Surprised the two connect as one like I'm
Reduce the path as Cook and Levin's way.
These two completes the heart of poly time.
So now we know where P and NP lie:
The hardest open problem worthy try!
People perceive "pseudorandom" intuitively;
we say "no poly circuits distinguish it
from true randomness".
People perceive "oneway function" intuitively;
we say "no poly circuits compute its inverse".
Computational Complexity is a powerful tool
of defining fuzzy concepts that involves
judgements of the intelligent.
a series of haikus:
On computational complexity:
Like drops on a pane
Of glass, all of our problems
Gather into camps.
On open problems:
It seems so simple
The greatest open problem
P equals NP?
On the homework:
Stumbling in the dark
Hoping for a spark to light
The once trodden path.
All these problems really ask
Is the same question
On existence proofs:
The solution space
Expanding so rapidly
I must find just one.
Stretch it craftily into
On quantum mechanics:
Spooky action at
A distance is how Einstein
On measuring qubits:
Entangled bits acquiesce.
It's really just math.
Took out of intrest
Discrete logic and theory
I am a bit weird
First part was old hat
Last class covered basic stuff
Made a good review
Then came the random
Little statistics background
Bit over my head
Curious open problems
So it continues
Most recent was weird
Not like classical at all
Overall good class
Lots of interesting stuff
But now it must end
Before my first class in theory,
I thought the professor would be eerie,
Though he brought a bloody knife and threatened our lives,
He actually was pretty cheery.
So I SAT in the very first row,
While he reviewed all we should know,
When out from the screen charged a Turing Machine,
Firing strings of ones and zeros.
Outnumbered, we called Mary for aid,
She said "NP, I'll be there right away!"
"This problem is hard but these bits we’ll discard",
"And in poly-time we will end this raid."
Through trees and random walks Mary led,
And we thought hard of a plan as we fled,
This problem we'll have to reduce to a simpler one and we'll use
The solution to that instead.
Hiding in a fort by the Shor,
Guarded with Hadamard doors,
We zapped two bits into one until there were none
As we blasted cannonballs of XOR's.
The machine's input tapes did expend,
And soon the fight did end,
Towards infinity and beyond, it approached epsilon,
As we gathered and shouted "Horray!"
I remember the days of September
We were so close together
I was humming the songs of silence
Sweetly plucking the harp of book
Every moment was sacred and mystic
We were near to the shore of eternity
The days are gone and will never come back
I remember the days of October
You were trying to sit beside me
All alone in the shuttered places
I was waiting for fall break
Every moment was plodding and tedious
I was hoping the break was eternal
The break is gone and will never come back
A poem is a strange way to express my feelings, but I guess it will have to do.
I have a more to say, maybe it would be better to just talk to you.
My overall class experience was overwhelmingly positive,
but for much of this, the book and subject matter were causitive.
The structure was fantastic, all homeworks and exams were great.
I really liked how you encouraged our assignments not to be late.
I appreciated how Mary was helpful, clear and available,
and especially of her mastery of material that sometimes seemed unassailable.
Dr. Shi's kindness, desire to teach effectively, and clear understanding were unprecedented,
to accuse him of not caring one's brain would have to be cemented.
Though the material interests me and for knownledge I yearn,
the whole second half seemed impossible to learn.
I'm not sure if this is due to teaching style (doubtful), pace of coverage, effort, or stupidity,
But certainly my understanding didn't come with near the rapidity.
Twas the last night of finals, and I was trying my best
To hopefully finish this complexity test
My notes were all lying by the printer with care,
In hopes that the answers would somehow be there
There was really no hope of going to bed,
All the caffiene and sugar just danced in my head
So I got the test out, put the book on my knee,
And I just settled down to work on part 3
I was given a problem which was simply defined,
But I had to come up with the complexity in time.
My thoughts were all jumbled, they seemed like a clatter.
I just couldn't get it, just what was the matter?
Into my mind all the options came,
And for each one I pondered, and called it by name
Is it #P, or NL, or EXP I seek?
Is it only NP, or is it NP-complete?
The quantum one stumped me, till I got it with glee,
Use a Toffoli gate, then apply sigma-z.
But first Hadamard, to a |0> you do.
It gives |0> plus |1>, all over root 2.
There's an expander problem? At that I won't balk,
I know what to do, just use random walk.
I moved onto randomness, And it was hard I soon found,
Do I use Hoeffding's here, or a Chernoff bound?
And the distribution phi, it was easy to say,
Has support size n, and min-entropy k.
But one of the problems I had to abandon,
I just couldn't show it was pseudorandom.
But I finally finished, and felt pretty good,
And realized that most of the stuff I had understood.
The class had been useful, it made some things clear
that I hadn't used since my sophomore year.
It had been so long since my linear lectures,
And I'd never used eigenvalues or vectors.
And statistical methods that were sharpened in class,
Were sure to be useful beyond helping me pass.
So what if I'll never make a new quantum circuit,
I still think this class was definitely worth it.
And maybe proving complexity just isn't my passion,
but I'm sure what I learned can be used in some fashion.
So as I submitted my latex to ctools that night,
I'm not into theory, but with me that's alright.
When the size of the input grows to be
Bigger and bigger, in practicality, we would see
Polynomials and logarithms, and constants do scale,
But exponentials and faster most certainly fail.
The models we use wear no bikinis,
they're computational in nature, with lots of between-eez.
Then came Turing and Church, who made them equivalent,
Which simplifies our task, we need solely one treatment.
We put problems in classes base on limitations
Where the most important question is often terminations.
Both space and time are of primary concern,
But often the class boundaries are difficult to discern.
Each class is wide with many sub-sections,
And we relate them using various reductions.
The transformations depend on the classes at hand
But if SAT can be done in P, insert music from the band.
The linear algebra causes head-scratching and many pauses,
But often we find gadgets, i.e. for variables and clauses.
Do I make it a graph or think more like SAT?
At the end of the day, "how'd they think of that?"
We did counting, extraction, and expander graphs too,
But the quantum computing really drove me cookoo.
With qubits and tensors, and a notation real goofy,
Somehow quantum can do, to some, seem spoofy.
After taking this class, I know we're still rookies,
However, this was relieved since Mary brought cookies.
Our captain of intellect did help us grapple,
Through use of metaphor, my favorite, the apple.
A tough struggle
through problems and proofs,
not without joy.
Zeros and ones, where all story begins.
States and tapes, where language forms.
Thought gates and circuits, we see creations and innovations.
And this is computing all about, build the world from the origin.
The happiest week
The happiest week for me
Was the week when there was a mid-term
I know it's ironical
But more ironical is that
Homework is more difficult than exam
It is as much ironical as that
I still do not understand how early bird bonus works
And I am still curious
Who is Compton
There once was a system |Phi->
That held a lot of surprises
You can pick any basis
But you'll find that the case is
It still has the form |ab>, |ba>, with a minus.
One day I will prove
P != NP
at my expoential age, or
in a random branch of life
A Shaolin monk spoke. He spoke of other Shaolin monks. He spoke of the shackles they had broken: some of wood, some of stone, some of hardened metal. He spoke of the seams, the cracks, the smallest fissures in the shackles. He spoke of the entanglements, the expansions, the transformations that widened these gaps until the shackles broke. And he spoke of still unbroken shackles.
The wisdom of the elder Shaolin monks was vast. How could they see these gaps before they were widened? Where did they gain the strength to break the shackles? How could any young monk break the shackles the elders had not broken?
But the Shaolin monk did not let his students despair. Nor did he let his students idly admire the great monks of the past. He shackled his students, as the monks had been shackled before. Some of the shackles weighed heavy as the most solid stone. The students tried to find fissures like the great monks had found. But some lessons were forgotten, some shackles allowed different motions, and some shackles refused to crack. So the monk's assistant spoke again of the wisdom of the elders. And the students reviewed the scrolls that stored this wisdom. After reflection and channeling of the randomness of the mind, the students split the shackles. They shared their seeds of knowledge with the monk, his assistant, and all who would listen.
Although the great elders could split the shackles like paper, the students rejoiced in their newfound strength. Perhaps the students' wisdom would one day measure in the same plane as the elders. The stories of the elders were no longer the stories of the distant past. Perhaps the stories of the students will be the stories of the near future.
Today's work is on a function of one way,
Fairy of inspiration please don't go away,
When there comes an idea that's smart,
Which looks like piece of art,
This makes a wonderful start to a great day!
"I am Shi, and she is he!"
In a jovial atmosphere, the class began with the professor's corny joke,
Little did the student know that the class would become a choke.
He went to class with an excited anticipation,
Only to leave with an aggravation.
Along with the never been heard Compton scheme,
He gradually lost his self esteem.
Throughout about 30 seed lectures,
He has seen them stretched to homework problems
that are computationally indistinguishable from uniformly random problems;
Though her being poly-time constructible is still questionable,
He decides to call Mary a pseudorandom generator.
With passing this class still at stake,
He better not consider other chances to take.
He realizes that it's the Sunday night,
And writes this poem uptight.
He is me,
And I am you.
There was a grad student named Mary
Who GSI'd for complexity thary
She learned a whole lot
From the great questions she got
and she hopes that y'all's breaks are real merry.