OpenRaiser/Intern-Atlas huggingface dataset:
Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
Venue: arXiv cs.CC 2016
Year: 2016

Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant $0 < γ\leq 1/4$, the SOS/Lasserre SDP hierarchy at degree $4\lceil \frac{1}{4γ}\rceil$ certifies the statement "the maximum independent set in the Frankl--Rödl graph $\mathrm{FR}^{n}_γ$ has fractional size~$o(1)$". Here $\mathrm{FR}^{n}_γ = (V,E)$ is the graph with $V = \{0,1\}^n$ and $(x,y) \in E$ whenever $Δ(x,y) = (1-γ)n$ (an even integer). In particular, we show the degree-$4$ SOS algorithm certifies the chromatic number lower bound "$χ(\mathrm{FR}^{n}_{1/4}) = ω(1)$", even though $\mathrm{FR}^{n}_{1/4}$ is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "$χ(\mathrm{FR}^{n}_{1/4}) > 3$". Finally, we also give an SOS proof of (a generalization of) the sharp $(2,q)$-hypercontractive inequality for any even integer $q$.
Binocular disparity as an explanation for the moon illusion
Venue: arXiv cs.CV 2016
Year: 2016

We present another explanation for the moon illusion, the phenomenon in which the moon looks larger near the horizon than near the zenith. In our model of the moon illusion, the sky is considered a spatially-contiguous and geometrically-smooth surface. When an object such as the moon breaks the contiguity of the surface, instead of perceiving the object as appearing through a hole in the surface, humans perceive an occlusion of the surface. Binocular vision dictates that the moon is distant, but this perception model contradicts our binocular vision, dictating that the moon is closer than the sky. To resolve the contradiction, the brain distorts the projections of the moon to increase the binocular disparity, which results in an increase in the perceived size of the moon. The degree of distortion depends upon the apparent distance to the sky, which is influenced by the surrounding objects and the condition of the sky. As the apparent distance to the sky decreases, the illusion becomes stronger. At the horizon, apparent distance to the sky is minimal, whereas at the zenith, few distance cues are present, causing difficulty with distance estimation and weakening the illusion.
Constructing a genome assembly that has the maximum likelihood
Venue: arXiv cs.CE 2016
Year: 2016

We formulate genome assembly problem as an optimization problem in which the objective function is the likelihood of the assembly given the reads.
In Love With a Robot: the Dawn of Machine-To-Machine Marketing
Venue: arXiv cs.AI 2016
Year: 2016

The article looks at mass market artificial intelligence tools in the context of their ever-growing sophistication, availability and market penetration. The subject is especially relevant today for these exact reasons - if a few years ago AI was the subject of high tech research and science fiction novels, today, we increasingly rely on cloud robotics to cater to our daily needs - to trade stock, predict weather, manage diaries, find friends and buy presents online.
Efficient long division via Montgomery multiply
Venue: arXiv cs.DS 2016
Year: 2016

We present a novel right-to-left long division algorithm based on the Montgomery modular multiply, consisting of separate highly efficient loops with simply carry structure for computing first the remainder (x mod q) and then the quotient floor(x/q). These loops are ideally suited for the case where x occupies many more machine words than the divide modulus q, and are strictly linear time in the "bitsize ratio" lg(x)/lg(q). For the paradigmatic performance test of multiword dividend and single 64-bit-word divisor, exploitation of the inherent data-parallelism of the algorithm effectively mitigates the long latency of hardware integer MUL operations, as a result of which we are able to achieve respective costs for remainder-only and full-DIV (remainder and quotient) of 6 and 12.5 cycles per dividend word on the Intel Core 2 implementation of the x86_64 architecture, in single-threaded execution mode. We further describe a simple "bit-doubling modular inversion" scheme, which allows the entire iterative computation of the mod-inverse required by the Montgomery multiply at arbitrarily large precision to be performed with cost less than that of a single Newtonian iteration performed at the full precision of the final result. We also show how the Montgomery-multiply-based powering can be efficiently used in Mersenne and Fermat-number trial factorization via direct computation of a modular inverse power of 2, without any need for explicit radix-mod scalings.
Dimension Independent Matrix Square using MapReduce
Venue: arXiv cs.DS 2016
Year: 2016

