All the names that were investigated, even those whose background checks came up empty, were cataloged so police could refer to them in the future.
The legal justification for the program is unclear from the documents obtained by the AP. Because of its history of spying on anti-war protesters and political activists, the NYPD has long been required to follow a federal court order when gathering intelligence. That order allows the department to conduct background checks only when police have information about possible criminal activity, and only as part of "prompt and extremely limited" checking of leads.
The NYPD's rules also prohibit opening investigations based solely on activities protected by the First Amendment. Federal courts have held that people have a right to change their names and, in the case of religious conversion, that right is protected by the First Amendment.
The NYPD is not alone in its monitoring of Muslim neighborhoods. The FBI has its own ethnic mapping program that singled out Muslim communities and agents have been criticized for targeting mosques.
The name change program is an example of how, while the NYPD says it operates under the same rules as the FBI, police have at times gone beyond what is allowed by the federal government. The FBI would not be allowed to run a similar program because of First Amendment and privacy concerns and because the goal is too vague and the program too broad, according to FBI rules and interviews with federal officials.
Police expanded their efforts in late 2009, according to documents and interviews. After analysts ran background checks, police began selecting a handful of people to visit and interview.
Internally, some police groused about the program. Many people who were approached didn't want to talk and police couldn't force them to.
A Pakistani cab driver, for instance, told police he did not want to talk to them about why he took Sheikh as a new last name, documents show.
Police also knew that a would-be terrorist who Americanized his name in hopes of lying low was unlikely to confess as much to detectives. In fact, of those who agreed to talk at all, many said they Americanized their names because they were being harassed or were having problems getting a job and thought a new name would help.
But as with other intelligence programs at the NYPD, Cohen hoped it would send a message to would-be bombers that police were watching, current and former officials said.
As it expanded, the program began to target Muslims even more directly, drawing criticism from Stuart Parker, an in-house NYPD lawyer, who said there had to be standards for who was being interviewed, a person involved in the discussions recalled. In response, police interviewed people with Arabic-sounding names but only if their background checks matched specific criteria.
The names of those who were interviewed, even those who chose not to speak with police, were recorded in police reports storied in the department's database, according to documents and interviews, while names of those who received only background checks were kept in a separate file in the Intelligence Division.
Donna Gabaccia, director of the Immigration History Research Center at the University of Minnesota, said that for many families, name changes are important aspects of the American story. Despite the myth that officials at Ellis Island Americanized the names of people arriving in the U.S., most immigrants changed their names themselves to avoid ridicule and discrimination or just to fit in, she said.
The NYPD program, she said, turned that story on its head.
"In the past, you changed your name in response to stigmatization," she said. "And now, you change your name and you are stigmatized. There's just something very sad about this."
As for converts to Islam, the religion does not require them to take Arabic names but many do as a way to publicly identify their faith, said Jonathan Brown, a Georgetown University professor of Islamic studies.
Taking an Arabic name might be a sign that someone is more religious, Brown said, but it doesn't necessarily suggest someone is more radical. He said law enforcement nationwide has often confused the two points in the fight against terrorism.
"It's just an example of the silly, conveyor-belt approach they have, where anyone who gets more religious is by definition more dangerous," Brown said.
Sarah Feinstein-Borenstein, a 75-year-old Jewish woman who lives on Manhattan's Upper West Side, was surprised to learn that she was among the Americans drawn into the NYPD program in its infancy. She hyphenated her last name in 2009. Police investigated and recorded her information in a police intelligence file because of it.
"It's rather shocking to me," she said. "I think they would have better things to do. It's is a waste of my tax money."
Feinstein-Borenstein was born in Egypt and lived there until the Suez Crisis in 1956. With a French mother and a Jewish religion, she and her family were labeled "undesirable" and were kicked out. She came to the U.S. in 1963.
"If you live long enough," she said, "you see everything."
Contact the Washington investigative team at DCInvestigations(at)ap.org
Read AP's previous stories and documents about the NYPD at: http://www.ap.org/nypd
- 10 Things to See: A week of top AP photos
- Why Utahns are some of the biggest spenders,...
- 35 arrested in Oakland after protest march
- Rubber chickens, afros and clowns: A look at...
- Evangelicals with gay children challenging...
- Ferguson grand jury papers full of...
- In Britain, US turkey dinner is big for business
- Families uncover Civil War drama, 150 years...
- As Ferguson verdict is read, protesters... 70
- Grand jury won't indict Ferguson cop in... 30
- Obama: Americans want 'new car smell'... 29
- Ferguson businesses torched in... 17
- Under pressure, Hagel steps down as... 15
- Obama heads to Chicago to pitch... 13
- Why Utahns are some of the biggest... 12
- Attorney General Eric Holder:... 11