^June July – 2012 ^August

First is the FiniteSat algorithm, an efficient detection method for finite satisfiability problems in UML class diagrams. I will sketch the main arguments for its correctness and scope. The algorithm is strengthened by a propagation method for implied missing constraints. Next, I will present an identification method which points to the causes for finite satisfiability problems. > The second contribution of my research deals with analysis of inter-association constraints in UML class diagrams. These constraints although intensively used in the UML meta-model, have obscure and contradictory semantics. The analysis reaches semantic agreements based on constraint observables that minimize meta-model changes. This analysis has yielded recommendations and guidelines for modelers. > The last part of the talk relates to the human factor in modeling. We describe a catalog of anti-patterns that characterize correctness and quality problems in class diagrams. Formalization of the anti-patterns involves a template-oriented extension of the class diagram language. The catalog role was tested in a series of experiments. The novelty of the research lies in the integration of formal and educational methods for improving model design quality in class diagrams.

Privacy Preserving Data Publishing (PPDP) is a research field that deals with the development of methods to enable publishing of data while minimizing distortion, for maintaining usability on one hand, and respecting privacy on the other hand. Sequential release is a scenario of data publishing where multiple releases of the same underlying table are published over a period of time. A violation of privacy, in this case, may emerge from any one of the releases, or as a result of joining information from different releases. Similarly to [Wang and Fung 2006], our privacy definitions limit the ability of an adversary who combines information from all releases, to link values of the quasi-identifiers to sensitive values. We extend the framework that was considered in [Wang and Fung 2006] in three ways: We allow a greater number of releases, we consider the more flexible local recoding model of ``cell generalization" (as opposed to the global recoding model of ``cut generalization" in [Wang and Fung 2006]), and we include the case where records may be added to the underlying table from time to time. Our extension of the framework requires also to modify the manner in which privacy is evaluated. We show that while [Wang and Fung 2006] based their privacy evaluation on the notion of the Match Join between the releases, it is no longer suitable for the extended framework considered here. We define more restrictive types of join between the published releases (the Full Match Join and the Kernel Match Join) that are more suitable for privacy evaluation in this context. We then present a top-down algorithm for anonymizing sequential releases in the cell generalization model, that is based on our modified privacy evaluations. Our theoretical study is followed by experimentation that demonstrates a staggering improvement in terms of utility due to the adoption of the cell generalization model, and exemplifies the correction in the privacy evaluation as offered by using the Full or Kernel Match Joins instead of the Match Join.

A client on the earth surface wants to know his/her geographical location. The Global Positioning System (GPS) was built to ful…ll this task. It works as follows: Satellites send to earth their location. For simplicity, the location of a satellite is a bit b 2 f1g: The satellite transmits to the earth a sequence of N  1000 complex numbers S[0]; S[1]; :::; S[N 􀀀1] multiplied by its location b: The client receives the sequence R of the form R[n] = b
0
e 2i N !0
n
S[n +  0] +W[n]; (1) where 0 2 C is the complex amplitude, with j0j  1; !0 2 ZN encodes the radial velocity of the satellite with respect to the client,  0 2 ZN encodes the distance between the satellite and the client, and W is a random white noise. The GPS Problem is: Problem 1 (GPS Problem) Design S, and an e¤ective method of extracting (b;  0) from S and R satisfying (1). A client can compute his/her location by knowing the locations of at least three satellites and distances to them. The current sequences S which are used are pseudo-random and the algorithm they support takes O(N2 logN) arithmetic operations: In my lecture I will explain our recent construction of sequences S that allow us to introduce a much faster algorithm called the "Flag Method". It solves the GPS Problem in O(N logN) operations. This is a joint work with A. Fish (Mathematics, Madison), R. Hadani (Math- ematics, Austin), A. Sayeed (Electrical and Computer Engineering, Madison), and O. Schwartz (Electrical Engineering and Computer Science, Berkeley).