We investigate the label complexity of active learning under some smoothness assumptions on the data-generating process.We propose a procedure, PLAL, for “activising” passive, sample-based learners. The procedure takes an unlabeledsample, queries the labels of some of its members, and outputs a full labeling of that sample. Assuming the data satisfies “Probabilistic Lipschitzness”, a notion of clusterability, we show that for several common learning paradigms, applying our procedure as a preprocessing leads to provable label complexity reductions (over any “passive”learning algorithm, under the same data assumptions). Our labeling procedure is simple and easy to implement. We complement our theoretical findings with experimental validations.

We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances.

We have implemented a firewall application on a Network Interface Card (NIC). We have tested the CPU utilization and the bandwidth in a variety of scenarios. The benefits of offloading code are most pronounced when rejecting packets. Our results suggest significant benefits of offloading applications and in particular firewall logic to a NIC. I. INTRODUCTION There are many communication applications that act on every incoming packet. Offloading such applications to the network interface card (NIC) has many potential advantages. Utilizing the onboard computational power of the NIC can reduce the demands put on the CPU. If the NIC can process incoming information it can avoid costly interrupts to the CPU. In addition, the NIC can serve as a gatekeeper thus avoiding potential threats to the CPU. Furthermore, applications on a NIC can be built such that they are system and OS indepen- dent. An application of particular promise for offloading is a firewall application. Since a firewall is an application that filters packets by a user defined security policy, earlier filtering (especially discarding packets) has a potential for significant improvements in performance. A firewall application on a NIC also has the additional advantage that it is harder for an adversary to modify than a software application running at the host. We have designed and implemented a firewall application which we call SCIRON (Secure-Communication IntegRated Over NIC) on a NIC. The system consists of three elements: The firewall logic, a management console and a policy builder. This paper presents SCIRON, and shows that offloading full applications has significant advantages and market potential more so than TCP offload engines (9) (TOEs) or protocol specific offloaded extensions.