Search

Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the number of triangles in a graph using only polylogarithmic queries when \emph{the number of triangles on any edge in the graph is polylogarithmically bounded}. Our query oracle {\em Tripartite Independent Set} (TIS) takes three disjoint sets of vertices $A$, $B$ and $C$ as inputs, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of \emph{group queries} (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the {\em Bipartite Independent Set} (BIS) query oracle of Beame {\em et al.} (ITCS 2018). We extend the algorithmic framework of Beame {\em et al.}, with \tis replacing \bis, for approximately counting triangles in graphs., 27 pages. A preliminary version has been appeared in ISAAC'2019. This version contains improved bound on query complexity

The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial k centers when using the Lloyd's algorithm for the k-means problem. It was conjectured by Brunsch and Roglin 9 that k-means++ behaves well for datasets with small dimension. More specifically, they conjectured that the k-means++ seeding algorithm gives O ( log ? d ) approximation with high probability for any d-dimensional dataset. In this work, we refute this conjecture by giving two dimensional datasets on which the k-means++ seeding algorithm achieves an O ( log ? k ) approximation ratio with probability exponentially small in k. This solves open problems posed by Mahajan et al. 12 and by Brunsch and Roglin 9.

Sintered hubs are typically used in automotive transmission gearbox synchronizer due to its near net shape. Sintered hubs have complex design due to their functional and packaging requirements. The required hardness and density are obtained using different grades of sintered powders, sintering temperature and the press load capacity. Many sintering materials with good mechanical properties are available with or without secondary heat treatment. However, there are concerns of sintered hub failure in the vehicle validation or during the intended service of the vehicle. This paper describes the design of automotive gearbox synchronizer sintered hub to meet the endurance life of the gearbox. The sintered hub wear on the synchronizer hub face and tooth flank are studied experimentally in the gearbox rig level test. This study is done for materials such as medium carbon sinter-hardened PM grade, sintered high carbon diffusion alloyed PM grade and sintered high carbon diffusion alloyed PM grade along with induction hardening process. The different gearbox loading conditions cause wear up to 70 µm on the synchronizer hubs. The hub to gear interface as well as hub tooth to sleeve tooth interface contact pressures and wear are studied based on the test results. The amount of hub digging is proportional to the applied load and the test duration. The medium carbon sinter-hardened material can withstand less pressure and less time when compared with the high carbon diffusion alloyed material with induction hardening. The design considerations to avoid hub digging and or material changes with process changes are analyzed. This paper also describes prediction methodology in FEA for the failure modes of synchronizer hub spline tooth crack and strut detent slot crack. The physical validation shows good trend matching correlation with the high-fidelity approach in CAE.

Ashtiani et al. (NIPS 2016) introduced a semi-supervised framework for clustering (SSAC) where a learner is allowed to make same-cluster queries. More specifically, in their model, there is a query oracle that answers queries of the form “given any two vertices, do they belong to the same optimal cluster?”. In many clustering contexts, this kind of oracle queries are feasible. Ashtiani et al. showed the usefulness of such a query framework by giving a polynomial time algorithm for the k-means clustering problem where the input dataset satisfies some separation condition. Ailon et al. extended the above work to the approximation setting by giving an efficient \((1+\varepsilon )\)-approximation algorithm for k-means for any small \(\varepsilon > 0\) and any dataset within the SSAC framework. In this work, we extend this line of study to the correlation clustering problem. Correlation clustering is a graph clustering problem where pairwise similarity (or dissimilarity) information is given for every pair of vertices and the objective is to partition the vertices into clusters that minimise the disagreement (or maximises agreement) with the pairwise information given as input. These problems are popularly known as \(\mathsf {MinDisAgree}\) and \(\mathsf {MaxAgree}\) problems, and \(\mathsf {MinDisAgree}[k]\) and \(\mathsf {MaxAgree}[k]\) are versions of these problems where the number of optimal clusters is at most k. There exist Polynomial Time Approximation Schemes (PTAS) for \(\mathsf {MinDisAgree}[k]\) and \(\mathsf {MaxAgree}[k]\) where the approximation guarantee is \((1+\varepsilon )\) for any small \(\varepsilon \) and the running time is polynomial in the input parameters but exponential in k and \(1/\varepsilon \). We get a significant running time improvement within the SSAC framework at the cost of making a small number of same-cluster queries. We obtain an \((1+ \varepsilon )\)-approximation algorithm for any small \(\varepsilon \) with running time that is polynomial in the input parameters and also in k and \(1/\varepsilon \). We also give non-trivial upper and lower bounds on the number of same-cluster queries, the lower bound being based on the Exponential Time Hypothesis (ETH). Note that the existence of an efficient algorithm for \(\mathsf {MinDisAgree}[k]\) in the SSAC setting exhibits the power of same-cluster queries since such polynomial time algorithm (polynomial even in k and \(1/\varepsilon \)) is not possible in the classical (non-query) setting due to our conditional lower bounds. Our conditional lower bound is particularly interesting as it not only establishes a lower bound on the number of same cluster queries in the SSAC framework but also establishes a conditional lower bound on the running time of any \((1+\varepsilon )\)-approximation algorithm for \(\mathsf {MinDisAgree}[k]\).

The classical center based clustering problems such as k-means/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. For instance, consider the r -gather clustering problem where there is an additional constraint that each of the clusters should have at least r points or the capacitated clustering problem where there is an upper bound on the cluster sizes. Consider a variant of the k-means problem that may be regarded as a general version of such problems. Here, the optimal clusters O 1, ..., O k are an arbitrary partition of the dataset and the goal is to output k-centers c 1, ..., c k such that the objective function ${\sum }_{i = 1}^{k} {\sum }_{x \in O_{i}} ||x - c_{i}||^{2}$ is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter e > 0, let l denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1 + e) approximation w.r.t. the objective function above. In this paper, we show an upper bound on l by giving a randomized algorithm that outputs a list of $2^{\tilde {O}(k/\varepsilon )}$ k-centers. We also give a closely matching lower bound of $2^{\tilde {\Omega }(k/\sqrt {\varepsilon })}$ . Moreover, our algorithm runs in time $O \left (n d \cdot 2^{\tilde {O}(k/\varepsilon )} \right )$ . This is a significant improvement over the previous result of Ding and Xu (2015) who gave an algorithm with running time O(n d ⋅ (log n) k ⋅ 2 p o l y(k/e)) and output a list of size O((log n) k ⋅ 2 p o l y(k/e)). Our techniques generalize for the k-median problem and for many other settings where non-Euclidean distance measures are involved.

