Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

We present a randomized procedure named Hierarchical Sampling from Sketches (Hss) that can be used for estimating a class of functions over the frequency vector f of update streams of the form . We illustrate this by applying the Hss technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p≥2 and for estimating the entropy of a data stream. Preliminary version of this paper appeared as the following conference publications. “Simpler algorithm for estimating frequency moments of data streams,” Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh and Chandan Saha, Proceedings of the ACM Symposium on Discrete Algorithms, 2006, pp. 708–713 and “Estimating entropy over data streams,” Lakshminath Bhuvanagiri and Sumit Ganguly, Proceedings of the European Symposium on Algorithms, LNCS, vol. 4168, pp. 148–159, Springer, 2006.     

The Calculus of Relations as a Foundation for Mathematics

A variable-free, equational logic $\mathcal{L}^\timesA variable-free, equational logic based on the calculus of relations (a theory of binary relations developed by De Morgan, Peirce, and Schr?der during the period 1864–1895) is shown to provide an adequate framework for the development of all of mathematics. The expressive and deductive powers of are equivalent to those of a system of first-order logic with just three variables. Therefore, three-variable first-order logic also provides an adequate framework for mathematics. Finally, it is shown that a variant of may be viewed as a subsystem of sentential logic. Hence, there are subsystems of sentential logic that are adequate to the task of formalizing mathematics. This paper is an expanded version of a talk given by the author at the Special Session on Automated Reasoning in Mathematics and Logic, held March 8–10, 2002, at the Georgia Institute of Technology, during the Joint Southeastern Section MAA/Southeast Regional AMS Meeting. The session was organized by Johan G. F. Belinfante.     

Logic-based automated multi-issue bilateral negotiation in peer-to-peer e-marketplaces

We present a novel logic-based framework to automate multi-issue bilateral negotiation in e-commerce settings. The approach exploits logic as communication language among agents, and optimization techniques in order to find Pareto-efficient agreements. We introduce , a propositional logic extended with concrete domains, which allows one to model relations among issues (both numerical and non-numerical ones) via logical entailment, differently from well-known approaches that describe issues as uncorrelated. Through it is possible to represent buyer’s request, seller’s supply and their respective preferences as formulas endowed with a formal semantics, e.g., “if I spend more than 30000 € for a sedan then I want more than a two-years warranty and a GPS system included”. We mix logic and utility theory in order to express preferences in a qualitative and quantitative way. We illustrate the theoretical framework, the logical language, the one-shot negotiation protocol we adopt, and show we are able to compute Pareto-efficient outcomes, using a mediator to solve an optimization problem. We prove the computational adequacy of our method by studying the complexity of the problem of finding Pareto-efficient solutions in our setting.     

Simplifying Proofs in Fitch-Style Natural Deduction Systems

We present an algorithm for simplifying Fitch-style natural-deduction proofs in classical first-order logic. We formalize Fitch-style natural deduction as a denotational proof language,, with a rigorous syntax and semantics. Based on that formalization, we define an array of simplifying transformations and show them to be terminating and to respect the formal semantics of the language. We also show that the transformations never increase the size or complexity of a deduction – in the worst case, they produce deductions of the same size and complexity as the original. We present several examples of proofs containing various types of superfluous “detours,” and explain how our procedure eliminates them, resulting in smaller and cleaner deductions. All of the transformations are fully implemented in SML-NJ, and the complete code listing is available on the Web.     

PolicyUpdater: a system for dynamic access control

PolicyUpdater is a fully-implemented authorisation system that provides policy evaluations as well as dynamic policy updates. These functions are achieved by the use of a logic-based language, , to represent the underlying access control policies, constraints and update propositions. The system performs access control query evaluations and conditional policy updates by translating the language policies to a normal logic program in a form suitable for evaluation using the Stable Model semantics. In this paper, we show the underlying mechanisms that make up the PolicyUpdater system, including the theoretical foundation of its formal language, system structure, implementation issues and performance analysis.     

Fuzzy logic models in a category of fuzzy relations

We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models . Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572.     

Set-driven and rearrangement-independent learning of recursive languages

