OpenRaiser/Intern-Atlas huggingface dataset:
Gradient-Domain Fusion for Color Correction in Large EM Image Stacks
Venue: arXiv cs.GR 2015
Year: 2015

We propose a new gradient-domain technique for processing registered EM image stacks to remove inter-image discontinuities while preserving intra-image detail. To this end, we process the image stack by first performing anisotropic smoothing along the slice axis and then solving a Poisson equation within each slice to re-introduce the detail. The final image stack is continuous across the slice axis and maintains sharp details within each slice. Adapting existing out-of-core techniques for solving the linear system, we describe a parallel algorithm with time complexity that is linear in the size of the data and space complexity that is sub-linear, allowing us to process datasets as large as five teravoxels with a 600 MB memory footprint.
Nested Lattice Codes for Secure Bidirectional Relaying with Asymmetric Channel Gains
Venue: arXiv cs.IT 2015
Year: 2015

The basic problem of secure bidirectional relaying involves two users who want to exchange messages via an intermediate "honest-but-curious" relay node. There is no direct link between the users, all communication must take place via the relay node. The links between the user nodes and the relay are wireless links with Gaussian noise. It is required that the users' messages be kept secure from the relay. In prior work, we proposed coding schemes based on nested lattices for this problem, assuming that the channel gains from the two user nodes to the relay are identical. We also analyzed the power-rate tradeoff for secure and reliable message exchange using our coding schemes. In this paper, we extend our prior work to the case when the channel gains are not necessarily identical, and are known to the relay node but perhaps not to the users. We show that using our scheme, perfect secrecy can be obtained only for certain values of the channel gains, and analyze the power-rate tradeoff in these cases. We also make similar observations for our strongly-secure scheme.
Considering Human Aspects on Strategies for Designing and Managing Distributed Human Computation
Venue: arXiv cs.HC 2015
Year: 2015

A human computation system can be viewed as a distributed system in which the processors are humans, called workers. Such systems harness the cognitive power of a group of workers connected to the Internet to execute relatively simple tasks, whose solutions, once grouped, solve a problem that systems equipped with only machines could not solve satisfactorily. Examples of such systems are Amazon Mechanical Turk and the Zooniverse platform. A human computation application comprises a group of tasks, each of them can be performed by one worker. Tasks might have dependencies among each other. In this study, we propose a theoretical framework to analyze such type of application from a distributed systems point of view. Our framework is established on three dimensions that represent different perspectives in which human computation applications can be approached: quality-of-service requirements, design and management strategies, and human aspects. By using this framework, we review human computation in the perspective of programmers seeking to improve the design of human computation applications and managers seeking to increase the effectiveness of human computation infrastructures in running such applications. In doing so, besides integrating and organizing what has been done in this direction, we also put into perspective the fact that the human aspects of the workers in such systems introduce new challenges in terms of, for example, task assignment, dependency management, and fault prevention and tolerance. We discuss how they are related to distributed systems and other areas of knowledge.
Kasami type codes of higher relative dimension
Venue: arXiv cs.IT 2015
Year: 2015

Some new Kasami type codes of higher relative dimension is introduced. Their weight distribution is determined.
On approximating tree spanners that are breadth first search trees
Venue: arXiv cs.CC 2015
Year: 2015

A tree $t$-spanner $T$ of a graph $G$ is a spanning tree of $G$ such that the distance in $T$ between every pair of verices is at most $t$ times the distance in $G$ between them. There are efficient algorithms that find a tree $t\cdot O(\log n)$-spanner of a graph $G$, when $G$ admits a tree $t$-spanner. In this paper, the search space is narrowed to $v$-concentrated spanning trees, a simple family that includes all the breadth first search trees starting from vertex $v$. In this case, it is not easy to find approximate tree spanners within factor almost $o(\log n)$. Specifically, let $m$ and $t$ be integers, such that $m>0$ and $t\geq 7$. If there is an efficient algorithm that receives as input a graph $G$ and a vertex $v$ and returns a $v$-concentrated tree $t\cdot o((\log n)^{m/(m+1)})$-spanner of $G$, when $G$ admits a $v$-concentrated tree $t$-spanner, then there is an algorithm that decides 3-SAT in quasi-polynomial time.
Topological abstraction of higher-dimensional automata
Venue: arXiv cs.FL 2015
Year: 2015

