OpenRaiser/Intern-Atlas huggingface dataset:
Unshredding of Shredded Documents: Computational Framework and Implementation
Venue: arXiv cs.CV 2015
Year: 2015

A shredded document $D$ is a document whose pages have been cut into strips for the purpose of destroying private, confidential, or sensitive information $I$ contained in $D$. Shredding has become a standard means of government organizations, businesses, and private individuals to destroy archival records that have been officially classified for disposal. It can also be used to destroy documentary evidence of wrongdoings by entities who are trying to hide $I$. In this paper, we present an optimal $O((n\times m)^2)$ algorithm $A$ that reconstructs an $n$-page $D$, where each page $p$ is shredded into $m$ strips. We also present the efficacy of $A$ in reconstructing three document types: hand-written, machine typed-set, and images.
Synchronization of ad hoc Clock Networks
Venue: arXiv cs.DC 2015
Year: 2015

We introduce a graph-theoretic approach to synchronizing clocks in an {\em ad hoc} network of $N$~timepieces. Clocks naturally drift away from being synchronized because of many physical factors. The manual way of clock synchronization suffers from an inherrent propagation of the so called "clock drift" due to "word-of-mouth effect." The current standard way of automated clock synchronization is either via radio band transmission of the global clock or via the software-based Network Time Protocol (NTP). Synchronization via radio band transmission suffers from the wave transmission delay, while the client-server-based NTP does not scale to increased number of clients as well as to unforeseen server overload conditions (e.g., flash crowd and time-of-day effects). Further, the trivial running time of NTP for synchronizing an $N$-node network, where each node is a clock and the NTP server follows a single-port communication model, is~$\bigO(N)$. We introduce in this paper a $\bigO(\log N)$ time for synchronizing the clocks in exchange for an increase of $\bigO(N)$ in space complexity, though through creative "tweaking," we later reduced the space requirement to~$\bigO(1)$. Our graph-theoretic protocol assumes that the network is $\K_N$, while the subset of clocks are in an embedded circulant graph $\C_{n<N}^q$ with $q$~jumps and clock information is communicated through circular shifts within the $\C_{n<N}^q$. All $N$~nodes communicate via a single-port duplex channel model. Theoretically, this synchronization protocol allows for $N(\log N)^{-1} - 1$ more synchronizations than the client-server-based one. Empirically through statistically replicated multi-agent-based microsimulation runs, our protocol allows at most 80\% of the clocks synchronized compared to the current protocol which only allows up to 30\% after some steady-state time.
Dynamic Mechanism Design with Interdependent Valuations
Venue: arXiv cs.GT 2015
Year: 2015

We consider an infinite horizon dynamic mechanism design problem with interdependent valuations. In this setting the type of each agent is assumed to be evolving according to a first order Markov process and is independent of the types of other agents. However, the valuation of an agent can depend on the types of other agents, which makes the problem fall into an interdependent valuation setting. Designing truthful mechanisms in this setting is non-trivial in view of an impossibility result which says that for interdependent valuations, any efficient and ex-post incentive compatible mechanism must be a constant mechanism, even in a static setting. Mezzetti (2004) circumvents this problem by splitting the decisions of allocation and payment into two stages. However, Mezzetti's result is limited to a static setting and moreover in the second stage of that mechanism, agents are weakly indifferent about reporting their valuations truthfully. This paper provides a first attempt at designing a dynamic mechanism which is efficient, `strict' ex-post incentive compatible and ex-post individually rational in a setting with interdependent values and Markovian type evolution.
Efficient mesh management in Firedrake using PETSc-DMPlex
Venue: arXiv cs.MS 2015
Year: 2015

The use of composable abstractions allows the application of new and established algorithms to a wide range of problems while automatically inheriting the benefits of well-known performance optimisations. This work highlights the composition of the PETSc DMPlex domain topology abstraction with the Firedrake automated finite element system to create a PDE solving environment that combines expressiveness, flexibility and high performance. We describe how Firedrake utilises DMPlex to provide the indirection maps required for finite element assembly, while supporting various mesh input formats and runtime domain decomposition. In particular, we describe how DMPlex and its accompanying data structures allow the generic creation of user-defined discretisations, while utilising data layout optimisations that improve cache coherency and ensure overlapped communication during assembly computation.
Mobile Homophily and Social Location Prediction
Venue: arXiv cs.SI 2015
Year: 2015

