OpenRaiser/Intern-Atlas huggingface dataset:
A new class of hyper-bent Boolean functions in binomial forms
Venue: arXiv cs.IT 2012
Year: 2012

Bent functions, which are maximally nonlinear Boolean functions with even numbers of variables and whose Hamming distance to the set of all affine functions equals $2^{n-1}\pm 2^{\frac{n}{2}-1}$, were introduced by Rothaus in 1976 when he considered problems in combinatorics. Bent functions have been extensively studied due to their applications in cryptography, such as S-box, block cipher and stream cipher. Further, they have been applied to coding theory, spread spectrum and combinatorial design. Hyper-bent functions, as a special class of bent functions, were introduced by Youssef and Gong in 2001, which have stronger properties and rarer elements. Many research focus on the construction of bent and hyper-bent functions. In this paper, we consider functions defined over $\mathbb{F}_{2^n}$ by $f_{a,b}:=\mathrm{Tr}_{1}^{n}(ax^{(2^m-1)})+\mathrm{Tr}_{1}^{4}(bx^{\frac{2^n-1}{5}})$, where $n=2m$, $m\equiv 2\pmod 4$, $a\in \mathbb{F}_{2^m}$ and $b\in\mathbb{F}_{16}$. When $a\in \mathbb{F}_{2^m}$ and $(b+1)(b^4+b+1)=0$, with the help of Kloosterman sums and the factorization of $x^5+x+a^{-1}$, we present a characterization of hyper-bentness of $f_{a,b}$. Further, we use generalized Ramanujan-Nagell equations to characterize hyper-bent functions of $f_{a,b}$ in the case $a\in\mathbb{F}_{2^{\frac{m}{2}}}$.
Sampling High-Dimensional Bandlimited Fields on Low-Dimensional Manifolds
Venue: arXiv cs.IT 2012
Year: 2012

Consider the task of sampling and reconstructing a bandlimited spatial field in $\Re^2$ using moving sensors that take measurements along their path. It is inexpensive to increase the sampling rate along the paths of the sensors but more expensive to increase the total distance traveled by the sensors per unit area, which we call the \emph{path density}. In this paper we introduce the problem of designing sensor trajectories that are minimal in path density subject to the condition that the measurements of the field on these trajectories admit perfect reconstruction of bandlimited fields. We study various possible designs of sampling trajectories. Generalizing some ideas from the classical theory of sampling on lattices, we obtain necessary and sufficient conditions on the trajectories for perfect reconstruction. We show that a single set of equispaced parallel lines has the lowest path density from certain restricted classes of trajectories that admit perfect reconstruction. We then generalize some of our results to higher dimensions. We first obtain results on designing sampling trajectories in higher dimensional fields. Further, interpreting trajectories as 1-dimensional manifolds, we extend some of our ideas to higher dimensional sampling manifolds. We formulate the problem of designing $κ$-dimensional sampling manifolds for $d$-dimensional spatial fields that are minimal in \emph{manifold density}, a natural generalization of the path density. We show that our results on sampling trajectories for fields in $\Re^2$ can be generalized to analogous results on $d-1$-dimensional sampling manifolds for $d$-dimensional spatial fields.
Computing on Binary Strings
Venue: arXiv cs.DS 2012
Year: 2012

Many problems in Computer Science can be abstracted to the following question: given a set of objects and rules respectively, which new objects can be produced? In the paper, we consider a succinct version of the question: given a set of binary strings and several operations like conjunction and disjunction, which new binary strings can be generated? Although it is a fundamental problem, to the best of our knowledge, the problem hasn't been studied yet. In this paper, an O(m^2n) algorithm is presented to determine whether a string s is representable by a set W, where n is the number of strings in W and each string has the same length m. However, looking for the minimum subset from a set to represent a given string is shown to be NP-hard. Also, finding the smallest subset from a set to represent each string in the original set is NP-hard. We establishes inapproximability results and approximation algorithms for them. In addition, we prove that counting the number of strings representable is #P-complete. We then explore how the problems change when the operator negation is available. For example, if the operator negation can be used, the number is some power of 2. This difference maybe help us understand the problem more profoundly.
A Cyclic Representation of Discrete Coordination Procedures
Venue: arXiv cs.MA 2012
Year: 2012

We show that any discrete opinion pooling procedure with positive weights can be asymptotically approximated by DeGroot's procedure whose communication digraph is a Hamiltonian cycle with loops. In this cycle, the weight of each arc (which is not a loop) is inversely proportional to the influence of the agent the arc leads to.
Twitter reciprocal reply networks exhibit assortativity with respect to happiness
Venue: arXiv cs.SI 2012
Year: 2012

