OpenRaiser/Intern-Atlas huggingface dataset:
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
Venue: arXiv cs.CC 2017
Year: 2017

We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any $γ\leq 1 + O(\log n/n)$, we obtain an efficient dimension-preserving reduction from $γ^{O(n/\log n)}$-SVP to $γ$-GapSVP and an efficient dimension-preserving reduction from $γ^{O(n)}$-CVP to $γ$-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when $γ= 1$. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction---we reduce $γ^{O(n/\log n)}$-SVP to $γ$-unique SVP, a potentially easier problem than $γ$-GapSVP.
How the medium shapes the message: Printing and the rise of the arts and sciences
Venue: arXiv cs.CY 2017
Year: 2017

Communication technologies, from printing to social media, affect our historical records by changing the way ideas are spread and recorded. Yet, finding statistical instruments to address the endogeneity of this relationship has been problematic. Here we use a city's distance to Mainz as an instrument for the introduction of the printing press in European cities, together with data on nearly 50 thousand biographies, to show that cities that adopted printing earlier were more likely to be the birthplace of a famous scientist or artist in the years after the introduction of printing. At the global scale, we find that the introduction of printing is associated with a significant and discontinuous increase in the number of biographies available from people born after the introduction of printing. We bring these findings to more recent communication technologies by showing that the number of radios and televisions in a country correlates with the number of performing artists and sports players from that country that reached global fame, even after controlling for GDP, population, and including country and year fixed effects. These findings support the hypothesis that the introduction of communication technologies shift historical records in the direction of the content that is best suited for each technology.
Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
Venue: arXiv cs.IT 2017
Year: 2017

This paper builds theoretical foundations for the recovery of a newly proposed class of smooth graph signals, approximately bandlimited graph signals, under three sampling strategies: uniform sampling, experimentally designed sampling and active sampling. We then state minimax lower bounds on the maximum risk for the approximately bandlimited class under these three sampling strategies and show that active sampling cannot fundamentally outperform experimentally designed sampling. We propose a recovery strategy to compare uniform sampling with experimentally designed sampling. As the proposed recovery strategy lends itself well to statistical analysis, we derive the exact mean square error for each sampling strategy. To study convergence rates, we introduce two types of graphs and find that (1) the proposed recovery strategy achieves the optimal rates; and (2) the experimentally designed sampling fundamentally outperforms uniform sampling for Type-2 class of graphs. To validate our proposed recovery strategy, we test it on five specific graphs: a ring graph with $k$ nearest neighbors, an Erdős-Rényi graph, a random geometric graph, a small-world graph and a power-law graph and find that experimental results match the proposed theory well. This work also presents a comprehensive explanation for when and why sampling for semi-supervised learning with graphs works.
Strong Data Processing Inequalities for Input Constrained Additive Noise Channels
Venue: arXiv cs.IT 2017
Year: 2017

This paper quantifies the intuitive observation that adding noise reduces available information by means of non-linear strong data processing inequalities. Consider the random variables $W\to X\to Y$ forming a Markov chain, where $Y=X+Z$ with $X$ and $Z$ real-valued, independent and $X$ bounded in $L_p$-norm. It is shown that $I(W;Y) \le F_I(I(W;X))$ with $F_I(t)<t$ whenever $t>0$, if and only if $Z$ has a density whose support is not disjoint from any translate of itself. A related question is to characterize for what couplings $(W,X)$ the mutual information $I(W;Y)$ is close to maximum possible. To that end we show that in order to saturate the channel, i.e. for $I(W;Y)$ to approach capacity, it is mandatory that $I(W;X)\to\infty$ (under suitable conditions on the channel). A key ingredient for this result is a deconvolution lemma which shows that post-convolution total variation distance bounds the pre-convolution Kolmogorov-Smirnov distance. Explicit bounds are provided for the special case of the additive Gaussian noise channel with quadratic cost constraint. These bounds are shown to be order-optimal. For this case simplified proofs are provided leveraging Gaussian-specific tools such as the connection between information and estimation (I-MMSE) and Talagrand's information-transportation inequality.
Recent Advances in Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

