Pre-trained large language models, such as GPT-2 and BERT, are often fine-tuned to achieve state-of-the-art performance on a downstream task. One natural example is the "Smart Reply" application where a pre-trained model is tuned to provide suggested responses for a given query message. Since the tuning data is often sensitive data such as emails or chat transcripts, it is important to understand and mitigate the risk that the model leaks its tuning data. We investigate potential information leakage vulnerabilities in a typical Smart Reply pipeline. We consider a realistic setting where the adversary can only interact with the underlying model through a frontend interface that constrains what types of queries can be sent to the model. Previous attacks do not work in these settings, but require the ability to send unconstrained queries directly to the model. Even when there are no constraints on the queries, previous attacks typically require thousands, or even millions, of queries to extract useful information, while our attacks can extract sensitive data in just a handful of queries. We introduce a new type of active extraction attack that exploits canonical patterns in text containing sensitive data. We show experimentally that it is possible for an adversary to extract sensitive user information present in the training data, even in realistic settings where all interactions with the model must go through a front-end that limits the types of queries. We explore potential mitigation strategies and demonstrate empirically how differential privacy appears to be a reasonably effective defense mechanism to such pattern extraction attacks.

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.

We consider the Knapsack Covering problem subject to a matroid constraint. In this problem, we are given an universe U of n items where item i has attributes: a cost c(i) and a size s(i). We also have a demand D. We are also given a matroid M = (U, I) on the set U. A feasible solution S to the problem is one such that (i) the cumulative size of the items chosen is at least D, and (ii) the set S is independent in the matroid M (i.e. S is in I). The objective is to minimize the total cost of the items selected, sum_{i in S}c(i). Our main result proves a 2-factor approximation for this problem. The problem described above falls in the realm of mixed packing covering problems. We also consider packing extensions of certain other covering problems and prove that in such cases it is not possible to derive any constant factor pproximations.

In this paper we study the unsplittable flow problem (UFP) on tree networks in a distributed setting. We have a set of processors (or agents) and a set of tree networks defined over some vertex set. Each processor can access a subset of the tree networks. Each edge in each of the tree networks is associated with a capacity. Each processor has a demand specified as a pair of vertices u and v, along with a profit and a height; the processor wishes to send data between u and v and requires bandwidth equal to its height. Towards that goal, the processor needs to select a tree network accessible to it. A feasible solution selects a subset of demands and schedules each selected demand on a tree network accessible to the processor owning the demand. The requirement is that for any tree network and any edge in the network, the sum of heights of demands scheduled on the network and passing through the edge must not exceed the capacity offered by the edge. The goal is to output a solution having the maximum aggregate profit. Prior work has addressed the above problem in a distributed setting for the special case where all the edge capacities are uniform, say one unit. The main contributions of this paper is to address the general case where the edge capacities can be non-uniform and arbitrary. For this case, we present distributed algorithms with poly-logarithmic approximation ratio.

In this paper we consider the problem of finding the densest subset subject to co-matroid constraints. We are given a monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/|S|. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid M a set S is feasible, iff the complement of S is independent in the matroid. Under such constraints, the problem becomes NP-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thereby we improve the approximation guarantees for the result for partition matroids in the literature.

In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem. In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose $k$ jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem. We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem.

We have a set of processors (or agents) and a set of graph networks defined over some vertex set. Each processor can access a subset of the graph networks. Each processor has a demand specified as a pair of vertices ‹u, v›, along with a profit; the processor wishes to send data between u and v. Towards that goal, the processor needs to select a graph network accessible to it and a path connecting u and v within the selected network. The processor requires exclusive access to the chosen path, in order to route the data. Thus, the processors are competing for routes/channels. A feasible solution selects a subset of demands and schedules each selected demand on a graph network accessible to the processor owning the demand; the solution also specifies the paths to use for this purpose. The requirement is that for any two demands scheduled on the same graph network, their chosen paths must be edge disjoint. The goal is to output a solution having the maximum aggregate profit. Prior work has addressed the above problem in a distibuted setting for the special case where all the graph networks are simply paths (i.e, line-networks). Distributed constant factor approximation algorithms are known for this case.

We consider the problem of scheduling jobs that require multiple resources such as memory, bandwidth and processors. For each job, the input specifies start time, finish time and profit; the input also specifies the job's requirement for each resource. Each resource has a fixed capacity (called bandwidth). A feasible solution is a subset of jobs such that for any timeslot and any resource, the total requirement of the jobs active at the timeslot does not exceed the capacity of the resource. The goal is to maximize the profit of the jobs selected. We present an approximation algorithm with provable guarantees and effective heuristics for this problem. The algorithm has an approximation ratio of O(r), where r is the number of resources. We present an experimental evaluation of our algorithms that exhibit their effectiveness.

With the growing use of virtual servers for hosting applications, management of large IT infrastructure faces new challenges. In order to reduce the capital expenditure at data centers, virtual server consolidation approaches has been the focus of attention. However, server consolidation inadvertently introduces a new point of failure, which is the physical resource on which the virtual machines are hosted. A common practice is that for a multi-tier application, different tiers of the application are hosted from a single physical machine. Although this is beneficial in maintaining low cost of ownership when the number of hosted applications is low, with increasing number of hosted applications this leads to a skewed distribution of the applications. We propose that spreading the virtual servers of different applications across the available physical resources can lead to a more resilient design for multi-tier application hosting. We formulate the problem of striping the virtual machines across multiple physical machines as an optimization problem. We propose two MIP based techniques, where the first solution is fast but may be infeasible in many cases, while the other one is better in terms of accuracy but takes more time. The solution is tested on data sets representing typical hosting environments.