We compute the singular values of an $m \times n$ sparse matrix $A$ in a distributed setting, without communication dependence on $m$, which is useful for very large $m$. In particular, we give a simple nonadaptive sampling scheme where the singular values of $A$ are estimated within relative error with constant probability. Our proven bounds focus on the MapReduce framework, which has become the de facto tool for handling such large matrices that cannot be stored or even streamed through a single machine. On the way, we give a general method to compute $A^TA$. We preserve singular values of $A^TA$ with $ε$ relative error with shuffle size $O(n^2/ε^2)$ and reduce-key complexity $O(n/ε^2)$. We further show that if only specific entries of $A^TA$ are required and $A$ has nonnegative entries, then we can reduce the shuffle size to $O(n \log(n) / s)$ and reduce-key complexity to $O(\log(n)/s)$, where $s$ is the minimum cosine similarity for the entries being estimated. All of our bounds are independent of $m$, the larger dimension. We provide open-source implementations in Spark and Scalding, along with experiments in an industrial setting.
Dictionary learning based image enhancement for rarity detection
Venue: arXiv cs.CV 2016
Year: 2016

Image enhancement is an important image processing technique that processes images suitably for a specific application e.g. image editing. The conventional solutions of image enhancement are grouped into two categories which are spatial domain processing method and transform domain processing method such as contrast manipulation, histogram equalization, homomorphic filtering. This paper proposes a new image enhance method based on dictionary learning. Particularly, the proposed method adjusts the image by manipulating the rarity of dictionary atoms. Firstly, learn the dictionary through sparse coding algorithms on divided sub-image blocks. Secondly, compute the rarity of dictionary atoms on statistics of the corresponding sparse coefficients. Thirdly, adjust the rarity according to specific application and form a new dictionary. Finally, reconstruct the image using the updated dictionary and sparse coefficients. Compared with the traditional techniques, the proposed method enhances image based on the image content not on distribution of pixel grey value or frequency. The advantages of the proposed method lie in that it is in better correspondence with the response of the human visual system and more suitable for salient objects extraction. The experimental results demonstrate the effectiveness of the proposed image enhance method.
Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Full Version
Venue: arXiv cs.DS 2016
Year: 2016

We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for a more general model which includes Markov decision processes and non-unit transition times. When preemption is allowed, we provide a (1/2-eps)-approximation, along with an example showing this is tight. When preemption isn't allowed, we provide a 1/12-approximation, which improves to a 4/27-approximation when transition times are unity. Our model encompasses the Markovian Bandits model of Gupta et al, the Stochastic Knapsack model of Dean, Goemans, and Vondrak, and the Budgeted Learning model of Guha and Munagala, and our algorithms improve existing results in all three areas. In our analysis, we encounter and overcome to our knowledge a novel obstacle - an algorithm that provably exists via polyhedral arguments, but cannot be found in polynomial time.
Opinion dynamics and wisdom under out-group discrimination
Venue: arXiv cs.MA 2016
Year: 2016

We study a DeGroot-like opinion dynamics model in which agents may oppose other agents. As an underlying motivation, in our setup, agents want to adjust their opinions to match those of the agents of their 'in-group' and, in addition, they want to adjust their opinions to match the 'inverse' of those of the agents of their 'out-group'. Our paradigm can account for persistent disagreement in connected societies as well as bi- and multi-polarization. Outcomes depend upon network structure and the choice of deviation function modeling the mode of opposition between agents. For a particular choice of deviation function, which we call soft opposition, we derive necessary and sufficient conditions for long-run polarization. We also consider social influence (who are the opinion leaders in the network?) as well as the question of wisdom in our naive learning paradigm, finding that wisdom is difficult to attain when there exist sufficiently strong negative relations between agents.
Bank Conflict Free Comparison-based Sorting On GPUs
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we present a framework for designing algorithms in shared memory of GPUs without incurring memory bank conflicts. Using our framework we develop the first comparison-based shared memory sorting algorithm that incurs no bank conflicts. It can be used as a subroutine for GPU sorting algorithms to replace current use of sorting networks in shared memory. Using our bank conflict free shared memory sorting subroutine as a black box, we design BCFMergesort, an algorithm for merging sorted streams of data that are larger than shared memory. Our algorithm performs all accesses to global memory in coalesced manner and incurs no bank conflicts during the merge.
Cryptanalyzing a class of image encryption schemes based on Chinese Remainder Theorem
Venue: arXiv cs.CR 2016
Year: 2016

As a fundamental theorem in number theory, the Chinese Reminder Theorem (CRT) is widely used to construct cryptographic primitives. This paper investigates the security of a class of image encryption schemes based on CRT, referred to as CECRT. Making use of some properties of CRT, the equivalent secret key of CECRT can be recovered efficiently. The required number of pairs of chosen plaintext and the corresponding ciphertext is only $(1+\lceil (\log_2L)/l \rceil)$. The attack complexity is only $O(L)$, where $L$ is the plaintext length and $l$ is the number of bits representing a plaintext symbol. In addition, other defects of CECRT such as invalid compression function and low sensitivity to plaintext, are reported. The work in this paper will help clarify positive role of CRT in cryptology.
Fast Multipole Preconditioners for Sparse Matrices Arising from Elliptic Equations
Venue: arXiv cs.NA 2016
Year: 2016