In the last few years, deep learning has led to very good performance on a variety of problems, such as visual recognition, speech recognition and natural language processing. Among different types of deep neural networks, convolutional neural networks have been most extensively studied. Leveraging on the rapid growth in the amount of the annotated data and the great improvements in the strengths of graphics processor units, the research on convolutional neural networks has been emerged swiftly and achieved state-of-the-art results on various tasks. In this paper, we provide a broad survey of the recent advances in convolutional neural networks. We detailize the improvements of CNN on different aspects, including layer design, activation function, loss function, regularization, optimization and fast computation. Besides, we also introduce various applications of convolutional neural networks in computer vision, speech and natural language processing.
DDoS Attacks in Cloud Computing: Issues, Taxonomy, and Future Directions
Venue: arXiv cs.CR 2017
Year: 2017

Security issues related to the cloud computing are relevant to various stakeholders for an informed cloud adoption decision. Apart from data breaches, the cyber security research community is revisiting the attack space for cloud-specific solutions as these issues affect budget, resource management, and service quality. Distributed Denial of Service (DDoS) attack is one such serious attack in the cloud space. In this paper, we present developments related to DDoS attack mitigation solutions in the cloud. In particular, we present a comprehensive survey with a detailed insight into the characterization, prevention, detection, and mitigation mechanisms of these attacks. Additionally, we present a comprehensive solution taxonomy to classify DDoS attack solutions. We also provide a comprehensive discussion on important metrics to evaluate various solutions. This survey concludes that there is a strong requirement of solutions, which are designed keeping utility computing models in mind. Accurate auto-scaling decisions, multi-layer mitigation, and defense using profound resources in the cloud, are some of the key requirements of the desired solutions. In the end, we provide a definite guideline on effective solution building and detailed solution requirements to help the cyber security research community in designing defense mechanisms. To the best of our knowledge, this work is a novel attempt to identify the need of DDoS mitigation solutions involving multi-level information flow and effective resource management during the attack.
Communicating with sentences: A multi-word naming game model
Venue: arXiv cs.CL 2017
Year: 2017

Naming game simulates the process of naming an object by a single word, in which a population of communicating agents can reach global consensus asymptotically through iteratively pair-wise conversations. We propose an extension of the single-word model to a multi-word naming game (MWNG), simulating the case of describing a complex object by a sentence (multiple words). Words are defined in categories, and then organized as sentences by combining them from different categories. We refer to a formatted combination of several words as a pattern. In such an MWNG, through a pair-wise conversation, it requires the hearer to achieve consensus with the speaker with respect to both every single word in the sentence as well as the sentence pattern, so as to guarantee the correct meaning of the saying, otherwise, they fail reaching consensus in the interaction. We validate the model in three typical topologies as the underlying communication network, and employ both conventional and man-designed patterns in performing the MWNG.
Unveiling Contextual Similarity of Things via Mining Human-Thing Interactions in the Internet of Things
Venue: arXiv cs.CY 2017
Year: 2017

With recent advances in radio-frequency identification (RFID), wireless sensor networks, and Web services, physical things are becoming an integral part of the emerging ubiquitous Web. Finding correlations of ubiquitous things is a crucial prerequisite for many important applications such as things search, discovery, classification, recommendation, and composition. This article presents DisCor-T, a novel graph-based method for discovering underlying connections of things via mining the rich content embodied in human-thing interactions in terms of user, temporal and spatial information. We model these various information using two graphs, namely spatio-temporal graph and social graph. Then, random walk with restart (RWR) is applied to find proximities among things, and a relational graph of things (RGT) indicating implicit correlations of things is learned. The correlation analysis lays a solid foundation contributing to improved effectiveness in things management. To demonstrate the utility, we develop a flexible feature-based classification framework on top of RGT and perform a systematic case study. Our evaluation exhibits the strength and feasibility of the proposed approach.
On some bounds for symmetric tensor rank of multiplication in finite fields
Venue: arXiv cs.IT 2017
Year: 2017

We establish new upper bounds about symmetric bilinear complexity in any extension of finite fields. Note that these bounds are not asymptotical but uniform. Moreover we give examples of Shimura curves that do not descend over their field of moduli, which discusses the validity of certain published bounds.
On node models for high-dimensional road networks
Venue: arXiv cs.SY 2017
Year: 2017

