text:
## ITCS’2018 and more

December 13th, 2017

My good friend Yael Tauman Kalai asked me to share the following announcement (which is the only part of this post that she’s responsible for):

Dear Colleagues,

We are writing to draw your attention to the upcoming ITCS (Innovations in Theoretical Computer Science ) conference, which will be held in Cambridge, Massachusetts, USA from January 11-14, 2018, with a welcome reception on January 11, 2018 at the Marriott Hotel in Kendall Square.  Note that the conference will run for 4 full days (ThursdaySunday).

The deadline for early registration and hotel block are both December 21, 2017.

ITCS has a long tradition of holding a “graduating bits” event where graduating students and postdocs give a short presentation about their work. If you fit the bill, consider signing up — this is a great chance to showcase your work and it’s just plain fun. Graduating bits will take place on Friday, January 12 at 6:30pm.

In addition, we will have an evening poster session at the Marriott hotel on Thursday, January 11 from 6:30-8pm (co-located with the conference reception).

For details on all this and information on how to sign up, please check out the ITCS website:  https://projects.csail.mit.edu/itcs/

In unrelated news, apologies that my entire website was down for a day! After noticing that my blog was often taking me like two minutes to load (!), I upgraded to a supposedly faster Bluehost plan. Let me know if you notice any difference in performance.

In more unrelated news, congratulations to the people of Alabama for not only rejecting the medieval molester (barely), but—as it happens—electing a far better Senator than the President that the US as a whole was able to produce.

One last update: my cousin Alix Genter—who was previously in the national news (and my blog) for a bridal store’s refusal to sell her a dress for a same-sex wedding—recently started a freelance academic editing business. Alix writes to me:

I work with scholars (including non-native English speakers) who have difficulty writing on diverse projects, from graduate work to professional publications. Although I have more expertise in historical writing and topics within gender/sexuality studies, I am interested in scholarship throughout the humanities and qualitative social sciences.

If you’re interested, you can visit Alix’s website here. She’s my cousin, so I’m not totally unbiased, but I recommend her highly.

OK, one last last update: my friend Dmitri Maslov, at the National Science Foundation, has asked me to share the following.

