Math News July 20th, 2009
Patrick Stein

An aggregation of some of the math blogs that I follow.

Math News (1 - 25 of about 3173) (xml) (Feedlist)


the other shoe dropsQuantum query complexity
(01.07.2015 03:06h)

Two weeks ago I blogged about a breakthrough in query complexity: namely, the refutation by Ambainis et al. of a whole slew of conjectures that had stood for decades and that I mostly believed, and that had helped draw me into theoretical computer science as a teenager about the largest possible gaps between various complexity measures for total Boolean functions. Specifically, Ambainis et al. built on a recent example of Göös, Pitassi, and Watson to construct bizarre Boolean functions f with, among other things, near-quadratic gaps between D f and R0 f where D is deterministic query complexity and R0 ... [Link]

Celebrate gay marriage—and its 2065 equivalentScott
(27.06.2015 16:14h)

Yesterday was a historic day for the United States, and I was as delighted as everyone else I know. I’ve supported gay marriage since the mid-1990s, when as a teenager, I read Andrew Hodges’ classic biography of Alan Turing, and burned with white-hot rage at Turing’s treatment. In the world he was born into—our world, until fairly recently—Turing was “free”: free to prove the unsolvability of the halting problem, free to help save civilization from the Nazis, just not free to pursue the sexual and romantic fulfillment that nearly everyone else took for granted. I resolved then that, if I ... [Link]

“Can Quantum Computing Reveal the True Meaning of Quantum Mechanics?”Scott
(25.06.2015 14:46h)

I now have a 3500-word post on that question up at NOVA’s “Nature of Reality” blog. If you’ve been reading Shtetl-Optimized religiously for the past decade why? , there won’t be much new to you there, but if not, well, I hope you like it! Comments are welcome, either here or there. Thanks so much to Kate Becker at NOVA for commissioning this piece, and for her help editing it. [Link]

FCRC HighlightsScott
(19.06.2015 21:42h)

By popular request, here are some highlights from this week’s FCRC conference in Portland, Oregon: The edit distance between two strings means the minimum number of insertions, deletions, and replacements needed to convert one string to the other: for example, SHTETL and SHETLAND have an edit distance of 4. Edit distance has major, obvious applications to DNA sequence comparison, as well as plagiarism detection and many other things. There’s a clever dynamic programming algorithm to compute the edit distance between two n-bit strings, but it takes ~n2 time, which is already too slow for many applications. Can you do better? ... [Link]

A query complexity breakthroughScott
(18.06.2015 00:41h)

Update June 26 : See this just-released paper, which independently obtains a couple of the same results as the Ambainis et al. paper, but in a different way using the original Göös et al. function, rather than modifications of it . Lots of people have accused me of overusing the word “breakthrough” on this blog. So I ask them: what word should I use when a paper comes out that solves not one, not two, but three of the open problems I’ve cared about most for literally half of my life, since I was 17 years old? Yesterday morning, Andris ... [Link]

97% environmentalistScott
(07.06.2015 17:42h)

I decided to add my name to a petition by, as of this writing, 81 MIT faculty, calling on MIT to divest its endowment from fossil fuel companies. My co-signatories include Noam Chomsky, so I guess there’s something we agree about! There’s also a wider petition signed by nearly 3500 MIT students, faculty, and staff, mirroring similar petitions all over the world. When the organizers asked me for a brief statement about why I signed, I sent them the following: Signing this petition wasn’t an obvious choice for me, since I’m sensitive to the charge that divestment petitions are just ... [Link]

Can blog posts nourish the soul? Scott A. alas, not me as existence proofScott
(03.06.2015 19:31h)

Reading the essays and speculative fiction of Scott Alexander, as they’ve grown in awesomeness even just within the past half-year, has for me been like witnessing the birth of a new Asimov. For more Alexandery goodness, check out Universal Love, Said the Cactus Person. That this nerd-bard, this spinner of stupid Internet memes into reflections on eternity, came to my attention by way of his brilliantly defending me, is almost immaterial at this point; I don’t think it plays any role in my continuing admiration for his work. Whatever you do, just keep writing, other Scott A. [Link]

The End of Suffering?Scott
(02.06.2015 00:40h)

A computer science undergrad who reads this blog recently emailed me about an anxiety he’s been feeling connected to the Singularity—not that it will destroy all human life, but rather that it will make life suffering-free and therefore no longer worth living more Brave New World than Terminator, one might say . As he puts it: This probably sounds silly, but I’ve been existentially troubled by certain science fiction predictions for about a year or two, most of them coming from the Ray Kurzweil/Singularity Institute types … What really bothers me is the idea of the “abolition of suffering” as ... [Link]

