Association for Computing Machinery
Welcome to the August 11, 2010 edition of ACM TechNews, providing timely information for IT professionals three times a week.


HP Researcher Claims to Crack Compsci Complexity Conundrum
IDG News Service (08/09/10) Jackson, Joab

Hewlett-Packard researcher Vinay Deolalikar claims to have solved the computer science problem widely known as P versus NP. In an email to a group of math professors, Deolalikar said he was announcing proof that polynomial time (P) is not equal to nondeterministic polynomial time (NP), which may mean certain problems can only be solved by brute force searching, if solutions can be found at all. Deolalikar said he pieced together principles from multiple areas within mathematics. "The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens," Deolalikar wrote. No one who is familiar with the problem has said Deolalikar has solved it thus far, considering the amount of checking that needs to be done on his solution. The Clay Mathematics Institute has promised to pay $1 million to the person who solves the problem. The P versus NP problem involves "determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the institute.

Web Plan From Google and Verizon Is Criticized
New York Times (08/09/10) Miller, Claire Cain

Google and Verizon's proposal for how Internet service should be regulated was criticized by groups in favor of keeping the Web as open as possible. The proposal prevents Internet service providers from blocking producers of online content or offering them a paid "fast lane," and it calls on the U.S. Federal Communications Commission (FCC) to stop or fine rule-breakers. However, it creates an exception for Internet access over wireless networks, and for potential new services that broadband providers might offer. The plan "creates an Internet for the haves and an Internet for the have-nots," says Media Access Project's Jay Schwartzman. Critics also warn that the proposal leaves out future services that broadband providers may create. "It is time to move a decision forward--a decision to reassert FCC authority over broadband telecommunications, to guarantee an open Internet now and forever, and to put the interests of consumers in front of the interests of giant corporations," says FCC commissioner Michael J. Copps. Some Internet firms are wary of the proposal. "We are concerned that this proposal appears to condone services that could harm consumer Internet access," says's Paul Misener.

Researchers Successfully Test New Alternative to Traditional Semiconductors
OSU News (08/10/10) Gorder, Pam Frost

Ohio State University (OSU) researchers have developed a plastic memory device based on spintronics technology. The device is a hybrid of a semiconductor that is made from organic materials and a special magnetic polymer semiconductor, says OSU professor Arthur J. Epstein. "Spintronics is often just seen as a way to get more information out of an electron, but really it's about moving to the next generation of electronics," Epstein says. "We could solve many of the problems facing computers today by using spintronics." He notes that spintronic devices use less energy than traditional microelectronics, produce hardly any heat, and can store and transfer twice as much data per electron. "We would love to take portable electronics to a spin platform," Epstein says. "If we had a lighter weight spintronic device which operates itself at a lower energy cost, and if we could make it on a flexible polymer display ... users could just roll it up and carry it. We see this portable technology as a powerful platform for helping people."

Multi-Core With Virtualization, a Solution for Future Smart Phones
Ruhr-University Bochum (Germany) (08/11/10)

The Embedded Multi-Core Processing for Mobile Communications (eMuCo) project has released an open source software platform designed to enable the efficient use of multi-core chips on mobile embedded computing devices by using virtualization techniques. "The system opens access to the latest embedded multi-core architectures offering efficient programming and processing of a broad range of different applications, ranging from special purpose applications such as protocol implementation to whole virtualized commodity operating systems," says eMuCo's Adam Lackorzynski. "It is expected that the emerging multi-core and virtualization technology will revolutionize how a mobile phone will be perceived and opens new business models in the telecommunication market," says eMuCo's Maria Elizabeth Gonzalez. The eMuCo project was launched to explore the feasibility of multi-core and virtualization as a way to provide higher computational performance and flexibility while limiting power consumption. "Today's smartphone users want to download applications and individually customize their phones according to their needs and preferences" notes eMuCo's Attila Bilgic.

How Wearable Cameras Could Help Diagnose Dementia
Technology Review (08/06/10)

Researchers looking for an objective way to evaluate the onset of dementia are working on a technique that would enable a computer to make sense of an endless stream of video footage. A team at the University of Bordeaux is categorizing daily activities in footage taken from a shoulder-mounted camera. Svebor Karaman and colleagues define a scene as a sequence of frames in which the camera is relatively still. They categorize each sequence according to the colors present in the frames, which remain relatively constant even when the individual frames are blurred or dim. They manually label the scenes with titles such as "moving in the kitchen" or "moving in home office." A computer can use the information to detect similar patterns elsewhere in the footage, and present a reasonably accurate picture of the activities of a person on a daily basis. However, to make the technique useful for wearable video cameras that record a person's every movement, the team will have to automate the process or make it easier and faster for providing information about each behavior, and training it to recognize places.

