OpenRaiser/Intern-Atlas huggingface dataset:
On Vertex Sparsifiers with Steiner Nodes
Venue: arXiv cs.DS 2012
Year: 2012

Given an undirected graph $G=(V,E)$ with edge capacities $c_e\geq 1$ for $e\in E$ and a subset $T$ of $k$ vertices called terminals, we say that a graph $H$ is a quality-$q$ cut sparsifier for $G$ iff $T\subseteq V(H)$, and for any partition $(A,B)$ of $T$, the values of the minimum cuts separating $A$ and $B$ in graphs $G$ and $H$ are within a factor $q$ from each other. We say that $H$ is a quality-$q$ flow sparsifier for $G$ iff $T\subseteq V(H)$, and for any set $D$ of demands over the terminals, the values of the minimum edge congestion incurred by fractionally routing the demands in $D$ in graphs $G$ and $H$ are within a factor $q$ from each other. So far vertex sparsifiers have been studied in a restricted setting where the sparsifier $H$ is not allowed to contain any non-terminal vertices, that is $V(H)=T$. For this setting, efficient algorithms are known for constructing quality-$O(\log k/\log\log k)$ cut and flow vertex sparsifiers, as well as a lower bound of $\tildeΩ(\sqrt{\log k})$ on the quality of any flow or cut sparsifier. We study flow and cut sparsifiers in the more general setting where Steiner vertices are allowed, that is, we no longer require that $V(H)=T$. We show algorithms to construct constant-quality cut sparsifiers of size $O(C^3)$ in time $\poly(n)\cdot 2^C$, and constant-quality flow sparsifiers of size $C^{O(\log\log C)}$ in time $n^{O(\log C)}\cdot 2^C$, where $C$ is the total capacity of the edges incident on the terminals.
Secure Comparison Without Explicit XOR
Venue: arXiv cs.CR 2012
Year: 2012

We propose an efficient protocol for secure comparison of integers when both integers are shared between two parties. Such protocols are useful for implementing secure auctions. The proposed protocol's computational complexity is roughly half the complexity of the best known efficient protocol. The efficiency of the proposed protocol stems from the removal of the XOR computation which is a time consuming operation.
Designing an Energy Efficient Framework for Data Gathering in Wireless Sensor Network
Venue: arXiv cs.NI 2012
Year: 2012

Wireless sensor network (WSN) is a collection of nodes which can communicate with each other without any prior infrastructure along with the ability to collect data autonomously and effectively after being deployed in an ad-hoc fashion to monitor a given area. One major problem encountered in data gathering wireless systems is to obtain an optimal balance among the number of nodes deployed, energy efficiency and lifetime as energy of nodes cannot be replenished. In this paper we propose first a scheme to estimate the number of nodes to be deployed in a WSN for a predetermined lifetime so that total energy utilization and complete connectivity are ensured under all circumstances. This scheme also guarantees that during each data gathering cycle, every node dissipates the requisite amount of energy, which thus minimizes the number of nodes required to achieve the desired network lifetime. Second, this paper has proposed a framework to conduct data gathering in WSN. Extensive simulations have been carried out in ns2 to establish the effectiveness of this framework.
Secret Key Agreement Using Correlated Sources over the Generalized Multiple Access Channel
Venue: arXiv cs.IT 2012
Year: 2012

A secret key agreement setup between three users is considered in which each of the users 1 and 2 intends to share a secret key with user 3 and users 1 and 2 are eavesdroppers with respect to each other. The three users observe i.i.d. outputs of correlated sources and there is a generalized discrete memoryless multiple access channel (GDMMAC) from users 1 and 2 to user 3 for communication between the users. The secret key agreement is established using the correlated sources and the GDMMAC. In this setup, inner and outer bounds of the secret key capacity region are investigated. Moreover, for a special case where the channel inputs and outputs and the sources form Markov chains in some order, the secret key capacity region is derived. Also a Gaussian case is considered in this setup.
Proving Termination of Probabilistic Programs Using Patterns
Venue: arXiv cs.LO 2012
Year: 2012

