I'm really heartened by the speech Obama just gave in Cairo. (It's encouraging that Obama consulted with American religious leaders as the speech was being formulated.) Now, let's see whether Israel responds in a positive vein.

CAIRO, June 4 --President Obama asked Thursday for a "new beginning between the United States and Muslims around the world" in a speech that urged Islamic nations to embrace democracy, women's rights, religious tolerance and the right of Israel to co-exist with an independent Palestinian state.

In an address designed to change perceptions of the United States in the Arab Middle East and beyond, Obama reviewed the troubled historical legacy between Islam and the rest of the world, from colonialism through the wars in Iraq and Afghanistan and the uncertainty surrounding cultural and economic globalization.

"So long as our relationship is defined by our differences, we will empower those who sow hatred rather than peace, and who promote conflict rather than the cooperation that can help all of our people achieve justice and prosperity," Obama told an audience of hundreds gathered in a domed hall at Cairo University. "This cycle of suspicion and discord must end."

Yeah, that and the invasions and detentions! But I digress.

Obama's speech, carried live by many networks around the world, marks his latest outreach to Islam since taking office on a pledge to reach out more directly to U.S. rivals. Drawing at times on his father's Islamic heritage and his own childhood in Indonesia, the third most-populous Muslim nation, Obama condemned religious intolerance and bigotry across nations, and warned that "a small but potent minority of Muslims" have used those tensions to promote religious violence.

The speech at times had the feel of a history lesson as Obama listed the accomplishments of Muslims in America and the contributions Islamic culture has contributed to civilization over the centuries. He also sought to share the blame for the ruptured relationship, even as he sharply criticized Islamist extremism and called the attacks of Sept. 11, 2001, "not opinions to be debated" but "facts to be dealt with."

"I consider it part of my responsibility as president of the United States to fight against negative stereotypes of Islam wherever they appear," he said. "But that same principle must apply to Muslim perceptions of America . Just as Muslims do not fit a crude stereotype, America is not the crude stereotype of a self-interested empire."

Obama used far stronger and more specific language than his previous remarks on some of the most contested issues in the Muslim world, including the Israeli-Palestinian conflict. Although he urged Arab nations to do more to achieve peace with Israel, Obama also spoke passionately about what he called the Palestinian right to a state.

"America's strong bonds with Israel are well known. This bond is unbreakable," Obama said. It is based upon cultural and historical ties, and the recognition that the aspiration for a Jewish homeland is rooted in a tragic history that cannot be denied."

Citing the destruction of six million Jews in the Nazi Holocaust, Obama said that "threatening Israeli with destruction, or repeating vile stereotypes about Jews, is deeply wrong."

At the same time, he said, "it is also undeniable that the Palestinian people -- Muslims and Christians -- have suffered in pursuit of a homeland . . . They endure the daily humiliations -- large and small -- that come with occupation. So let there be no doubt: the situation for the Palestinian people is intolerable. America will not turn our backs on the legitimate Palestinian aspiration for dignity, opportunity, and a state of their own."

The audience, which had stayed silent while Obama described the U.S.-Israel relationship, anti-Semitism and the legacy of the Holocaust, broke into warm applause.