Macroscopic traffic models are necessary for simulation and study of traffic's complex macro-scale dynamics, and are often used by practitioners for road network planning, integrated corridor management, and other applications. These models have two parts: a link model, which describes traffic flow behavior on individual roads, and a node model, which describes behavior at road junctions. As the road networks under study become larger and more complex --- nowadays often including arterial networks --- the node model becomes more important. This paper focuses on the first order node model and has two main contributions. First, we formalize the multi-commodity flow distribution at a junction as an optimization problem with all the necessary constraints. Most interesting here is the formalization of input flow priorities. Then, we discuss a very common "conservation of turning fractions" or "first-in-first-out" (FIFO) constraint, and how it often produces unrealistic spillback. This spillback occurs when, at a diverge, a queue develops for a movement that only a few lanes service, but FIFO requires that all lanes experience spillback from this queue. As we show, avoiding this unrealistic spillback while retaining FIFO in the node model requires complicated network topologies. Our second contribution is a "partial FIFO" mechanism that avoids this unrealistic spillback, and a node model and solution algorithm that incorporates this mechanism. The partial FIFO mechanism is parameterized through intervals that describe how individual movements influence each other, can be intuitively described from physical lane geometry and turning movement rules, and allows tuning to describe a link as having anything between full FIFO and no FIFO. Excepting the FIFO constraint, the present node model also fits within the well-established "general class of first-order node models" for multi-commodity flows.
Joint Backhaul-Access Analysis of Full Duplex Self-Backhauling Heterogeneous Networks
Venue: arXiv cs.NI 2017
Year: 2017

With the successful demonstration of in-band full-duplex (IBFD) transceivers, a new research dimension has been added to wireless networks. This paper proposes an interesting use case of this capability for IBFD self-backhauling heterogeneous networks (HetNet). IBFD self-backhauling in a HetNet refers to IBFD-enabled small cells backhauling themselves with macro cells over the wireless channel. Owing to their IBFD capability, the small cells simultaneously communicate over the access and backhaul links, using the same frequency band. The idea is doubly advantageous, as it obviates the need for fiber backhauling small cells every hundred meters and allows the access spectrum to be reused for backhauling at no extra cost. This work considers the case of a two-tier cellular network with IBFD-enabled small cells, wirelessly backhauling themselves with conventional macro cells. For clear exposition, the case considered is that of FDD network, where within access and backhaul links, the downlink (DL) and uplink (UL) are frequency duplexed ($f1$, $f2$ respectively), while the total frequency spectrum used at access and backhaul ($f1+f2$) is the same. Analytical expressions for coverage and average downlink (DL) rate in such a network are derived using tools from the field of stochastic geometry. It is shown that DL rate in such networks could be close to double that of a conventional TDD/FDD self-backhauling network, at the expense of reduced coverage due to higher interference in IBFD networks. For the proposed IBFD network, the conflicting aspects of increased interference on one side and high spectral efficiency on the other are captured into a mathematical model. The mathematical model introduces an end-to-end joint analysis of backhaul (or fronthaul) and access links, in contrast to the largely available access-centric studies.
Informational Braess' Paradox: The Effect of Information on Traffic Congestion
Venue: arXiv cs.GT 2017
Year: 2017

To systematically study the implications of additional information about routes provided to certain users (e.g., via GPS-based route guidance systems), we introduce a new class of congestion games in which users have differing information sets about the available edges and can only use routes consisting of edges in their information set. After defining the notion of Information Constrained Wardrop Equilibrium (ICWE) for this class of congestion games and studying its basic properties, we turn to our main focus: whether additional information can be harmful (in the sense of generating greater equilibrium costs/delays). We formulate this question in the form of Informational Braes' Paradox (IBP), which extends the classic Braess' Paradox in traffic equilibria, and asks whether users receiving additional information can become worse off. We provide a comprehensive answer to this question showing that in any network in the series of linearly independent (SLI) class, which is a strict subset of series-parallel networks, IBP cannot occur, and in any network that is not in the SLI class, there exists a configuration of edge-specific cost functions for which IBP will occur. In the process, we establish several properties of the SLI class of networks, which include the characterization of the complement of the SLI class in terms of embedding a specific set of networks, and also an algorithm which determines whether a graph is SLI in linear time. We further prove that the worst-case inefficiency performance of ICWE is no worse than the standard Wardrop equilibrium.
Funnel Libraries for Real-Time Robust Feedback Motion Planning
Venue: arXiv cs.RO 2017
Year: 2017

