2007 Turing Award Winners Announced
Dr. Dobb's Journal (02/04/08)
Carnegie Mellon University professor Edmund M. Clarke, University of
Texas, Austin professor E. Allen Emerson, and Joseph Sifakis of the
University of Grenoble have been named the recipients of ACM's 2007 A.M.
Turing Award for their work on Model Checking, an automated method for
finding design errors in computer hardware and software. Model Checking is
the most widely used technique for detecting errors in hardware and
software and has helped improve the reliability of complex computer chips,
systems, and networks. Model Checking is a type of formal verification
that analyzes the logic underlying a design. The Turing Award, named for
British mathematician Alan M. Turing, is presented annually by ACM and is
considered the most prestigious award in computing. Clarke, Emerson, and
Sifakis will share the $250,000 prize. Clarke and Emerson originated the
idea of Model Checking at Harvard in 1981, and Clarke implemented the first
Model Checker in 1982. The first Model Checker was limited to relatively
small designs, significantly smaller than the systems being built by
computer manufacturers. In 1987, Clarke's graduate student Kenneth
McMillian realized that Model Checking could be implemented by a series of
operations on binary decision diagrams. The new system, called Symbolic
Model Checking, can analyze billion of billions of states and can be used
for commercial computer design problems. In 1998, Clarke, Emerson, and
McMillan (along with Randal E. Bryant) won ACM's Paris Kanellakis Award for
Theory and Practice.
Click Here to View Full Article
to the top
Friends, Colleagues, Plan Tribute to Renowned Scientist
Jim Gray
University of California, Berkeley (02/04/08) Harmon, Keith; Silverman,
Sarah
ACM, the University of California, Berkeley, and IEEE will jointly host a
tribute to legendary computer scientist Jim Gray on May 31, 2008, at UC
Berkeley's Zellerbach Hall. Gray, who has been missing at sea since Jan.
28, 2007, is renowned for his work as a programmer and database expert that
helped make possible such technologies as the cash machine, databases like
Google, e-commerce, and online ticketing. He received UC Berkeley's first
PhD in computer science in 1969 and worked at Bell Labs, IBM, Tandem
Computers, Digital Equipment Corp., and most recently at Microsoft. Gray
received ACM's A.M. Turing Award in 1998. "Jim was a true visionary and
leader in this field," says Shankar Sastry, dean of the College of
Engineering at UC Berkeley. "We are honored to host this tribute to Jim's
remarkable achievements and the impact he made on so many of us." The
tribute's general session will take place from 9-10:30 a.m., followed by
technical sessions that require registration. Speakers at the tribute will
include UC Berkeley computer science professor Joe Hellerstein, University
of Washington professor Ed Lazowska, and Microsoft's Rich Rashid and David
Vaskevitch, among others.
Click Here to View Full Article
to the top
States Prepare for Tests of Voting-System Changes
New York Times (02/05/08) P. A14; Urbina, Ian
California's switch from touch-screen voting machines to paper-based
ballots for Tuesday's primary has also brought back issues related to paper
ballots, such as absentee ballots that fall apart at the fold lines and the
ballot transportation helicopter being grounded by intense fog. "They may
be high-tech or they could be low-tech, but the problems are always there,"
says Barbara Dunmore, the Riverside County registrar of voters. Election
officials in at least 20 California counties without paper trails were told
by the state to switch back to paper ballots, but the ballots will have to
be counted at a central location where the absentee ballots are being
counted because the counties were not able to acquire enough machines to
perform tallies at individual polling places. All polling places in New
Jersey, Delaware, and Georgia, as well as most of Tennessee, are using
paperless touch-screen machines for their primary elections on February 5,
and were considered "high risk" for voting problems before the election
according to a report released by Common Cause and the Verified Voting
Foundation. Experts say that meaningful recounts are impossible in a close
race without a paper trail, and if problems occur with the voting machines,
officials will be unable to audit contested results. Growing concerns
about potential tampering or malfunctions have led election directors in
Ohio, Florida, California, and Colorado to shift away from paperless
touch-screen systems, but only California was ready in time for the
February 5th elections.
Click Here to View Full Article
to the top
New Super-Efficient Chip Could Run on Body Heat
Wired News (02/04/08) Madrigal, Alexis
MIT researchers, working with researchers at Texas Instruments, have
developed a chip that uses 70 percent less voltage than current chip
technologies, which could lead to an order-of-magnitude increase in energy
efficiency for electronics in the next five years. "It will extend the
battery lifetime of portable devices in areas like medical electronics,"
says MIT electrical engineering professor Anantha Chandrakasan. "When you
look at the digital processor, the fact is that we may be able to reduce
the energy needed by 10 times." The chip uses so little power that it
could allow sensors, communication devices, and other gadgets to run on
body heat and movement alone. Better batteries and circuit design have
already led to smaller, more mobile electronic devices, but changing a
battery is often not an option for military and medical personnel.
Military researchers at DARPA, which helped fund the MIT research, want to
increase the lifespan of mobile technology, and even eliminate the need to
recharge a device. Military strategist believe that such low-power chips
could be used in body and environmental sensors. Creating a low-voltage
chip is difficult because transistors use voltage to switch on and off, and
at low voltages variations introduced during transistor production can
cause errors. "When you scale voltages, the first thing to break is memory
on a chip," Chandrakasan says. "You have to redesign the memory and logic
so you can handle the variation." Chandrakasan says working with scalable
energy voltages requires a whole suite of design techniques, including a
fundamental change in the memory cell from six transistors to eight.
Click Here to View Full Article
to the top
A Wireless Network Think Tank ... With Toys
Network World (02/04/08) Cox, John
The Rutgers University Wireless Information Network Laboratory (WINLAB) is
working to solve some of the most difficult problems facing large-scale
wireless networks, including radio coexistence in crowded frequencies to
re-engineering the Internet for mobile traffic. WINLAB currently focuses
its research on the mobile Internet, cognitive radios, and pervasive
wireless, three broad areas that, combined, envision a world that is bound
together by short- and long-range wireless networks, intelligent devices,
and sensors. WINLAB's mobile Internet research aims to redesign the modern
Internet architecture and protocols to include mobile users and wireless
links. "We wanted to change the vertically-oriented cellular architecture
into a flat architecture, like the Internet," says WINLAB director Dipankar
Raychaudhuri. Other groups are also exploring new Internet architectures,
including the Global Environment for Network Innovations (GENI) and the
National Science Foundation's Future Internet Design (FIND) program. "The
notion is that the Internet needs to transform itself, so that a car [with
an embedded radio], for example, can act as a radio router," Raychaudhuri
says. "Today's Internet doesn't recognize this: It's a scenario that's too
dynamic for existing [Internet] protocols." WINLAB's research into a new
Internet architecture led to the creation of the Open Access Radio Grid
Testbed (ORBIT), a wireless network based on a flat architecture that lets
researchers test experimental protocols under controlled conditions. "We
want devices talking to each other through just one or two layers of
protocols, as the wired Internet does," Raychaudhuri says. "That's a very
important step in achieving our vision of a wireless world."
Click Here to View Full Article
to the top
Microsoft Preps New Modeling Language
eWeek (02/05/08) Taft, Darryl K.
Microsoft is working on a new declarative programming language, a
supporting editing tool, and other components for its Oslo model-driven
development initiative, according to sources close to the company.
Microsoft announced Oslo as part of a vision for simplifying development,
design, management, and deployment. Company officials say Oslo will
represent a core set of technology investments that will include both a
services infrastructure, such as server, client, and Internet "cloud," as
well as an executable modeling platform that will have a general-purpose
modeling language, tools, and repository. Sources say the heart of the
Oslo initiative is a new declarative programming language known as "D"
under development at Microsoft for the purpose of building applications and
components for the Oslo repository. D is expected to be a textual modeling
language suitable for business professionals and domain experts.
Supporting D will be a new editing tool called Intellipad that will serve
as a text editor for the D language and further support the development of
applications and content for the repository. Intellipad will also be able
to support other declarative languages, and will be customizable and
suitable for scripting, sources say.
Click Here to View Full Article
to the top
Americans Overseas Head to Polls
Associated Press (02/05/08) McDowell, Robin
Americans living overseas and registered as Democrats were able to cast
their votes online for Democratic candidates in the presidential primaries
on Feb. 5th for the first time ever. About 6 million expatriates are
eligible to vote, but only a fraction have done so in past elections.
Until recently, the only way to vote from a foreign country was to mail an
absentee ballot request form and hope that the ballot is received by voting
officials in time to count. Now, expatriates registered as Democrats can
vote online, but some caution that online voting may not be secure. Former
ACM President Barbara Simons, a member of the nonprofit Verified Voting
Foundation, warns that just because a system is simple does not mean it is
successful. "How do I know if ballot box stuffing was done," Simons says.
"How do I know they were legitimate votes? This is not the way to run an
election." To vote online in the primaries, citizens must first register
with Democrats Abroad. Once registered, they receive a PIN code and a
ballot number via email and a link to the voting Web site. Voters are
asked to enter their birth date and address for verification, along with
the PIN code and ballot. A similar program is not yet available for
Republicans, and the e-voting system is not an option for the general
election.
Click Here to View Full Article
to the top
Music Lovers Get the 'Meta' of Digital Audio
ICT Results (01/30/08)
European researchers have developed "first of its kind" software for
automatically extracting and classifying audio signals. Audio signal
metadata can be used to tag audio files so they can be more accurately
picked up by search engines equipped to handle such information. The
researchers say that audio metadata could be the next big step in boosting
online music sales by helping companies exploit their archives more
thoroughly and helping consumers find songs they might have otherwise
missed. "We are in concrete discussions with a number of interested
companies on using some of the developments from our project," says
research coordinator Hugues Vinet. Vinet, the scientific director at the
Paris-based Institute for Music/Acoustic Research and Coordination, was
part of a team that included researchers from Spain and Israel, as well as
Oracle and Sony. The researchers developed a music browser, an online
sound palette, and sound-authoring software that can analyze and index
sound according to the digital patterns displayed by each song. The
research involved developing several techniques for capturing specific
qualities from audio files, such as timbre, energy, and rhythm.
Click Here to View Full Article
to the top
Smart 'Lego' Conjures Up Virtual 3D Twin
New Scientist (01/31/08) Inman, Mason
Carnegie Mellon University researchers have developed Posey, a new
computer interface that uses plastic hubs and struts with LEDs and sensors
to replicate shapes on a computer. When the plastic pieces are combined in
different ways, an exact copy of the shape appears on a computer screen.
Every alteration to the shape, even as small as twisting one of the hubs,
is detected by the LEDs and sensors and recreated on a computer in real
time. The plastic pieces communicate wirelessly to a computer using the
ZigBee low-power protocol. Applications for Posey include using it to
create real-world and virtual models of molecules simultaneously. A
program created by the researchers allows each piece to represent either an
atom or a bond between atoms. Creating a real-world model will
simultaneously create a 3D virtual replica that displays the molecular
structure and physical properties. The program also suggests related
molecules that could be built with minor alterations. Posey could also be
used as a toy to create skeletons of animated characters and animals that
could be fitted with a virtual skin and other features on the computer,
enabling children to create virtual puppet shows.
Click Here to View Full Article
to the top
Meeting Lays Foundation for European HPC
Infrastructure
HPC Wire (01/29/08)
Over 60 representatives from 14 European countries recently gathered at
the first meeting of the Partnership for Advanced Computing in Europe
(PRACE) project at the Research Center Juelich. PRACE was established to
create a persistent pan-European high-performance computer service for
European researchers that is far beyond what is available at a national
level. During the preliminary phase, which will run until the end of 2009,
the project will establish the basis of a transitional organizational
structure for scientific supercomputing in Europe. The project includes a
coordinated approach to hardware procurement and potentially a European
platform for the development of hardware and software. Cooperation with
national and regional computer centers and scientific organizations will
facilitate access to computing resources at all levels for scientists,
engineers, academia, and industry. "Supercomputers have become an
essential tool for all of the sciences," says PRACE coordinator Achim
Bachem, chairman of the Board of Directors at Research Center Juelich. "In
the future, giant leaps in knowledge will only be possible with the help of
complex simulations."
Click Here to View Full Article
to the top
Upgraded Technology Aids Stadium Viewing
USA Today (02/04/08) Martin, Jeff
The technology on display at large sporting arenas is impressive, but it
may pale in comparison with the technology that is just over the horizon.
Engineers are striving for what could be the next big thing at sporting
events--three-dimensional imaging technology that allows fans to view
sporting events as 3D holographic images. "I think in the next decade
you're going to see some revolutionary technologies in 3D," says Zebra
Imaging's Jim Gardner, a former research scientist with Honeywell. Gardner
says 3D imaging holds potential for a variety of industries, including
displaying underground oil fields to 3D cityscapes for emergency workers.
James Oliver, director of the CyberInnovation Institute and Virtual Reality
Applications Center at Iowa State University, says sporting events will
continue to have an increasing number of cameras on wires over the field,
and games could soon be broadcast in 3D. "You might go to a theater to see
the game in 3D," says Oliver. "It's all just right around the corner."
Click Here to View Full Article
to the top
Moving Molecules at IBM Almaden
CNet (02/04/08) Kanellos, Michael
Potential data storage solutions have become the focus of scientists at
the IBM Almaden Research Center in the San Francisco Bay Area. "The
problems we're looking at aren't computationally driven per se, but more
information management problems," says Mark Dean, an IBM fellow and
director of Almaden. "Computation is not the hard part anymore." Some
computers may not be charged with coming up with absolute answers from a
billion gigabytes of data in the years to come. Instead, their role may be
to narrow the scope of an inquiry to approximate answers, before another
computer takes over to return accurate answers. The human brain may serve
as a model for how some of the systems will function. Almaden hopes to
deliver new types of hardware for storing data so far ahead of its time
that they will consist of a few molecules.
Click Here to View Full Article
to the top
UA-Led Research Team Awarded $50 Million to Solve Plant
Biology's Grand Challenges
University of Arizona (01/30/08)
University of Arizona researchers are leading a team that received a $50
million National Science Foundation grant to create a global center and
computer cyberinfrastructure to solve plant biology's grand challenges.
Plant scientists, computer scientists, and information scientists from
around the world will collaborate for the first time to provide answers to
questions of global importance. The five-year project, called the iPlant
Collaborative, is potentially renewable for a second five years and a total
of $100 million. "This global center is going to change the way we do
science," says Richard Jorgensen, UA plant sciences professor and director
of the iPlant Collaborative. "We're bringing many different types of
scientists together who rarely had opportunities to talk to one another
before. In so doing, we'll create the kind of multidisciplinary
environment that is necessary to crack the toughest problems in modern
biology." The researchers will rely heavily on a cyberinfrastructure that
uses computational thinking, a form of problem-solving that assigns
computers the jobs they are most efficient at, freeing up time for human
researchers. The iPlant Collaborative will work to map the full expanse of
plant biology, similar to how Google Earth physically maps the planet.
Click Here to View Full Article
to the top
Democratic Parties: An Interview With UCLA Computer
Scientist Kevin Eustice
Techdirt (01/30/08) Sanchez, Julian
University of California, Los Angeles graduate student Kevin Eustice is
the co-creator of Smart Party, a system that can read the music playlist on
Wi-Fi-enabled devices and choose the song that is most likely to please a
group of people based on what people have in their playlists. Smart Party
was developed as part of a National Science Foundation-funded project to
develop a secure infrastructure for ubiquitous computing. Smart Party is
built on an infrastructure called Panoply that supports the management of
location context, device configuration, and secure session establishment,
among other things. "Panoply is a middleware for developers to easily
build ubiquitous computing applications; it looks at the device as the
representative of the user in the digital world--your avatar, in the sense
that it represents the user," Eustice says. He says the goal is to enable
Panoply-based applications to function on behalf of the user based on the
location and social context of the situation. For example, Eustice says
Panoply was used last year to create a group-based interactive narrative at
UCLA that supported arbitrary social groups tied to specific locations.
Another application he envisions is using Panoply for context-aware museum
experiences. He admits that privacy is an issue with ubiquitous computing
applications. "Ubiquitous computing has potential to do great good, but
obviously when you're talking about sharing immense amounts of personal
data there's also potential for great harm," he says.
Click Here to View Full Article
to the top
Designing for Robotics
Design News (02/04/08) Shah, Kamran
The right development platform will be a factor in determining the success
that researchers have with sensors and actuators in robotics, says National
Instruments' Kamran Shah. Engineers need to interface with the right
sensors and actuators, which include analog input and output, digital
lines, GPS sensors, LIDARs, cameras, motors and CAN interfaces for
vehicles. Software becomes central to any robotic system as a result, Shah
says. Developers also have to combine algorithms from basic filters with
more complex image processing for robotic systems. Robotics stands to
benefit tremendously from multi-core processors, which can allow developers
to isolate the control algorithm for a robot on one core to ensure it runs
at the desired loop rate and use the other cores on the processor for
lower-priority tasks or for performing specific signal processing. Another
key enabling technology involves FPGAs, which enable developers to define
as many parallel running portions of their application as the FPGA fabric
allows. He cited Virginia Tech's autonomous humanoid soccer-playing robot
called DARwin and the school's autonomous vehicle that competed in the
DARPA Urban Challenge as exciting examples of robots. Shah expects robots
or elements of robotics to become more of a presence in everyday life
within the next decade.
Click Here to View Full Article
to the top
Swarm Approach to Photography
EurekAlert (02/01/08)
Researchers in the United Kingdom and Jordan have used the Swarm
Intelligence paradigm as a way to clean up digital photos and other images.
Malik Braik and Alaa Sheta, information technology specialists at Al-Balqa
Applied University in Salt, have teamed up with Aladdin Ayesh, a computer
engineering expert at De Montfort University in Leicester, to create a
computer algorithm based on a mathematical model of the social interactions
of swarms. The Particle Swarm Optimization (PSO) algorithm improves an
image's contrast and detail without distorting it. PSO views each version
of an image as an individual member of the swarm; adjusts contrast levels,
edge sharpness, and other image parameters; and then determines whether the
change is better or worse based an objective fitness criterion. "The
objective of the algorithm is to maximize the total number of pixels in the
edges, thus being able to visualize more details in the images," the
researchers say. The enhancement is repeated to create a swarm of images
in computer memory that are graded relative to each other, with the fittest
at the front of the swarm until the single, most effectively enhanced
individual is rendered. The technique could be used to improve CCTV
quality, and images produced with camera phones or other lower quality
cameras.
Click Here to View Full Article
to the top
Overhaul of Net Addresses Begins
BBC News (02/04/08)
The master address books for the Internet were updated Feb. 4 to include
the IP version 6 (IPv6) format. The update is the beginning of a massive
effort to overhaul the Internet's addressing system to correct a shortage
available addresses. Just 14 percent of the addresses available under the
IPv4 format are still open, and those are expected to be completely
allocated by 2011. Upgrading to IPv6 would add an almost unlimited pool of
addresses to the Internet. Some companies have already begun using IPv6 on
large internal networks and Cable TV suppliers are using it for cable boxes
in consumers' homes. Still, the results of the switch will not be felt for
a long while, and home routers may eventually need to be upgraded or
replaced so they can use the longer IPv6 addresses. "It's not a Y2K
problem per se," said ICANN President Paul Twomey. "But there's going to
be a crush, so we need to get people applying for them now."
Click Here to View Full Article
to the top
Accidental Algorithms
American Scientist (02/08) Vol. 96, No. 1, P. 9; Hayes, Brian
"Holographic" or "accidental" algorithms comprise a new and unanticipated
algorithmic family that offers efficient techniques for several problems
whose solutions could only previously be worked out by brute-force
computation. The algorithms facilitate deeper investigation into the
barrier between P problems, which are problems with at least one
polynomial-time algorithm, and nondeterministic polynomial (NP) problems.
Within the NP class reside NP-complete problems, which stand out by virtue
of having a polynomial-time solution that can be adapted to rapidly solve
all problems in NP. Problems known to be NP-complete currently number in
the thousands, and collectively they form a massive weave of interdependent
computations. Harvard University's Leslie G. Valiant says holographic
algorithms get their name from the fact that their computational power
extends from the mutual cancellation of many contributions to a sum, much
like the optical interference pattern responsible for generating a
hologram. Holographic reductions tap a class of transformations that do
not necessarily connect individual problem instances, but they do retain
the number of solutions or the sum of the solutions. This is adequate for
certain counting problems.
Click Here to View Full Article
to the top