The advent of social media has provided an extraordinary, if imperfect, 'big data' window into the form and evolution of social networks. Based on nearly 40 million message pairs posted to Twitter between September 2008 and February 2009, we construct and examine the revealed social network structure and dynamics over the time scales of days, weeks, and months. At the level of user behavior, we employ our recently developed hedonometric analysis methods to investigate patterns of sentiment expression. We find users' average happiness scores to be positively and significantly correlated with those of users one, two, and three links away. We strengthen our analysis by proposing and using a null model to test the effect of network topology on the assortativity of happiness. We also find evidence that more well connected users write happier status updates, with a transition occurring around Dunbar's number. More generally, our work provides evidence of a social sub-network structure within Twitter and raises several methodological points of interest with regard to social network reconstructions.
The Role of Persistent Graphs in the Agreement Seeking of Social Networks
Venue: arXiv cs.MA 2012
Year: 2012

This paper investigates the role persistent arcs play for a social network to reach a global belief agreement under discrete-time or continuous-time evolution. Each (directed) arc in the underlying communication graph is assumed to be associated with a time-dependent weight function which describes the strength of the information flow from one node to another. An arc is said to be persistent if its weight function has infinite $\mathscr{L}_1$ or $\ell_1$ norm for continuous-time or discrete-time belief evolutions, respectively. The graph that consists of all persistent arcs is called the persistent graph of the underlying network. Three necessary and sufficient conditions on agreement or $ε$-agreement are established, by which we prove that the persistent graph fully determines the convergence to a common opinion in social networks. It is shown how the convergence rates explicitly depend on the diameter of the persistent graph. The results adds to the understanding of the fundamentals behind global agreements, as it is only persistent arcs that contribute to the convergence.
Minimum Average Distance Triangulations
Venue: arXiv cs.CG 2012
Year: 2012

We study the problem of finding a triangulation T of a planar point set S such as to minimize the expected distance between two points x and y chosen uniformly at random from S. By distance we mean the length of the shortest path between x and y along edges of T. The length of a path is the sum of the weights of its edges. Edge weights are assumed to be given as part of the problem for every pair of distinct points (x,y) in S^2. In a different variant of the problem, the points are vertices of a simple polygon and we look for a triangulation of the interior of the polygon that is optimal in the same sense. We prove that a general formulation of the problem in which the weights are arbitrary positive numbers is strongly NP-complete. For the case when all the weights are equal we give polynomial-time algorithms. In the end we mention several open problems.
Caveats for using statistical significance tests in research assessments
Venue: arXiv cs.DL 2012
Year: 2012

This paper raises concerns about the advantages of using statistical significance tests in research assessments as has recently been suggested in the debate about proper normalization procedures for citation indicators. Statistical significance tests are highly controversial and numerous criticisms have been leveled against their use. Based on examples from articles by proponents of the use statistical significance tests in research assessments, we address some of the numerous problems with such tests. The issues specifically discussed are the ritual practice of such tests, their dichotomous application in decision making, the difference between statistical and substantive significance, the implausibility of most null hypotheses, the crucial assumption of randomness, as well as the utility of standard errors and confidence intervals for inferential purposes. We argue that applying statistical significance tests and mechanically adhering to their results is highly problematic and detrimental to critical thinking. We claim that the use of such tests do not provide any advantages in relation to citation indicators, interpretations of them, or the decision making processes based upon them. On the contrary their use may be harmful. Like many other critics, we generally believe that statistical significance tests are over- and misused in the social sciences including scientometrics and we encourage a reform on these matters.
Inference in Probabilistic Logic Programs with Continuous Random Variables
Venue: arXiv cs.AI 2012
Year: 2012

