**Complexity Class**

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

exciting discoveries

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

and coding,

like playing dice

Even designing,

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 :-(

*-DB*

**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

*-Matthew Burgess*

一道二道三道题

却似千道万道题

山重水

疑无路

圣诞节后是结束

*-Shirley Zhe Chen*

**Quantum**

Quite

Understandably

A

Nerve-Wracking

Time

Utilizing

Math

**Qubits**

Potential inspires

But the collapsing saddens

Frustrating qubits

*-Robin Givens*

**Ahem**

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

**Inception**

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

*-Mark Gordon*

**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

Harray! Harray!

Finish this sh**, fly to NYC!

*-Sirius Gu*

Remember ST-Connectivity

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.

*-Dan Hathaway*

**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!"

*-Augie Hill*

**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!

*-Chun-Hung Hsiao*

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.

*-Nan Jiang*

**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.

*On reductions:*

NP completeness

All these problems really ask

Is the same question

*On existence proofs:*

The solution space

Expanding so rapidly

I must find just one.

*On pseudorandomness:*

Consume randomness

Stretch it craftily into

Pseudorandomness

*On quantum mechanics:*

Spooky action at

A distance is how Einstein

characterized it.

*On measuring qubits:*

Superpositions,

Entangled bits acquiesce.

It's really just math.

*-Ben King*

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

Wide variety

Curious open problems

So it continues

Most recent was weird

Not like classical at all

Quantum confusion

Overall good class

Lots of interesting stuff

But now it must end

*-Tim Lane*

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!"

*-Jennifer Li*

**To EECS574**

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

*-Gang Liang*

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.

*-Travis Martin*

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.

*-Aaron Mininger*

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.

*-Ryan Morton*

A tough struggle

through problems and proofs,

not without joy.

*Dmitriy Musatkin*

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.

*-Yumin Pan*

**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

*-Yongjoo Park*

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.

*-Paul Rigge*

One day I will prove

P != NP

at my expoential age, or

in a random branch of life

*-Yaoyun Shi*

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.

*-Nicholas Triantafillou*

nonuniform source

derandomization fails

use entanglement

*-Bryce Wiedenbeck*

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!

朝暮捧读夜静思，朦胧云开似不知。

先生言语若灵犀，便得醍醐灌顶时。

*-Tianjie Xu*

"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.

*-Minsub Yim*

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.

*-Mary Wootters*