Latest adventuresKowalski
(24.05.2015 12:29h)

The last two weeks were quite eventful… First I spent four days in China for the conference in honor of N. Katz’s 71st birthday. I was lucky with jetlag and was able to really enjoy this trip, despite its short length. The talks themselves were quite interesting, even if most of them were rather far from my areas of expertise. I talked about my work with W. Sawin on Kloosterman paths; the slides are now online. I only had time to participate in one of the excursions, to the Forbidden City, Forbidden City were I took many pictures of Chinese ... [Link]

The Power of PrecomputationNSA in P/poly
(23.05.2015 01:41h)

Even after the Snowden revelations, there remained at least one big mystery about what the NSA was doing and how. The NSA’s classified 2013 budget request mentioned, as a priority item, “groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” There was a requested increase, of several hundred million dollars, for “cryptanalytic IT services” and “cryptanalysis and exploitation services program C” whatever that was . And a classified presentation slide showed encrypted data being passed to a high-performance computing system called “TURMOIL,” and decrypts coming out. But whatever was going on inside TURMOIL seemed to be secret even ... [Link]

Five announcementsScott
(17.05.2015 03:08h)

1. Sanjeev Arora sent me a heads-up that there’s a discussion about the future of the STOC conference at the Windows on Theory blog—in particular, about the idea of turning STOC into a longer “CS theory festival.” If you have opinions about this, don’t miss the chance to make your voice heard. 2. Back in January, I blogged about a new quantum optimization algorithm by Farhi, Goldstone, and Gutmann, which was notable for being, as far as anyone could tell, the first quantum algorithm to achieve a provably better approximation ratio than the best-known classical algorithm for an NP-hard optimization ... [Link]

New versions, new bugsKowalski
(07.05.2015 07:22h)

Ph. Michel found the first bug in the new version of Kloostermania: when entering a modulus for a sum from the menu, there was no check that it is prime or adjustment to make it so . This is now corrected in version 1.01, to be found in the usual place. As another bonus feature, a double tap on the screen will cycle between the types of sums presented: Kloosterman sum to Birch sum to both to Kloosterman… [Link]

Kloostermania turns 1.0Kowalski
(04.05.2015 16:21h)

Since the Pocket Kloostermania has remained unchanged for almost five years, an update is probably welcome! This is now available, in time to honor N. Katz on the occasion of this 71st birthday which I will help celebrate in China next week . Important changes in the new version: 1 It was recompiled — hence a new modern look instead of a style reminiscent of the dark ages –, and the resulting binary should work on any Android system with version 4.0.3 or later; 2 To keep up with recent progress, the program now displays Kloosterman sums and/or Birch sums, ... [Link]

“Is There Something Mysterious About Math?”Scott
(22.04.2015 07:08h)

When it rains, it pours: after not blogging for a month, I now have a second thing to blog about in as many days. Aeon, an online magazine, asked me to write a short essay responding to the question above, so I did. My essay is here. Spoiler alert: my thesis is that yes, there’s something “mysterious” about math, but the main mystery is why there isn’t even more mystery than there is. Also—shameless attempt to get you to click—the essay discusses the “discrete math is just a disorganized mess of random statements” view of Luboš Motl, who’s useful for ... [Link]

Two papersScott
(21.04.2015 12:32h)

Just to get myself back into the habit of blogging: For those of you who don’t read Lance’s and Bill’s blog, there was a pretty significant breakthrough in complexity theory announced last week. And yes, I’m now spending one of the two or so uses of the word “breakthrough” that I allow myself per year—wait, did I just spend the second one with this sentence? Ben Rossman a former MIT PhD student whose thesis committee I was honored to serve on , Rocco Servedio, and Li-Yang Tan have now shown that the polynomial hierarchy is infinite relative to a random ... [Link]

Worms, brains and “graphes expanseurs”Kowalski
(11.04.2015 11:03h)

Two days ago, I was in Paris and visited the École Polytechnique there for the first time, as it turns out , in order to give the traditional introductory lecture presenting various aspects of mathematics that is given each year to the incoming class of students. Many people would wonder how a new class can be incoming in April; this is because the students of École Polytechnique, which is a military school, begin their studies with a military/civil service from September to April . I had selected expander graphs as the topic of my talk, as being simultaneously a very ... [Link]

Kummer extensions, Hilbert’s Theorem 90 and judicious expansionKowalski
(26.03.2015 15:45h)

This semester, I am teaching “Algebra II” for the first time. After “Algebra I” which covers standard “Groups, rings and fields”, this follow-up is largely Galois theory. In particular, I have to classify cyclic extensions. In the simplest case where is a cyclic extension of degree and contains all -th roots of unity and is coprime to the characteristic of , this essentially means proving that if has cyclic Galois group of order , then there is some with and belongs to . Indeed, the converse is relatively simple in the technical sense that I can do it on paper ... [Link]