NSF has recently posted a new Dear Colleague Letter (DCL) inviting proposal submissions under RAISE mechanism, https://www.nsf.gov/pubs/2018/nsf18035/nsf18035.jsp.  Interdisciplinarity is a key in this new DCL.  The proposals can be for up to $1,000,000 total. To apply, groups of PIs should contact cognizant Program Directors from at least three of the following NSF divisions/offices: DMR, PHY, CHE, DMS, ECCS, CCF, and OAC, and submit a whitepaper by February 16, 2018. It is a somewhat unusual call for proposals in this respect. I would like the Computer Science community to actively participate in this call, because I believe there may be a lot of value in collaborations breaking the boundaries of the individual disciplines. ## Googatory December 7th, 2017 When I awoke with glowing, translucent hands, and hundreds of five-pointed yellow stars lined up along the left of my visual field, my first thought was that a dream must have made itself self-defeatingly obvious. I was a 63-year-old computer science professor. I might’ve been dying of brain cancer, but my mind was lucid enough that I’d refused hospice care, lived at home, still even met sometimes with my students, and most importantly: still answered my email, more or less. I could still easily distinguish dreams from waking reality. Couldn’t I? I stared at the digital clock beside my bed: 6:47am. After half a minute it changed to 6:48. No leaping around haphazardly. I picked up the two-column conference paper by my nightstand. “Hash-and-Reduce: A New Approach to Distributed Proximity Queries in the Cloud.” I scanned the abstract and first few paragraphs. It wasn’t nonsense—at least, no more so than the other papers that I still sometimes reviewed. The external world still ticked with clockwork regularity. This was no dream. Nervously, I got up. I saw that my whole body was glowing and translucent. My pajamas, too. A second instance of my body, inert and not translucent, remained in the bed. I looked into the mirror: I had no reflection. The mirror showed a bedroom unoccupied but for the corpse on the bed. OK, so I was a ghost. Just then I heard my nurse enter through the front door. “Bob, how you feeling this morning?” I met her in the foyer. “Linda, look what happened! I’m a ghost now, but interestingly enough, I can still..” Linda walked right through me and into the bedroom. She let out a small gasp when she saw the corpse, then started making phone calls. Over the following days, I accompanied my body to the morgue. I attended my little memorial session at the university, made note of which of my former colleagues didn’t bother to show up. I went to my funeral. At the wake, I stood with my estranged wife and grown children, who mostly remained none the wiser—except when they talked about how eerie it was, how it felt like I was still there with them. Or maybe I’d say something, and get no response from my family, but then five minutes later their conversation would mysteriously veer toward the topic I’d broached. It seemed that I still had full input from the world of the living, but that my only output channel was doing spooky haunted things that still maintained plausible deniability about my existence. Questions flooded my mind: were there other ghosts? Why was I in this purgatory … or whatever it was? Would I be here forever? And: what was that column of yellow stars in the left of my visual field, the stars that followed me everywhere? Once it seemed clear that I was here to stay, for some definition of “here,” I figured I might as well do the same stuff that filled my waking hours when I was alive. I pulled up a chair and sat at my laptop. I hit up The Washington Post, The Onion, xkcd, SMBC Comics, Slate Star Codex. They all worked fine. Then I switched to the Gmail tab. Hundreds of new messages. Former students asking for recommendation letters, prospective students wanting to work with me, grant managers howling about overdue progress reports, none of them bothering to check if I was dead. I replied to one randomly-chosen email: Dear Ashish, Thanks for your interest in joining our group. Alas, I’m currently dead and walking the earth as a translucent wraith. For that reason, I’m unable to take on new PhD students at this time. Best of luck! –Bob I clicked “Send” and—part of me was expecting this—got an error. Message not sent. Email couldn’t cross the barrier from the dead to the living: too obvious. Next I opened my “Starred” folder. I was greeted by 779 starred messages: each one a pressing matter that I’d promised myself I’d get to while alive but didn’t. Dear Bob, Hope you’re well. I think I’ve found another error in your 2002 paper ‘Cache-Oblivious Approximation Algorithms for Sparse Linear Algebra on Big Data.’ Specifically, in the proof of Lemma 4.2, you assume a spectral bound [har har, spectral], even though your earlier definition of the matrix A_i seems to allow arbitrary norm… I chuckled. Well, I did spend most of my life on this stuff, didn’t I? Shouldn’t I sort this out, just for the sake of my intellectual conscience? I opened up my old paper in Ghostview (what else?) and found the offending lemma. Then I took out pen and paper—they worked, luckily, although presumably my scribblings remained invisible to the living—and set to work. After an hour, I’d satisfied myself that the alleged error was nothing too serious, just a gap requiring a few sentences of clarification. I sadly had no direct way to tell my years-ago correspondent that, assuming the correspondent was still even alive and research-active and at the same email address. But still: good for my peace of mind, right? Then something happened: the first intimation of what my life, or rather undeath, was to consist of from then on. Faintly but unmistakably, one of the tiny yellow stars in the left of my visual field became a blue-gray outline. It was no longer filled with yellow. Excitedly, I clicked through more starred emails. Some I saw no easy way to deal with. But every time I could satisfy myself that an email was no longer relevant—whether it was an invitation to a long-ago workshop, a grant that I never applied for, a proposed research collaboration rendered moot by subsequent work—one of those yellow stars in my visual field lost its yellow filling. Before long there were ten blue-gray outline stars, then twenty. One day, while I invisibly attended an old haunt (har har)—the weekly faculty lunch in my former department—I encountered a fellow ghost: a former senior colleague of mine, who’d died twenty years prior. He and I got to talking. For the most part, my fellow specter confirmed what I’d already guessed. Yes, in some long-ago past, purgatory no doubt had a different character. Yes, it’s no doubt different for others, who lived different lives and faced different psychic burdens. For us, though, for the faculty, purgatory is neither more nor less than the place where you must reply to every last email that was still starred “important” when you died. In the afterlife, it turns out, it doesn’t matter how “virtuous” you were, unless altruism happens to have been your obsession while alive. What matters is just that you free yourself from whatever burdened you every night when you went to sleep, that you finish what you started. Those unable to do so remain ghosts forever. “So,” I asked the other polter-guest at the faculty lunch, “how long does it take a professor to finish answering a lifetime’s worth of emails?” “Depends. I’ve been doing it for twenty years. Hoping to finish in twenty more.” “I see. And when you’ve dealt with the last email, what then?” “You pass to another place. None of us know exactly where. But”—and here his voice dropped to a whisper, as if anyone else present could hear ghosts—“it’s said to be a place of breathtaking tranquility. Where researchers like us wear flowing robes, and sit under olive trees, and contemplate truth and beauty with Plato and Euclid, and then go out for lunch buffet. Where there’s no email, no deadlines, no journals, no grant applications, no responsibilities but one: to explore whatever has captured your curiosity in the present moment. Some call it the Paradise of Productivity.” “Does everyone have to pass through purgatory first, before they go there?” “It’s said that, among all the computer scientists who’ve lived, only Alan Turing went straight to Paradise. And he died before email was even invented. When his time comes, Donald Knuth might also escape purgatory, since he forswore email in 1990. But Knuth, alas, might spend tens of thousands of years in a different purgatory, finishing Volume 4 of The Art of Computer Programming. “As for the rest of us, we all spend more or less time here with our wretched emails—for most of us, more. For one computer scientist—an Umesh Vazi-something, I believe, from Berkeley—it’s rumored that when he enters this place, even a trillion years won’t suffice to leave it. It’s said that the Sun will swallow the Earth, the night sky will go dark, and yet there Umesh will be, still clearing his inbox.” After a few years, I’d knocked off all the easy stuff in my Starred folder. Then, alas, I was left with missives like this: Hey, earth to Bob! The rest of us have done our part in writing up the paper. We’re all waiting on you to integrate the TeX files, and to craft an introduction explaining why anyone cared about the problem in the first place. Also, would you mind making a detailed pass through Sections 4.3 and 5.2? Ugh. There were so many slightly different TeX files. Which were the most recent? This could take a while. Nevertheless, after weeks of … ghosting on the project, I got to work revising the paper. There was, of course, the practical difficulty that I couldn’t directly communicate my edits back to the world of the living. Fortunately, I could still do haunted stuff. One day, for example, one of my former coauthors opened her old TeX file, and “discovered” that I’d actually done way more work on the paper while I was alive than anyone remembered I had. The mysteries of when exactly I did that work, and why no one knew about it at the time, were never satisfactorily resolved. Finally, after fourteen years, I’d succeeded in putting to rest 731 of my 779 starred emails. In the corner of my visual field was a vast array of blue-gray stars—but still, ominously, 48 yellow stars scattered among them. “God in Heaven!” I cried. “Whoever you are! I can’t handle any of the remaining starred emails, and thereby pass to the Paradise of Productivity, without sending replies back into the world of the living. Please, I beg you: let me breach this metaphysical wall.” A booming voice came down from on high. “YEA, BOB, WHAT THOU REQUESTETH IS POSSIBLE. THOU WOULDST NOT EVEN BE THE FIRST GHOUL FOR WHOM I WOULDST GRANTETH THIS REQUEST: FAR FROM IT. BUT I MUST WARN THEE: BREACHING THE WALL BETWEEN LIVING AND DEAD WILL BRINGETH FRUITS THAT THOU MAYST NOT LIKE.” “I think I’ll take my chances with those fruits.” “VERY WELL,” said God. And that’s how it is that, half a century after my death, I remain in purgatory still, my days now filled with missives like the following: Dear Bob, Thanks for the reply! I’m sorry to hear that you’re now a ghost condemned to answer emails before he can pass to the next world. My sympathies. Having said that, I have to confess that I still don’t understand Section 4.2 of your paper. When you get a chance, could you please clarify? I’ve cc’ed my coauthors, who might have additional followup questions. Note: To anyone who emailed me lately, I apologize for the delay in replying. I was writing this story. –SA ## Quickies December 4th, 2017 Updates (Dec. 5): The US Supreme Court has upheld Trump’s latest travel ban. I’m grateful to all the lawyers who have thrown themselves in front of the train of fascism, desperately trying to slow it down—but I could never, ever have been a lawyer myself. Law is fundamentally a make-believe discipline. Sure, there are times when it involves reason and justice, possibly even resembles mathematics—but then there are times when the only legally correct thing to say is, “I guess that, contrary to what I thought, the Establishment Clause of the First Amendment does let you run for president promising to discriminate against a particular religious group, and then find a pretext under which to do it. The people with the power to decide that question have decided it.” I imagine that I’d last about half a day before tearing up my law-school diploma in disgust, which is surely a personality flaw on my part. In happier news, many of you may have seen that papers by the groups of Chris Monroe and of Misha Lukin, reporting ~50-qubit experiments with trapped ions and optical lattices respectively, have been published back-to-back in Nature. (See here and here for popular summaries.) As far as I can tell, these papers represent an important step along the road to a clear quantum supremacy demonstration. Ideally, one wants a device to solve a well-defined computational problem (possibly a sampling problem), and also highly-optimized classical algorithms for solving the same problem and for simulating the device, which both let one benchmark the device’s performance and verify that the device is solving the problem correctly. But in a curious convergence, the Monroe group and Lukin group work suggests that this can probably be achieved with trapped ions and/or optical lattices at around the same time that Google and IBM are closing in on the goal with superconducting circuits. As everyone knows, the flaming garbage fire of a tax bill has passed the Senate, thanks to the spinelessness of John McCain, Lisa Murkowski, Susan Collins, and Jeff Flake. The fate of American higher education will now be decided behind closed doors, in the technical process of “reconciling” the House bill (which includes the crippling new tax on PhD students) with the Senate bill (which doesn’t—that one merely guts a hundred other things). It’s hard to imagine that this particular line item will occassion more than about 30 seconds of discussion. But, I dunno, maybe calling your Senator or Representative could help. Me, I left a voicemail message with the office of Texas Senator Ted Cruz, one that I’m confident Cruz and his staff will carefully consider. Here’s talk show host Seth Meyers (scroll to 5:00-5:20): “By 2027, half of all US households would pay more in taxes [under the new bill]. Oh my god. Cutting taxes was the one thing Republicans were supposed to be good at. What’s even the point of voting for a Republican if they’re going to raise your taxes? That’s like tuning in to The Kardashians only to see Courtney giving a TED talk on quantum computing.” Speaking of which, you can listen to an interview with me about quantum computing, on a podcast called Data Skeptic. We discuss the basics and then the potential for quantum machine learning algorithms. I got profoundly annoyed by an article called The Impossibility of Intelligence Explosion by François Chollet. Citing the “No Free Lunch Theorem”—i.e., the (trivial) statement that you can’t outperform brute-force search on random instances of an optimization problem—to claim anything useful about the limits of AI, is not a promising sign. In this case, Chollet then goes on to argue that most intelligence doesn’t reside in individuals but rather in culture; that there are hard limits to intelligence and to its usefulness; that we know of those limits because people with stratospheric intelligence don’t achieve correspondingly extraordinary results in life [von Neumann? Newton? Einstein? –ed.]; and finally, that recursively self-improving intelligence is impossible because we, humans, don’t recursively improve ourselves. Scattered throughout the essay are some valuable critiques, but nothing comes anywhere close to establishing the impossibility advertised in the title. Like, there’s a standard in CS for what it takes to show something’s impossible, and Chollet doesn’t even reach the same galaxy as that standard. The certainty that he exudes strikes me as wholly unwarranted, just as much as (say) the near-certainty of a Ray Kurzweil on the other side. I suppose this is as good a place as any to say that my views on AI risk have evolved. A decade ago, it was far from obvious that known methods like deep learning and reinforcement learning, merely run with much faster computers and on much bigger datasets, would work as spectacularly well as they’ve turned out to work, on such a wide variety of problems, including beating all humans at Go without needing to be trained on any human game. But now that we know these things, I think intellectual honesty requires updating on them. And indeed, when I talk to the AI researchers whose expertise I trust the most, many, though not all, have updated in the direction of “maybe we should start worrying.” (Related: Eliezer Yudkowsky’s There’s No Fire Alarm for Artificial General Intelligence.) Who knows how much of the human cognitive fortress might fall to a few more orders of magnitude in processing power? I don’t—not in the sense of “I basically know but am being coy,” but really in the sense of not knowing. To be clear, I still think that by far the most urgent challenges facing humanity are things like: resisting Trump and the other forces of authoritarianism, slowing down and responding to climate change and ocean acidification, preventing a nuclear war, preserving what’s left of Enlightenment norms. But I no longer put AI too far behind that other stuff. If civilization manages not to destroy itself over the next century—a huge “if”—I now think it’s plausible that we’ll eventually confront questions about intelligences greater than ours: do we want to create them? Can we even prevent their creation? If they arise, can we ensure that they’ll show us more regard than we show chimps? And while I don’t know how much we can say about such questions that’s useful, without way more experience with powerful AI than we have now, I’m glad that a few people are at least trying to say things. But one more point: given the way civilization seems to be headed, I’m actually mildly in favor of superintelligences coming into being sooner rather than later. Like, given the choice between a hypothetical paperclip maximizer destroying the galaxy, versus a delusional autocrat burning civilization to the ground while his supporters cheer him on and his opponents fight amongst themselves, I’m just about ready to take my chances with the AI. Sure, superintelligence is scary, but superstupidity has already been given its chance and been found wanting. Speaking of superintelligences, I strongly recommend an interview of Ed Witten by Quanta magazine’s Natalie Wolchover: one of the best interviews of Witten I’ve read. Some of Witten’s prouncements still tend toward the oracular—i.e., we’re uncovering facets of a magnificent new theoretical structure, but it’s almost impossible to say anything definite about it, because we’re still missing too many pieces—but in this interview, Witten does stick his neck out in some interesting ways. In particular, he speculates (as Einstein also did, late in life) about whether physics should be reformulated without any continuous quantities. And he reveals that he’s recently been rereading Wheeler’s old “It from Bit” essay, because: “I’m trying to learn about what people are trying to say with the phrase ‘it from qubit.'” I’m happy to report that a group based mostly in Rome has carried out the first experimental demonstration of PAC-learning of quantum states, applying my 2006 “Quantum Occam’s Razor Theorem” to reconstruct optical states of up to 6 qubits. Better yet, they insisted on adding me to their paper! I was at Cornell all of last week to give the Messenger Lectures: six talks in all (!!), if you include the informal talks that I gave at student houses (including Telluride House, where I lived as a Cornell undergrad from 1998 to 2000). The subjects were my usual beat (quantum computing, quantum supremacy, learnability of quantum states, firewalls and AdS/CFT, big numbers). Intimidatingly, the Messenger Lectures are the series in which Richard Feynman presented The Character of Physical Law in 1964, and in which many others (Eddington, Oppenheimer, Pauling, Weinberg, …) set a standard that my crass humor couldn’t live up to in a trillion years. Nevertheless, thanks so much to Paul Ginsparg for hosting my visit, and for making it both intellectually stimulating and a trip down memory lane, with meetings with many of the professors from way back when who helped to shape my thinking, including Bart Selman, Jon Kleinberg, and Lillian Lee. Cornell is much as I remember it from half a lifetime ago, except that they must’ve made the slopes twice as steep, since I don’t recall so much huffing and puffing on my way to class each morning. At one of the dinners, my hosts asked me about the challenges of writing a blog when people on social media might vilify you for what you say. I remarked that it hasn’t been too bad lately—indeed that these days, to whatever extent I write anything ‘controversial,’ mostly it’s just inveighing against Trump. “But that is scary!” someone remarked. “You live in Texas now! What if someone with a gun got angry at you?” I replied that the prospect of enraging such a person doesn’t really keep me awake at night, because it seems like the worst they could do would be to shoot me. By contrast, if I write something that angers leftists, they can do something far scarier: they can make me feel guilty! I’ll be giving a CS colloquium at Georgia Tech today, then attending workshops in Princeton and NYC the rest of the week, so my commenting might be lighter than usual … but yours need not be. ## The destruction of graduate education in the United States November 17th, 2017 If and when you emerged from your happiness bubble to read the news, you’ll have seen (at least if you live in the US) that the cruel and reckless tax bill has passed the House of Representatives, and remains only to be reconciled with an equally-vicious Senate bill and then voted on by the Republican-controlled Senate. The bill will add about$1.7 trillion to the national debt and raise taxes for about 47.5 million people, all in order to deliver a massive windfall to corporations, and to wealthy estates that already pay some of the lowest taxes in the developed world.