Higher-dimensional automata constitute a very expressive model for concurrent systems. In this paper, we discuss "topological abstraction" of higher-dimensional automata, i.e., the replacement of HDAs by smaller ones that can be considered equivalent from both a computer scientific and a topological point of view. By definition, topological abstraction preserves the homotopy type, the trace category, and the homology graph of an HDA. We establish conditions under which cube collapses yield topological abstractions of HDAs.
A Framework for Constrained and Adaptive Behavior-Based Agents
Venue: arXiv cs.AI 2015
Year: 2015

Behavior Trees are commonly used to model agents for robotics and games, where constrained behaviors must be designed by human experts in order to guarantee that these agents will execute a specific chain of actions given a specific set of perceptions. In such application areas, learning is a desirable feature to provide agents with the ability to adapt and improve interactions with humans and environment, but often discarded due to its unreliability. In this paper, we propose a framework that uses Reinforcement Learning nodes as part of Behavior Trees to address the problem of adding learning capabilities in constrained agents. We show how this framework relates to Options in Hierarchical Reinforcement Learning, ensuring convergence of nested learning nodes, and we empirically show that the learning nodes do not affect the execution of other nodes in the tree.
Reflection Invariance: an important consideration of image orientation
Venue: arXiv cs.CV 2015
Year: 2015

In this position paper, we consider the state of computer vision research with respect to invariance to the horizontal orientation of an image -- what we term reflection invariance. We describe why we consider reflection invariance to be an important property and provide evidence where the absence of this invariance produces surprising inconsistencies in state-of-the-art systems. We demonstrate inconsistencies in methods of object detection and scene classification when they are presented with images and the horizontal mirror of those images. Finally, we examine where some of the invariance is exhibited in feature detection and descriptors, and make a case for future consideration of reflection invariance as a measure of quality in computer vision algorithms.
Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives
Venue: arXiv cs.GT 2015
Year: 2015

We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest nonzero probability employed. Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single nonabsorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting stationary epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience may be needed for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.
NP-hardness of sortedness constraints
Venue: arXiv cs.CC 2015
Year: 2015

In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, several sortedness constraints have been defined, for which propagation algorithms are available, but for which the tractability is not settled. We show that the sort(U,V) constraint (Older et. al, 1995) is intractable for integer variables whose domains are not limited to intervals. As a consequence, the similar result holds for the sort(U,V, P) constraint (Zhou, 1996). Moreover, the intractability holds even under the stability condition present in the recently introduced keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014), and requiring that the order of the variables with the same value in the list U be preserved in the list V. Therefore, keysorting(U,V,Keys,P) is intractable as well.
SVM and ELM: Who Wins? Object Recognition with Deep Convolutional Features from ImageNet
Venue: arXiv cs.LG 2015
Year: 2015

Deep learning with a convolutional neural network (CNN) has been proved to be very effective in feature extraction and representation of images. For image classification problems, this work aim at finding which classifier is more competitive based on high-level deep features of images. In this report, we have discussed the nearest neighbor, support vector machines and extreme learning machines for image classification under deep convolutional activation feature representation. Specifically, we adopt the benchmark object recognition dataset from multiple sources with domain bias for evaluating different classifiers. The deep features of the object dataset are obtained by a well-trained CNN with five convolutional layers and three fully-connected layers on the challenging ImageNet. Experiments demonstrate that the ELMs outperform SVMs in cross-domain recognition tasks. In particular, state-of-the-art results are obtained by kernel ELM which outperforms SVMs with about 4% of the average accuracy. The features and codes are available in http://www.escience.cn/people/lei/index.html
Learning Mixtures of Ising Models using Pseudolikelihood
Venue: arXiv cs.LG 2015
Year: 2015

Maximum pseudolikelihood method has been among the most important methods for learning parameters of statistical physics models, such as Ising models. In this paper, we study how pseudolikelihood can be derived for learning parameters of a mixture of Ising models. The performance of the proposed approach is demonstrated for Ising and Potts models on both synthetic and real data.
Fast ConvNets Using Group-wise Brain Damage
Venue: arXiv cs.CV 2015
Year: 2015

We revisit the idea of brain damage, i.e. the pruning of the coefficients of a neural network, and suggest how brain damage can be modified and used to speedup convolutional layers. The approach uses the fact that many efficient implementations reduce generalized convolutions to matrix multiplications. The suggested brain damage process prunes the convolutional kernel tensor in a group-wise fashion by adding group-sparsity regularization to the standard training process. After such group-wise pruning, convolutions can be reduced to multiplications of thinned dense matrices, which leads to speedup. In the comparison on AlexNet, the method achieves very competitive performance.
Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, fits into the framework of RC-FDM. We prove linear convergence for both R-FDM and RC-FDM under the weak strong convexity assumption. Moreover, we show that the duality gap converges linearly for RC-FDM, which implies that the duality gap also converges linearly for SDCA applied to the SVM dual problem.
A novel approach to Service Discovery in Mobile Adhoc Network
Venue: arXiv cs.NI 2015
Year: 2015

