IBM Research welcomes members of the research community to our seminars. To ensure compliance with IBM security guidelines, we request you to contact the seminar host in advance. When you arrive at the Research lab, please provide the host's name to the receptionist.
| On Basing Lower-Bounds for Learning on Worst-Case Assumptions | ||||
| Benny Applebaum | On: | 8-May-2008 11:00 AM - 12:00 PM | ||
| Princeton University | At: | Watson Research Center (Hawthorne), Room 3N-J21 | ||
| Host: | Rosario Gennaro | |||
Abstract: We consider the question of whether P \neq NP implies that there exists some concept class that is efficiently representable but is still hard to learn in the PAC model of Valiant (CACM '84). We show that unless the Polynomial Hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if a language L reduces to the task of improper learning circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard. Joint work with Boaz Barak and David Xiao | ||||
| Internet path-quality monitoring using secure sketches | ||||
| Sharon Goldberg | On: | 7-May-2008 04:00 PM - 05:00 PM | ||
| Princeton University | At: | Watson Research Center (Hawthorne), Room 3S-K24 | ||
| Host: | Rosario Gennaro | |||
Abstract: Internet routers need effective monitoring techniques to drive routing decisions and detect contract violations. Secure path-quality monitoring (PQM) protocols provide this functionality by robustly raising an alarm when the packet-loss rate on a path becomes too high, even when adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets. In this talk I will present our new secure PQM protocol based on sketching, that is efficient enough to be deployed in the highly constrained environment of high-speed routers. Our protocol combines sublinear second-moment estimation techniques with ideas from cryptography and requires O(log T) storage in order to monitor T packets sent on an Internet data path; e.g., monitoring billions of packets requires only 200-600 bytes of storage and a single IP packet of communication. Time permitting, I will discuss PQM protocols designed for the client-server setting, as well as the relationship between our PQM protocols and the Adversarial Sketch Model as defined by Mironov, Naor, and Segev in their new STOC 2008 paper. Joint work with David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford | ||||