How an Ancient Printer Can Spill Your Most Intimate Secrets
The Register (UK) (08/10/10) Goodin, Dan

Saarland University researchers have developed a way to recover confidential messages by analyzing the sounds made when documents are reproduced on dot-matrix printers. The so-called side-channel attack works by recording the sounds that are made when a document is being printed, and then using software to translate the sounds into words, with up to 72 percent accuracy. "We have presented a novel attack that takes as input a sound recording of a dot-matrix printer processing English text," the researchers say. The attack was demonstrated by using a microphone to record the sounds of a dot-matrix printer as it printed several articles from Wikipedia, the medical prescription of a fictitious patient, and declarations from a living will. The researchers used the Viterbi speech recognition algorithm to increase the software's success rate. "Intuitively, this technology works well for us because most errors that we encounter in the recognition phase are due to incorrectly recognized words that do not fit the context," the researchers say. The technique can be used to steal information from several different types of dot-matrix printers.

Teraflop Troubles: The Power of Graphics Processing Units May Threaten the World’s Password Security System
Georgia Tech Research Institute (08/10/10) Englehardt, Kirk J.; Toon, John

Georgia Tech Research Institute (GTRI) computer scientists are studying whether desktop computers with graphics processing units (GPUs) are so powerful that they compromise password protection. "Right now we can confidently say that a seven-character password is hopelessly inadequate--and as GPU power continues to go up every year, the threat will increase," says GTRI's Richard Boyd. Modern GPUs are so fast because they are designed as parallel computers. When given a problem, GPUs divide the task among multiple processing units and tackle different parts of the problem simultaneously. Software programs designed to break passwords are freely available on the Internet, and these programs, combined with the availability of GPUs, mean it is only a matter of time before the password threat will be immediate, the researchers say. GTRI's Joshua L. Davis says the best password is an entire sentence that includes numbers or symbols, because it is both long and complex and yet easy to remember.

Micromachines for a Safer World
American Friends of Tel Aviv University (08/10/10)

Tel Aviv University (TAU) researchers are working to make microelectromechanical systems (MEMS) even smaller, less expensive, and more sensitive by combining old-school mechanics with advanced electrical engineering. "The widespread penetration of miniature MEMS sensors into the devices surrounding us is transforming our way of life," says TAU's Slava Krylov. Krylov and doctoral student Assaf Ya'akobovitz have demonstrated how amplification techniques developed at their lab can be used for improving the performance of micro-accelerometers. Krylov's device uses a tiny electrode, a silicon chip, and a mechanical transformer coupled with an optical sensor to amplify the smallest changes in motion and acceleration. He says the technology could be used in iPhones as motion sensors, and in high-end navigation devices for airplanes and missiles. Eventually, Krylov says the technology could be used to help harvest clean energy and in medical applications.

Virtual Walkers Lead the Way for Robots
New Scientist (08/06/10) Campbell, MacGregor

Researchers are studying ways to use simulated physics and evolution to give robots and virtual characters more realistic gaits. Simulated evolution, a process developed by NaturalMotion, begins with a population of virtual skeletons controlled by a network of virtual nerves. Each skeleton has a slightly different network, affecting its ability to walk. Those that can walk furthest are declared "most fit" and are used to spawn the next generation, in which a subset of the nerves are slightly altered. Over several generations the skeletons automatically evolve into better walkers. Meanwhile, University of British Columbia researcher Michiel van de Panne and University of Toronto researcher Martin de Lasa have developed overarching controllers, instead of animating a character by controlling each joint independently. The controllers create rules that specify how the character should behave, and the individual joints move to obey them. In the researchers' model, once the path of the swinging foot is specified by the controller, the angles between various joints in the leg and hip are automatically calculated. The researchers want to apply their work for use in humanoid robots.

In a Video Game, Tackling the Complexities of Protein Folding
New York Times (08/09/10) Markoff, John