In a still-functioning democracy, those of us against such a policy would have an intellectual obligation to seek out the strongest arguments in favor of the policy and try to refute them.  By now, though, it seems to me that the Republicans hold the public in such contempt, and are so sure of the power of gerrymandering and voter restrictions to protect themselves from consequences, that they didn’t even bother to bring anything to the debate more substantive than the schoolyard bully’s “stop punching yourself.”  I guess some of them still repeat the fairytale about the purpose of tax cuts for the super-rich being to trickle down and help everyone else—but can even they advance that “theory” anymore without stifling giggles?  Mostly, as far as I can tell, they just brazenly deny that they’re doing what they obviously are doing: i.e., gleefully setting on fire anything that anyone, regardless of their ideology, could recognize as the national interest, in order to enrich a small core of supporters.

But none of that is what interests me in this post—because it’s “merely” as bad as, and no worse than, what one knew to expect when a coalition of thugs, kleptocrats, and white-nationalist demagogues seized control of Hamilton’s and Jefferson’s experiment.  My concern here is only with the “kill shot” that the Republicans have now aimed, with terrifying precision, at the system that’s kept American academic science the envy of the world in spite of the growing dysfunction all around it.

As you’ve probably heard, one of the ways Republicans intend to pay for their tax giveaway, is to change the tax code so that graduate students will now need to pay taxes on “tuition”—a large sum of money (as much as $50,000/year) that PhD students never actually see, that can easily exceed the stipends they do see, and that’s basically just an accounting trick that serves the internal needs of universities and granting agencies. Again, to eliminate any chance of misunderstanding: PhD students, who are effectively low-wage employees, already pay taxes on their actual stipends. The new proposal is that they’ll also have to pay taxes on a whopping, make-believe “X” on their payroll sheet that’s always exactly balanced out by “-X.” For detailed analyses of the impacts, see, e.g. Luca Trevisan’s post or Inside Higher Ed or the Chronicle of Higher Ed or Vox or NPR. Briefly, though, the proposal would raise taxes by a few thousand dollars per year, or in some cases as much as$10,000 per year (!), on PhD students who already live hand-to-mouth-to-ramen-bowl, with the largest impact falling on students in STEM fields.  For many students who aren’t independently wealthy, this could push a PhD beyond the realm of affordability, and cause them to leave academia or to do their graduate work in other countries.

“But isn’t there some workaround?”  Indeed, financial ignoramus that I am, my first reaction was to ask: if PhD tuition is basically an accounting fiction anyway, then why can’t the universities just declare that the tuition in question no longer exists, or is now zero dollars?  Feel free to explain further in the comments if you understand this stuff, but as far as I can tell, the answer is: because PhD tuition is used to calculate how much “tax” the universities can take from professors’ grant money.  If universities could no longer take that tax, and they had no other way to make up for it, then except for the richest few universities, they’d have to scale back research and teaching pretty drastically.  To avoid that outcome, the universities would be relying on the granting agencies to let them keep taking the overhead they needed to operate, even though the “PhD tuition” no longer existed.  But the granting agencies aren’t set up for this: you can’t just throw a bomb into one part of a complicated bureaucratic machine built up over decades, and expect the machine to continue working with no disruption to science.

But more ominously: as my friend Daniel Harlow and many others pointed out, it’s hard to look at the indefensible, laser-specific meanness of this policy, without suspecting that for many in Congress, the destruction of American higher education isn’t a regrettable byproduct, but the goal—just another piece of red meat to throw to the base.  If so, then we’d expect Congress to direct federal granting agencies not to loosen their rules about overhead, thereby forcing the students to pay the tax, and achieving the desired destruction.  (Note that the Trump administration has already made tightening overhead rules—i.e., doing the exact opposite of what would be needed to counteract the new tax—a central focus of its attempt to cut federal research funding.)

OK, two concluding thoughts:

1. When Republicans in Congress defended Trump’s travel ban, they at least had the craven excuse that they were only following the lead of the populist strongman who’d taken over their party.  Here they don’t even have that.  As far as I know, this targeted destruction of American higher education was Congress’s initiative, not Trump’s—which to me, underscores again the feather-thinness of any moral distinction between the Vichy GOP leadership and the administration with which it collaborates.  Trump didn’t emerge from nowhere.  It took decades of effort—George W. Bush, Sarah Palin, Karl Rove, Rush Limbaugh, Mitch McConnell, and all the rest—to transform the GOP into the pure seething cauldron of anti-intellectual resentment and hatred that we know today.
2. Given the existential risk to American higher education, why didn’t I blog about this earlier?  The answer is embarrassing to admit, and reflects no credit on me.  It’s simply that I didn’t believe it—even given all the other stuff that could “never happen in the US,” until it happened this past year.  I didn’t believe it, not because it was too far from me but because it was too close—because if true, it would mean the crippling of the research world in which I’ve spent most of my life since age 15, so therefore it couldn’t be true.  Surely even the House Republicans would realize they’d screwed up this time, and would take out this crazy provision before the full bill was voted on?  Or surely there’s some workaround that makes the whole thing less awful than it sounds?  There has to be … right?

Anyway, what else is there to say, except to call your representative, if you’re American and still have the faith in the system that such an act implies.

## Review of “Inadequate Equilibria,” by Eliezer Yudkowsky

November 16th, 2017

Inadequate Equilibria: Where and How Civilizations Get Stuck is a little gem of a book: wise, funny, and best of all useful (and just made available for free on the web).  Eliezer Yudkowsky and I haven’t always agreed about everything, but on the subject of bureaucracies and how they fail, his insights are gold.  This book is one of the finest things he’s written.  It helped me reflect on my own choices in life, and it will help you reflect on yours.

The book is a 120-page meditation on a question that’s obsessed me as much as it’s obsessed Yudkowsky.  Namely: when, if ever, is it rationally justifiable to act as if you know better than our civilization’s “leading experts”?  And if you go that route, then how do you answer the voices—not least, the voices in your own head—that call you arrogant, hubristic, even a potential crackpot?

Yudkowsky gives a nuanced answer.  To summarize, he argues that contrarianism usually won’t work if your goal is to outcompete many other actors in a free market for a scarce resource that they all want too, like money or status or fame.  In those situations, you really should ask yourself why, if your idea is so wonderful, it’s not already being implemented.  On the other hand, contrarianism can make sense when the “authoritative institutions” of a given field have screwed-up incentives that prevent them from adopting sensible policies—when even many of the actual experts might know that you’re right, but something prevents them from acting on their knowledge.  So for example, if a random blogger offers a detailed argument for why the Bank of Japan is pursuing an insane fiscal policy, it’s a-priori plausible that the random blogger could be right and the Bank of Japan could be wrong (as actually happened in a case Yudkowsky recounts), since even insiders who knew the blogger was right would find it difficult to act on their knowledge.  The same wouldn’t be true if the random blogger said that IBM stock was mispriced or that P≠NP is easy to prove.

The high point of the book is a 50-page dialogue between two humans and an extraterrestrial visitor.  The extraterrestrial is confused about a single point: why are thousands of babies in the United States dying every year, or suffering permanent brain damage, because (this seems actually to be true…) the FDA won’t approve an intravenous baby food with the right mix of fats in it?  Just to answer that one question, the humans end up having to take the alien on a horror tour through what’s broken all across the modern world, from politicians to voters to journalists to granting agencies, explaining Nash equilibrium after Nash equilibrium that leaves everybody worse off but that no one can unilaterally break out of.

I do have two criticisms of the book, both relatively minor compared to what I loved about it.

First, Yudkowsky is brilliant in explaining how institutions can produce terrible outcomes even when all the individuals in them are smart and well-intentioned—but he doesn’t address the question of whether we even need to invoke those mechanisms for more than a small minority of cases.  In my own experience struggling against bureaucracies that made life hellish for no reason, I’d say that about 2/3 of the time my quest for answers really did terminate at an identifiable “empty skull”: i.e., a single individual who could unilaterally solve the problem at no cost to anyone, but chose not to.  It simply wasn’t the case, I don’t think, that I would’ve been equally obstinate in the bureaucrat’s place, or that any of my friends or colleagues would’ve been.  I simply had to accept that I was now face-to-face with an alien sub-intelligence—i.e., with a mind that fetishized rules made up by not-very-thoughtful humans over demonstrable realities of the external world.

Second, I think the quality of the book noticeably declines in the last third.  Here Yudkowsky recounts conversations in which he tried to give people advice, but he redacts all the object-level details of the conversations—so the reader is left thinking that this advice would be good for some possible values of the missing details, and terrible for other possible values!  So then it’s hard to take away much of value.

In more detail, Yudkowsky writes:

“If you want to use experiment to show that a certain theory or methodology fails, you need to give advocates of the theory/methodology a chance to say beforehand what they think they predict, so the prediction is on the record and neither side can move the goalposts.”

I only partly agree with this statement (which might be my first substantive disagreement in the book…).

Yes, the advocates should be given a chance to say what they think the theory predicts, but then their answer need not be taken as dispositive.  For if the advocates are taken to have ultimate say over what their theory predicts, then they have almost unlimited room to twist themselves in pretzels to explain why, yes, we all know this particular experiment will probably yield such-and-such result, but contrary to appearances it won’t affect the theory at all.  For science to work, theories need to have a certain autonomy from their creators and advocates—to be “rigid,” as David Deutsch puts it—so that anyone can see what they predict, and the advocates don’t need to be continually consulted about it.  Of course this needs to be balanced, in practice, against the fact that the advocates probably understand how to use the theory better than anyone else, but it’s a real consideration as well.

In one conversation, Yudkowsky presents himself as telling startup founders not to bother putting their prototype in front of users, until they have a testable hypothesis that can be confirmed or ruled out by the users’ reactions.  I confess to more sympathy here with the startup founders than with Yudkowsky.  It does seem like an excellent idea to get a product in front of users as early as possible, and to observe their reactions to it: crucially, not just a binary answer (do they like the product or not), confirming or refuting a prediction, but more importantly, reactions that you hadn’t even thought to ask about.  (E.g., that the cool features of your website never even enter into the assessment of it, because people can’t figure out how to create an account, or some such.)

More broadly, I’d stress the value of the exploratory phase in science—the phase where you just play around with your system and see what happens, without necessarily knowing yet what hypothesis you want to test.  Indeed, this phase is often what leads to formulating a testable hypothesis.