Proving programs terminating is a fundamental computer science challenge. Recent research has produced powerful tools that can check a wide range of programs for termination. The analog for probabilistic programs, namely termination with probability one ("almost-sure termination"), is an equally important property for randomized algorithms and probabilistic protocols. We suggest a novel algorithm for proving almost-sure termination of probabilistic programs. Our algorithm exploits the power of state-of-the-art model checkers and termination provers for nonprobabilistic programs: it calls such tools within a refinement loop and thereby iteratively constructs a "terminating pattern", which is a set of terminating runs with probability one. We report on various case studies illustrating the effectiveness of our algorithm. As a further application, our algorithm can improve lower bounds on reachability probabilities.
Realizable Rate Distortion Function and Bayesian FIltering Theory
Venue: arXiv cs.IT 2012
Year: 2012

The relation between rate distortion function (RDF) and Bayesian filtering theory is discussed. The relation is established by imposing a causal or realizability constraint on the reconstruction conditional distribution of the RDF, leading to the definition of a causal RDF. Existence of the optimal reconstruction distribution of the causal RDF is shown using the topology of weak convergence of probability measures. The optimal non-stationary causal reproduction conditional distribution of the causal RDF is derived in closed form; it is given by a set of recursive equations which are computed backward in time. The realization of causal RDF is described via the source-channel matching approach, while an example is briefly discussed to illustrate the concepts.
Analytic Methods for Optimizing Realtime Crowdsourcing
Venue: arXiv cs.SI 2012
Year: 2012

Realtime crowdsourcing research has demonstrated that it is possible to recruit paid crowds within seconds by managing a small, fast-reacting worker pool. Realtime crowds enable crowd-powered systems that respond at interactive speeds: for example, cameras, robots and instant opinion polls. So far, these techniques have mainly been proof-of-concept prototypes: research has not yet attempted to understand how they might work at large scale or optimize their cost/performance trade-offs. In this paper, we use queueing theory to analyze the retainer model for realtime crowdsourcing, in particular its expected wait time and cost to requesters. We provide an algorithm that allows requesters to minimize their cost subject to performance requirements. We then propose and analyze three techniques to improve performance: push notifications, shared retainer pools, and precruitment, which involves recalling retainer workers before a task actually arrives. An experimental validation finds that precruited workers begin a task 500 milliseconds after it is posted, delivering results below the one-second cognitive threshold for an end-user to stay in flow.
Building Fastest Broadcast Trees in Periodically-Varying Graphs
Venue: arXiv cs.DC 2012
Year: 2012

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Still, connectivity can generally be established over time and space. The optimality of a temporal path (journey) in this context can be defined in several terms, including topological (e.g. {\em shortest} in hops) and temporal (e.g. {\em fastest, foremost}). The combinatorial problem of computing shortest, foremost, and fastest journeys {\em given full knowledge} of the network schedule was addressed a decade ago (Bui-Xuan {\it et al.}, 2003). A recent line of research has focused on the distributed version of this problem, where foremost, shortest or fastest {\em broadcast} are performed without knowing the schedule beforehand. In this paper we show how to build {\em fastest} broadcast trees (i.e., trees that minimize the global duration of the broadcast, however late the departure is) in Time-Varying Graphs where intermittent edges are available periodically (it is known that the problem is infeasible in the general case even if various parameters of the graph are know). We address the general case where contacts between nodes can have arbitrary durations and thus fastest routes may consist of a mixture of {\em continuous} and {\em discontinuous} segments (a more complex scenario than when contacts are {\em punctual} and thus routes are only discontinuous). Using the abstraction of \tclocks to compute the temporal distances, we solve the fastest broadcast problem by first learning, at the emitter, what is its time of {\em minimum temporal eccentricity} (i.e. the fastest time to reach all the other nodes), and second by building a {\em foremost} broadcast tree relative to this particular emission date.
Neuroevolution Results in Emergence of Short-Term Memory for Goal-Directed Behavior
Venue: arXiv cs.NE 2012
Year: 2012