This paper studies the impact of order independence to the learnability of indexed families of uniformly recursive languages from positive data. In particular, we considerset-driven andrearrangement-independent learners, i.e., learning devices whose output exclusively depends on the range and on the range and length of their input, respectively. The impact of set-drivenness and rearrangement-independence on the behavior of learners to their learning power is studied in dependence on thehypothesis space the learners may use. We distinguish betweenexact learnability ( has to be inferred with respect to ),class-preserving learning ( has to be inferred with respect to some suitably chosen enumeration of all the languages from ), andclass-comprising inference ( has to be learned with respect to some suitably chosen enumeration of uniformly recursive languages containing at least all the languages from ). Furthermore, we consider the influence of set-drivenness and rearrangement-independence for learning devices that realize thesubset principle to different extents. Thereby we distinguish betweenstrong-monotonic, monotonic, andWeakmonotonic orconservative learning. The results obtained are threefold. First, rearrangement-independent learning does not constitute a restriction except in the case of monotonic learning. Next, we prove that for all but two of the learning models considered set-drivenness is a severe restriction. However, class-comprising set-drivenconservative learning is exactly as powerful as unrestricted class-comprisingconservative learning. Finally, the power of class-comprising set-driven learning in the limit is characterized by equating the collection of learnable indexed families with the collection of class-comprisingly conservatively inferable indexed families. These results considerably extend previous work done in the field (see, e.g., [20] and [5]). This is a substantially revised version of the authors' paper inProceedings of the 5th International Workshop on Algorithmic Learning Theory (ALT '94), Lecture Notes in Artificial Intelligence, Vol. 872, pp. 453–468, Springer-Verlag, Berlin. The first author has been partially supported by the German Ministry for Research and Technology (BMFT) under Grant No. 01 IW 101.     

Performing work in broadcast networks

We consider the problem of how to schedule t similar and independent tasks to be performed in a synchronous distributed system of p stations communicating via multiple-access channels. Stations are prone to crashes whose patterns of occurrence are specified by adversarial models. Work, defined as the number of the available processor steps, is the complexity measure. We consider only reliable algorithms that perform all the tasks as long as at least one station remains operational. It is shown that every reliable algorithm has to perform work Ω(t+p√t) even when no failures occur. An optimal deterministic algorithm for the channel with collision detection is developed, which performs work (t+p√t). Another algorithm, for the channel without collision detection, performs work (t+p √t+ p min {f,t}), where f < p is the number of failures. This algorithm is proved to be optimal, provided that the adversary is restricted in failing no more than f stations. Finally, we consider the question if randomization helps against weaker adversaries for the channel without collision detection. A randomized algorithm is developed which performs the expected minimum amount (t+p√t) of work, provided that the adversary may fail a constant fraction of stations and it has to select failure-prone stations prior to the start of an execution of the algorithm. The work of the first author is supported by the NSF Grant 0310503. A preliminary version of this paper appeared as “The do-all problem in broadcast networks,” in Proceedings, 20th ACM Symposium on Principles of Distributed Computing, Newport, Rhode Island, 2001, pp. 117–126.     

The superconvergence of composite Newton–Cotes rules for Hadamard finite-part integral on a circle

We study the general (composite) Newton–Cotes rules for the computation of Hadamard finite-part integral on a circle with the hypersingular kernel and focus on their pointwise superconvergence phenomenon, i.e., when the singular point coincides with some a priori known point, the convergence rate is higher than what is globally possible. We show that the superconvergence rate of the (composite) Newton–Cotes rules occurs at the zeros of a special function and prove the existence of the superconvergence points. The relation between and defined in Wu and Sun (Numer Math 109:143–165, 2008) is established, and the efficient calculation of Cotes coefficients is also discussed. Several numerical examples are provided to validate the theoretical analysis.      

Alternative 2D Shape Representations using the Symmetry Set

