OpenRaiser/Intern-Atlas huggingface dataset:
Optimization Problems with Diseconomies of Scale via Decoupling
Venue: arXiv cs.DS 2015
Year: 2015

We present a new framework for solving optimization problems with a diseconomy of scale. In such problems, our goal is to minimize the cost of resources used to perform a certain task. The cost of resources grows superlinearly, as $x^q$, $q\ge 1$, with the amount $x$ of resources used. We define a novel linear programming relaxation for such problems, and then show that the integrality gap of the relaxation is $A_q$, where $A_q$ is the $q$-th moment of the Poisson random variable with parameter 1. Using our framework, we obtain approximation algorithms for the Minimum Energy Efficient Routing, Minimum Degree Balanced Spanning Tree, Load Balancing on Unrelated Parallel Machines, and Unrelated Parallel Machine Scheduling with Nonlinear Functions of Completion Times problems. Our analysis relies on the decoupling inequality for nonnegative random variables. The inequality states that $$\big \|\sum_{i=1}^n X_i\big\|_{q} \leq C_q \,\big \|\sum_{i=1}^n Y_i\big\|_{q},$$ where $X_i$ are independent nonnegative random variables, $Y_i$ are possibly dependent nonnegative random variable, and each $Y_i$ has the same distribution as $X_i$. The inequality was proved by de la Peña in 1990. De la Peña, Ibragimov, and Sharakhmetov (2003) showed that $C_q\leq 2$ for $q\in (1,2)$ and $C_q\leq A_q^{1/q}$ for $q\geq 2$. We show that the optimal constant is $C_q=A_q^{1/q}$ for any $q\geq 1$. We then prove a more general inequality: For every convex function $φ$, $$\mathbb{E}[φ\Big(\sum_{i=1}^n X_i\Big)]\leq \mathbb{E}[φ\Big(P\sum_{i=1}^n Y_i\Big)],$$ and, for every concave function $ψ$, $$\mathbb{E}[ψ\Big(\sum_{i=1}^n X_i\Big)] \geq \mathbb{E}[ψ\Big(P\sum_{i=1}^n Y_i\Big)],$$ where $P$ is a Poisson random variable with parameter 1 independent of the random variables $Y_i$.
Interactive Isogeometric Volume Visualization with Pixel-Accurate Geometry
Venue: arXiv cs.GR 2015
Year: 2015

A recent development, called isogeometric analysis, provides a unified approach for design, analysis and optimization of functional products in industry. Traditional volume rendering methods for inspecting the results from the numerical simulations cannot be applied directly to isogeometric models. We present a novel approach for interactive visualization of isogeometric analysis results, ensuring correct, i.e., pixel-accurate geometry of the volume including its bounding surfaces. The entire OpenGL pipeline is used in a multi-stage algorithm leveraging techniques from surface rendering, order-independent transparency, as well as theory and numerical methods for ordinary differential equations. We showcase the efficiency of our approach on different models relevant to industry, ranging from quality inspection of the parametrization of the geometry, to stress analysis in linear elasticity, to visualization of computational fluid dynamics results.
Spinner: Scalable Graph Partitioning in the Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Several organizations, like social networks, store and routinely analyze large graphs as part of their daily operation. Such graphs are typically distributed across multiple servers, and graph partitioning is critical for efficient graph management. Existing partitioning algorithms focus on finding graph partitions with good locality, but disregard the pragmatic challenges of integrating partitioning into large-scale graph management systems deployed on the cloud, such as dealing with the scale and dynamicity of the graph and the compute environment. In this paper, we propose Spinner, a scalable and adaptive graph partitioning algorithm based on label propagation designed on top of the Pregel model. Spinner scales to massive graphs, produces partitions with locality and balance comparable to the state-of-the-art and efficiently adapts the partitioning upon changes. We describe our algorithm and its implementation in the Pregel programming model that makes it possible to partition billion-vertex graphs. We evaluate Spinner with a variety of synthetic and real graphs and show that it can compute partitions with quality comparable to the state-of-the art. In fact, by using Spinner in conjunction with the Giraph graph processing engine, we speed up different applications by a factor of 2 relative to standard hash partitioning.
Improved Analysis of Deterministic Load-Balancing Schemes
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time $T = O(\log (Kn)/μ)$, any algorithm of their class achieves a discrepancy of $O(d\log n/μ)$, where $μ$ is the spectral gap of the transition matrix of the graph, and $K$ is the initial load discrepancy in the system. In this work we identify some natural additional conditions on deterministic balancing algorithms, resulting in a class of algorithms reaching a smaller discrepancy. This class contains well-known algorithms, eg., the Rotor-Router. Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive time steps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms which are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of $O(\min\{d\sqrt{\log n/μ},d\sqrt{n}\})$ in time $O(T)$. We also show that in general neither of these assumptions may be omitted without increasing discrepancy. We then show by a combinatorial potential reduction argument that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of $O(d)$ almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.
Supervised detection of anomalous light-curves in massive astronomical catalogs
Venue: arXiv cs.CE 2015
Year: 2015