Animals behave adaptively in the environment with multiply competing goals. Understanding of the mechanisms underlying such goal-directed behavior remains a challenge for neuroscience as well for adaptive system research. To address this problem we developed an evolutionary model of adaptive behavior in the multigoal stochastic environment. Proposed neuroevolutionary algorithm is based on neuron's duplication as a basic mechanism of agent's recurrent neural network development. Results of simulation demonstrate that in the course of evolution agents acquire the ability to store the short-term memory and, therefore, use it in behavioral strategies with alternative actions. We found that evolution discovered two mechanisms for short-term memory. The first mechanism is integration of sensory signals and ongoing internal neural activity, resulting in emergence of cell groups specialized on alternative actions. And the second mechanism is slow neurodynamical processes that makes possible to code the previous behavioral choice.
Information, Community, and Action: How Nonprofit Organizations Use Social Media
Venue: arXiv cs.CY 2012
Year: 2012

The rapid diffusion of "microblogging" services such as Twitter is ushering in a new era of possibilities for organizations to communicate with and engage their core stakeholders and the general public. To enhance understanding of the communicative functions microblogging serves for organizations, this study examines the Twitter utilization practices of the 100 largest nonprofit organizations in the United States. The analysis reveals there are three key functions of microblogging updates-"information," "community," and "action." Though the informational use of microblogging is extensive, nonprofit organizations are better at using Twitter to strategically engage their stakeholders via dialogic and community-building practices than they have been with traditional websites. The adoption of social media appears to have engendered new paradigms of public engagement. Keywords: microblogging; Twitter; social media; stakeholder relations; organizational communication; organization-public relations; nonprofit organizations
Optimizing the Medium Access Control in Multi-hop Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of geometric optimization of medium access control in multi-hop wireless network. We discuss the optimal placements of simultaneous transmitters in the network and our general framework allows us to evaluate the performance gains of highly managed medium access control schemes that would be required to implement these placements. In a wireless network consisting of randomly distributed nodes, our performance metrics are the optimum transmission range that achieves the most optimal tradeoff between the progress of packets in desired directions towards their respective destinations and the total number of transmissions required to transport packets to their destinations. We evaluate ALOHA based scheme where simultaneous transmitters are dispatched according to a uniform Poisson distribution and compare it with various grid pattern based schemes where simultaneous transmitters are positioned in specific regular patterns. Our results show that optimizing the medium access control in multi-hop network should take into account the parameters like signal-to-interference ratio threshold and attenuation coefficient. For instance, at typical values of signal-to-interference ratio threshold and attenuation coefficient, the most optimal scheme is based on triangular grid pattern and, under no fading channel model, the most optimal transmission range and network capacity are higher than the optimum transmission range and capacity achievable with ALOHA based scheme by factors of two and three respectively. Later on, we also identify the optimal medium access control schemes when signal-to-interference ratio threshold and attenuation coefficient approach the extreme values and discuss how fading impacts the performance of all schemes we evaluate in this article.
Assessing and improving an approach to delay-tolerant networking
Venue: arXiv cs.NI 2012
Year: 2012

Delay-tolerant networking (DTN) is a term invented to describe and encompass all types of long-delay, disconnected, disrupted or intermittently-connected networks, where mobility and outages or scheduled contacts may be experienced. 'DTN' is also used to refer to the Bundle Protocol, which has been proposed as the one unifying solution for disparate DTN networking scenarios, after originally being designed solely for use in deep space for the 'Interplanetary Internet.' We evaluated the Bundle Protocol by testing it in space and on the ground. We have found architectural weaknesses in the Bundle Protocol that may prevent engineering deployment of this protocol in realistic delay-tolerant networking scenarios, and have proposed approaches to address these weaknesses.
Broadcast Search in Innovation Contests: Case for Hybrid Models
Venue: arXiv cs.SI 2012
Year: 2012