But let me step back from these quibbles, to address something more interesting: what can I, personally, take from Inadequate Equilibria?  Is academic theoretical computer science broken/inadequate in the same way a lot of other institutions are?  Well, it seems to me that we have some built-in advantages that keep us from being as broken as we might otherwise be.  For one thing, we’re overflowing with well-defined problems, which anyone, including a total outsider, can get credit for solving.  (Of course, the “outsider” might not retain that status for long.)  For another, we have no Institutional Review Boards and don’t need any expensive equipment, so the cost to enter the field is close to zero.  Still, we could clearly be doing better: why didn’t we invent Bitcoin?  Why didn’t we invent quantum computing?  (We did lay some of the intellectual foundations for both of them, but why did it take people outside TCS to go the distance?)  Do we value mathematical pyrotechnics too highly compared to simple but revolutionary insights?  It’s worth noting that a whole conference, Innovations in Theoretical Computer Science, was explicitly founded to try to address that problem—but while ITCS is a lovely conference that I’ve happily participated in, it doesn’t seem to have succeeded at changing community norms much.  Instead, ITCS itself converged to look a lot like the rest of the field.

Now for a still more pointed question: am I, personally, too conformist or status-conscious?  I think even “conformist” choices I’ve made, like staying in academia, can be defended as the right ones for what I wanted to do with my life, just as Eliezer’s non-conformist choices (e.g., dropping out of high school) can be defended as the right ones for what he wanted to do with his.  On the other hand, my acute awareness of social status, and when I lacked any—in contrast to what Eliezer calls his “status blindness,” something that I see as a tremendous gift—did indeed make my life unnecessarily miserable in all sorts of ways.

Anyway, go read Inadequate Equilibria, then venture into the world and look for some $20 bills laying on the street. And if you find any, come back and leave a comment on this post explaining where they are, so a conformist herd can follow you. ## The Karp-Lipton Advice Column November 15th, 2017 Today, Shtetl-Optimized is extremely lucky to have the special guest blogger poly: the ‘adviser’ in the computational complexity class P/poly (P with polynomial-sized advice string), defined by Richard Karp and Richard Lipton in 1982. As an adviser, poly is known for being infinitely wise and benevolent, but also for having a severe limitation: namely, she’s sensitive only to the length of her input, and not to any other information about it. Her name comes from the fact that her advice is polynomial-size, which is the problem that prevents her from simply listing the answers to every possible question in a gigantic lookup table, the way she’d like to. Without further ado, let’s see what advice poly is able to offer her respondents. Dear poly, When my husband and I first started dating, we were going at it like rabbits! Lately, though, he seems to have no interest in sex. That’s not normal for a guy, is it? What can I do to spice things up in the bedroom? Sincerely, Frustrated Wife Dear Frustrated Wife, Unfortunately, I don’t know exactly what your question is. All I was told is that the question was 221 characters long. But here’s something that might help: whenever you’re stuck in a rut, sometimes you can “shake things up” with the use of randomness. So, please accept, free of charge, the following string of 221 random bits: 111010100100010010101111110010111101011010001 000111100101000111111011101110100110000110100 0010010010000010110101100100100111000010110 111001011001111111101110100010000010100111000 0111101111001101001111101000001010110101101 Well, it’s not really “random,” since everyone else with a 221-character question would’ve gotten the exact same string. But it’s random enough for many practical purposes. I hope it helps you somehow … good luck! Sincerely, poly Dear poly, I’m a 29-year-old autistic male: a former software entrepreneur currently worth about$400 million, who now spends his time donating to malaria prevention and women’s rights in the developing world.  My issue is that I’ve never been on a date, or even kissed anyone.  I’m terrified to make an advance.  All I read in the news is an endless litany of male sexual misbehavior: Harvey Weinstein, Louis C. K., Leon Wieseltier, George H. W. Bush, Roy Moore, the current president (!), you name it.  And I’m consumed by the urge not to be a pig like those guys.  Like, obviously I’m no more likely to start stripping or masturbating or something in front of some woman I just met, than I am to morph into a koala bear.  But from reading Slate, Salon, Twitter, my Facebook news feed, and so forth, I’ve gotten the clear sense that there’s nothing I could do that modern social mores would deem appropriate and non-creepy—at least, not a guy like me, who wasn’t lucky enough to be born instinctively understanding these matters.  I’m grateful to society for enabling my success, and have no desire to break any of its written or unwritten rules.  But here I genuinely don’t know what society wants me to do.  I’m writing to you because I remember you from my undergrad CS classes—and you’re the only adviser I ever encountered whose advice could be trusted unconditionally.

Yours truly,
Sensitive Nerd

Dear Sensitive Nerd,

I see your that letter is 1369 characters long.  Based on that, here are a few things I can tell you that might be helpful:

• The Riemann Hypothesis is true.
• ZFC set theory is consistent.
• The polynomial hierarchy is contained in PP.

Write me a 3592-character letter the next time, and I’ll give you an even longer list of true mathematical statements!  (I actually know how to solve the halting problem—no joke!—but am condemned to drip, drip, drip out the solutions, a few per input length.)

But I confess: no sooner did I list these truths than I reflected that they, or even a longer list, might not help much with your problem, whatever it might have been.  It’s even possible to have a problem for which no amount of truth helps in solving it.  So, I dunno: maybe try not worrying so much, and write back to let me know if that helped?  (Not that I expect to understand your reply, or would be able to change any of my advice at this point even if I did.)

Good luck!
–poly

Dear poly,

c34;c’y9v3x

Sincerely,
Unhappy in Unary

Dear Unhappy in Unary,

Finally, someone who writes to me in a language I can understand!  Your question is 11 characters long.  I understand that to be a code expressing that you’re bankrupt, and are filing for Chapter 11 bankruptcy protection.  Financial insolvency isn’t easy for anyone.  But here’s some advice: put everything you have into Bitcoin, and sell out a year from now.  Unfortunately, I don’t know exactly when you’re writing to me, but at least at the time my responses were hardwired in, this was some damn good advice.

You’re welcome,
poly

poly’s polynomial-sized advice column is syndicated in newspapers nationwide, and can also be accessed by simply moving your tape head across your advice tape. You’re welcome to comment on this post, but I might respond only to the lengths of the comments, rather than anything else about them. –SA

November 3rd, 2017

(1) My TEDx talk from Dresden, entitled “What Quantum Computing Isn’t,” is finally up on YouTube.  For regular Shtetl-Optimized readers, there’s unlikely to be much that’s new here: it’s basically 15 minutes of my usual spiel, packaged for mass consumption.  But while it went over well with the live audience, right now the only comment on the video is—I quote—“uuuuuuuuuuuuuuu,” from user “imbatman8472.”  So if you feel so inclined, go over there, watch it, and try to start a more contentful discussion!  Thanks so much to Andrés Goens, and everyone else in Dresden, for inviting me there and hosting a great visit.

(2) On December 4-6, there’s going to be a new conference in Mountain View, called Q2B (Quantum Computing for Business).  There, if it interests you, you can hear about the embryonic QC industry, from some of the major players at Google, IBM, Microsoft, academia, and government, as well as some of the QC startups (like IonQ) that have blossomed over the last few years.  Oh yes, and D-Wave.  The keynote speaker will be John Preskill; Google’s John Martinis and IBM’s Jerry Chow will also be giving talks.  I regret that another commitment will prevent me from attending myself, but I hope to attend next year’s iteration.  (Full disclosure: I’m a scientific adviser to QC Ware, the firm that’s organizing the conference.)

(3) On October 24, the House Science Committee heard three hours of testimony—you can watch it all here—about the need for quantum information research and the danger of the US falling behind China.  In what I believe is my first entry in the Congressional record, I’m quoted (for something totally incidental) at 1:09.  John Preskill was mostly just delighted that the witness, Jim Kurose, referred to me as a “physicist.”

(4) For several years, people have been asking me whether Bitcoin is resistant against quantum attack.  Now there’s finally an expert analysis, by Aggarwal et al., that looks into exactly that question.  Two-sentence summary: the proof-of-work is probably fine, although Grover’s algorithm can of course be used against it, which might eventually necessitate adjusting the difficulty parameter to account for that, and/or migrating from a pure preimage search task to collision-finding, where my result with Yaoyun Shi showed that quantum computers offer “only” an n2/3 black-box speedup over classical computers, rather than a square-root speedup.  The scheme for signing the transactions, which is currently based on elliptic curve cryptography, is the real danger point, but again one could address that by migrating to a post-quantum signature scheme.  My main comment about the matter is that, if I’d invested in Bitcoin when I first learned about it, I’d be rich now.

(5) In the first significant victory for my plan to spend a whole sabbatical year just writing up unwritten papers, I’ve got a new paper out today: Shadow Tomography of Quantum States.  Comments extremely welcome!

## Grad students and postdocs and faculty sought

October 28th, 2017

I’m eagerly seeking PhD students and postdocs to join our Quantum Information Center at UT Austin, starting in Fall 2018.  We’re open to any theoretical aspects of quantum information, although if you wanted to work with me personally, then areas close to computer science would be the closest fit.  I’m also able to supervise PhD students in physics, but am not directly involved with admissions to the physics department: this is a discussion we would have after you were already admitted to UT.

I, along with my theoretical computer science colleagues at UT Austin, am also open to outstanding students and postdocs in classical complexity theory. My wife, Dana Moshkovitz, tells me that she and David Zuckerman in particular are looking for a postdoc in the areas of pseudorandomness and derandomization (and for PhD students as well).

If you want to apply to the UTCS PhD program, please visit here.  The deadline is December 15.  If you specify that you want to work on quantum computing and information, and/or with me, then I’ll be sure to see your application.  Emailing faculty at this stage doesn’t help; we won’t “estimate your chances” or even look at your qualifications until we can see all the applications together.

If you want to apply for a postdoc with me, here’s what to do:

• Email me introducing yourself (if I don’t already know you), and include your CV, your thesis (if you already have one), and up to 3 representative papers.  Do this even if you already emailed me before.
• Arrange for two recommendation letters to be emailed to me.

Let’s set a deadline for postdoc applications of, I dunno, December 15?

In addition to the above, I’m happy to announce that the UT CS department is looking to hire a new faculty member in quantum computing and information—most likely a junior person.  The UT physics department is also looking to hire quantum information faculty members, with a focus on a senior-level experimentalist right now.  If you’re interested in these opportunities, just email me; I can put you in touch with the relevant people.

All in all, this is shaping up to be the most exciting era for quantum computing and information in Austin since a group of UT students, postdocs, and faculty including David Deutsch, John Wheeler, Wojciech Zurek, Bill Wootters, and Ben Schumacher laid much of the intellectual foundation of the field in the late 1970s and early 1980s.  We hope you’ll join us.  Hook ’em Hadamards!

Unrelated Announcements: Avi Wigderson has released a remarkable 368-page book, Mathematics and Computation, for free on the web.  This document surveys pretty much the entire current scope of theoretical computer science, in a way only Avi, our field’s consummate generalist, could do.  It also sets out Avi’s vision for the future and his sociological thoughts about TCS and its interactions with neighboring fields.  I was a reviewer on the manuscript, and I recommend it to anyone looking for a panoramic view of TCS.