We consider the problem of generating motion plans for a robot that are guaranteed to succeed despite uncertainty in the environment, parametric model uncertainty, and disturbances. Furthermore, we consider scenarios where these plans must be generated in real-time, because constraints such as obstacles in the environment may not be known until they are perceived (with a noisy sensor) at runtime. Our approach is to pre-compute a library of "funnels" along different maneuvers of the system that the state is guaranteed to remain within (despite bounded disturbances) when the feedback controller corresponding to the maneuver is executed. We leverage powerful computational machinery from convex optimization (sums-of-squares programming in particular) to compute these funnels. The resulting funnel library is then used to sequentially compose motion plans at runtime while ensuring the safety of the robot. A major advantage of the work presented here is that by explicitly taking into account the effect of uncertainty, the robot can evaluate motion plans based on how vulnerable they are to disturbances. We demonstrate and validate our method using extensive hardware experiments on a small fixed-wing airplane avoiding obstacles at high speed (~12 mph), along with thorough simulation experiments of ground vehicle and quadrotor models navigating through cluttered environments. To our knowledge, these demonstrations constitute one of the first examples of provably safe and robust control for robotic systems with complex nonlinear dynamics that need to plan in real-time in environments with complex geometric constraints.
On the Control of Asynchronous Automata
Venue: arXiv cs.FL 2017
Year: 2017

The decidability of the distributed version of the Ramadge and Wonham controller synthesis problem,where both the plant and the controllers are modeled as asynchronous automataand the controllers have causal memoryis a challenging open problem.There exist three classes of plants for which the existence of a correct controller with causal memory has been shown decidable: when the dependency graph of actions is series-parallel, when the processes are connectedly communicating and when the dependency graph of processes is a tree. We design a class of plants, called decomposable games, with a decidable controller synthesis problem.This provides a unified proof of the three existing decidability results as well as new examples of decidable plants.
Analysis and Observations from the First Amazon Picking Challenge
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a overview of the inaugural Amazon Picking Challenge along with a summary of a survey conducted among the 26 participating teams. The challenge goal was to design an autonomous robot to pick items from a warehouse shelf. This task is currently performed by human workers, and there is hope that robots can someday help increase efficiency and throughput while lowering cost. We report on a 28-question survey posed to the teams to learn about each team's background, mechanism design, perception apparatus, planning and control approach. We identify trends in this data, correlate it with each team's success in the competition, and discuss observations and lessons learned based on survey results and the authors' personal experiences during the challenge.
Relief R-CNN : Utilizing Convolutional Features for Fast Object Detection
Venue: arXiv cs.CV 2017
Year: 2017

R-CNN style methods are sorts of the state-of-the-art object detection methods, which consist of region proposal generation and deep CNN classification. However, the proposal generation phase in this paradigm is usually time consuming, which would slow down the whole detection time in testing. This paper suggests that the value discrepancies among features in deep convolutional feature maps contain plenty of useful spatial information, and proposes a simple approach to extract the information for fast region proposal generation in testing. The proposed method, namely Relief R-CNN (R2-CNN), adopts a novel region proposal generator in a trained R-CNN style model. The new generator directly generates proposals from convolutional features by some simple rules, thus resulting in a much faster proposal generation speed and a lower demand of computation resources. Empirical studies show that R2-CNN could achieve the fastest detection speed with comparable accuracy among all the compared algorithms in testing.
On Optimal Geographical Caching in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this work we investigate optimal geographical caching in heterogeneous cellular networks where different types of base stations (BSs) have different cache capacities. Users request files from a content library according to a known probability distribution. The performance metric is the total hit probability, which is the probability that a user at an arbitrary location in the plane will find the content that it requires in one of the BSs that it is covered by. We consider the problem of optimally placing content in all BSs jointly. As this problem is not convex, we provide a heuristic scheme by finding the optimal placement policy for one type of base station conditioned on the placement in all other types. We demonstrate that these individual optimization problems are convex and we provide an analytical solution. As an illustration, we find the optimal placement policy of the small base stations (SBSs) depending on the placement policy of the macro base stations (MBSs). We show how the hit probability evolves as the deployment density of the SBSs varies. We show that the heuristic of placing the most popular content in the MBSs is almost optimal after deploying the SBSs with optimal placement policies. Also, for the SBSs no such heuristic can be used; the optimal placement is significantly better than storing the most popular content. Finally, we show that solving the individual problems to find the optimal placement policies for different types of BSs iteratively, namely repeatedly updating the placement policies, does not improve the performance.
Convex Optimization of Real Time SoC
Venue: arXiv cs.DC 2017
Year: 2017

Convex optimization methods are employed to optimize a real-time (RT) system-on-chip (SoC) under a variety of physical resource-driven constraints, demonstrated on an industry MPEG2 encoder SoC. The power optimization is compared to conventional performance-optimization framework, showing a factor of two and a half saving in power. Convex optimization is shown to be very efficient in a high-level early stage design exploration, guiding computer architects as to the choice of area, voltage, and frequency of the individual components of the Chip Multiprocessor (CMP).