Space efficient algorithms play a central role in dealing with large amount of data. In such settings, one would like to analyse the large data using small amount of “working space”. One of the key steps in many algorithms for analysing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings – (i) streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in above two settings: In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using \(O(\log n)\) random bits and \(O(\log n)\) space, where n is the number of elements seen so far. We can extend this to the case when elements have weights as well. In the query model, there are n elements with weights \(w_1, \ldots , w_n\) (which are w-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using \(nw +1 \) space (whereas, the information theoretic lower bound is n w). We consider the approximate sampling problem, where we are given an error parameter \(\varepsilon \), and the sampling probability of an element can be off by an \(\varepsilon \) factor. We give matching upper and lower bounds for this problem.

Space efficient algorithms play a central role in dealing with large amount of data. In such settings, one would like to analyse the large data using small amount of "working space". One of the key steps in many algorithms for analysing large data is to maintain a (or a small number) random sample from the data points. In this paper, we consider two space restricted settings -- (i) streaming model, where data arrives over time and one can use only a small amount of storage, and (ii) query model, where we can structure the data in low space and answer sampling queries. In this paper, we prove the following results in above two settings: - In the streaming setting, we would like to maintain a random sample from the elements seen so far. We prove that one can maintain a random sample using $O(\log n)$ random bits and $O(\log n)$ space, where $n$ is the number of elements seen so far. We can extend this to the case when elements have weights as well. - In the query model, there are $n$ elements with weights $w_1, ..., w_n$ (which are $w$-bit integers) and one would like to sample a random element with probability proportional to its weight. Bringmann and Larsen (STOC 2013) showed how to sample such an element using $nw +1 $ space (whereas, the information theoretic lower bound is $n w$). We consider the approximate sampling problem, where we are given an error parameter $\varepsilon$, and the sampling probability of an element can be off by an $\varepsilon$ factor. We give matching upper and lower bounds for this problem.

Eta pairing over supersingular elliptic curves is widely used in designing many cryptographic protocols. Because of efficiency considerations, curves over finite fields of small characteristics are preferred. In this paper, we report several of our implementations of eta pairing over finite fields of characteristics two and three. We exploit SIMD features available in Intel processors to speed up eta-pairing computations. We study two ways of vectorizing the computations: horizontal (intra-pairing) and vertical (inter-pairing). We report our experimental results using SSE2 and AVX2 features supported by the Haswell microarchitecture. Our implementations use two popular curves. Recently proposed discrete-logarithm algorithms make these curves less secure than previously thought. We discuss the implications of these developments in the context of our implementations.

Eta pairing on a supersingular elliptic curve over the binary field \(F_{2^{1223}}\) used to offer 128-bit security, and has been studied extensively for efficient implementations. In this paper, we report our GPU-based implementations of this algorithm on an NVIDIA Tesla C2050 platform. We propose efficient parallel implementation strategies for multiplication, square, square root and inverse in the underlying field. Our implementations achieve the best performance when Lopez-Dahab multiplication with four-bit precomputations is used in conjunction with one-level Karatsuba multiplication. We have been able to compute up to 566 eta pairings per second. To the best of our knowledge, ours is the fastest GPU-based implementation of eta pairing. It is about twice as fast as the only reported GPU implementation, and about five times as fast as the fastest reported single-core SIMD implementation. We estimate that the NVIDIA GTX 480 platform is capable of producing the fastest known software implementation of eta pairing.