Mobile Adhoc Network (MANET) is a network of a number of mobile routers and associated hosts, organized in a random fashion via wireless links. During recent years MANET has gained enormous amount of attention and has been widely used for not only military purposes but for search-and-rescue operations, intelligent transportation system, data collection, virtual classrooms and ubiquitous computing. Service Discovery is one of the most important issues in MANET. It is defined as the process of facilitating service providers to advertise their services in a dynamic way and to allow consumers to discover and access those services in an efficient and scalable manner. In this paper, we are proposing a flexible and efficient approach to service discovery for MANET by extending the work of Torres et al. (2004)...
Service Discovery in Mobile Ad hoc Networks Using Association Rules Mining
Venue: arXiv cs.NI 2015
Year: 2015

We have proposed a novel approach to Service Discovery in Mobile Ad hoc Networks. We have simulated the proposed approach in JIST/SWANS simulator and the results have shown significant performance improvement.
Software Carpentry get more done in less time
Venue: arXiv cs.CY 2015
Year: 2015

The aim of this study was to investigate if participants of Software Carpentry (SC) get more done in less time. We asked 32 questions to assess 24 former participants to analyse if SC gave them the computing skills to accomplish this. Our research shows that time was already saved during the workshop as it could shorten the learning process of new skills. A majority of participants were able to use these new skills straight away and thus could speed up their day to day work.
Circulant temporal encoding for video retrieval and temporal alignment
Venue: arXiv cs.CV 2015
Year: 2015

We address the problem of specific video event retrieval. Given a query video of a specific event, e.g., a concert of Madonna, the goal is to retrieve other videos of the same event that temporally overlap with the query. Our approach encodes the frame descriptors of a video to jointly represent their appearance and temporal order. It exploits the properties of circulant matrices to efficiently compare the videos in the frequency domain. This offers a significant gain in complexity and accurately localizes the matching parts of videos. The descriptors can be compressed in the frequency domain with a product quantizer adapted to complex numbers. In this case, video retrieval is performed without decompressing the descriptors. We also consider the temporal alignment of a set of videos. We exploit the matching confidence and an estimate of the temporal offset computed for all pairs of videos by our retrieval approach. Our robust algorithm aligns the videos on a global timeline by maximizing the set of temporally consistent matches. The global temporal alignment enables synchronous playback of the videos of a given scene.
Interference as Noise: Friend or Foe?
Venue: arXiv cs.IT 2015
Year: 2015

This paper shows that for the two-user Gaussian Interference Channel (G-IC) Treating Interference as Noise without Time Sharing (TINnoTS) achieves the closure of the capacity region to within either a constant gap, or to within a gap of the order O(logln(min(S,I))) where S is the largest Signal to Noise Ratio (SNR) on the direct links and I is the largest Interference to Noise Ratio (INR) on the cross links. As a consequence, TINnoTS is optimal from a generalized Degrees of Freedom (gDoF) perspective for all channel gains except for a subset of zero measure. TINnoTS with Gaussian inputs is known to be optimal to within 1/2 bit for a subset of the weak interference regime. Surprisingly, this paper shows that TINnoTS is gDoG optimal in all parameter regimes, even in the strong and very strong interference regimes where joint decoding of Gaussian inputs is optimal. For approximate optimality of TINnoTS in all parameter regimes it is critical to use non-Gaussian inputs. This work thus proposes to use mixed inputs as channel inputs where a mixed input is the sum of a discrete and a Gaussian random variable. Interestingly, compared to the Han-Kobayashi inner bound, the discrete part of a mixed input is shown to effectively act as a common message in the sense that, although treated as noise, its effect on the achievable rate region is as if it were jointly decoded together with the desired messages at a non-intended receiver. The practical implication is that a discrete interfering input is a 'friend', while a Gaussian interfering input is in general a 'foe'. Since TINnoTS requires neither joint decoding nor time sharing, the results of this paper are applicable to a variety of oblivions or asynchronous channels, such as the block asynchronous G-IC (which is not an information stable) and the G-IC with partial codebook knowledge at one or more receivers.
Using complex networks towards information retrieval and diagnostics in multidimensional imaging
Venue: arXiv cs.IR 2015
Year: 2015