Noether on GoogleKowalski
(23.03.2015 09:35h)

Today’s Google doodle celebrates Emmy Noether. Noether Algebra would look very different without her “successive sets of symbols with the same second suffix“ . [Link]

A parity lemma of A. IrvingKowalski
(16.03.2015 10:31h)

In his recent work on the divisor function in arithmetic progressions to smooth moduli, A. Irving proves the following rather amusing lemma see Lemma 4.5 in his paper : Lemma Let be an odd prime number, let be an integer and let be a -tuple of elements of . For any subset of , denote and for any , let denote the multiplicity of among the . Then if none of the is zero, there exists some for which is odd. I will explain two proofs of this result, first Irving’s, and then one that I came up with. I’m ... [Link]

Who proved the Peter-Weyl theorem for compact groups?Kowalski
(15.03.2015 18:03h)

Tamas Hausel just asked me because of my previous post on the paper of Peter and Weyl how could Peter and Weyl have proved the “Peter-Weyl Theorem” for compact groups in 1926, not having Haar measure at their disposal? Indeed, Haar’s work is from 1933! The answer is easy to find, although I had completely overlooked the point when reading the paper: Peter and Weyl assume that their compact group is a compact Lie group, which allows them to discuss Haar measure using differential forms! Peter-Weyl So the question is: who first proved the full “Peter-Weyl” Theorem for all compact ... [Link]

The ultimate physical limits of privacyScott
(11.03.2015 15:44h)

Somewhat along the lines of my last post, the other day a reader sent me an amusing list of questions about privacy and fundamental physics. The questions, and my answers, are below. 1. Does the universe provide us with a minimum level of information security? I’m not sure what the question means. Yes, there are various types of information security that are rooted in the known laws of physics—some of them like quantum key distribution even relying on specific aspects of quantum physics—whose security one can argue for by appealing to the known properties of the physical world. Crucially, however, ... [Link]

The flow of emails within the block inboxScott
(07.03.2015 16:06h)

As a diversion from the important topics of shaming, anti-shaming, and anti-anti-shaming, I thought I’d share a little email exchange with my interlocutor’s kind permission , which gives a good example of what I find myself doing all day when I’m not blogging, changing diapers, or thinking about possibly doing some real work but where did all the time go? . Dear Professor Aaronson, I would be very pleased to know your opinion about time. In a letter of condolence to the Besso family, Albert Einstein wrote: “Now he has departed from this strange world a little ahead of me. ... [Link]

RadioKowalski
(27.02.2015 17:31h)

For those readers who understand spoken French or simply appreciate the musicality of the language and are interested in the history of mathematics, I warmly recommend listening to the recording of a recent programme of Radio France Internationale entitled “Pourquoi Bourbaki ?” In addition to the dialogue of Sophie Joubert with Michèle Audin and Antoine Chambert-Loir, one can hear some extracts of older émissions with L. Schwartz, A. Weil, H. Cartan, J. Dieudonné, for instance. [Link]

How can we fight online shaming campaigns?Scott
(25.02.2015 13:15h)

Longtime friend and colleague Boaz Barak sent me a fascinating New York Times Magazine article that profiles people who lost their jobs or otherwise had their lives ruined, because of a single remark that then got amplified a trillionfold in importance by social media. The author, Jon Ronson, also has a forthcoming book on the topic. The article opens with Justine Sacco: a woman who, about to board a flight to Cape Town, tweeted “Going to Africa. Hope I don’t get AIDS. Just kidding. I’m white!” To the few friends who read Sacco’s Twitter feed, it would’ve been obvious that ... [Link]

“The Man Who Tried to Redeem the World with Logic”Scott
(18.02.2015 17:21h)

No, I’m not talking about me! Check out an amazing Nautilus article of that title by Amanda Gefter, a fine science writer of my acquaintance. The article tells the story of Walter Pitts, who [spoiler alert] grew up on the mean streets of Prohibition-era Detroit, discovered Russell and Whitehead’s Principia Mathematica in the library at age 12 while hiding from bullies, corresponded with Russell about errors he’d found in the Principia, then ran away from home at age 15, co-invented neural networks with Warren McCulloch in 1943, became the protégé of Norbert Wiener at MIT, was disowned by Wiener because ... [Link]

Item (1 - 25 of about 3173)Next page

 

ArchiveEarlier 1.7.2015  

Generiert mit Parteibuch Aggregator 0.5.2

Updates In Email

Email:

l