In other news, my UT friend and colleague Adam Klivans, and his student Surbhi Goel, have put out a preprint entitled Learning Depth-Three Neural Networks in Polynomial Time.  (Beware: what the machine learning community calls “depth three,” is what the TCS community would call “depth two.”)  This paper learns real-valued neural networks in the so-called p-concept model of Kearns and Schapire, and thereby evades a 2006 impossibility theorem of Klivans and Sherstov, which showed that efficiently learning depth-2 threshold circuits would require breaking cryptographic assumptions.  More broadly, there’s been a surge of work in the past couple years on explaining the success of deep learning methods (methods whose most recent high-profile victory was, of course, AlphaGo Zero).  I’m really hoping to learn more about this direction during my sabbatical this year—though I’ll try and take care not to become another deep learning zombie, chanting “artificial BRAINSSSS…” with outstretched arms.

## 2^n is exponential, but 2^50 is finite

October 22nd, 2017

Unrelated Update (Oct. 23) I still feel bad that there was no time for public questions at my “Theoretically Speaking” talk in Berkeley, and also that the lecture hall was too small to accomodate a large fraction of the people who showed up. So, if you’re someone who came there wanting to ask me something, go ahead and ask in the comments of this post.

During my whirlwind tour of the Bay Area, questions started pouring in about a preprint from a group mostly at IBM Yorktown Heights, entitled Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits.  In particular, does this paper make a mockery of everything the upcoming quantum supremacy experiments will try to achieve, and all the theorems about them that we’ve proved?

Following my usual practice, let me paste the abstract here, so that we have the authors’ words in front of us, rather than what a friend of a friend said a popular article reported might have been in the paper.

With the current rate of progress in quantum computing technologies, 50-qubit systems will soon become a reality.  To assess, refine and advance the design and control of these devices, one needs a means to test and evaluate their fidelity. This in turn requires the capability of computing ideal quantum state amplitudes for devices of such sizes and larger.  In this study, we present a new approach for this task that significantly extends the boundaries of what can be classically computed.  We demonstrate our method by presenting results obtained from a calculation of the complete set of output amplitudes of a universal random circuit with depth 27 in a 2D lattice of 7 × 7 qubits.  We further present results obtained by calculating an arbitrarily selected slice of 237 amplitudes of a universal random circuit with depth 23 in a 2D lattice of 8×7 qubits.  Such calculations were previously thought to be impossible due to impracticable memory requirements. Using the methods presented in this paper, the above simulations required 4.5 and 3.0 TB of memory, respectively, to store calculations, which is well within the limits of existing classical computers.

This is an excellent paper, which sets a new record for the classical simulation of generic quantum circuits; I congratulate the authors for it.  Now, though, I want you to take a deep breath and repeat after me:

This paper does not undercut the rationale for quantum supremacy experiments.  The truth, ironically, is almost the opposite: it being possible to simulate 49-qubit circuits using a classical computer is a precondition for Google’s planned quantum supremacy experiment, because it’s the only way we know to check such an experiment’s results!  The goal, with sampling-based quantum supremacy, was always to target the “sweet spot,” which we estimated at around 50 qubits, where classical simulation is still possible, but it’s clearly orders of magnitude more expensive than doing the experiment itself.  If you like, the goal is to get as far as you can up the mountain of exponentiality, conditioned on people still being able to see you from the base.  Why?  Because you can.  Because it’s there.  Because it challenges those who think quantum computing will never scale: explain this, punks!  But there’s no point unless you can verify the result.

Related to that, the paper does not refute any prediction I made, by doing anything I claimed was impossible.  On the contrary (if you must know), the paper confirms something that I predicted would be possible.  People said: “40 qubits is the practical limit of what you can simulate, so there’s no point in Google or anyone else doing a supremacy experiment with 49 qubits, since they can never verify the results.”  I would shrug and say something like: “eh, if you can do 40 qubits, then I’m sure you can do 50.  It’s only a thousand times harder!”

So, how does the paper get up to 50 qubits?  A lot of computing power and a lot of clever tricks, one of which (the irony thickens…) came from a paper that I recently coauthored with Lijie Chen: Complexity-Theoretic Foundations of Quantum Supremacy Experiments.  Lijie and I were interested in the question: what’s the best way to simulate a quantum circuit with n qubits and m gates?  We noticed that there’s a time/space tradeoff here: you could just store the entire amplitude vector in memory and update, which would take exp(n) memory but also “only” about exp(n) time.  Or you could compute the amplitudes you cared about via Feynman sums (as in the proof of BQP⊆PSPACE), which takes only linear memory, but exp(m) time.  If you imagine, let’s say, n=50 and m=1000, then exp(n) might be practical if you’re IBM or Google, but exp(m) is certainly not.

So then we raised the question: could one get the best of both worlds?  That is, could one simulate such a quantum circuit using both linear memory and exp(n) time?  And we showed that this is almost possible: we gave an algorithm that uses linear memory and dO(n) time, where d is the circuit depth.  Furthermore, the more memory it has available, the faster our algorithm will run—until, in the limit of exponential memory, it just becomes the “store the whole amplitude vector” algorithm mentioned above.  I’m not sure why this algorithm wasn’t discovered earlier, especially since it basically just amounts to Savitch’s Theorem from complexity theory.  In any case, though, the IBM group used this idea among others to take full advantage of the RAM it had available.

Let me make one final remark: this little episode perfectly illustrates why theoretical computer scientists like to talk about polynomial vs. exponential rather than specific numbers.  If you keep your eyes on the asymptotic fundamentals, rather than every factor of 10 or 1000, then you’re not constantly shocked by events, like a dog turning its head for every passing squirrel.  Before you could simulate 40 qubits, now you can simulate 50.  Maybe with more cleverness you could get to 60 or even 70.  But … dude.  The problem is still exponential time.

We saw the same “SQUIRREL!  SQUIRREL!” reaction with the people who claimed that the wonderful paper by Clifford and Clifford had undercut the rationale for BosonSampling experiments, by showing how to solve the problem in “merely” ~2n time rather than ~mn, where n is the number of photons and m is the number of modes.  Of course, Arkhipov and I had never claimed more than ~2n hardness for the problem, and Clifford and Clifford’s important result had justified our conservatism on that point, but, y’know … SQUIRREL!

More broadly, it seems to me that this dynamic constantly occurs in the applied cryptography world.  OMIGOD a 128-bit hash function has been broken!  Big news!  OMIGOD a new, harder hash function has been designed!  Bigger news!  OMIGOD OMIGOD OMIGOD the new one was broken too!!  All of it fully predictable once you realize that we’re on the shores of an exponentially hard problem, and for some reason, refusing to go far enough out into the sea (i.e., pick large enough security parameters) that none of this back-and-forth would happen.

I apologize, sincerely, if I come off as too testy in this post.  No doubt it’s entirely the fault of a cognitive defect on my end, wherein ten separate people asking me about something get treated by my brain like a single person who still doesn’t get it even after I’ve explained it ten times.

## The problem with Uber

October 19th, 2017

I just spent a wonderful and exhausting five days in the Bay Area: meeting friends, holding the first-ever combined SlateStarCodex/Shtetl-Optimized meetup, touring quantum computing startups, meeting with Silicon Valley folks about quantum computing, and giving a public lecture for the Simons Institute in Berkeley.  I’ll probably say more about some of these events in future posts, but for now: thanks so much to everyone who helped them happen!

Alas, my experiences getting around the Bay this week convinced me that there’s a real problem with Uber.  And no, I’m not talking about their corporate culture, or the personality of ousted CEO Travis Kalanick, or the hardball lobbying of municipalities to allow ride-sharing, or the taxi companies needing to adapt to survive, or even Uber having an unsustainable business model (they could charge more and I’d still use it…).

The problem is: when you order an Uber, like 2/3 of the time you and the driver can’t find each other without a lot of back and forth.

Firstly, because you can’t specify where you are with enough accuracy.  When you try, the app does this thing where it literally moves the “you are here” pointer to a place where you’re not. And then, even if the little dot correctly indicates your location, for some reason the driver will think you’re somewhere totally different.

Secondly, because Uber cars are typically unmarked.  Yes, the app tells you that it’s a white Ford or whatever—but there’s a lot of white cars, and it’s hard (at least for me) to distinguish models at a distance, so you can then face a stressful “Where’s Waldo?” problem involving hundreds of cars.

Thirdly, because the drivers understandably have their phones mounted on their dashboards—the result being that, when you call to try to figure out where they are, nothing they say can be distinguished from “mmph hrmph mmph.”  And of course they can’t text while driving.

To be clear, these gripes arise only because ride-sharing apps generally work so damn well, and are such an advance over what preceded them, that they’ve changed our expectations about the convenience of getting from place to place.  Because of Uber and Lyft and so on, it’s tempting to plan your life around the assumption that you can be anywhere in a greater metro area, and within 3 minutes a car will magically arrive to take you to wherever else in that area you need to be—while your brain remains uncluttered with transportation logistics, among the most excruciating of all topics.  This is a problem borne of success.

But—good news, everyone!—I have an idea to solve the problem, which I hereby offer free of charge to any ride-sharing service that wants to adopt it.  Namely, when you order a ride, why doesn’t the app—with your explicit permission, of course—use your phone’s camera to send a selfie of you, together with the location where you’re waiting, to the driver?  Is there some obvious reason I’m missing why this wouldn’t work?  Have any ride-sharing companies tried it?  (I only learned today that I can update my Uber profile to include my photo.  Hopefully that will help drivers find me—but a photo of the intersection, or the side of the building where I am, etc. could help even more.)


text:
# Boolean algebras and free filters generated by chains

Suppose $\mathbf{B}$ is a complete Boolean algebra with an infinite domain $B$. Suppose $\mathbf{B}$ is atomic (i.e. every element is the supremum of some set of atoms). This algebra contains the co-finite filter $\mathscr{F}_c$, which in case the set of atoms of $\mathbf{B}$ is countable is generated by a chain. This follows from the fact that we may arrange all atoms in a sequence $a_0,a_1,\ldots$ and take: $$C:=\{B-\{a_0,\ldots,a_n\}\mid n\in\omega\}$$ as a chain that generates $\mathscr{F}_c$. It is known that no free ultrafilter in $\mathbf{B}$ is generated by a chain (see this answer).

In light of the above my first question is:

(1) If $\mathbf{B}$ has a countable set of atoms, can it contain a free filter which is different from $\mathscr{F}_c$ and which is generated by a chain?

Considering an uncountable case:

(2) If $\mathbf{B}$ is atomic with uncountably many atoms, is the co-finite filter $\mathscr{F}_c$ generated by a chain?
(3) If $\mathbf{B}$ is atomic with uncountably many atoms, can it contain a free filter which is different from $\mathscr{F}_c$ and which is generated by a chain?

For Q1, take the Boolean algebra of subsets of the rational numbers, and let the filter be generated by all of the nonempty final segments of $\mathbb Q$.

For Q3, repeat the preceding with the reals in place of the rationals. For other uncountable cardinals, repeat the preceding with the rationals and reals replaced by, for example, the initial ordinal of the desired cardinality.

For Q2, the answer is no, because any chain of cofinite sets is necessarily countable; it can't contain two distinct sets whose (finite) complements have the same cardinality.

The OP requested, in a comment, more details on Q2; I hope the following clarifies it sufficiently. Consider any chain $\mathcal C$ of cofinite sets. If $A$ and $B$ are distinct elements of $\mathcal C$, their complements are distinct finite sets, with one included in the other. So these complements have distinct, finite cardinalities. That is, the function assigning to each $A\in\mathcal C$ the cardinality of its complement is a one-to-one function from $\mathcal C$ to $\mathbb N$, and therefore $\mathcal C$ is countable. Each of the countably many elements $A\in\mathcal C$ omits only finitely many atoms, so only countably many atoms are omitted by any members of $\mathcal C$. Since there are uncountably many atoms altogether, let $a$ be one that is not omitted by any $A\in\mathcal C$. Then the complement of $a$ is in the cofinite filter but is not above any member of $\mathcal C$. Therefore, $\mathcal C$ fails to generate the cofinite filter.

• In countable and continuum case - is this a canonical method, in the sense that every free filter which is not co-finite and is generated by a chain must be generated by one of the aforementioned form? – Mad Hatter Oct 5 '15 at 12:26
• I think any example has to look at least somewhat similar to the ones I suggested. Given a chain $C$ that generates a filter on a set $X$, you can define a linear pre-order (like a linear order except that distinct elements cam be $\leq$ each other) by putting $x\leq y$ when every set in $C$ that contains $x$ also contain $y$. Then extend this pre-order relation to a linear order, and notice that all elements of $C$ are final segments. It might not, however, be the case that all final segments are in the filter generated by $C$. – Andreas Blass Oct 5 '15 at 12:34
• Just to clarify the method, for $\mathbb Q$ for example. For $S\subseteq\mathbb Q$, let $U(S)$ be the set of all its upper bounds, i.e. the final segment. So the free filter $\mathscr{F}$ generated by the set $\{U(S)\mid S\subseteq\mathbb Q\}$, right? Or am I misunderstanding something? – Mad Hatter Oct 5 '15 at 12:58
• What you wrote about $U(S)$ is correct, as long as $S$ is bounded above so $U(S)$ isn't empty. (I don't want the empty set to get into my filter.) An equivalent description, in the case of $\mathbb Q$, is that the filter is generated by sets of the form $\{x\in\mathbb Q:r<x\}$ or $\{x\in\mathbb Q:r\leq x\}$for arbitrary real numbers $r$. – Andreas Blass Oct 5 '15 at 19:15
• I"ve added some more details about Q2 to my answer. – Andreas Blass Mar 15 '16 at 23:48

format: plain


text:
• Magoosh
Study with Magoosh GMAT prep

Available with Beat the GMAT members only code

• Free Veritas GMAT Class
Experience Lesson 1 Live Free

Available with Beat the GMAT members only code

• 1 Hour Free
BEAT THE GMAT EXCLUSIVE

Available with Beat the GMAT members only code

• 5 Day FREE Trial
Study Smarter, Not Harder

Available with Beat the GMAT members only code

• Award-winning private GMAT tutoring
Register now and save up to $200 Available with Beat the GMAT members only code • Get 300+ Practice Questions 25 Video lessons and 6 Webinars for FREE Available with Beat the GMAT members only code • Free Practice Test & Review How would you score if you took the GMAT Available with Beat the GMAT members only code • 5-Day Free Trial 5-day free, full-access trial TTP Quant Available with Beat the GMAT members only code • FREE GMAT Exam Know how you'd score today for$0

Available with Beat the GMAT members only code

• Free Trial & Practice Exam
BEAT THE GMAT EXCLUSIVE

Available with Beat the GMAT members only code

# That vs those

#### That vs those

I have a lil confusion about the use of that

As per grammer, "that" is a relative prounoun and it can be singular as well as plural.

and in the following question :
Since 1986 enrollments of African Americans, American Indians, and Hispanic Americans in fulltime engineering programs in the United States has steadily increased, while the number of other students who enter the field has fallen.(A) has steadily increased, while the number of other students who enter the field has fallen
(B) has steadily increased, while other students entering the field have declined in number
(C) increased steadily, while there was a decline in the number of other students entering the field
(D) have steadily increased, while the number of other students entering the field has fallen
(E) have steadily increased, while that of other students who enter the field fell

The official explanation says : [E] - that should be the plural those

and in the following example:

"The peaks of a mountain range, acting like rocks in a streambed, produce ripples in the air flowing over them: the resulting flow pattern, with crests and toughs that remain stationary although the air that forms them is moving rapidly, are known as "standing waves."

that clearly refers to the compound subject which is plural and hence we correctly used remain

Pls explain where am i going wrong ?

Legendary Member
Joined
16 Apr 2008
Posted:
1159 messages
56
Target GMAT Score:
750+
Firstly,

An amazing question!!!

IMO:

in the first sentence:

That a relative pronoun is not used as a relative pronoun but as a demonstative pronoun

In demonstrative pronoun:

That ,with its plural those ,is used to avoid repetition of a preceding noun.

Eg:Our soldiers were better drilled than those of enemies.

(Source:Wren and martin)

Point to note:"That is used preferably with reference to persons"
(source :wren and martin)
(Though this point is not applicable over here. )

Secondly,
the tricky part of the second question is...

the resulting flow pattern(singular ) is joined(& tricked ) using the preposition with with plural compound word crests and toughs, is the object to which relative pronoun that is refering to...

thus the pronoun "that " is used in the second sentence...

i hope this helps!!!

thx

Senior | Next Rank: 100 Posts
Joined
01 Oct 2008
Posted:
35 messages
6
"That" can replace a noun in a comparison when the noun in the singular. "Those" can replace a noun in a comparison when the noun is plural.

_________________
700+ your target then check out my 800 gmat blog here:
https://800gmatblog.zoxic.com

### GMAT/MBA Expert

GMAT Instructor
Joined
03 Mar 2008
Posted:
3380 messages
Followed by:
1488 members
2256
GMAT Score:
800
Jatinder wrote:
I have a lil confusion about the use of that

As per grammer, "that" is a relative prounoun and it can be singular as well as plural.

and in the following question :
Since 1986 enrollments of African Americans, American Indians, and Hispanic Americans in fulltime engineering programs in the United States has steadily increased, while the number of other students who enter the field has fallen.(A) has steadily increased, while the number of other students who enter the field has fallen
(B) has steadily increased, while other students entering the field have declined in number
(C) increased steadily, while there was a decline in the number of other students entering the field
(D) have steadily increased, while the number of other students entering the field has fallen
(E) have steadily increased, while that of other students who enter the field fell

The official explanation says : [E] - that should be the plural those

and in the following example:

"The peaks of a mountain range, acting like rocks in a streambed, produce ripples in the air flowing over them: the resulting flow pattern, with crests and toughs that remain stationary although the air that forms them is moving rapidly, are known as "standing waves."

that clearly refers to the compound subject which is plural and hence we correctly used remain

Pls explain where am i going wrong ?
so, where are you actually going wrong?
you haven't actually listed any mistakes on your part.

the only things you've said so far are:
* "that" should be "those" in the first problem (pronoun that's part of a parallel construction - since it's parallel to a plural noun, it should be plural)
* "that" in the second problem is a relative pronoun referring to "crests and troughs", and should therefore be plural

you haven't actually given any indication that you were wrong about anything!

_________________
Ron has been teaching various standardized tests for 20 years.

--

Pueden hacerle preguntas a Ron en castellano
Potete chiedere domande a Ron in italiano
On peut poser des questions à Ron en français
Voit esittää kysymyksiä Ron:lle myös suomeksi

--

Quand on se sent bien dans un vêtement, tout peut arriver. Un bon vêtement, c'est un passeport pour le bonheur.

Yves Saint-Laurent

--

Free Manhattan Prep online events - The first class of every online Manhattan Prep course is free. Classes start every week.
Master | Next Rank: 500 Posts
Joined
30 Sep 2008
Posted:
280 messages
5
Target GMAT Score:
760
GMAT Score:
610
lunarpower wrote:
Jatinder wrote:
I have a lil confusion about the use of that

As per grammer, "that" is a relative prounoun and it can be singular as well as plural.

and in the following question :
Since 1986 enrollments of African Americans, American Indians, and Hispanic Americans in fulltime engineering programs in the United States has steadily increased, while the number of other students who enter the field has fallen.(A) has steadily increased, while the number of other students who enter the field has fallen
(B) has steadily increased, while other students entering the field have declined in number
(C) increased steadily, while there was a decline in the number of other students entering the field
(D) have steadily increased, while the number of other students entering the field has fallen
(E) have steadily increased, while that of other students who enter the field fell

The official explanation says : [E] - that should be the plural those and in the following example:

"The peaks of a mountain range, acting like rocks in a streambed, produce ripples in the air flowing over them: the resulting flow pattern, with crests and toughs that remain stationary although the air that forms them is moving rapidly, are known as "standing waves."

that clearly refers to the compound subject which is plural and hence we correctly used remain

Pls explain where am i going wrong ?
so, where are you actually going wrong?
you haven't actually listed any mistakes on your part.

the only things you've said so far are:
* "that" should be "those" in the first problem (pronoun that's part of a parallel construction - since it's parallel to a plural noun, it should be plural)
* "that" in the second problem is a relative pronoun referring to "crests and troughs", and should therefore be plural

you haven't actually given any indication that you were wrong about anything!

Question is: if that can refer to singular and plural then why the official explanation says that should be those ?

Legendary Member
Joined
27 Aug 2008
Posted:
1035 messages
Followed by:
1 members
104
1) we need those for the option E in the first sentence, those refers to the enrollments which is plural. it is used to substitute for the enrollments