Among optimal hierarchical algorithms for the computational solution of elliptic problems, the Fast Multipole Method (FMM) stands out for its adaptability to emerging architectures, having high arithmetic intensity, tunable accuracy, and relaxable global synchronization requirements. We demonstrate that, beyond its traditional use as a solver in problems for which explicit free-space kernel representations are available, the FMM has applicability as a preconditioner in finite domain elliptic boundary value problems, by equipping it with boundary integral capability for satisfying conditions at finite boundaries and by wrapping it in a Krylov method for extensibility to more general operators. Here, we do not discuss the well developed applications of FMM to implement matrix-vector multiplications within Krylov solvers of boundary element methods. Instead, we propose using FMM for the volume-to-volume contribution of inhomogeneous Poisson-like problems, where the boundary integral is a small part of the overall computation. Our method may be used to precondition sparse matrices arising from finite difference/element discretizations, and can handle a broader range of scientific applications. Compared with multigrid methods, it is capable of comparable algebraic convergence rates down to the truncation error of the discretized PDE, and it offers potentially superior multicore and distributed memory scalability properties on commodity architecture supercomputers. Compared with other methods exploiting the low rank character of off-diagonal blocks of the dense resolvent operator, FMM-preconditioned Krylov iteration may reduce the amount of communication because it is matrix-free and exploits the tree structure of FMM. We describe our tests in reproducible detail with freely available codes and outline directions for further extensibility.
System Power Minimization to Access Non-Contiguous Spectrum in Cognitive Radio Networks
Venue: arXiv cs.NI 2016
Year: 2016

Wireless transmission using non-contiguous chunks of spectrum is becoming increasingly important due to a variety of scenarios such as: secondary users avoiding incumbent users in TV white space; anticipated spectrum sharing between commercial and military systems; and spectrum sharing among uncoordinated interferers in unlicensed bands. Multi-Channel Multi-Radio (MCMR) platforms and Non-Contiguous Orthogonal Frequency Division Multiple Access (NC-OFDMA) technology are the two commercially viable transmission choices to access these non-contiguous spectrum chunks. Fixed MC-MRs do not scale with increasing number of non-contiguous spectrum chunks due to their fixed set of supporting radio front ends. NC-OFDMA allows nodes to access these non-contiguous spectrum chunks and put null sub-carriers in the remaining chunks. However, nulling sub-carriers increases the sampling rate (spectrum span) which, in turn, increases the power consumption of radio front ends. Our work characterizes this trade-off from a cross-layer perspective, specifically by showing how the slope of ADC/DAC power consumption versus sampling rate curve influences scheduling decisions in a multi-hop network. Specifically, we provide a branch and bound algorithm based mixed integer linear programming solution that performs joint power control, spectrum span selection, scheduling and routing in order to minimize the system power of multi-hop NC-OFDMA networks. We also provide a low complexity (O(E^2 M^2)) greedy algorithm where M and E denote the number of channels and links respectively. Numerical simulations suggest that our approach reduces system power by 30% over classical transmit power minimization based cross-layer algorithms.
Data-Driven Grasp Synthesis - A Survey
Venue: arXiv cs.RO 2016
Year: 2016