Probabilistic Logic Programming (PLP), exemplified by Sato and Kameya's PRISM, Poole's ICL, Raedt et al's ProbLog and Vennekens et al's LPAD, is aimed at combining statistical and logical knowledge representation and inference. A key characteristic of PLP frameworks is that they are conservative extensions to non-probabilistic logic programs which have been widely used for knowledge representation. PLP frameworks extend traditional logic programming semantics to a distribution semantics, where the semantics of a probabilistic logic program is given in terms of a distribution over possible models of the program. However, the inference techniques used in these works rely on enumerating sets of explanations for a query answer. Consequently, these languages permit very limited use of random variables with continuous distributions. In this paper, we present a symbolic inference procedure that uses constraints and represents sets of explanations without enumeration. This permits us to reason over PLPs with Gaussian or Gamma-distributed random variables (in addition to discrete-valued random variables) and linear equality constraints over reals. We develop the inference procedure in the context of PRISM; however the procedure's core ideas can be easily applied to other PLP languages as well. An interesting aspect of our inference procedure is that PRISM's query evaluation process becomes a special case in the absence of any continuous random variables in the program. The symbolic inference procedure enables us to reason over complex probabilistic models such as Kalman filters and a large subclass of Hybrid Bayesian networks that were hitherto not possible in PLP frameworks. (To appear in Theory and Practice of Logic Programming).
Synthesis of Spherical 4R Mechanism for Path Generation using Differential Evolution
Venue: arXiv cs.CE 2012
Year: 2012

The problem of path generation for the spherical 4R mechanism is solved using the Differential Evolution algorithm (DE). Formulas for the spherical geodesics are employed in order to obtain the parametric equation for the generated trajectory. Direct optimization of the objective function gives the solution to the path generation task without prescribed timing. Therefore, there is no need to separate this task into two stages to make the optimization. Moreover, the order defect problem can be solved without difficulty by means of manipulations of the individuals in the DE algorithm. Two examples of optimum synthesis showing the simplicity and effectiveness of this approach are included.
Supervised Generative Reconstruction: An Efficient Way To Flexibly Store and Recognize Patterns
Venue: arXiv cs.CV 2012
Year: 2012

Matching animal-like flexibility in recognition and the ability to quickly incorporate new information remains difficult. Limits are yet to be adequately addressed in neural models and recognition algorithms. This work proposes a configuration for recognition that maintains the same function of conventional algorithms but avoids combinatorial problems. Feedforward recognition algorithms such as classical artificial neural networks and machine learning algorithms are known to be subject to catastrophic interference and forgetting. Modifying or learning new information (associations between patterns and labels) causes loss of previously learned information. I demonstrate using mathematical analysis how supervised generative models, with feedforward and feedback connections, can emulate feedforward algorithms yet avoid catastrophic interference and forgetting. Learned information in generative models is stored in a more intuitive form that represents the fixed points or solutions of the network and moreover displays similar difficulties as cognitive phenomena. Brain-like capabilities and limits associated with generative models suggest the brain may perform recognition and store information using a similar approach. Because of the central role of recognition, progress understanding the underlying principles may reveal significant insight on how to better study and integrate with the brain.
Automatic post-picking improves particle image detection from Cryo-EM micrographs
Venue: arXiv cs.CV 2012
Year: 2012

Cryo-electron microscopy (cryo-EM) studies using single particle reconstruction is extensively used to reveal structural information of macromolecular complexes. Aiming at the highest achievable resolution, state of the art electron microscopes acquire thousands of high-quality images. Having collected these data, each single particle must be detected and windowed out. Several fully- or semi-automated approaches have been developed for the selection of particle images from digitized micrographs. However they still require laborious manual post processing, which will become the major bottleneck for next generation of electron microscopes. Instead of focusing on improvements in automated particle selection from micrographs, we propose a post-picking step for classifying small windowed images, which are output by common picking software. A supervised strategy for the classification of windowed micrograph images into particles and non-particles reduces the manual workload by orders of magnitude. The method builds on new powerful image features, and the proper training of an ensemble classifier. A few hundred training samples are enough to achieve a human-like classification performance.
CloudGenius: Automated Decision Support for Migrating Multi-Component Enterprise Applications to Clouds
Venue: arXiv cs.DC 2012
Year: 2012

One of the key problems in migrating multi-component enterprise applications to Clouds is selecting the best mix of VM images and Cloud infrastructure services. A migration process has to ensure that Quality of Service (QoS) requirements are met, while satisfying conflicting selection criteria, e.g. throughput and cost. When selecting Cloud services, application engineers must consider heterogeneous sets of criteria and complex dependencies across multiple layers impossible to resolve manually. To overcome this challenge, we present the generic recommender framework CloudGenius and an implementation that leverage well known multi-criteria decision making technique Analytic Hierarchy Process to automate the selection process based on a model, factors, and QoS requirements related to enterprise applications. In particular, we introduce a structured migration process for multi-component enterprise applications, clearly identify the most important criteria relevant to the selection problem and present a multi-criteria-based selection algorithm. Experiments with the software prototype CumulusGenius show time complexities.
Approximating Non-Uniform Sparsest Cut via Generalized Spectra
Venue: arXiv cs.DS 2012
Year: 2012