The development of synoptic sky surveys has led to a massive amount of data for which resources needed for analysis are beyond human capabilities. To process this information and to extract all possible knowledge, machine learning techniques become necessary. Here we present a new method to automatically discover unknown variable objects in large astronomical catalogs. With the aim of taking full advantage of all the information we have about known objects, our method is based on a supervised algorithm. In particular, we train a random forest classifier using known variability classes of objects and obtain votes for each of the objects in the training set. We then model this voting distribution with a Bayesian network and obtain the joint voting distribution among the training objects. Consequently, an unknown object is considered as an outlier insofar it has a low joint probability. Our method is suitable for exploring massive datasets given that the training process is performed offline. We tested our algorithm on 20 millions light-curves from the MACHO catalog and generated a list of anomalous candidates. We divided the candidates into two main classes of outliers: artifacts and intrinsic outliers. Artifacts were principally due to air mass variation, seasonal variation, bad calibration or instrumental errors and were consequently removed from our outlier list and added to the training set. After retraining, we selected about 4000 objects, which we passed to a post analysis stage by perfoming a cross-match with all publicly available catalogs. Within these candidates we identified certain known but rare objects such as eclipsing Cepheids, blue variables, cataclysmic variables and X-ray sources. For some outliers there were no additional information. Among them we identified three unknown variability types and few individual outliers that will be followed up for a deeper analysis.
Lax functors and coalgebraic weak bisimulation
Venue: arXiv cs.LO 2015
Year: 2015

We generalize the work by Sobociński on relational presheaves and their connection with weak (bi)simulation for labelled transistion systems to a coalgebraic setting. We show that the coalgebraic notion of saturation studied in our previous work can be expressed in the language of lax functors in terms of existence of a certain adjunction between categories of lax functors. This observation allows us to generalize the notion of the coalgebraic weak bisimulation to lax functors. We instantiate this definition on two examples of timed systems and show that it coincides with their time-abstract behavioural equivalence.
Converses for Secret Key Agreement and Secure Computing
Venue: arXiv cs.IT 2015
Year: 2015

We consider information theoretic secret key agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the secret key length, which is derived using a reduction of binary hypothesis testing to multiparty secret key agreement. Building on this basic result, we derive new converses for multiparty secret key agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to secret key agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.
Coherence Optimization and Best Complex Antipodal Spherical Codes
Venue: arXiv cs.IT 2015
Year: 2015

Vector sets with optimal coherence according to the Welch bound cannot exist for all pairs of dimension and cardinality. If such an optimal vector set exists, it is an equiangular tight frame and represents the solution to a Grassmannian line packing problem. Best Complex Antipodal Spherical Codes (BCASCs) are the best vector sets with respect to the coherence. By extending methods used to find best spherical codes in the real-valued Euclidean space, the proposed approach aims to find BCASCs, and thereby, a complex-valued vector set with minimal coherence. There are many applications demanding vector sets with low coherence. Examples are not limited to several techniques in wireless communication or to the field of compressed sensing. Within this contribution, existing analytical and numerical approaches for coherence optimization of complex-valued vector spaces are summarized and compared to the proposed approach. The numerically obtained coherence values improve previously reported results. The drawback of increased computational effort is addressed and a faster approximation is proposed which may be an alternative for time critical cases.
Input anticipating critical reservoirs show power law forgetting of unexpected input events
Venue: arXiv cs.NE 2015
Year: 2015