Organizations use broadcast search to identify new avenues of innovation. Research on innovation contests provides insights on why excellent ideas are created in a broadcast search. However, there is little research on how excellent ideas are selected. Drawing from the brainstorming literature we find that the selection of excellent ideas needs further investigation. We propose that a hybrid model may lead to selection of better ideas. The hybrid model is a broadcast search approach that exploits the strengths of different actors and procedures in idea generation and the selection phase.
A New Low-Complexity Decodable Rate-1 Full-Diversity 4 x 4 STBC with Nonvanishing Determinants
Venue: arXiv cs.IT 2012
Year: 2012

Space-time coding techniques have become common-place in wireless communication standards as they provide an effective way to mitigate the fading phenomena inherent in wireless channels. However, the use of Space-Time Block Codes (STBCs) increases significantly the optimal detection complexity at the receiver unless the low complexity decodability property is taken into consideration in the STBC design. In this letter we propose a new low-complexity decodable rate-1 full-diversity 4 x 4 STBC. We provide an analytical proof that the proposed code has the Non-Vanishing-Determinant (NVD) property, a property that can be exploited through the use of adaptive modulation which changes the transmission rate according to the wireless channel quality. We compare the proposed code to existing low-complexity decodable rate-1 full-diversity 4 x 4 STBCs in terms of performance over quasi-static Rayleigh fading channels, detection complexity and Peak-to-Average Power Ratio (PAPR). Our code is found to provide the best performance and the smallest PAPR which is that of the used QAM constellation at the expense of a slight increase in detection complexity w.r.t. certain previous codes but this will only penalize the proposed code for high-order QAM constellations.
Unequal Error Protected JPEG 2000 Broadcast Scheme with Progressive Fountain Codes
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a novel scheme, based on progressive fountain codes, for broadcasting JPEG 2000 multimedia. In such a broadcast scheme, progressive resolution levels of images/video have been unequally protected when transmitted using the proposed progressive fountain codes. With progressive fountain codes applied in the broadcast scheme, the resolutions of images (JPEG 2000) or videos (MJPEG 2000) received by different users can be automatically adaptive to their channel qualities, i.e. the users with good channel qualities are possible to receive the high resolution images/vedio while the users with bad channel qualities may receive low resolution images/vedio. Finally, the performance of the proposed scheme is evaluated with the MJPEG 2000 broadcast prototype.
Bayesian Data Cleaning for Web Data
Venue: arXiv cs.DB 2012
Year: 2012

Data Cleaning is a long standing problem, which is growing in importance with the mass of uncurated web data. State of the art approaches for handling inconsistent data are systems that learn and use conditional functional dependencies (CFDs) to rectify data. These methods learn data patterns--CFDs--from a clean sample of the data and use them to rectify the dirty/inconsistent data. While getting a clean training sample is feasible in enterprise data scenarios, it is infeasible in web databases where there is no separate curated data. CFD based methods are unfortunately particularly sensitive to noise; we will empirically demonstrate that the number of CFDs learned falls quite drastically with even a small amount of noise. In order to overcome this limitation, we propose a fully probabilistic framework for cleaning data. Our approach involves learning both the generative and error (corruption) models of the data and using them to clean the data. For generative models, we learn Bayes networks from the data. For error models, we consider a maximum entropy framework for combing multiple error processes. The generative and error models are learned directly from the noisy data. We present the details of the framework and demonstrate its effectiveness in rectifying web data.
Automatic Prediction Of Small Group Performance In Information Sharing Tasks
Venue: arXiv cs.SI 2012
Year: 2012