Among the many attempts made to represent families of 2D shapes in a simpler way, the Medial Axis takes a prominent place. Its graphical representation is intuitively appealing and can be computed efficiently. Small perturbations of the shape can have large impact on the and are regarded as instabilities, although these changes are mathematically known from the investigations on a super set, the Symmetry Set . This set has mainly been in a mathematical research stage, partially due to computational aspects, and partially due to its unattractive representation in the plane. In this paper novel methods are introduced to overcome both aspects. As a result, it is possible to represent the as a string is presented. The advantage of such a structure is that it allows fast and simple query algorithms for comparisons. Second, alternative ways to visualize the are presented. They use the distances from the shape to the set as extra dimension as well as the so-called pre-Symmetry Set and anti-Symmetry Set. Information revealed by these representations can be used to calculate the linear string representation structure. Example shapes from a data base are shown and their data structures derived. Arjan Kuijper is Senior Researcher at the Johann Radon Institute (RICAM) of the Austrian Academy of Sciences in Linz, Austria. He received his M.Sc. degree in applied mathematics in 1995 from the University of Twente, The Netherlands. During the period 1996–1997 he worked at ELTRA Parkeergroep, Ede, The Netherlands. He has been a Ph.D. student (1997–2001), associate researcher (2001–2002), and postdoc (202) at the Institute of Information and Computing Sciences of Utrecht University. In 2003-2005 he served as assistant research professor at the IT University of Copenhagen in Denmark. His interest subtends all mathematical aspects of image and shape analysis, notably multi-scale representations (scale spaces), catastrophe and singularity theory, medial axes and symmetry sets, partial differential equations, singular theories, and their applications. Ole Fogh Olsen is associate professor in the image group at the IT University of Copenhagen. He received the PhD degree in 2000 in computer science from University of Copenhagen, Denmark. Main research interest areas are image analysis, medical image analysis and computer vision with focus on scale space theory, differential geometry, singularity theory, statistics, segmentation, optic flow and shape modelling. Peter Giblin is Professor of Mathematics at the University of Liverpool and a former Head of the Mathematical Sciences Department. He joined the staff there in 1967 and has been visiting professor at the University of North Carolina at Chapel Hill, Five Colleges in Amherst, Massachusetts, and Brown University. His research interests are in singularity theory and its applications to differential geometry and computer vision. Mads Nielsen received a MSc in 1992 and a PhD in 1995 both in computer science from DIKU, Department of Computer Science, University of Copenhagen, Denmark. During his PhD studies he spent one year 93–94 at the Robotvis lab at INRIA, Sophia-Antipolis, France. In the second half of 1995 he was post-doc at the Image Sciences Institute of Utrecht University, The Netherlands. In 1996 he was joint post-doc at DIKU and 3D-Lab, School of Dentistry, University of Copenhagen, where he served as assistant professor 1997–99. In 1998–99 he served as external associate professor at Institute of Mathematical Modelling, Technical University of Denmark. April 1999 he became the first associate professor at the new IT University of Copenhagen. Since June 2002 he has been professor the same place heading the Image Analysis Group. He is head of the PhD-studies at ITU, member of the Academical Council of ITU, General chair of MICCAI 2006, member of the editorial board of IJCV and JMIV. His research interests are in the mathematical foundation of image analysis, the computational aspects, and the applications, especially in the medical area.     

A graph theoretic approach to authorization delegation and conflict resolution in decentralised systems

The problem of resolving conflicts in delegated authorizations has not been systematically addressed by researchers. In (Ruan and Varadharajan in Proceedings of the 7th Australasian Conference on Information Security and Privacy, pp. 271–285, 2002) we proposed a graph based framework that supports authorization delegation and conflict resolution. In this paper, we have extended the model to allow grantors of delegations to express degrees of certainties about their delegations and grants of authorizations. This expression of certainty gives the subjects (e.g. users) more flexibility to control their delegations of access rights. We propose a new conflict resolution policy based on weighted lengths of authorization paths. This policy provides a greater degree of flexibility in that it enables to specify and analyse the effect of predecessor-successor relationship as well as the weights of authorizations on the conflicts. We present a detailed algorithm to evaluate authorization delegations and conflict resolutions. The correctness proof and time complexity of the algorithm are also provided. Since in a dynamic environment, the authorization state is not static, we have considered how authorization state changes occur and have developed an algorithm to analyse authorization state transformations and given correctness proofs. Finally, we discuss how to achieve a global decision policy from local authorization policies in a distributed environment. Three integration models based on the degrees of node autonomy are proposed, and different strategies of integrating the local policies into the global policies in each model are systematically discussed.     

Topology on the set of R 0 semantics for R 0 algebras

This paper introduces the concepts of R ₀ valuation, R ₀ semantic, countable R ₀ category , R ₀ fuzzy topological category , etc. It is established in a natural way that the fuzzy topology δ and its cut topology on the set Ω _M consisting of all R ₀ valuations of an R ₀ algebra M, and some properties of fuzzy topology δ and its cut topology are investigated carefully. Moreover, the representation theorem for R ₀ algebras by means of fuzzy topology is given, that is to say the category is equivalent to the category . By studying the relation between valuations and filters, the Loomis–Sikorski theorem for R ₀ algebras is obtained. As an application, K-compactness of the R ₀ logic is discussed.     

Self-adaptation of evolution strategies under noisy fitness evaluations