The mobility behavior of human beings is predictable to a varying degree e.g. depending on the traits of their personality such as the trait extraversion - introversion: the mobility of introvert users may be more dominated by routines and habitual movement patterns, resulting in a more predictable mobility behavior on the basis of their own location history while, in contrast, extrovert users get about a lot and are explorative by nature, which may hamper the prediction of their mobility. However, socially more active and extrovert users meet more people and share information, experiences, believes, thoughts etc. with others. which in turn leads to a high interdependency between their mobility and social lives. Using a large LBSN dataset, his paper investigates the interdependency between human mobility and social proximity, the influence of social networks on enhancing location prediction of an individual and the transmission of social trends/influences within social networks.
Canonizing Graphs of Bounded Tree Width in Logspace
Venue: arXiv cs.CC 2015
Year: 2015

Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms. This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous class of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.
Stochastic Analysis of Chemical Reaction Networks Using Linear Noise Approximation
Venue: arXiv cs.LO 2015
Year: 2015

Stochastic evolution of Chemical Reactions Networks (CRNs) over time is usually analysed through solving the Chemical Master Equation (CME) or performing extensive simulations. Analysing stochasticity is often needed, particularly when some molecules occur in low numbers. Unfortunately, both approaches become infeasible if the system is complex and/or it cannot be ensured that initial populations are small. We develop a probabilistic logic for CRNs that enables stochastic analysis of the evolution of populations of molecular species. We present an approximate model checking algorithm based on the Linear Noise Approximation (LNA) of the CME, whose computational complexity is independent of the population size of each species and polynomial in the number of different species. The algorithm requires the solution of first order polynomial differential equations. We prove that our approach is valid for any CRN close enough to the thermodynamical limit. However, we show on four case studies that it can still provide good approximation even for low molecule counts. Our approach enables rigorous analysis of CRNs that are not analyzable by solving the CME, but are far from the deterministic limit. Moreover, it can be used for a fast approximate stochastic characterization of a CRN.
General Caching Is Hard: Even with Small Pages
Venue: arXiv cs.CC 2015
Year: 2015

Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes and fault costs. We give the first NP-hardness result for general caching with small pages: General caching is (strongly) NP-hard even when page sizes are limited to {1, 2, 3}. It holds already in the fault model (each page has unit fault cost) as well as in the bit model (each page has the same fault cost as size). We also give a very short proof of the strong NP-hardness of general caching with page sizes restricted to {1, 2, 3} and arbitrary costs.
Dynamic Time-domain Duplexing for Self-backhauled Millimeter Wave Cellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

Millimeter wave (mmW) bands between 30 and 300 GHz have attracted considerable attention for next-generation cellular networks due to vast quantities of available spectrum and the possibility of very high-dimensional antenna ar-rays. However, a key issue in these systems is range: mmW signals are extremely vulnerable to shadowing and poor high-frequency propagation. Multi-hop relaying is therefore a natural technology for such systems to improve cell range and cell edge rates without the addition of wired access points. This paper studies the problem of scheduling for a simple infrastructure cellular relay system where communication between wired base stations and User Equipment follow a hierarchical tree structure through fixed relay nodes. Such a systems builds naturally on existing cellular mmW backhaul by adding mmW in the access links. A key feature of the proposed system is that TDD duplexing selections can be made on a link-by-link basis due to directional isolation from other links. We devise an efficient, greedy algorithm for centralized scheduling that maximizes network utility by jointly optimizing the duplexing schedule and resources allocation for dense, relay-enhanced OFDMA/TDD mmW networks. The proposed algorithm can dynamically adapt to loading, channel conditions and traffic demands. Significant throughput gains and improved resource utilization offered by our algorithm over the static, globally-synchronized TDD patterns are demonstrated through simulations based on empirically-derived channel models at 28 GHz.
Characterization and Architectural Implications of Big Data Workloads
Venue: arXiv cs.DC 2015
Year: 2015

Big data areas are expanding in a fast way in terms of increasing workloads and runtime systems, and this situation imposes a serious challenge to workload characterization, which is the foundation of innovative system and architecture design. The previous major efforts on big data benchmarking either propose a comprehensive but a large amount of workloads, or only select a few workloads according to so-called popularity, which may lead to partial or even biased observations. In this paper, on the basis of a comprehensive big data benchmark suite---BigDataBench, we reduced 77 workloads to 17 representative workloads from a micro-architectural perspective. On a typical state-of-practice platform---Intel Xeon E5645, we compare the representative big data workloads with SPECINT, SPECCFP, PARSEC, CloudSuite and HPCC. After a comprehensive workload characterization, we have the following observations. First, the big data workloads are data movement dominated computing with more branch operations, taking up to 92% percentage in terms of instruction mix, which places them in a different class from Desktop (SPEC CPU2006), CMP (PARSEC), HPC (HPCC) workloads. Second, corroborating the previous work, Hadoop and Spark based big data workloads have higher front-end stalls. Comparing with the traditional workloads i. e. PARSEC, the big data workloads have larger instructions footprint. But we also note that, in addition to varied instruction-level parallelism, there are significant disparities of front-end efficiencies among different big data workloads. Third, we found complex software stacks that fail to use state-of-practise processors efficiently are one of the main factors leading to high front-end stalls. For the same workloads, the L1I cache miss rates have one order of magnitude differences among diverse implementations with different software stacks.
ASOC: An Adaptive Parameter-free Stochastic Optimization Techinique for Continuous Variables
Venue: arXiv cs.NE 2015
Year: 2015

