Computer Science Colloquia
Overview:
Whither Wireless?
| |
Adding Unsafe Constraints to Improve SAT Solver Performance
| |
(Security Series) The Art and Science of Information Hiding
| |
Ex-Ante Information and the Design of Keyword Auctions
| |
The list of Colloquia for 2007-2008 |
September 3, 2008, 4:00pm,
257 FPAT (Refreshments served 3:30, 763 FPAT)
Title: Ex-Ante Information and the Design of Keyword Auctions
De Liu
Gatton College of Business and Economics, University of Kentucky
Abstract:
Keyword advertising, including sponsored links and contextual
advertising, powers many of today's online information services
such as search engines and Internet-based emails. This paper
examines the design of keyword auctions, a novel mechanism that
keyword advertising providers such as Google and Yahoo! use to
allocate advertising slots. In our keyword auction model,
advertisers bid their willingness-to-pay per click on their
advertisements, and the advertising provider can weight
advertisers' bids differently and require different minimum bids
based on advertisers' click-generating potential. We study the
impact and design of such weighting schemes and minimum-bids
policies. We find that weighting scheme determines how advertisers
with different click-generating potential match in equilibrium.
Minimum bids exclude low-valuation advertisers and at the same
time may distort the equilibrium matching. The efficient design of
keyword auctions requires weighting advertisers' bids by their
expected click-through-rates, and requires the same minimum
weighted bids. The revenue-maximizing weighting scheme may or may
not favor advertisers with low click-generating potential. The
revenue-maximizing minimum-bid policy differs from those
prescribed in the standard auction design literature. Keyword
auctions that employ the revenue-maximizing weighting scheme and
differentiated minimum bid policy can generate higher revenue than
standard fixed-payment auctions. We draw managerial implications
for pay-per-click and other pay-for-performance auctions and
discuss potential applications to other areas.
(joint work with Jianqing Chen, and Andrew Whinston)
Host: Professor J. Goldsmith.
October 8, 2008, 4:00pm,
257 FPAT (Anderson Tower). (Refreshments served 3:30, 763 FPAT)
(Security Series) Title: The Art and Science of Information Hiding
Samson Cheung
Electrical and Computer Engineering Department, University of Kentucky
Abstract:
A treasure map, drawn with invisible ink,
Gradually reveals itself by putting a candle
light underneath a famous painting ...
Such a plotline can be found in many adventure stories and just about every Nicholas Cage's movie. While the arts of hiding secret information can be traced back two thousand years ago to the ancient Greeks, the serious study of the science of modern digital information hiding did not begin until the late eighties. Since then, we have applied information hiding techniques in a great variety of applications ranging from anti-counterfeiting, covert communication to error correction and multimedia privacy. Also we have developed sophisticated models to better understand the fundamental limits on the capacity of hiding information in various data sources, the robustness against both benign and malicious attacks as well as the detectability of the hidden messages. In this installment of the seminar series in computer security, I will survey some of these applications and provide an overview on the mathematical modeling of information hiding. My focus will be on hiding information in digital signals like images and videos. I will review a number of information hiding techniques including the earlier spread spectrum schemes and the more recent binning-based quantization schemes. I will also discuss practical designs that enables fully reversible hiding and public-key hiding.
October 10, 2008, 4:00 p.m.,
257 FPAT (Anderson Tower). (Refreshments served 3:30, 763 FPAT)
Title: Adding Unsafe Constraints to Improve SAT Solver Performance (joint work
with M. Kouril and S. Weaver)
John Franco
EECSE Department, University of Cincinnati
Abstract:
We examine the structure of CNF representations of common problems, such as bounded model checking, in Formal Verification. We observe that this structure arises in a variety of other difficult problems as well. We show why such structures are difficult for current Satisfiability solvers: namely, that inferences typically can be discovered only after a large number of variables have been set. Thus, for example, clause learning is not as effective on such structures as we would like it to be. We propose some ideas which may lead to significantly reduced solution times for these and other problems. These have have to do with guessing inferences a priori BASED ON SOLUTION STRUCTURE and not formula structure as is typically done in preprocessing. That is, the structure of solutions that can be found for smaller versions of a problem are examined for necessary patterns of variable values - either to support or reject the solutions - and constraints are added to the original formula to enforce inclusion or rejection of these patterns. Adding guessed constraints can reduce search enormously but may eliminate some solution traces, so at some search depth these guessed constraints are removed and search continues to the end. The trick is to prevent all solutions from being lost if at least one exists. For Formal Verification problems this means, at worst, getting a result with a certain confidence. Some other problems can be solved more directly. For example, this idea was used to find a van der Waerden number W(2,6) = 1132 by first getting a bound then using solution patterns to reduce a full search to something manageable. We are still refining this technique.
Host: Professor V. Marek.
October 15, 2008, 4:00 p.m.,
206, Student Center.
Title: Whither Wireless?
Craig Partridge
BBN Corp.
Abstract:
We are in the early years of a revolution in wireless communications and the future holds many possibilities. Central to this revolution is the ability to dynamically program (and reprogram) radios, so that innovation in radios will come at the speed of software releases rather than hardware releases. But programmability is only part of the story. There are regulatory issues. There are potential innovations in energy use. In this talk I sketch how how research innovations in wireless are likely to unfold over the next dozen years or so with some (naive) discussions of how the innovations will affect the marketplace. I'll follow this talk with a brief talk on the current status of GENI.
Bio:
Dr. Craig Partridge is Chief Scientist for Networking Research at BBN Technologies and Outreach Director for the GENI Project Office. Craig's been doing data communications research since 1983 and his contributions include designing how Internet email is routed and co-developing the world's first 40 Gbps Internet router. He's an IEEE and ACM fellow and a former editor-in-chief of both IEEE Network Magazine and ACM Computer Communication Review. He received his A.B., M.Sc. and Ph.D. degrees from Harvard University.
Host: Professor J. Griffioen.