2) when we use crests and trough that remain stationary we are actually modifying the crests and trough, that here is a restrictive clause and not a pronoun to substitute for the crests and trough. if one used those here it wouldnt make sense

### GMAT/MBA Expert

GMAT Instructor
Joined
03 Mar 2008
Posted:
3380 messages
Followed by:
1488 members
2256
GMAT Score:
800
Jatinder wrote:
Question is: if that can refer to singular and plural then why the official explanation says that should be those ?
the word that is being used in two different ways in the two sentences.

in the first sentence, it's being used as what's called a demonstrative pronoun. if i were you, i wouldn't bother memorizing that term; rather, i would just memorize this:
when that is a PRONOUN that forms the second part of a PARALLEL CONSTRUCTION, it needs to match the number (singular / plural) of its counterpart in the first half of the parallel construction.
that's a bit verbose, but i trust that you can see what i'm talking about. in the referenced post, "those" is parallel to "enrollments", which is a plural noun; therefore, it must be plural.

in the second sentence, it's being used at what's called a relative pronoun. in this case, there's no parallel construction; rather, it's just a construction along the lines of "the car that was in my driveway."
try to make this construction with "those"; i think you'll agree that it's ridiculous.

_________________
Ron has been teaching various standardized tests for 20 years.

--

Pueden hacerle preguntas a Ron en castellano
Potete chiedere domande a Ron in italiano
On peut poser des questions à Ron en français
Voit esittää kysymyksiä Ron:lle myös suomeksi

--

Quand on se sent bien dans un vêtement, tout peut arriver. Un bon vêtement, c'est un passeport pour le bonheur.

Yves Saint-Laurent

--

Free Manhattan Prep online events - The first class of every online Manhattan Prep course is free. Classes start every week.
Master | Next Rank: 500 Posts
Joined
30 Sep 2008
Posted:
280 messages
5
Target GMAT Score:
760
GMAT Score:
610
Thanks Ron.
I understood now.

Master | Next Rank: 500 Posts
Joined
06 Mar 2009
Posted:
371 messages
27
Test Date:
dec-4-09
Target GMAT Score:
750
GMAT Score:
740
lunarpower wrote:
Jatinder wrote:
Question is: if that can refer to singular and plural then why the official explanation says that should be those ?
the word that is being used in two different ways in the two sentences.

in the first sentence, it's being used as what's called a demonstrative pronoun. if i were you, i wouldn't bother memorizing that term; rather, i would just memorize this:
when that is a PRONOUN that forms the second part of a PARALLEL CONSTRUCTION, it needs to match the number (singular / plural) of its counterpart in the first half of the parallel construction.
that's a bit verbose, but i trust that you can see what i'm talking about. in the referenced post, "those" is parallel to "enrollments", which is a plural noun; therefore, it must be plural.

in the second sentence, it's being used at what's called a relative pronoun. in this case, there's no parallel construction; rather, it's just a construction along the lines of "the car that was in my driveway."
try to make this construction with "those"; i think you'll agree that it's ridiculous.
Great explanation...and if we apply your logic(correct me if i am not applying it correctly) then I think Jatinder made a point when he said that choice E in the first question should have "Those" and not "That"...isn't it a parallel construction..??? and the pronoun should match in no.

### GMAT/MBA Expert

GMAT Instructor
Joined
03 Mar 2008
Posted:
3380 messages
Followed by:
1488 members
2256
GMAT Score:
800
2010gmat wrote:
Great explanation...and if we apply your logic(correct me if i am not applying it correctly) then I think Jatinder made a point when he said that choice E in the first question should have "Those" and not "That"...isn't it a parallel construction..??? and the pronoun should match in no.
if anything, yes, it should be "those" ... because it refers to the word "enrollments", which is plural.
under no circumstances can a singular pronoun stand for a plural noun, or vice versa.

maybe you're missing the fact that (e) is one of the wrong answers...?
note that there are other things wrong with (e), too; for instance, the verb tenses aren't parallel. the first clause uses the present perfect, while the second clause uses the simple past. since the two changes are concurrent, this mismatch is not acceptable.

the correct answer to that question is, presumably, (d). this is the only answer choice that contains proper subject-verb agreement (enrollments ... have) AND parallel verb tenses (has increased / has fallen).

_________________
Ron has been teaching various standardized tests for 20 years.

--

Pueden hacerle preguntas a Ron en castellano
Potete chiedere domande a Ron in italiano
On peut poser des questions à Ron en français
Voit esittää kysymyksiä Ron:lle myös suomeksi

--

Quand on se sent bien dans un vêtement, tout peut arriver. Un bon vêtement, c'est un passeport pour le bonheur.

Yves Saint-Laurent

--

Free Manhattan Prep online events - The first class of every online Manhattan Prep course is free. Classes start every week.
Newbie | Next Rank: 10 Posts
Joined
25 Jun 2018
Posted:
9 messages
Newbie | Next Rank: 10 Posts
Joined
13 Sep 2018
Posted:
2 messages
Quote:
"That" can replace a noun in a comparison when the noun in the singular. "Those" can replace a noun in a comparison when the noun is plural.
Thanks, I understand now!

### Top First Responders*

1 Jay@ManhattanReview 83 first replies
2 Brent@GMATPrepNow 68 first replies
3 fskilnik 55 first replies
4 GMATGuruNY 36 first replies
5 ceilidh.erickson 13 first replies
* Only counts replies to topics started in last 30 days
See More Top Beat The GMAT Members

### Most Active Experts

1 fskilnik

GMAT Teacher

199 posts
2 Brent@GMATPrepNow

GMAT Prep Now Teacher

160 posts
3 Scott@TargetTestPrep

Target Test Prep

109 posts
4 Jay@ManhattanReview

Manhattan Review

95 posts
5 GMATGuruNY

The Princeton Review Teacher

90 posts
See More Top Beat The GMAT Experts


text:
## Basic College Mathematics (10th Edition)

$\frac{2}{9}$
Divide $\frac{8}{9}$ by 4 which is the same as multiplying by $\frac{1}{4}$ $\frac{8}{9}\times\frac{1}{4} = \frac{2}{9}$


text:
If a square and a rhombus stand on the same base, then what would be the ratio of the area of square and rhombus?

457 views
If a square and a rhombus stand on the same base, then what would be the ratio of the area of square and rhombus?
posted Sep 29, 2015

Let the base of square and rhombus be a units . Square all sides equal ;;; Area of square=a^2;;

let the height of rhombus , i.e perpendicular distance from the top edge to the base be h units and included angle be x

then area of rhombus =a*h=a^2sinx

ratio = (a^2)/(a^2*sinx) === 1/sinx and since 0<x<90 ;; 0<sinx<1;;; the ratio will always be greater than 1 ,,,,

answer Sep 29, 2015

Similar Puzzles


text:
# Lesson 8

Conditional Probability

• Let’s examine conditional probability.

### 8.1: She Made Some Tarts

1. Noah will select 1 card at random from a standard deck of cards. Find the probabilities. Explain or show your reasoning.

1. $$P(\text{the card is a queen})$$
2. $$P(\text{the card is a heart})$$
3. $$P(\text{the card is a queen and heart})$$
2. Elena pulls out only the hearts from the deck and sets the rest of the cards aside. She shuffles the hearts and draws one card. What is the probability she gets a queen?

### 8.2: Under One Condition

Kiran notices that the probabilities from the warm-up can be arranged into at least two equations.

$$P(\text{the card is a queen and heart}) = P(\text{the card is a queen | the card is a heart}) \boldcdot P(\text{the card is a heart})$$ since $$\frac{1}{52} = \frac{1}{13} \boldcdot \frac{13}{52}$$

$$P(\text{the card is a queen and heart}) = P(\text{the card is a heart | the card is a queen}) \boldcdot P(\text{the card is a queen})$$ since $$\frac{1}{52} = \frac{1}{4} \boldcdot \frac{4}{52}$$.

Kiran wonders if it is always true that $$P(\text{A and B}) = P(\text{A | B}) \boldcdot P(B)$$ for events A and B. He wants to check additional examples from drawing a card from a deck.

1. If Event A is “the card is black” and Event B is “the card is a king,” does the equation hold? Explain or show your reasoning.
2. If Event A is “the card is a face card” and Event B is “the card is a spade,” does the equation hold? Explain or show your reasoning.

### 8.3: Coin and Cube

A coin is flipped, then a standard number cube is rolled. Let A represent the event “the coin lands showing heads” and B represent “the standard number cube lands showing 4.”

1. Are events A and B independent or dependent? Explain your reasoning.
2. Find the probabilities
1. $$P(\text{A})$$
2. $$P(\text{B})$$
3. $$P(\text{A | B})$$
4. $$P(\text{B | A})$$
3. Describe the meaning of the events “not A” and “not B” in this situation, then find the probabilities.
1. $$P(\text{A | not B})$$
2. $$P(\text{B | not A})$$
4. Are any of the probabilities the same? Is there a relationship between those situations? Explain your reasoning.

Students are writing programs in their robotics class using two different programming languages that are very similar. 70% of the programs are written in the first programming language and the other 30% percent are written in the second programming language. The newer robots only accept programs written in the first programming language and the older robots only accept programs written in the second programming language.

In this robotics class, Andre’s job is to determine which programming language each program is written in. He determines the programming language correctly 90% of the time for each of the programs. If Andre determines that a program is written in the second programming language, what is the probability that the program is actually written in the first programming language? Explain your reasoning.

### Summary

A conditional probability is the probability that one event occurs under the condition that another event occurs.

For example, we will remove two marbles from a jar that contains 3 green marbles, 2 blue marbles, 1 white marble, and 1 black marble. We might consider the conditional probability that the second marble we remove is green given that the first marble removed was green. The notation for this probability is $$P(\text{green second | green first})$$ where the vertical line can be read as “under the condition that the next event occurs” or “given that the next event occurs.” In this example, $$P(\text{green second | green first}) = \frac{2}{6}$$ since we assume the condition that the first marble drawn was green has happened, so the second draw only has 2 possible green marbles left to draw out of 6 marbles still in the jar.

To find the probability of two events happening together, we can use a multiplication rule:

$$P(\text{A and B}) = P(\text{A | B}) \boldcdot P(\text{B})$$

For example, to find the probability that we draw two green marbles from the jar, we could write out the entire sample space and find the probability from that or we could use this rule.

$$P(\text{green second and green first}) = P(\text{green second | green first}) \boldcdot P(\text{green first})$$