Stochastic optimization is an important task in many optimization problems where the tasks are not expressible as convex optimization problems. In the case of non-convex optimization problems, various different stochastic algorithms like simulated annealing, evolutionary algorithms, and tabu search are available. Most of these algorithms require user-defined parameters specific to the problem in order to find out the optimal solution. Moreover, in many situations, iterative fine-tunings are required for the user-defined parameters, and therefore these algorithms cannot adapt if the search space and the optima changes over time. In this paper we propose an \underline{a}daptive parameter-free \underline{s}tochastic \underline{o}ptimization technique for \underline{c}ontinuous random variables called ASOC.
Humor in Collective Discourse: Unsupervised Funniness Detection in the New Yorker Cartoon Caption Contest
Venue: arXiv cs.CL 2015
Year: 2015

The New Yorker publishes a weekly captionless cartoon. More than 5,000 readers submit captions for it. The editors select three of them and ask the readers to pick the funniest one. We describe an experiment that compares a dozen automatic methods for selecting the funniest caption. We show that negative sentiment, human-centeredness, and lexical centrality most strongly match the funniest captions, followed by positive sentiment. These results are useful for understanding humor and also in the design of more engaging conversational agents in text and multimodal (vision+text) systems. As part of this work, a large set of cartoons and captions is being made available to the community.
The Third Infoscape: Data, Information and Knowledge in the city. New paradigms for urban interaction
Venue: arXiv cs.CY 2015
Year: 2015

The Third Infoscape refers to the information and knowledge generated through the myriads of micro-histories, through the progressive, emergent and polyphonic sedimentation of the expressions of the daily lives of city dwellers. To all effects, with the development of wireless sensors, of smart dust1, and with the possibility to engage human beings in urban sensing processes, the dimension of virtuality collapses. Heading towards a state which is basically comparable to the one of telepathy (among human beings, human beings and machines, machines and machines...), reconfiguring urban ecologies so that mapping virtuality or physicality would not be needed anymore, and replacing this need with the possibility to create recombinant inventories of the telepathic migration of dusts, of the myriads of pulverized sensors which are disseminated, diffused. We can imagine information mutating into landscape, delineating an urban space which is not determined by distance and time, but from the transformation of densities and presences.
Generalized Space and Frequency Index Modulation
Venue: arXiv cs.IT 2015
Year: 2015

Unlike in conventional modulation where information bits are conveyed only through symbols from modulation alphabets defined in the complex plane (e.g., quadrature amplitude modulation (QAM), phase shift keying (PSK)), in index modulation (IM), additional information bits are conveyed through indices of certain transmit entities that get involved in the transmission. Transmit antennas in multi-antenna systems and subcarriers in multi-carrier systems are examples of such transmit entities that can be used to convey additional information bits through indexing. In this paper, we introduce {\em generalized space and frequency index modulation}, where the indices of active transmit antennas and subcarriers convey information bits. We first introduce index modulation in the spatial domain, referred to as generalized spatial index modulation (GSIM). For GSIM, where bits are indexed only in the spatial domain, we derive the expression for achievable rate as well as easy-to-compute upper and lower bounds on this rate. We show that the achievable rate in GSIM can be more than that in spatial multiplexing, and analytically establish the condition under which this can happen. It is noted that GSIM achieves this higher rate using fewer transmit radio frequency (RF) chains compared to spatial multiplexing. We also propose a Gibbs sampling based detection algorithm for GSIM and show that GSIM can achieve better bit error rate (BER) performance than spatial multiplexing. For generalized space-frequency index modulation (GSFIM), where bits are encoded through indexing in both active antennas as well as subcarriers, we derive the achievable rate expression. Numerical results show that GSFIM can achieve higher rates compared to conventional MIMO-OFDM. Also, BER results show the potential for GSFIM performing better than MIMO-OFDM.
On the H-Free Extension Complexity of the TSP
Venue: arXiv cs.CC 2015
Year: 2015