We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any $ε,δ\in (0,1)$, given cost and demand graphs with edge weights $C, D$ respectively, we can find a set $T\subseteq V$ with $\frac{C(T,V\setminus T)}{D(T,V\setminus T)}$ at most $\frac{1+ε}δ$ times the optimal non-uniform sparsest cut value, in time $2^{r/(δε)}\poly(n)$ provided $λ_r \ge Φ^*/(1-δ)$. Here $λ_r$ is the $r$'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; $C(T,V\setminus T)$ (resp. $D(T,V\setminus T)$) is the weight of edges crossing the $(T,V\setminus T)$ cut in cost (resp. demand) graph and $Φ^*$ is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the $r$'th smallest eigenvalue of the normalized Laplacian playing the role of $λ_r$ in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting $\ell_1$-embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut.
Circular-Arc Cartograms
Venue: arXiv cs.CG 2012
Year: 2012

We present a new circular-arc cartogram model in which countries are drawn as polygons with circular arcs instead of straight-line segments. Given a political map and values associated with each country in the map, a cartogram is a distorted map in which the areas of the countries are proportional to the corresponding values. In the circular-arc cartogram model straight-line segments can be replaced by circular arcs in order to modify the areas of the polygons, while the corners of the polygons remain fixed. The countries in circular-arc cartograms have the aesthetically pleasing appearance of clouds or snowflakes, depending on whether their edges are bent outwards or inwards. This makes it easy to determine whether a country has grown or shrunk, just by its overall shape. We show that determining whether a given map and given area-values can be realized as a circular-arc cartogram is an NP-hard problem. Next we describe a heuristic method for constructing circular-arc cartograms, which uses a max-flow computation on the dual graph of the map, along with a computation of the straight skeleton of the underlying polygonal decomposition. Our method is implemented and produces cartograms that, while not yet perfectly accurate, achieve many of the desired areas in our real-world examples.
Coded Path Protection: Efficient Conversion of Sharing to Coding
Venue: arXiv cs.NI 2012
Year: 2012

Link failures in wide area networks are common and cause significant data losses. Mesh-based protection schemes offer high capacity efficiency but they are slow and require complex signaling. Additionally, real-time reconfiguration of a cross-connect threatens their transmission integrity. On the other hand, coding-based protection schemes are proactive. Therefore, they have higher restoration speed, lower signaling complexity, and higher transmission integrity. This paper introduces a coding-based protection scheme, named Coded Path Protection (CPP). In CPP, a backup copy of the primary data is encoded with other data streams, resulting in capacity savings. This paper presents an optimal and simple capacity placement and coding group formation algorithm. The algorithm converts the sharing structure of any solution of a Shared Path Protection (SPP) technique into a coding structure with minimum extra capacity. We conducted quantitative and qualitative comparisons of our technique with the SPP and, another technique, known as p-cycle protection. Simulation results confirm that the CPP is significantly faster than the SPP and p-cycle techniques. CPP incurs marginal extra capacity on top of SPP. Its capacity efficiency is lower than the p-cycle technique for dense networks but can be higher for sparse networks. In addition, unlike p-cycle protection, CPP is inherently suitable for the wavelength continuity constraint in optical networks.
AdCell: Ad Allocation in Cellular Networks
Venue: arXiv cs.DS 2012
Year: 2012

With more than four billion usage of cellular phones worldwide, mobile advertising has become an attractive alternative to online advertisements. In this paper, we propose a new targeted advertising policy for Wireless Service Providers (WSPs) via SMS or MMS- namely {\em AdCell}. In our model, a WSP charges the advertisers for showing their ads. Each advertiser has a valuation for specific types of customers in various times and locations and has a limit on the maximum available budget. Each query is in the form of time and location and is associated with one individual customer. In order to achieve a non-intrusive delivery, only a limited number of ads can be sent to each customer. Recently, new services have been introduced that offer location-based advertising over cellular network that fit in our model (e.g., ShopAlerts by AT&T) . We consider both online and offline version of the AdCell problem and develop approximation algorithms with constant competitive ratio. For the online version, we assume that the appearances of the queries follow a stochastic distribution and thus consider a Bayesian setting. Furthermore, queries may come from different distributions on different times. This model generalizes several previous advertising models such as online secretary problem \cite{HKP04}, online bipartite matching \cite{KVV90,FMMM09} and AdWords \cite{saberi05}. ...