In this paper, we describe a novel approach, based on Markov jump processes, to model small group conversational dynamics and to predict small group performance. More precisely, we estimate conversational events such as turn taking, backchannels, turn-transitions at the micro-level (1 minute windows) and then we bridge the micro-level behavior and the macro-level performance. We tested our approach with a cooperative task, the Information Sharing task, and we verified the relevance of micro- level interaction dynamics in determining a good group performance (e.g. higher speaking turns rate and more balanced participation among group members).
On the Computation of the Higher Order Statistics of the Channel Capacity over Generalized Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

The higher-order statistics (HOS) of the channel capacity $μ_n=\mathbb{E}[\log^n(1+γ_{end})]$, where $n\in\mathbb{N}$ denotes the order of the statistics, has received relatively little attention in the literature, due in part to the intractability of its analysis. In this letter, we propose a novel and unified analysis, which is based on the moment generating function (MGF) technique, to exactly compute the HOS of the channel capacity. More precisely, our mathematical formalism can be readily applied to maximal-ratio-combining (MRC) receivers operating in generalized fading environments (i.e., the sum of the correlated noncentral chi-squared distributions / the correlated generalized Rician distributions). The mathematical formalism is illustrated by some numerical examples focussing on the correlated generalized fading environments.
Computational linear algebra over finite fields
Venue: arXiv cs.SC 2012
Year: 2012

We present here algorithms for efficient computation of linear algebra problems over finite fields.
Collective Creativity: Where we are and where we might go
Venue: arXiv cs.SI 2012
Year: 2012

Creativity is individual, and it is social. The social aspects of creativity have become of increasing interest as systems have emerged that mobilize large numbers of people to engage in creative tasks. We examine research related to collective intelligence and differentiate work on collective creativity from other collective activities by analyzing systems with respect to the tasks that are performed and the outputs that result. Three types of systems are discussed: games, contests and networks. We conclude by suggesting how systems that generate collective creativity can be improved and how new systems might be constructed.
Re-differentiation as collective intelligence: The Ktunaxa language online community
Venue: arXiv cs.SI 2012
Year: 2012

This paper presents preliminary results of an investigation of collectively intelligent behavior in a Native North American speech community. The research reveals several independently initiated strategies organized around the collective problem of language endangerment. Specifically, speakers are engaging in self-organizing efforts to reverse historical language simplification that resulted from cultural trauma. These acts of collective intelligence serve to reduce entropy in speech community identity.
Tracking the 2011 Student-led Collective Movement in Chile through Social Media Use
Venue: arXiv cs.SI 2012
Year: 2012

Using social media archives of the 2011 Chilean student unrest and dynamic social network analysis, we study how leaders and participants use social media such as Twitter, and the Web to self-organize and communicate with each other, and thus generate one of the biggest "smart movements" in the history of Chile. In this paper we i) describe the basic network topology of the 2011 student-led social movement in Chile; ii) explore how the student leaders are connected to, and how are they seen by (a) political leaders, and (b) University authorities; iii) hypothesize about key success factors and risk variables for the Student Network Movement's organization process and sustainability over time. We contend that this social media enabled massive movement is yet another manifestation of the network era, which leverages agents' socio-technical networks, and thus accelerates how agents coordinate, mobilize resources and enact collective intelligence.
Convolutional Neural Networks Applied to House Numbers Digit Classification
Venue: arXiv cs.CV 2012
Year: 2012

We classify digits of real-world house numbers using convolutional neural networks (ConvNets). ConvNets are hierarchical feature learning neural networks whose structure is biologically inspired. Unlike many popular vision approaches that are hand-designed, ConvNets can automatically learn a unique set of features optimized for a given task. We augmented the traditional ConvNet architecture by learning multi-stage features and by using Lp pooling and establish a new state-of-the-art of 94.85% accuracy on the SVHN dataset (45.2% error improvement). Furthermore, we analyze the benefits of different pooling methods and multi-stage features in ConvNets. The source code and a tutorial are available at eblearn.sf.net.