This paper investigates the self-adaptation behavior of ()-evolution strategies (ES) on the noisy sphere model. To this end, the stochastic system dynamics is approximated on the level of the mean value dynamics. Being based on this “microscopic” analysis, the steady state behavior of the ES for the scaled noise scenario and the constant noise strength scenario will be theoretically analyzed and compared with real ES runs. An explanation will be given for the random walk like behavior of the mutation strength in the vicinity of the steady state. It will be shown that this is a peculiarity of the -ES and that intermediate recombination strategies do not suffer from such behavior.     

Strong non-standard completeness for fuzzy logics

In this paper we are going to introduce the notion of strong non-standard completeness (SNSC) for fuzzy logics. This notion naturally arises from the well known construction by ultraproduct. Roughly speaking, to say that a logic is strong non-standard complete means that, for any countable theory Γ over and any formula φ such that , there exists an evaluation e of -formulas into a -algebra such that the universe of is a non-Archimedean extension of the real unit interval [0,1], e is a model for Γ, but e(φ) < 1. Then we will apply SNSC to prove that various modal fuzzy logics allowing to deal with simple and conditional probability of infinite-valued events are complete with respect to classes of models defined starting from non-standard measures, that is measures taking value in .     

Faster communication in known topology radio networks

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D + O(log³ n), and a randomized algorithm for computing a radio schedule of length D + O(log² n). These results improve on the best currently known D + O(log⁴ n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log³ n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time , for any network with the diameter D = Ω(log ⁱ⁺⁴ n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log³ n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms 52(1), 8–25, 2004). The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering. Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool.     

Key substitution attacks revisited: Taking into account malicious signers

Given a signature sfor some message malong with a corresponding public verification key yin a key substitution attack an attacker derives another verification key ≠ y—possibly along with a matching secret key—such that sis also a valid signature of mfor the verification key . Menezes and Smart have shown that with suitable parameter restrictions DSA and EC-DSA are immune to such attacks. Here, we show that in the presence of a malicious signer key substitution attacks against several signature schemes that are secure in the sense introduced by Menezes and Smart can be mounted. While for EC-DSA such an attack is feasible, other established signature schemes, including EC-KCDSA, can be shown to be secure in this sense.     

Hierarchical matrix preconditioners for the Oseen equations

Hierarchical matrices provide a technique for the data-sparse approximation and matrix arithmetic of large, fully populated matrices. In particular, approximate inverses as well as approximate LU factorizations of finite element stiffness matrices may be computed and stored in nearly optimal complexity. In this paper, we develop efficient -matrix preconditioners for the Oseen equations. In particular, -matrices will provide efficient preconditioners for the auxiliary (scalar) discrete convection–diffusion and pressure Schur complement problems. We will provide various numerical tests comparing the resulting preconditioners with each other. This work was supported in part by the US Department of Energy under Grant No. DE-FG02-04ER25649 and in part by the National Science Foundation under grant No. DMS-0408950.     

On the Relation between States and Maps in Infinite Dimensions

Relations between states and maps, which are known for quantum systems in finitedimensional Hilbert spaces, are formulated rigorously in geometrical terms with no use of coordinate (matrix) interpretation. In a tensor product realization they are represented simply by a permutation of factors. This leads to natural generalizations for infinite-dimensional Hilbert spaces and a simple proof of a generalized Choi Theorem. The natural framework is based on spaces of Hilbert-Schmidt operators and the corresponding tensor products of Hilbert spaces. It is proved that the corresponding isomorphisms cannot be naturally extended to compact (or bounded) operators, nor reduced to the trace-class operators. On the other hand, it is proven that there is a natural continuous map from trace-class operators on (with the nuclear norm) into compact operators mapping the space of all bounded operators on into trace class operators on (with the operator-norm). Also in the infinite-dimensional context, the Schmidt measure of entanglement and multipartite generalizations of state-maps relations are considered in the paper.     

Low-randomness constant-round private XOR computations

In this paper we study the randomness complexity needed to distributively perform k XOR computations in a t-private way using constant-round protocols in the case in which the players are honest but curious. We show that the existence of a particular family of subsets allows the recycling of random bits for constant-round private protocols. More precisely, we show that after a 1-round initialization phase during which random bits are distributed among n players, it is possible to perform each of the k XOR computations using two rounds of communication. For , for any c < 1/2, we design a protocol that uses O(kt ²log n) random bits.     

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.