Here is a logic question I will ask today and answer next week. Feel free to leave comments with
the answer- you may come up with a different proof than me and that would be great!
Our lang will have the usual logic symbols, quantification over the domain, quantification over subsets of the domain (so second order) the = sign, and the symbol +
Examples of sentences:
(∀ x)(∀ y)[ x+y=y+x]
true over Q,R,N. False in S_n for n\ge 4 (group of perms of n elements)
(∃ x)(∀ y)[ x+y=y]
true in Q, R by taking 0. not true in {1,2,3,...}
Lets assume it is true and call the x 0
(∀ x)(∃ y)[x+y=0]
True in Q, R, Z, not true in N.
QUESTION ONE: Is there any sentence in the first order theory that is TRUE over (Q,+) but
FALSE over (R,+)?
QUESTION TWO: Is there any sentence in the second order theory that is TRUE over (Q,+)
but false over (R,+)?
Thursday, September 29, 2016
Tuesday, September 27, 2016
Who's Afraid
The playwright Edward Albee passed away earlier this month at the age of 88. I had never actually seen any of his plays so I took the opportunity to watch the 1966 movie Who's Afraid of Virginia Woolf? based on the play.
The play has four characters, George, a history professor in his forties and his wife Martha, the daughter of the University's president. Joining them for a late get together is a young biology professor and his wife. The movie had an incredible cast: Richard Burton, Elizabeth Taylor, George Segal and Sandy Dennis. All nominated for academy awards. The women won.
The movie covers many themes, mostly revolving around the disintegrating relationship between George and Martha. George did not live up to his potential as a drunk Martha did not hesitate to point out in front of all of them.
Nevertheless Albee captures a fear many academics have. That one day we may wake up and realize we've become that bog. Stuck in our job because we can't afford to give up tenure, but just going through the motions. It's a fear that motivates us, to make us continually try to do new things and achieve new heights. But it's also a reminder that academics is a long career and one that could bog down before we even notice.
Edward Albee writes a play incredibly uncomfortable to watch yet impossible not to. So rare to see that in mainstream plays or movies today.
The play has four characters, George, a history professor in his forties and his wife Martha, the daughter of the University's president. Joining them for a late get together is a young biology professor and his wife. The movie had an incredible cast: Richard Burton, Elizabeth Taylor, George Segal and Sandy Dennis. All nominated for academy awards. The women won.
I actually fell for him. And the match seemed practical too. For a while Daddy thought George had the stuff to take over when he was ready to retire. Anyway, I married the S.O.B. I had it all planned out. First he'd take over the History Department, then the whole college. That's how it was supposed to be! That was how it was supposed to be. All very simple. Daddy thought it was a good idea too. For a while!
Until he started watching for a couple of years and and started thinking it wasn't such a good idea. That maybe Georgie-boy didn't have the stuff! That he didn't have it in him! George didn't have much push. He wasn't aggressive. In fact, he was sort of a flop! A great big, fat flop!
So here I am, stuck with this flop, this bog in the History Department. Who's married to the president's daughter who's expected to be somebody. Not just a nobody! A bookworm who's so goddamn complacent he can't make anything out of himself.The movie reflects an earlier time in academics, when all the professors were white males and success was measured by taking charge of a department.
Nevertheless Albee captures a fear many academics have. That one day we may wake up and realize we've become that bog. Stuck in our job because we can't afford to give up tenure, but just going through the motions. It's a fear that motivates us, to make us continually try to do new things and achieve new heights. But it's also a reminder that academics is a long career and one that could bog down before we even notice.
Edward Albee writes a play incredibly uncomfortable to watch yet impossible not to. So rare to see that in mainstream plays or movies today.
Thursday, September 22, 2016
Boris Trakhtenbrot (1921-2016)
I woke up this morning to two pieces of news. Subhash Khot has just been named a MacArthur Fellow, the "genius" award, for his work on unique games. But I also just learned about Monday's passing of the great Russian theorist Boris Trakhtenbrot at the age of 95.
Trakhtenbrot has a number of important results in automata theory, model theory and logic to name just a few areas. In computational complexity we know him best for the Gap Theorem which he proved independently with Allan Borodin. Roughly the gap theorem states that for any computable f there is a computable time-bound t such that DTIME(t) = DTIME(f(t)), every problem solvable in time f(t) can also be solved in time t. For example there is a time bound t such that DTIME(t) = DTIME(2t). This doesn't violate the time hierarchy since t may not be time-constructible. There is nothing special about time here, it works for space or any abstract complexity measure.
Borodin and Trakhtenbrot worked independently because they sat on different sides of the iron curtain during the cold war which very little communication in between. Boris Trakhtenbrot wrote A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (PDF) that traces this early history of Russian theory. He didn't hold back discussing some of the academic politics in Russia that stifled research into computational complexity and gave us a window into the Russian scientific community in the mid-20th century.
Thankfully the iron curtain has been replaced by a global internet and we can do science together. Let's hope it stays that way.
Borodin and Trakhtenbrot worked independently because they sat on different sides of the iron curtain during the cold war which very little communication in between. Boris Trakhtenbrot wrote A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms (PDF) that traces this early history of Russian theory. He didn't hold back discussing some of the academic politics in Russia that stifled research into computational complexity and gave us a window into the Russian scientific community in the mid-20th century.
Thankfully the iron curtain has been replaced by a global internet and we can do science together. Let's hope it stays that way.
Wednesday, September 14, 2016
Academic Rankings Foster Competition
This week US News and World Report released their undergraduate rankings earlier this week. A time for schools to brag. US News and World Report used to publish an actual weekly news magazine, now they mostly just focuses on rankings. Besides various categories of undergrad institutions USN&WR ranks engineering and business programs. There are many other ranking systems of varying quality but in the US we take the USN&WR rankings the most seriously.
Computer Science does not get an undergraduate ranking. Computer engineering does--not the same. CS does get rankings as a PhD program, last time in 2014. I've posted on rankings in 2005, on the failed NRC rankings of 2010, on using metrics for rankings, and Bill had his own so-called non-controversial thoughts on rankings.
In the September CACM, Moshe Vardi wrote his editor's column entitled Academic Rankings Considered Harmful
More importantly rankings cause us to compete against each other. Every CS department wants to raise their rankings (or stay on top) and use that goal to work on strengthening their departments and use rankings to make the case to upper administration and alumni to get the resources needed to continue to grow. By the nature of rankings, not everyone can rise up but we all get better in the process.
Computer Science does not get an undergraduate ranking. Computer engineering does--not the same. CS does get rankings as a PhD program, last time in 2014. I've posted on rankings in 2005, on the failed NRC rankings of 2010, on using metrics for rankings, and Bill had his own so-called non-controversial thoughts on rankings.
In the September CACM, Moshe Vardi wrote his editor's column entitled Academic Rankings Considered Harmful
Academic rankings, in general, provide highly misleading ways to inform academic decision making by individuals. An academic program or unit is a highly complex entity with numerous attributes. An academic decision is typically a multi-objective optimization problem, in which the objective function is highly personal. A unidimensional ranking provides a seductively easy objective function to optimize. Yet such decision making ignores the complex interplay between individual preferences and programs' unique patterns of strengths and weaknesses. Decision making by ranking is decision making by lazy minds, I believe.No potential grad student should decide based solely on rankings but neither can we expect them to solve a highly-complex multi-objective highly-personal optimization problem over all 266 PhD-granting CS departments. They will find ways to narrow down their list of schools somehow and a reasonable independent ranking of CS departments can certainly help.
More importantly rankings cause us to compete against each other. Every CS department wants to raise their rankings (or stay on top) and use that goal to work on strengthening their departments and use rankings to make the case to upper administration and alumni to get the resources needed to continue to grow. By the nature of rankings, not everyone can rise up but we all get better in the process.
Saturday, September 10, 2016
Noam Nisan wins the Knuth Prize
I've known Noam since we were fellow grad students in Berkeley in 1985 and we have become good friends and colleagues. Noam Nisan started his career in computational complexity and Luca posts about several of his seminal works in derandomization, interactive proofs, communication and circuit complexity. I'll focus this post on Nisan's 1992 paper with Mario Szegedy, On the degree of boolean functions as real polynomials.
Let f be a Boolean function on n variables and p a n-variate polynomial over the reals and suppose for every x in {0,1}n, |f(x)-p(x)| ≤ 1/3. Nisan and Szegedy show that the decision tree complexity of f is bounded by a polynomial in the degree of f. The decision tree complexity of a function is the number of bits one has to query to determine whether f is 0 or 1.
The theorem didn't have an immediate application but soon afterwards I told Noam we found a result that followed from his paper. His ears perked up until I told him the actual result (if P = PSPACE then P = AWPP relative to a Cohen generic oracle).
Later on Nisan-Szegedy would have direct applications to quantum computing, showing that quantum, random and deterministic decision tree complexity for total functions are polynomially related. Just last STOC we saw two papers giving tighter bounds on these relationships.
In 1997 Noam Nisan walked away from complexity and soon thereafter became one of the founding players in algorithmic game theory, co-organizing the 2001 DIMACS workshop that would kickstart this field. He won the 2012 Gödel Prize for his early work on algorithmic mechanism design with Amir Ronen.
Nisan and Szegedy begat one of my most frustrating open questions on the relationship between rational functions and decision tree complexity. I have an application for it but I don't think you really want to know.
Wednesday, September 07, 2016
Why I Don't Believe in ET
Is there life on other planets? The naive answer is "of course, why should Earth be special." What makes a lottery winner special? We could have just won the life lottery and the losers aren't around to complain.
The more scientific approach uses variants of the Drake Equation. I'll use the variant from the recent paper A New Empirical Constraint on the Prevalence of Technological Species in the Universe by Frank and Sullivan.
Frank and Sullivan's computations show that we expect there to only be life on Earth, say A=0.01 then f = flfift must be at most 2.5 x 10-24.
Seems small but is it really? 2.5 x 10-24 is roughly the probability of flipping 78 coin tosses and having them all come up heads. Maybe life requires 78 50/50 independent events to occur. Or 1060 independent events each with 95% probability. 1060 doesn't seem that big.
Our attempts at finding life, whether by SETI or Mars soil or UFOs have so far turned up nothing substantial. We just might be the only ones out there.
By no means am I arguing that we give up the search. I could be wrong, f could be much larger than 2.5 x 10-24. Let's keep looking, perhaps exploring the ice caps of Mars or the moons of Jupiter, keep listening the the stars, explore new ways to probe the galaxy. It would be incredible to find extraterrestrial life, but just don't be surprised if we don't.
The more scientific approach uses variants of the Drake Equation. I'll use the variant from the recent paper A New Empirical Constraint on the Prevalence of Technological Species in the Universe by Frank and Sullivan.
We define the ‘‘A-form’’ of the Drake equation, which describes the total number of technological species that have ever evolved anywhere in the currently observable Universe:
A = Nfpnpflfift
where N is the total number of stars, fp is the fraction of those stars that form planets, np is the average number of planets in the habitable zone of a star with planets, fl is theI first encountered the Drake equation in high school from Carl Sagan's book Cosmos. The conclusion that there must be life out there from the equation never satisfied me because of our inability to measure the f values.
probability that a habitable zone planet develops life, fi is the probability that a planet with life develops intelligence, and ft is the probability that a planet with intelligent life develops technology (of the ‘‘energy intensive’’ kind such as that of our own civilization).
Frank and Sullivan's computations show that we expect there to only be life on Earth, say A=0.01 then f = flfift must be at most 2.5 x 10-24.
Seems small but is it really? 2.5 x 10-24 is roughly the probability of flipping 78 coin tosses and having them all come up heads. Maybe life requires 78 50/50 independent events to occur. Or 1060 independent events each with 95% probability. 1060 doesn't seem that big.
Our attempts at finding life, whether by SETI or Mars soil or UFOs have so far turned up nothing substantial. We just might be the only ones out there.
By no means am I arguing that we give up the search. I could be wrong, f could be much larger than 2.5 x 10-24. Let's keep looking, perhaps exploring the ice caps of Mars or the moons of Jupiter, keep listening the the stars, explore new ways to probe the galaxy. It would be incredible to find extraterrestrial life, but just don't be surprised if we don't.
Thursday, September 01, 2016
The Letter
Guest post by Molly Fortnow, incoming member of the University of Chicago class of 2020.
On January 24, 2011, a miraculous thing happened. I was published on the internet for the very first time. Only twelve years old, a year into middle school, my fifteen year old sister and I decided to test Wikipedia, a source known for its open editing policy, and our findings were astonishing. So astonishing, in fact, that our father, the “famous computer scientist” (his words, not mine), let us write a guest post on his “very successful blog.” He titled it: Why My Kids Trust Wikipedia.
On January 24, 2011, a miraculous thing happened. I was published on the internet for the very first time. Only twelve years old, a year into middle school, my fifteen year old sister and I decided to test Wikipedia, a source known for its open editing policy, and our findings were astonishing. So astonishing, in fact, that our father, the “famous computer scientist” (his words, not mine), let us write a guest post on his “very successful blog.” He titled it: Why My Kids Trust Wikipedia.
Half a decade later, it still comes up fifth when you google me.
Going back to this post now, I can’t help but laugh. The comments are full of grown adults set off in a frenzy by a child’s conjecture, disproving us with everything from personal anecdotes to computer science to the inner workings of Wikipedia itself. Some directly addressed my sister and me, and asked us questions–questions I never even read until now. One commenter told another, “way to miss the joke,” and others accused my father of making up the story. I have to laugh at this especially–there really was no joke. My sister and I legitimately did this, and we legitimately trusted Wikipedia from there on. I’m sorry we never read your responses to know otherwise.
Though I never so much as skimmed the responses until now, I am amazed at the passion some had for arguing with our point. Though an online comment section like this allows a screen to hide behind, I can’t help but notice the open inquiry and debate that this short, somewhat meaningless post sparked. One commenter even acknowledged this phenomenon, saying, “I would like to thank Annie and Molly Fortnow for raising this wonderful question.” First of all, you’re welcome! Second of all, you make a great point. Hearing and comprehending opinions that differ from your own and questioning and debating them, though it can be uncomfortable at times, is a wonderful opportunity to learn and grow as a thinker and a member of society.
In a way, a comments section isn’t so much different from a university–a place where people’s ideas and beliefs are challenged and uprooted. Of course, a place of higher learning is a much more intense example of this, a hotbed of young adults rapidly expanding their intellect while finding empowerment to take action for things they believe in. At my sister’s institution, Brandeis University, protests are regular and progressive thinking is a culture–and this is not an isolated example. Students are thinkers and activists, and a University is, across the board, a place that cultivates and harvests opinions of all kinds–though hopefully educated ones.
I’m an incoming member of the University of Chicago class of 2020, which might ring a bell as to why I’m writing this blog post in the first place. Just a few days ago, everyone in my graduating class was sent a letter from Dean of Students John Ellison outlining the university’s policies on free speech and open inquiry, with one especially controversial statement:
Everyone seems to disagree about everything about this letter, from its message to its implications. Is free speech on campuses a partisan issue? An age issue? Is the shutdown of free speech an epidemic at schools across the nation? Did Ellison misuse the phrases “trigger warnings” and “safe spaces”? Are these two things important to have or not have at universities?
I can’t speak for anyone but myself, but here’s my take, after reading dozens of articles, editorials, and blog posts, as well as lengthy Facebook posts written by both incoming and current students of UChicago, as a member of the class of 2020 and a recipient of the letter:
I grew up in just about the safest suburb in the country, north of Chicago, surrounded by people just like me–mostly white and Jewish, affluent, and on their way to being well educated. The public schools in that area are some of the best in the country, the kids, as privileged as kids can be. I moved a year into high school to Atlanta, GA, one of the most liberal cities in the southeast, where I attended an extremely liberal private high school. Though I certainly encountered ideas and opinions over the years that surprised me, pushed my comfort zone, and even made me uncomfortable at times, I also felt intellectually safe a majority of the time, and shared almost all of my views with my close friends and many of my classmates.
What UChicago is saying to me is, they want to burst this bubble I have lived in. I have spent most of my life in a space of intellectual security, a world that has been constructed for me but that doesn’t really exist. If I want to be able to face the world head on, I’m going to have to understand on a deeper level that creating spaces where I feel consistently comfortable and censoring my life from opinions I disagree with is counterproductive to understanding the world. A university, as a place of higher learning, has a responsibility to provide me with discussions that shove me outside of my comfort zone, that make me feel vulnerable and push me to think on a more complex level. For the first time in my life, I will be living in a community of people from a litany of different backgrounds, whose voices are sometimes radically different than mine. And it’s my responsibility not just to argue and assert my voice as well, but also to listen and learn.
Not everyone my age grew up in the bubble I did, and it’s unfair to justify this letter’s argument with the assumption that we need this policy because we are all too coddled, self-righteous, and entitled to know what’s best for ourselves. It’s also unfair to say there will be no social safe spaces–like clubs for LGBTQ+ kids–or trigger warnings for those who really need them, like a warning of graphic content for people who have gone through trauma surrounding the issue. In fact, several current students and professors–as well as Dean Ellison himself–have asserted that both of these things currently exist at the university, and aren’t likely to go away anytime soon.
But overall, I have to say I’m pretty proud to go to a school that wants to challenge me on a higher level than just being one of the most rigorous schools in the country (which it is). The founder of my high school, Elliott Galloway, once said, “My hope for you is that you always choose the difficult, not the easy life.” I chose this university because I knew that it would put me in challenging situations that would prepare me, like no other institution can, for life ahead.
Feel free to disagree in in the comments. Maybe I’ll even read them this time.
Going back to this post now, I can’t help but laugh. The comments are full of grown adults set off in a frenzy by a child’s conjecture, disproving us with everything from personal anecdotes to computer science to the inner workings of Wikipedia itself. Some directly addressed my sister and me, and asked us questions–questions I never even read until now. One commenter told another, “way to miss the joke,” and others accused my father of making up the story. I have to laugh at this especially–there really was no joke. My sister and I legitimately did this, and we legitimately trusted Wikipedia from there on. I’m sorry we never read your responses to know otherwise.
Though I never so much as skimmed the responses until now, I am amazed at the passion some had for arguing with our point. Though an online comment section like this allows a screen to hide behind, I can’t help but notice the open inquiry and debate that this short, somewhat meaningless post sparked. One commenter even acknowledged this phenomenon, saying, “I would like to thank Annie and Molly Fortnow for raising this wonderful question.” First of all, you’re welcome! Second of all, you make a great point. Hearing and comprehending opinions that differ from your own and questioning and debating them, though it can be uncomfortable at times, is a wonderful opportunity to learn and grow as a thinker and a member of society.
In a way, a comments section isn’t so much different from a university–a place where people’s ideas and beliefs are challenged and uprooted. Of course, a place of higher learning is a much more intense example of this, a hotbed of young adults rapidly expanding their intellect while finding empowerment to take action for things they believe in. At my sister’s institution, Brandeis University, protests are regular and progressive thinking is a culture–and this is not an isolated example. Students are thinkers and activists, and a University is, across the board, a place that cultivates and harvests opinions of all kinds–though hopefully educated ones.
I’m an incoming member of the University of Chicago class of 2020, which might ring a bell as to why I’m writing this blog post in the first place. Just a few days ago, everyone in my graduating class was sent a letter from Dean of Students John Ellison outlining the university’s policies on free speech and open inquiry, with one especially controversial statement:
Our commitment to academic freedom means that we do not support so-called ‘trigger warnings,’ we do not cancel invited speakers because their topics might prove controversial, and we do not condone the creation of intellectual ‘safe spaces’ where individuals can retreat from ideas and perspectives at odds with their own.The next day our class of 2020 facebook group exploded. In the days following everyone seemed to have an opinion about this, not just the members of my class. The letter was featured everywhere from personal blogs to the front page of the New York Times. Professor Kevin Gannon tore the letter down , saying that it “reeks of arrogance, of a sense of entitlement, of an exclusionary mindset....It’s not about academic freedom; it’s about power”–that it is simply a reminder to students that we have no real agency in deciding who gets to speak at our school or how we want to be treated in certain situations. Other publications commended the refreshing, if blunt, statement, and urged other colleges to follow suit–one Chicago Tribune Editorial asserted, “we love the commitment to the marketplace of ideas, the implicit endorsement of democratic freedoms and the sheer feistiness. Intended or no, the university's position is a direct challenge to other schools that have buckled when controversial speakers or ideas threaten to disrupt the fake idyll of groupthink.”
Everyone seems to disagree about everything about this letter, from its message to its implications. Is free speech on campuses a partisan issue? An age issue? Is the shutdown of free speech an epidemic at schools across the nation? Did Ellison misuse the phrases “trigger warnings” and “safe spaces”? Are these two things important to have or not have at universities?
I can’t speak for anyone but myself, but here’s my take, after reading dozens of articles, editorials, and blog posts, as well as lengthy Facebook posts written by both incoming and current students of UChicago, as a member of the class of 2020 and a recipient of the letter:
I grew up in just about the safest suburb in the country, north of Chicago, surrounded by people just like me–mostly white and Jewish, affluent, and on their way to being well educated. The public schools in that area are some of the best in the country, the kids, as privileged as kids can be. I moved a year into high school to Atlanta, GA, one of the most liberal cities in the southeast, where I attended an extremely liberal private high school. Though I certainly encountered ideas and opinions over the years that surprised me, pushed my comfort zone, and even made me uncomfortable at times, I also felt intellectually safe a majority of the time, and shared almost all of my views with my close friends and many of my classmates.
What UChicago is saying to me is, they want to burst this bubble I have lived in. I have spent most of my life in a space of intellectual security, a world that has been constructed for me but that doesn’t really exist. If I want to be able to face the world head on, I’m going to have to understand on a deeper level that creating spaces where I feel consistently comfortable and censoring my life from opinions I disagree with is counterproductive to understanding the world. A university, as a place of higher learning, has a responsibility to provide me with discussions that shove me outside of my comfort zone, that make me feel vulnerable and push me to think on a more complex level. For the first time in my life, I will be living in a community of people from a litany of different backgrounds, whose voices are sometimes radically different than mine. And it’s my responsibility not just to argue and assert my voice as well, but also to listen and learn.
Not everyone my age grew up in the bubble I did, and it’s unfair to justify this letter’s argument with the assumption that we need this policy because we are all too coddled, self-righteous, and entitled to know what’s best for ourselves. It’s also unfair to say there will be no social safe spaces–like clubs for LGBTQ+ kids–or trigger warnings for those who really need them, like a warning of graphic content for people who have gone through trauma surrounding the issue. In fact, several current students and professors–as well as Dean Ellison himself–have asserted that both of these things currently exist at the university, and aren’t likely to go away anytime soon.
But overall, I have to say I’m pretty proud to go to a school that wants to challenge me on a higher level than just being one of the most rigorous schools in the country (which it is). The founder of my high school, Elliott Galloway, once said, “My hope for you is that you always choose the difficult, not the easy life.” I chose this university because I knew that it would put me in challenging situations that would prepare me, like no other institution can, for life ahead.
Feel free to disagree in in the comments. Maybe I’ll even read them this time.
Subscribe to:
Posts (Atom)