It is known that the extension complexity of the TSP polytope for the complete graph $K_n$ is exponential in $n$ even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets $\mathcal{H}$ of facet-defining inequalities of the TSP polytope. In particular, we consider the case when $\mathcal{H}$ is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called $(h,t)$-uniform inequalities, which may be of independent interest.
Threshold for the Outbreak of Cascading Failures in Degree-degree Uncorrelated Networks
Venue: arXiv cs.SI 2015
Year: 2015

In complex networks, the failure of one or very few nodes may cause cascading failures. When this dynamical process stops in steady state, the size of the giant component formed by remaining un-failed nodes can be used to measure the severity of cascading failures, which is critically important for estimating the robustness of networks. In this paper, we provide a cascade of overload failure model with local load sharing mechanism, and then explore the threshold of node capacity when the large-scale cascading failures happen and un-failed nodes in steady state cannot connect to each other to form a large connected sub-network. We get the theoretical derivation of this threshold in degree-degree uncorrelated networks, and validate the effectiveness of this method in simulation. This threshold provide us a guidance to improve the network robustness under the premise of limited capacity resource when creating a network and assigning load. Therefore, this threshold is useful and important to analyze the robustness of networks.
A Common Information-Based Multiple Access Protocol Achieving Full Throughput and Linear Delay
Venue: arXiv cs.NI 2015
Year: 2015

We consider a multiple access communication system where multiple users share a common collision channel. Each user observes its local traffic and the feedback from the channel. At each time instant the feedback from the channel is one of three messages: no transmission, successful transmission, collision. The objective is to design a transmission protocol that coordinates the users' transmissions and achieves high throughput and low delay. We present a decentralized Common Information-Based Multiple Access (CIMA) protocol that has the following features: (i) it achieves the full throughput region of the collision channel; (ii) it results in a delay that is linear in the number of users, and is significantly lower than that of CSMA protocols; (iii) it avoids collisions without channel sensing.
Tell and Predict: Kernel Classifier Prediction for Unseen Visual Classes from Unstructured Text Descriptions
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we propose a framework for predicting kernelized classifiers in the visual domain for categories with no training images where the knowledge comes from textual description about these categories. Through our optimization framework, the proposed approach is capable of embedding the class-level knowledge from the text domain as kernel classifiers in the visual domain. We also proposed a distributional semantic kernel between text descriptions which is shown to be effective in our setting. The proposed framework is not restricted to textual descriptions, and can also be applied to other forms knowledge representations. Our approach was applied for the challenging task of zero-shot learning of fine-grained categories from text descriptions of these categories.
Structural Vulnerability Analysis of Electric Power Distribution Grids
Venue: arXiv cs.SY 2015
Year: 2015

Power grid outages cause huge economical and societal costs. Disruptions in the power distribution grid are responsible for a significant fraction of electric power unavailability to customers. The impact of extreme weather conditions, continuously increasing demand, and the over-ageing of assets in the grid, deteriorates the safety of electric power delivery in the near future. It is this dependence on electric power that necessitates further research in the power distribution grid security assessment. Thus measures to analyze the robustness characteristics and to identify vulnerabilities as they exist in the grid are of utmost importance. This research investigates exactly those concepts- the vulnerability and robustness of power distribution grids from a topological point of view, and proposes a metric to quantify them with respect to assets in a distribution grid. Real-world data is used to demonstrate the applicability of the proposed metric as a tool to assess the criticality of assets in a distribution grid.
A differential analysis of the power flow equations
Venue: arXiv cs.SY 2015
Year: 2015

The AC power flow equations are fundamental in all aspects of power systems planning and operations. They are routinely solved using Newton-Raphson like methods. However, there is little theoretical understanding of when these algorithms are guaranteed to find a solution of the power flow equations or how long they may take to converge. Further, it is known that in general these equations have multiple solutions and can exhibit chaotic behavior. In this paper, we show that the power flow equations can be solved efficiently provided that the solution lies in a certain set. We introduce a family of convex domains, characterized by Linear Matrix Inequalities, in the space of voltages such that there is at most one power flow solution in each of these domains. Further, if a solution exists in one of these domains, it can be found efficiently, and if one does not exist, a certificate of non-existence can also be obtained efficiently. The approach is based on the theory of monotone operators and related algorithms for solving variational inequalities involving monotone operators. We validate our approach on IEEE test networks and show that practical power flow solutions lie within an appropriately chosen convex domain.