We review the work on data-driven grasp synthesis and the methodologies for sampling and ranking candidate grasps. We divide the approaches into three groups based on whether they synthesize grasps for known, familiar or unknown objects. This structure allows us to identify common object representations and perceptual processes that facilitate the employed data-driven grasp synthesis technique. In the case of known objects, we concentrate on the approaches that are based on object recognition and pose estimation. In the case of familiar objects, the techniques use some form of a similarity matching to a set of previously encountered objects. Finally for the approaches dealing with unknown objects, the core part is the extraction of specific features that are indicative of good grasps. Our survey provides an overview of the different methodologies and discusses open problems in the area of robot grasping. We also draw a parallel to the classical approaches that rely on analytic formulations.
Genie Tree and Degrees of Freedom of the Symmetric MIMO Interfering Broadcast Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the information theoretic maximal degrees of freedom (DoF) for the symmetric multi-input-multi-output (MIMO) interfering broadcast channel (IBC) with arbitrary antenna configurations. For the G-cell K-user MXN MIMO-IBC network, we find that the information theoretic maximal DoF per user are related to three DoF bounds: 1) the decomposition DoF bound d^{Decom}=MN/(M+KN), a lower-bound of linear interference alignment (IA) with infinite time/frequency extensions (called asymptotic IA); 2) the proper DoF bound d^{Proper}=(M+N)/(GK+1), an upper-bound of linear IA without time/frequency extensions (called linear IA); and 3) the quantity DoF bound d^{Quan}, a zigzag piecewise linear function of M and N. The whole region of M/N can be divided into two regions, Region I and Region II. Specifically, for most configurations in Region I, the information theoretic maximal DoF are the decomposition DoF bound and can be achieved by the asymptotic IA. For all configurations in Region II, the information theoretic maximal DoF are the quantity DoF bound and can be achieved by the linear IA. To obtain the tight upper-bound, we propose a unified way to construct genies, where the genies help each base station or user resolve the maximal number of interference. According to the feature that the designed genies with the same dimension can derive identical DoF upper-bound, we convert the information theoretic DoF upper-bound problem into a linear algebra problem and obtain the closed-form DoF upper-bound expression. Moreover, we develop a non-iterative linear IA transceiver to achieve the DoF upper-bound for the networks with antenna configurations in Region II, which means that the derived DoF upper-bound is tightest. The basic principles to derive the DoF upper-bound and design the linear IA transceiver to achieve the DoF upper-bound can be extended into general asymmetric networks.
Flipping Edge-Labelled Triangulations
Venue: arXiv cs.CG 2016
Year: 2016

Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We introduce the concept of the orbit of an edge $e$, which is the set of all edges reachable from $e$ via flips. We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight $Θ(n \log n)$ bounds for edge-labelled triangulations of $n$-vertex convex polygons and combinatorial triangulations, contrasting with the $Θ(n)$ bounds in their respective unlabelled settings. The $Ω(n \log n)$ lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to $O(\log^2 n)$, although we no longer have a matching lower bound. Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of $O(n^2)$ on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter $Ω(n^3)$.
Cornell SPF: Cornell Semantic Parsing Framework
Venue: arXiv cs.CL 2016
Year: 2016

The Cornell Semantic Parsing Framework (SPF) is a learning and inference framework for mapping natural language to formal representation of its meaning.
On the Expansion of Group-Based Lifts
Venue: arXiv cs.DM 2016
Year: 2016

A $k$-lift of an $n$-vertex base graph $G$ is a graph $H$ on $n\times k$ vertices, where each vertex $v$ of $G$ is replaced by $k$ vertices $v_1,\cdots{},v_k$ and each edge $(u,v)$ in $G$ is replaced by a matching representing a bijection $π_{uv}$ so that the edges of $H$ are of the form $(u_i,v_{π_{uv}(i)})$. Lifts have been studied as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are: (1) There is a constant $c_1$ such that for every $k\geq 2^{c_1nd}$, there does not exist an abelian $k$-lift $H$ of any $n$-vertex $d$-regular base graph with $H$ being almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most $O(\sqrt{d})$ in magnitude). This can be viewed as an analogue of the well-known no-expansion result for abelian Cayley graphs. (2) A uniform random lift in a cyclic group of order $k$ of any $n$-vertex $d$-regular base graph $G$, with the nontrivial eigenvalues of the adjacency matrix of $G$ bounded by $λ$ in magnitude, has the new nontrivial eigenvalues also bounded by $λ+O(\sqrt{d})$ in magnitude with probability $1-ke^{-Ω(n/d^2)}$. In particular, there is a constant $c_2$ such that for every $k\leq 2^{c_2n/d^2}$, there exists a lift $H$ of every Ramanujan graph in a cyclic group of order $k$ with $H$ being almost Ramanujan. We use this to design a quasi-polynomial time algorithm to construct almost Ramanujan expanders deterministically. The existence of expanding lifts in cyclic groups of order $k=2^{O(n/d^2)}$ can be viewed as a lower bound on the order $k_0$ of the largest abelian group that produces expanding lifts. Our results show that the lower bound matches the upper bound for $k_0$ (upto $d^3$ in the exponent).
Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players
Venue: arXiv cs.GT 2016
Year: 2016

We consider the problem of designing incentive-compatible, ex-post individually rational (IR) mechanisms for covering problems in the Bayesian setting, where players' types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We formulate a notion of incentive compatibility (IC) that we call {\em support-based IC} that is substantially more robust than Bayesian IC, and develop black-box reductions from support-based-IC mechanism design to algorithm design. For single-dimensional settings, this black-box reduction applies even when we only have an LP-relative {\em approximation algorithm} for the algorithmic problem. Thus, we obtain near-optimal mechanisms for various covering settings including single-dimensional covering problems, multi-item procurement auctions, and multidimensional facility location.
The Morse theory of Čech and Delaunay complexes
Venue: arXiv cs.CG 2016
Year: 2016

Given a finite set of points in $\mathbb R^n$ and a radius parameter, we study the Čech, Delaunay-Čech, Delaunay (or Alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.