We present a fresh and broad yet simple approach towards information retrieval in general and diagnostics in particular by applying the theory of complex networks on multidimensional, dynamic images. We demonstrate a successful use of our method with the time series generated from high content thermal imaging videos of patients suffering from the aqueous deficient dry eye (ADDE) disease. Remarkably, network analyses of thermal imaging time series of contact lens users and patients upon whom Laser-Assisted in situ Keratomileusis (Lasik) surgery has been conducted, exhibit pronounced similarity with results obtained from ADDE patients. We also propose a general framework for the transformation of multidimensional images to networks for futuristic biometry. Our approach is general and scalable to other fluctuation-based devices where network parameters derived from fluctuations, act as effective discriminators and diagnostic markers.
An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Venue: arXiv cs.CR 2015
Year: 2015

In this paper, we study the Learning With Errors problem and its binary variant, where secrets and errors are binary or taken in a small interval. We introduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on a quantization step that generalizes and fine-tunes modulus switching. In general this new technique yields a significant gain in the constant in front of the exponent in the overall complexity. We illustrate this by solving p within half a day a LWE instance with dimension n = 128, modulus $q = n^2$, Gaussian noise $α= 1/(\sqrt{n/π} \log^2 n)$ and binary secret, using $2^{28}$ samples, while the previous best result based on BKW claims a time complexity of $2^{74}$ with $2^{60}$ samples for the same parameters. We then introduce variants of BDD, GapSVP and UniqueSVP, where the target point is required to lie in the fundamental parallelepiped, and show how the previous algorithm is able to solve these variants in subexponential time. Moreover, we also show how the previous algorithm can be used to solve the BinaryLWE problem with n samples in subexponential time $2^{(\ln 2/2+o(1))n/\log \log n}$. This analysis does not require any heuristic assumption, contrary to other algebraic approaches; instead, it uses a variant of an idea by Lyubashevsky to generate many samples from a small number of samples. This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its security assumption). We are also able to solve subset sum problems in subexponential time for density $o(1)$, which is of independent interest: for such density, the previous best algorithm requires exponential time. As a direct application, we can solve in subexponential time the parameters of a cryptosystem based on this problem proposed at TCC 2010.
Weighted Impact Factor (WIF) for assessing the quality of scientific journals
Venue: arXiv cs.DL 2015
Year: 2015

Nowadays impact factor is the significant indicator for journal evaluation. In impact factor calculation is used number of all citations to journal, regardless of the prestige of cited journals, however, scientific units (paper, researcher, journal or scientific organization) cited by journals with high impact factor or researchers with high Hirsch index are more important than objects cited by journals without impact factor or unknown researcher. In this paper was offered weighted impact factor for getting more accurate rankings for journals, which consider not only quantity of citations, but also quality of citing journals. Correlation coefficients among different indicators for journal evaluation: impact factors by Thomson Scientific, weighted impact factors offered by different researchers, average and medians of all citing journals impact factors and 5-year impact factors were analysed.
Syntactic semigroup problem for the semigroup reducts of Affine Near-semirings over Brandt Semigroups
Venue: arXiv cs.FL 2015
Year: 2015

The syntactic semigroup problem is to decide whether a given finite semigroup is syntactic or not. This work investigates the syntactic semigroup problem for both the semigroup reducts of $A^+(B_n)$, the affine near-semiring over a Brandt semigroup $B_n$. It is ascertained that both the semigroup reducts of $A^+(B_n)$ are syntactic semigroups.
Fast and simple connectivity in graph timelines
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we study the problem of answering connectivity queries about a \emph{graph timeline}. A graph timeline is a sequence of undirected graphs $G_1,\ldots,G_t$ on a common set of vertices of size $n$ such that each graph is obtained from the previous one by an addition or a deletion of a single edge. We present data structures, which preprocess the timeline and can answer the following queries: - forall$(u,v,a,b)$ -- does the path $u\to v$ exist in each of $G_a,\ldots,G_b$? - exists$(u,v,a,b)$ -- does the path $u\to v$ exist in any of $G_a,\ldots,G_b$? - forall2$(u,v,a,b)$ -- do there exist two edge-disjoint paths connecting $u$ and $v$ in each of $G_a,\ldots,G_b$ We show data structures that can answer forall and forall2 queries in $O(\log n)$ time after preprocessing in $O(m+t\log n)$ time. Here by $m$ we denote the number of edges that remain unchanged in each graph of the timeline. For the case of exists queries, we show how to extend an existing data structure to obtain a preprocessing/query trade-off of $\langle O(m+\min(nt, t^{2-α})), O(t^α)\rangle$ and show a matching conditional lower bound.