Usually, reservoir computing shows an exponential memory decay. This paper investigates under which circumstances echo state networks can show a power law forgetting. That means traces of earlier events can be found in the reservoir for very long time spans. Such a setting requires critical connectivity exactly at the limit of what is permissible according the echo state condition. However, for general matrices the limit cannot be determined exactly from theory. In addition, the behavior of the network is strongly influenced by the input flow. Results are presented that use certain types of restricted recurrent connectivity and anticipation learning with regard to the input, where indeed power law forgetting can be achieved.
Recent Developments in China-U.S. Cooperation in Science
Venue: arXiv cs.DL 2015
Year: 2015

China's remarkable gains in science over the past 25 years have been well documented (e.g., Jin and Rousseau, 2005a; Zhou and Leydesdorff, 2006; Shelton & Foland, 2009) but it is less well known that China and the United States have become each other's top collaborating country. Science and technology has been a primary vehicle for growing the bilateral relationship between China and the United States since the opening of relations between the two countries in the late 1970s. During the 2000s, the scientific relationship between China and the United States--as measured in coauthored papers--showed significant growth. Chinese scientists claim first authorship much more frequently than U.S. counterparts by the end of the decade. The sustained rate of increase of collaboration with one other country is unprecedented on the U.S. side. Even growth in relations with eastern European nations does not match the growth in the relationship between China and the United States. Both countries can benefit from the relationship, but for the U.S., greater benefit would come from a more targeted strategy.
Parameterized Complexity Dichotomy for Steiner Multicut
Venue: arXiv cs.DS 2015
Year: 2015

The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether there is a set S of at most k edges or nodes s.t. of each set Ti at least one pair of terminals is in different connected components of G \ S. This problem generalizes several graph cut problems, in particular the Multicut problem (the case p = 2), which is fixed-parameter tractable for the parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. We provide a dichotomy of the parameterized complexity of Steiner Multicut. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). We highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for the parameter k+t on general graphs (but has no polynomial kernel, even on trees). We present two proofs: one using the randomized contractions technique of Chitnis et al, and one relying on new structural lemmas that decompose the Steiner cut into important separators and minimal s-t cuts. - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Hence, the results of Marx and Razgon, and Bousquet et al. do not generalize to Steiner Multicut. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1), and a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
Depth Lower Bounds against Circuits with Sparse Orientation
Venue: arXiv cs.CC 2015
Year: 2015

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure of the orientation vectors in any circuit $C$ computing the Clique function on an $n$ vertex graph. We prove that if $C$ is of depth $d$ and each gate computes a Boolean function with orientation of weight at most $w$ (in terms of the inputs to $C$), then $d \times w$ must be $Ω(n)$. In particular, if the weights are $o(\frac{n}{\log^k n})$, then $C$ must be of depth $ω(\log^k n)$. We prove a barrier for our general technique. However, using specific properties of the Clique function and the Karchmer-Wigderson framework (Karchmer and Wigderson, 1988), we go beyond the limitations and obtain lower bounds when the weight restrictions are less stringent. We then study the depth lower bounds when the structure of the orientation vector is restricted. Asymptotic improvements to our results (in the restricted setting), separates NP from NC. As our main tool, we generalize Karchmer-Wigderson gamefor monotone functions to work for non-monotone circuits parametrized by the weight/structure of the orientation. We also prove structural results about orientation and prove connections between number of negations and weight of orientations required to compute a function.
Distributed Quantization for Measurement of Correlated Sparse Sources over Noisy Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we design and analyze distributed vector quantization (VQ) for compressed measurements of correlated sparse sources over noisy channels. Inspired by the framework of compressed sensing (CS) for acquiring compressed measurements of the sparse sources, we develop optimized quantization schemes that enable distributed encoding and transmission of CS measurements over noisy channels followed by joint decoding at a decoder. The optimality is addressed with respect to minimizing the sum of mean-square error (MSE) distortions between the sparse sources and their reconstruction vectors at the decoder. We propose a VQ encoder-decoder design via an iterative algorithm, and derive a lower-bound on the end-to-end MSE of the studied distributed system. Through several simulation studies, we evaluate the performance of the proposed distributed scheme.
Feature selection for classification with class-separability strategy and data envelopment analysis
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, a novel feature selection method is presented, which is based on Class-Separability (CS) strategy and Data Envelopment Analysis (DEA). To better capture the relationship between features and the class, class labels are separated into individual variables and relevance and redundancy are explicitly handled on each class label. Super-efficiency DEA is employed to evaluate and rank features via their conditional dependence scores on all class labels, and the feature with maximum super-efficiency score is then added in the conditioning set for conditional dependence estimation in the next iteration, in such a way as to iteratively select features and get the final selected features. Eventually, experiments are conducted to evaluate the effectiveness of proposed method comparing with four state-of-the-art methods from the viewpoint of classification accuracy. Empirical results verify the feasibility and the superiority of proposed feature selection method.
A unified framework for linear dimensionality reduction in L1
Venue: arXiv cs.DS 2015
Year: 2015