Foldit is a free online game from University of Washington researchers in which thousands of volunteer gamers bested a computer program in determining how proteins fold into their three-dimensional shapes. The researchers say the success of the Foldit gamers reflects how nonscientists can collaborate to devise new algorithms and strategies that are distinct from conventional software solutions to the challenge of protein folding. Foldit starts with a series of tutorials in which the player controls protein-like structures on a computer display. As structures are tweaked in the game, a score is estimated based on how well the protein is folded. Gamers are provided with a set of controls that enable them to manipulate the backbone and the amino acid side shapes of a specific protein into a more efficient configuration. The researchers note that the Foldit players outperformed the software tools in areas that include pattern recognition.
View Full Article - May Require Free Registration | Return to Headlines

Tire Tags Reveal Driver Whereabouts
BusinessWeek (08/10/10) Jackson, Joab

Researchers at Rutgers University and the University of South Carolina (USC) have found that wireless signals between new cars and their tires can be intercepted or forged. Although the security risk from this finding is minimal, it demonstrates a glaring weakness in secure software development in new cars, says USC professor Wenyuan Xu. Tire pressure monitoring systems consist of battery-powered radio frequency identification (ID) tags on each tire, which can respond with the air pressure readings of the tire when wirelessly queried by an electronic control unit. The researchers found that each sensor has a unique 32-bit ID and that communication between the tag and the control unit was unencrypted, which allowed it to be intercepted from up to 40 meters away. "If the sensor IDs were captured at roadside tracking points and stored in databases, third parties could infer or prove that the driver has visited potentially sensitive locations such as medical clinics, political meetings, or nightclubs," the researchers say.

Speech Recognition Systems Must Get Smarter, Professor Says
IDG News Service (08/05/10) Jackson, Joab

Most modern computerized speech-recognition systems can understand what a human says up to 98 percent of the time, yet people still get frustrated using automated phone help-desk systems, says University of Rochester professor James Allen. He says the key to making speech-recognition systems less frustrating to use is giving them a deeper understanding of language and making them more interactive. Allen has been researching ways to make these systems more life-like in the way they interact with humans. The goal is to be able to "talk to a machine the same way we can talk to a person," he says. A program designed by Allen and his team, called Plow, can learn how to carry out common tasks on a computer. "This is a system that allows you to essentially use dialog to train your system how to do things for you," he says. Another program designed by Allen and his research team, called Cardiac, mimics the questions a nurse asks a patient with heart disease. The system determines what information was provided and what is still needed. However, Allen says better two-communications between users and computers is still needed.

Computer Scientists Build Pedestrian Remover
UCSD News (CA) (08/05/10) Kane, Daniel

University of California, San Diego (UCSD) graduate student Arturo Flores and professor Serge Belongie have developed a proof-of-concept computer vision system that can remove pedestrians from urban scenes pulled from Google Street View, which they say could help preserve privacy in public environments. The system removes pedestrians and replaces the holes in the images with an approximation of the actual background behind each pedestrian. The background pixels are pulled from an image taken right before or right after the image containing people. Google Street View currently blurs faces and license plates from its images. However, clothes, body shape, and height combined with geographical location can be enough to make some people identifiable even if the face is blurred out, say Flores and Belongie. "This is a cute idea that, as far as we know, has not been explored," Belongie says.

What the Doctor Prescribes: Customized Medical-Image Databases
Rochester Institute of Technology (08/02/10) Gawlowicz, Susan

Rochester Institute of Technology professor Anne Haake is developing medical-image databases designed with physician input and based on flexible user interfaces. U.S. National Science Foundation funding will support visual perception research using eye-tracking technology and the design of a content-based image retrieval system that will be accessible through touch, gaze, voice, and gesture. The researchers are using eye tracking to determine how to make biomedical image databases more useful. For example, monitoring where a physician looks while making a diagnosis using a medical image can reveal the key regions in an image in a more reliable manner than by asking the physician to remember where they concentrated their focus. "Eye tracking is a way to identify the perceptually important areas, what people pay attention to and where they are looking," Haake says. In the study, a tracking device attached to a monitor is used to record the physicians' eye movements while they study medical images. Vocabulary collected from audio recording of the physicians' explanations is used to create the common search words in the database.

Abstract News © Copyright 2010 INFORMATION, INC.
Powered by Information, Inc.

To submit feedback about ACM TechNews, contact: [email protected]
Current ACM Members: Unsubscribe/Change your email subscription by logging in at myACM.
Non-Members: Unsubscribe