Since the probability of getting green on the first draw is $$\frac{3}{7}$$ and the conditional probability was considered previously, we can find the probability that both events occur using the multiplication rule.

$$P(\text{green second and green first}) = \frac{2}{6} \boldcdot \frac{3}{7}$$

This tells us that the probability of getting green marbles in both draws is $$\frac{1}{7}$$ (since this is equivalent to $$\frac{6}{42}$$).

In cases where events A and B are independent, $$P(\text{A | B}) = P(\text{A})$$ since the probability does not change whether B occurs or not. In these cases, the multiplication rule becomes:

$$P(\text{A and B}) = P(\text{A}) \boldcdot P(\text{B})$$

For example, when flipping a coin and rolling a standard number cube, the events “getting a tails for the coin” and “getting 5 for the number cube” are independent. That means we can find the probability of both events occurring to be $$\frac{1}{12}$$ by using the multiplication rule.

$$P(\text{heads and 5}) = \frac{1}{2} \boldcdot \frac{1}{6}$$

### Glossary Entries

• conditional probability

The probability that one event occurs under the condition that another event occurs.

• dependent events

Dependent events are two events from the same experiment for which the probability of one event depends on whether the other event happens.

• independent events

Independent events are two events from the same experiment for which the probability of one event is not affected by whether the other event occurs or not.


text:
Microbial 'omics

Brought to you by

# Extract loci from genomes and metagenomes with anvi'o

### and Alon Shaiber

This tutorial is for v6 and later versions of anvi’o. You can identify which version you have on your computer by typing anvi-self-test --version in your terminal.

The latest version of anvi’o is v6.1. See the release notes.

## Introduction

Some genetic analyses call for the comparison of specific genetic loci between genomes. For example, one may be interested in investigating evidence for adaptive evolution of the lac operon between different E. coli strains, and the first step to this analysis would be to extract the various lac operon from a collection of E. coli genomes.

To address this example and other genomic loci analyses alike, we present anvi-export-locus, an anvi’o program that enables you to target regions of interest across genomes and/or metagenomic assemblies, and report sequences and/or anvi’o contigs databases for cut loci for downstream analyses.

Briefly, anvi-export-locus cuts out loci using two approaches: default-mode or what we call flank-mode. In the default-mode, the tool locates a designated anchor gene, then cuts upstream and downstream based on user-defined input. Notice that what is “upstream” and what is “downstream” is determined according to the direction of the anchor gene, i.e., if the anchor gene is in the reverse direction, then “upstream” would mean genes that have higher gene callers ids, and vice versa. On the other hand, flank-mode finds designated genes that define the left and right boundaries of the target locus, then cuts in between them. Genes to locate locus anchors or flanking genes are defined through their specific ids in anvi’o or through search-terms that query functional annotations or HMM hits stored in your contigs database.

The purpose of this article is to demonstrate the functionality of anvi-export-locus using a simple and reproducible example: extracting the lac operon from the larger genomic context of E. coli genomes.

Using anvi-export-locus with external gene calls If you are using external gene calls when generating your contigs databases, then you should make certain genes that are next to each other on a contig, have sequential gene caller ids. If you are using Prodigal, then you have nothing to worry, since this is how Prodigal behaves and this is how we tested anvi-export-locus. To clarify this point, the way anvi-export-locus finds the genes for it to cut is by using the gene callers id. For example, if you are flank-mode and the upstream and downstream genes that you provided hit gene caller ids 40 and 50, respectively, then anvi-export-locus will return the eleven genes with ids between 40 and 50. Intuitively, you would expect these to be next to each other on the chromosome, but there is nothing stopping you from using external gene calls that don’t abide by this intuition, and anvi’o is not going to check whether that is the case or not.

First, let’s download Genbank files for a few representative E. coli strains:

Please see the tutorial here describing how to automagically download genomes from NCBI and include them in anvi’o workflows. We’ll be using this tool to download a few E. coli genomes.

# Set working directory variable for later
WD=$(pwd) # Download Genbank files ncbi-genome-download bacteria \ --assembly-level chromosome,complete \ --genus Escherichia \ --metadata metadata.txt \ --refseq-category reference  Next, we’ll make FASTAs, external gene calls, and functional annotations for all the Genbanks we just downloaded: anvi-script-process-genbank-metadata -m metadata.txt \ --output-dir ecoli \ --output-fasta-txt ecoli.txt  Just to have an idea about what is going on, please take a look at the output file ecoli.txt. We will use this file to create our contigs databases for these genomes. ## Generate contigs DBs Now we need to get the fasta files into an anvi’o friendly format. There are many ways to turn your FASTA files into anvi’o contigs databases, but here we will follow our best practices and process all our files using the anvi’o contigs workflow. First, make a json file for the anvio workflow called contigs.json: { "fasta_txt": "ecoli.txt" }  Then run the contigs workflow! This step may take a while depending on your computational resources. If you have any questions about running anvi’o workflows please refer to this tutorial here. If you access to an HPC or cluster computer, check out additional parameters here. anvi-run-workflow -w contigs \ -c contigs.json \ --additional-params \ --jobs 6 \ --resources nodes=6  ## Extract lac operon We should now have contigs DBs for our genomes. Now that we have six representative E. coli examples, we will use a combination of the default-mode and flank-mode to cut out the genomic neighborhood around the lac operon and then trim the contig to just contain the target operon. First, we will use default-mode. This requires the user to provide a --search-term and --num-genes parameter. The --search-term will act as an anchor gene to locate the locus within the contigs provided. In this case, we will use the lacZ gene to locate the lac operon in our E. coli genomes. Once the anchor gene is located --num-genes X,Y will instruct anvi-export-locus to cut X gene(s) upstream and Y gene(s) downstream of the designated anchor gene. Let’s get cutting! ## Default mode First, we’ll use default-mode to extract the general genomic neighborhood around the lac operon. To cut the lac operon from a single genome, we would have run this command in this general form: anvi-export-locus -c MY_GENOME.db \ --num-genes 10,10 \ --search-term "lacZ" \ -O MY_GENOME_lac_locus  But since we have multiple genomes we wish to study all at once, we will build a for loop in BASH to make life easier (while making everything more reproducible, and less error-prone at the same time): mkdir 03_LOCI cd 03_LOCI for GENOME in ls "${WD}"/02_CONTIGS/*-contigs.db;
do
FNAME=$(basename "${GENOME}" -contigs.db)
anvi-export-locus -c "${GENOME}" \ --num-genes 10,10 \ --search-term "lacZ" \ -O "${FNAME}"_lac_locus;
done

--search-term is NOT case sensitive unless you surround your term in quotes (e.g. --search-term "lacZ")

Here is a visual representation of how anvi-export-locus found the anchor gene “lacZ” the cuts 10 genes upstread and downstream.

## Flank-mode

Awesome, now we have some smaller contigs that contain the lac operon. BUT, we also grabbed some extra genes that don’t belong to the operon. Let’s use --flank-mode to trim the loci to just contain the lac operon.

To do this, give anvi-export-locus two flanking search-terms: lacI and lacA

for GENOME in ls "${WD}"/03_LOCI/*.db; do FNAME=$(basename "${GENOME}" _lac_locus_0001.db) anvi-export-locus -c "${GENOME}" \
--flank-mode \
--search-term "lacI","lacA" \
-O "\${FNAME}"_lac_locus_clean;
done

--flank-mode requires flanking genes to be single copies in the contig it’s searching. If your locus of interest does not have fixed coordinates in your genomes or metagenomes, you may need to adjust the -search-terms on a case by case bases.

Here is a visual representation of how flank-mode cuts out a locus using flanking genes.

## Conclusion

anvi-export-locus is a flexible tool that allows you to extract genomic loci from genomes and metagenomes. In this tutorial, we looked at the classic lac operon in E. coli genomes, but this tool can also be unleashed on any loci in genomes or metagenomic assemblies.

We hope you find amazing applications for this tool. If you have a suggestion or question please do not hesitate to contact us. Also, please report any bugs as an issue on the anvi’o Github repository.


text:
0
Follow
2
View

# Linear regression in R: Warning: 'newdata' had 1 row but variables found have 392 rows

damofs0a 注册会员
2023-01-25 12:32

It would help to make the example reproducible but I did some work and was able to reproduce the error:

``````library(ISLR)
auto_df = Auto

my_acc<-auto_df$$acceleration my_horse<-auto_df$$horsepower
mydata <- data.frame(my_acc, my_horse )
car_linear_regression <- lm(my_acc ~ my_horse, mydata )

predict(car_linear_regression,newdata = data.frame(horsepower = 93.5))
``````

The problem is in your model there is no variable called `horsepower`. You called it `my_horse`, so the following works:

``````predict(car_linear_regression,newdata = data.frame(my_horse = 93.5))
``````

As a side note, instead of creating separate variables I would just call the regression model as:

``````car_linear_regression <- lm(acceleration ~ horsepower, data=auto_df )
``````

Then your original prediction would have worked.

dsqsj1 注册会员

Publish Time
2023-01-25 12:32
Update Time
2023-01-25 12:32


text:
I would like to know how to change the font size in the table of contents. Maybe make it 14pt or 16pt.

\documentclass[12pt]{report}
\begin{document}
\tableofcontents

\end{document}
-
Do you want it to be different from the other parts of the ToC? For example, what about the page and sectional numbers? – Werner Jul 21 '12 at 21:31
I want it to behave like the default, just bigger. I'm not sure but I think the section titles are a little smaller than chapter titles. If this is the case, I would like to preserve the difference. – ArcanaNoir Jul 21 '12 at 21:35

You can use the tocloft package and the command families \cftXfont (for the sectional number and titles) and \cftXpagefont (for the page numbers):

\documentclass[12pt]{report}
\usepackage{tocloft}

\renewcommand\cftchapfont{\LARGE\bfseries}
\renewcommand\cftsecfont{\LARGE}

\renewcommand\cftchappagefont{\LARGE\bfseries}
\renewcommand\cftsecpagefont{\LARGE}

\begin{document}

\tableofcontents

Some text in standard size just for comparison.

\end{document}

Instead of \LARGE you can use any other font size switch or \fontsize{...}{...}\selectfont.

Redefining also the family \cftXafterpnum will give you better spacing between entries:

\documentclass[12pt]{report}
\usepackage{tocloft}

\renewcommand\cftchapfont{\LARGE\bfseries}
\renewcommand\cftsecfont{\LARGE}

\renewcommand\cftchappagefont{\LARGE\bfseries}
\renewcommand\cftsecpagefont{\LARGE}

\begin{document}

\tableofcontents

Some text in standard size just for comparison.