For a family of interpolation norms $\| \cdot \|_{1,2,s}$ on $\mathbb{R}^n$, we provide a distribution over random matrices $Φ_s \in \mathbb{R}^{m \times n}$ parametrized by sparsity level $s$ such that for a fixed set $X$ of $K$ points in $\mathbb{R}^n$, if $m \geq C s \log(K)$ then with high probability, $\frac{1}{2} \| x \|_{1,2,s} \leq \| Φ_s (x) \|_1 \leq 2 \| x\|_{1,2,s}$ for all $x\in X$. Several existing results in the literature reduce to special cases of this result at different values of $s$: for $s=n$, $\| x\|_{1,2,n} \equiv \| x \|_{1}$ and we recover that dimension reducing linear maps can preserve the $\ell_1$-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For $s=1$, $\|x \|_{1,2,1} \equiv \| x \|_{2}$, and we recover an $\ell_2 / \ell_1$ variant of the Johnson-Lindenstrauss Lemma for Gaussian random matrices. Finally, if $x$ is $s$-sparse, then $\| x \|_{1,2,s} = \| x \|_1$ and we recover that $s$-sparse vectors in $\ell_1^n$ embed into $\ell_1^{\mathcal{O}(s \log(n))}$ via sparse random matrix constructions.
Information Nonanticipative Rate Distortion Function and Its Applications
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates applications of nonanticipative Rate Distortion Function (RDF) in a) zero-delay Joint Source-Channel Coding (JSCC) design based on average and excess distortion probability, b) in bounding the Optimal Performance Theoretically Attainable (OPTA) by noncausal and causal codes, and computing the Rate Loss (RL) of zero-delay and causal codes with respect to noncausal codes. These applications are described using two running examples, the Binary Symmetric Markov Source with parameter p, (BSMS(p)) and the multidimensional partially observed Gaussian-Markov source. For the multidimensional Gaussian-Markov source with square error distortion, the solution of the nonanticipative RDF is derived, its operational meaning using JSCC design via a noisy coding theorem is shown by providing the optimal encoding-decoding scheme over a vector Gaussian channel, and the RL of causal and zero-delay codes with respect to noncausal codes is computed. For the BSMS(p) with Hamming distortion, the solution of the nonanticipative RDF is derived, the RL of causal codes with respect to noncausal codes is computed, and an uncoded noisy coding theorem based on excess distortion probability is shown. The information nonanticipative RDF is shown to be equivalent to the nonanticipatory epsilon-entropy, which corresponds to the classical RDF with an additional causality or nonanticipative condition imposed on the optimal reproduction conditional distribution.
A Self-Adaptive Network Protection System
Venue: arXiv cs.NE 2015
Year: 2015

In this treatise we aim to build a hybrid network automated (self-adaptive) security threats discovery and prevention system; by using unconventional techniques and methods, including fuzzy logic and biological inspired algorithms under the context of soft computing.
New Results on the Minimum Amount of Useful Space
Venue: arXiv cs.FL 2015
Year: 2015

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak $\log\log n$ space, (ii) $\log\log n$ is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak $\log n$ space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong $\log\log n$ space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle $\log n$ space and bounded error.