We consider the problem of allocating resources for completing a collection of jobs. Each resource is specified by a start-time, finish-time and the capacity of resource available and has an associated cost, and each job is specified by a start-time, finish-time and the amount of the resource required (demand) during this interval. A feasible solution is a multiset of resources (i.e., multiple units of each resource may be picked) such that at any point of time, the sum of the capacities offered by the resources is at least the total demand of the jobs active at that point of time. The cost of the solution is the sum of the costs of the resources included in the solution (taking into account the units of the resources). The goal is to find a feasible solution of minimum cost. This problem arises naturally in many scenarios. For example, given a set of jobs, we would like to allocate some resource such as machines, memory or bandwidth in order to complete all the jobs. This problem generalizes a covering version of the knapsack problem which is known to be NP-hard. We present a constant factor approximation algorithm for this problem based on a Primal-Dual approach.

We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O ( r K ⋅ log N ), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value r K is a suitably defined Ramsey number, which is at most log K . We show that it is NP-hard to approximate the problem within a factor of Ω(log N ), even for binary tables (i.e., K =2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r 2 =2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdös.

The maximum independent set problem (MaxIS) on general graphs is known to be NP-hard to approximate within a factor of $n^{1-epsilon}$, for any $epsilon > 0$. However, there are many ``easy" classes of graphs on which the problem can be solved in polynomial time. In this context, an interesting question is that of computing the maximum independent set in a graph that can be expressed as the union of a small number of graphs from an easy class. The MaxIS problem has been studied on unions of interval graphs and chordal graphs. We study the MaxIS problem on unions of perfect graphs (which generalize the above two classes). We present an $O(sqrt{n})$-approximation algorithm when the input graph is the union of two perfect graphs. We also show that the MaxIS problem on unions of two comparability graphs (a subclass of perfect graphs) cannot be approximated within any constant factor.

We show that $S_2^psubseteq P^{prAM}$, where $S_2^p$ is the symmetric alternation class and $prAM$ refers to the promise version of the Arthur-Merlin class $AM$. This is derived as a consequence of our main result that presents an $FP^{prAM}$ algorithm for finding a small set of ``collectively irrefutable certificates'' of a given $S_2$-type matrix. The main result also yields some new consequences of the hypothesis that $NP$ has polynomial size circuits. It is known that the above hypothesis implies a collapse of the polynomial time hierarchy ($PH$) to $S_2^psubseteq ZPP^{NP}$ (Cai 2007, K"obler and Watanabe 1998). Under the same hypothesis, we show that $PH$ collapses to $P^{prMA}$. We also describe an $FP^{prMA}$ algorithm for learning polynomial size circuits for $SAT$, assuming such circuits exist. For the same problem, the previously best known result was a $ZPP^{NP}$ algorithm (Bshouty et al. 1996).

We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem to testing whether a matrix is singular, under the promise that its determinant is $0$ or $1$, thus obtaining a highly parallel SPL algorithm for bipartite planar graphs. This improves the earlier known bounds of non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Our techniques are elementary and simple.

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. This completely settles the question regarding the complexity of modular computation of the number of spanning trees in planar graphs. The techniques used rely heavily on algebraic-topology. In the spirit of counting problems modulo 2k, we also exhibit a highly parallel oplusL algorithm for finding the value of a Permanent modulo 2k. Previously, the best known result in this direction was Valiant's result that this problem lies in P.

We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O(rK • log N), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value rK is a suitably defined Ramsey number, which is at most log K. We show that it is NP-hard to approximate the problem within a factor of Ω(log N), even for binary tables (i.e. K=2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r2=2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdos.

We study the complexity of reachability problems on various classes of grid graphs. Reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1under AC0reductions but are not known to be hard far L; they thus give insight into the structure of L. In addition to explicating the structure of L, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. (2001), who showed that reachability in series-parallel digraphs is solvable in L. We show that reachability for single-source multiple sink planar dags is solvable in L

We show that ACC/sup 0/ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC/sup 0/. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that thickness two already suffices to capture all of NC/sup 1/.

We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.

Extends the lower-bound techniques of L. Fortnow (2000) to the unbounded-error probabilistic model. A key step in the argument is a generalization of V.A. Nepomnjas/spl caron/c/spl caron/ii/spl breve/'s (1970) theorem from the Boolean setting to the arithmetic setting. This generalization is made possible due to the recent discovery of logspace-uniform TC/sup 0/ circuits for iterated multiplication (A. Chiu et al., 2000). As an example of the sort of lower bounds that we obtain, we show that MAJ-MAJSAT is not contained in PrTiSp(n/sup 1+o(1)/, n/sup /spl epsiv//) for any /spl epsiv/<1. We also extend one of Fortnow's lower bounds, from showing that S~A~T~ does not have uniform NC/sup 1/ circuits of size n/sup 1+o(1)/, to a similar result for SAC/sup 1/ circuits.