OpenRaiser/Intern-Atlas huggingface dataset:
Random Ensembles of Lattices from Generalized Reductions
Venue: arXiv cs.IT 2018
Year: 2018

We propose a general framework to study constructions of Euclidean lattices from linear codes over finite fields. In particular, we prove general conditions for an ensemble constructed using linear codes to contain dense lattices (i.e., with packing density comparable to the Minkowski-Hlawka lower bound). Specializing to number field lattices, we obtain a number of interesting corollaries - for instance, the best known packing density of ideal lattices, and an elementary coding-theoretic construction of asymptotically dense Hurwitz lattices. All results are algorithmically effective, in the sense that, for any dimension, a finite family containing dense lattices is exhibited. For suitable constructions based on Craig's lattices, this family is significantly smaller, in terms of alphabet-size, than previous ones in the literature.
Automatic Prediction of Discourse Connectives
Venue: arXiv cs.CL 2018
Year: 2018

Accurate prediction of suitable discourse connectives (however, furthermore, etc.) is a key component of any system aimed at building coherent and fluent discourses from shorter sentences and passages. As an example, a dialog system might assemble a long and informative answer by sampling passages extracted from different documents retrieved from the Web. We formulate the task of discourse connective prediction and release a dataset of 2.9M sentence pairs separated by discourse connectives for this task. Then, we evaluate the hardness of the task for human raters, apply a recently proposed decomposable attention (DA) model to this task and observe that the automatic predictor has a higher F1 than human raters (32 vs. 30). Nevertheless, under specific conditions the raters still outperform the DA model, suggesting that there is headroom for future improvements.
Combining and Steganography of 3D Face Textures
Venue: arXiv cs.MM 2018
Year: 2018

One of the serious issues in communication between people is hiding information from others, and the best way for this, is deceiving them. Since nowadays face images are mostly used in three dimensional format, in this paper we are going to steganography 3D face images, detecting which by curious people will be impossible. As in detecting face only its texture is important, we separate texture from shape matrices, for eliminating half of the extra information, steganography is done only for face texture, and for reconstructing 3D face, we can use any other shape. Moreover, we will indicate that, by using two textures, how two 3D faces can be combined. For a complete description of the process, first, 2D faces are used as an input for building 3D faces, and then 3D textures are hidden within other images.
Contextually Customized Video Summaries via Natural Language
Venue: arXiv cs.CV 2018
Year: 2018

The best summary of a long video differs among different people due to its highly subjective nature. Even for the same person, the best summary may change with time or mood. In this paper, we introduce the task of generating customized video summaries through simple text. First, we train a deep architecture to effectively learn semantic embeddings of video frames by leveraging the abundance of image-caption data via a progressive and residual manner. Given a user-specific text description, our algorithm is able to select semantically relevant video segments and produce a temporally aligned video summary. In order to evaluate our textually customized video summaries, we conduct experimental comparison with baseline methods that utilize ground-truth information. Despite the challenging baselines, our method still manages to show comparable or even exceeding performance. We also show that our method is able to generate semantically diverse video summaries by only utilizing the learned visual embeddings.
How well can machine learning predict demographics of social media users?
Venue: arXiv cs.SI 2018
Year: 2018

The wide use of social media sites and other digital technologies have resulted in an unprecedented availability of digital data that are being used to study human behavior across research domains. Although unsolicited opinions and sentiments are available on these platforms, demographic details are usually missing. Demographic information is pertinent in fields such as demography and public health, where significant differences can exist across sex, racial and socioeconomic groups. In an attempt to address this shortcoming, a number of academic studies have proposed methods for inferring the demographics of social media users using details such as names, usernames, and network characteristics. Gender is the easiest trait to accurately infer, with measures of accuracy higher than 90 percent in some studies. Race, ethnicity and age tend to be more challenging to predict for a variety of reasons including the novelty of social media to certain age groups and a lack of significant deviations in user details across racial and ethnic groups. Although the endeavor to predict user demographics is plagued with ethical questions regarding privacy and data ownership, knowing the demographics in a data sample can aid in addressing issues of bias and population representation, so that existing societal inequalities are not exacerbated.
Distributed Domination on Graph Classes of Bounded Expansion
Venue: arXiv cs.DC 2018
Year: 2018

We provide a new constant factor approximation algorithm for the (connected) distance-$r$ dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance-$r$ dominating set problem is currently known. Our algorithm can be implemented in the \congestbc model of distributed computing and uses $\mathcal{O}(r^2 \log n)$ communication rounds. Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an $r$-neighborhood cover of radius~$2r$ and overlap $f(r)$ on every class of bounded expansion in $\mathcal{O}(r^2 \log n)$ communication rounds for some function~$f$.% in the $\mathcal{CONGEST}_{\mathrm{BC}}$ model. Finally, we show how to use the greater power of the $\mathcal{LOCAL}$ model to turn any distance-$r$ dominating set into a constantly larger connected distance-$r$ dominating set in $3r+1$ rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al.\ gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the $\mathcal{LOCAL}$ model, where the approximation ratio is only $6$ times larger than that of Lenzen et al.'s algorithm.
Feedback Capacity of Stationary Gaussian Channels Further Examined
Venue: arXiv cs.IT 2018
Year: 2018

It is well known that the problem of computing the feedback capacity of a stationary Gaussian channel can be recast as an infinite-dimensional optimization problem; moreover, necessary and sufficient conditions for the optimality of a solution to this optimization problem have been characterized, and based on this characterization, an explicit formula for the feedback capacity has been given for the case that the noise is a first-order autoregressive moving-average Gaussian process. In this paper, we further examine the above-mentioned infinite-dimensional optimization problem. We prove that unless the Gaussian noise is white, its optimal solution is unique, and we propose an algorithm to recursively compute the unique optimal solution, which is guaranteed to converge in theory and features an efficient implementation for a suboptimal solution in practice. Furthermore, for the case that the noise is a k-th order autoregressive moving-average Gaussian process, we give a relatively more explicit formula for the feedback capacity; more specifically, the feedback capacity is expressed as a simple function evaluated at a solution to a system of polynomial equations, which is amenable to numerical computation for the cases k=1, 2 and possibly beyond.
Sparsity/Undersampling Tradeoffs in Anisotropic Undersampling, with Applications in MR Imaging/Spectroscopy
Venue: arXiv cs.IT 2018
Year: 2018

We study anisotropic undersampling schemes like those used in multi-dimensional NMR spectroscopy and MR imaging, which sample exhaustively in certain time dimensions and randomly in others. Our analysis shows that anisotropic undersampling schemes are equivalent to certain block-diagonal measurement systems. We develop novel exact formulas for the sparsity/undersampling tradeoffs in such measurement systems. Our formulas predict finite-N phase transition behavior differing substantially from the well known asymptotic phase transitions for classical Gaussian undersampling. Extensive empirical work shows that our formulas accurately describe observed finite-N behavior, while the usual formulas based on universality are substantially inaccurate. We also vary the anisotropy, keeping the total number of samples fixed, and for each variation we determine the precise sparsity/undersampling tradeoff (phase transition). We show that, other things being equal, the ability to recover a sparse object decreases with an increasing number of exhaustively-sampled dimensions.
The Connectivity of Millimeter-Wave Networks in Urban Environments Modeled Using Random Lattices
Venue: arXiv cs.IT 2018
Year: 2018

Millimeter-wave (mmWave) communication opens up tens of giga-hertz (GHz) spectrum in the mmWave band for use by next-generation wireless systems, thereby solving the problem of spectrum scarcity. Maintaining connectivity stands out to be a key design challenge for mmWave networks deployed in urban regions due to the blockage effect characterizing mmWave propagation. Specifically, mmWave signals can be blocked by buildings and other large urban objects. In this paper, we set out to investigate the blockage effect on the connectivity of mmWave networks in a Manhattan-type urban region modeled using a random regular lattice while base stations (BSs) are Poisson distributed in the plane. In particular, we analyze the connectivity probability that a typical user is within the transmission range of a BS and connected by a line-of-sight. Using random lattice and stochastic geometry theories, different lower bounds on the connectivity probability are derived as functions of the buildings' size and probability of a lattice cell being occupied by a building as well as BS density and transmission range. The asymptotic connectivity probability is also derived for cases of dense buildings. Last, the results are extended to heterogeneous networks. Our study yields closed-form relations between the parameters of the building process and the BS process, providing useful guidelines for practical mmWave network deployment.
Derandomized Balanced Allocation
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we study the maximum loads of explicit hash families in the $d$-choice schemes when allocating sequentially $n$ balls into $n$ bins. We consider the \emph{Uniform-Greedy} scheme, which provides $d$ independent bins for each ball and places the ball into the bin with the least load, and its non-uniform variant --- the \emph{Always-Go-Left} scheme introduced by Vöcking. We construct a hash family with $O(\log n \log \log n)$ random bits based on the previous work of Celis et al. and show the following results. 1. With high probability, this hash family has a maximum load of $\frac{\log \log n}{\log d} + O(1)$ in the \emph{Uniform-Greedy} scheme. 2. With high probability, it has a maximum load of $\frac{\log \log n}{d \log ϕ_d} + O(1)$ in the \emph{Always-Go-Left} scheme for a constant $ϕ_d>1.61$. The maximum loads of our hash family match the maximum loads of a perfectly random hash function in the \emph{Uniform-Greedy} and \emph{Always-Go-Left} scheme separately, up to the low order term of constants. Previously, the best known hash families matching the same maximum loads of a perfectly random hash function in $d$-choice schemes were $O(\log n)$-wise independent functions, which needs $Θ(\log^2 n)$ random bits.
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
Venue: arXiv cs.CC 2018
Year: 2018

A graph $G$ is a $(Π_A,Π_B)$-graph if $V(G)$ can be bipartitioned into $A$ and $B$ such that $G[A]$ satisfies property $Π_A$ and $G[B]$ satisfies property $Π_B$. The $(Π_{A},Π_{B})$-Recognition problem is to recognize whether a given graph is a $(Π_A,Π_B)$-graph. There are many $(Π_{A},Π_{B})$-Recognition problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of $(Π_A,Π_B)$-Recognition based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard $(Π_{A},Π_{B})$-Recognition problems, Monopolar Recognition and 2-Subcoloring. We complement our algorithmic results with several hardness results for $(Π_{A},Π_{B})$-Recognition.
Regular Separability of Well Structured Transition Systems
Venue: arXiv cs.FL 2018
Year: 2018

We investigate the languages recognized by well-structured transition systems (WSTS) with upward and downward compatibility. Our first result shows that, under very mild assumptions, every two disjoint WSTS languages are regular separable: There is a regular language containing one of them and being disjoint from the other. As a consequence, if a language as well as its complement are both recognized by WSTS, then they are necessarily regular. In particular, no subclass of WSTS languages beyond the regular languages is closed under complement. Our second result shows that for Petri nets, the complexity of the backwards coverability algorithm yields a bound on the size of the regular separator. We complement it by a lower bound construction.
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
Venue: arXiv cs.LG 2018
Year: 2018

We study the Stochastic Gradient Langevin Dynamics (SGLD) algorithm for non-convex optimization. The algorithm performs stochastic gradient descent, where in each step it injects appropriately scaled Gaussian noise to the update. We analyze the algorithm's hitting time to an arbitrary subset of the parameter space. Two results follow from our general theory: First, we prove that for empirical risk minimization, if the empirical risk is point-wise close to the (smooth) population risk, then the algorithm achieves an approximate local minimum of the population risk in polynomial time, escaping suboptimal local minima that only exist in the empirical risk. Second, we show that SGLD improves on one of the best known learnability results for learning linear classifiers under the zero-one loss.
Intuitionistic Layered Graph Logic: Semantics and Proof Theory
Venue: arXiv cs.LO 2018
Year: 2018

Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic called ILGL that gives an account of layering. The logic is a bunched system, combining the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction (used to capture layering) and its associated implications. We give soundness and completeness theorems for a labelled tableaux system with respect to a Kripke semantics on graphs. We then give an equivalent relational semantics, itself proven equivalent to an algebraic semantics via a representation theorem. We utilise this result in two ways. First, we prove decidability of the logic by showing the finite embeddability property holds for the algebraic semantics. Second, we prove a Stone-type duality theorem for the logic. By introducing the notions of ILGL hyperdoctrine and indexed layered frame we are able to extend this result to a predicate version of the logic and prove soundness and completeness theorems for an extension of the layered graph semantics . We indicate the utility of predicate ILGL with a resource-labelled bigraph model.
On the Comparison of Context-Free Grammars
Venue: arXiv cs.FL 2018
Year: 2018

In this paper we consider the problem of context-free grammars comparison from the analysis point of view. We show that the problem can be reduced to numerical solution of systems of nonlinear matrix equations. The approach presented here forms a basis for probabilistic comparison algorithms oriented to automatic assessment of of student's answers in computer science.
How Much Urban Traffic is Searching for Parking? Simulating Curbside Parking as a Network of Finite Capacity Queues
Venue: arXiv cs.CY 2018
Year: 2018

With the increasing availability of transaction data collected by digital parking meters, paid curbside parking can be advantageously modeled as a network of interdependent queues. In this article we introduce methods for analyzing a special class of networks of finite capacity queues, where tasks arrive from an exogenous source, join the queue if there is an available server or are rejected and move to another queue in search of service according to the network topology. Such networks can be useful for modeling curbside parking since queues in the network perform the same function and drivers searching for an available server are under combinatorial constraints and jockeying is not instantaneous. Further, we provide a motivating example for such networks of finite capacity queues in the context of drivers searching for parking in the neighborhood of Belltown in Seattle, Washington, USA. Lastly, since the stationary distribution of such networks used to model parking are difficult to satisfactorily characterize, we also introduce a simulation tool for the purpose of testing the assumptions made to estimate interesting performance metrics. Our results suggest that a Markovian relaxation of the problem when solving for the mean rate metrics is comparable to deterministic service times reflective of a driver's tendency to park for the maximum allowable time.
Survey of Automated Vulnerability Detection and Exploit Generation Techniques in Cyber Reasoning Systems
Venue: arXiv cs.CR 2018
Year: 2018

Software is everywhere, from mission critical systems such as industrial power stations, pacemakers and even household appliances. This growing dependence on technology and the increasing complexity software has serious security implications as it means we are potentially surrounded by software that contain exploitable vulnerabilities. These challenges have made binary analysis an important area of research in computer science and has emphasized the need for building automated analysis systems that can operate at scale, speed and efficacy; all while performing with the skill of a human expert. Though great progress has been made in this area of research, there remains limitations and open challenges to be addressed. Recognizing this need, DARPA sponsored the Cyber Grand Challenge (CGC), a competition to showcase the current state of the art in systems that perform; automated vulnerability detection, exploit generation and software patching. This paper is a survey of the vulnerability detection and exploit generation techniques, underlying technologies and related works of two of the winning systems Mayhem and Mechanical Phish.
Comprehensive Data Set for Automatic Single Camera Visual Speed Measurement
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we focus on traffic camera calibration and a visual speed measurement from a single monocular camera, which is an important task of visual traffic surveillance. Existing methods addressing this problem are difficult to compare due to a lack of a common data set with reliable ground truth. Therefore, it is not clear how the methods compare in various aspects and what factors are affecting their performance. We captured a new data set of 18 full-HD videos, each around 1 hr long, captured at six different locations. Vehicles in the videos (20865 instances in total) are annotated with the precise speed measurements from optical gates using LiDAR and verified with several reference GPS tracks. We made the data set available for download and it contains the videos and metadata (calibration, lengths of features in image, annotations, and so on) for future comparison and evaluation. Camera calibration is the most crucial part of the speed measurement; therefore, we provide a brief overview of the methods and analyze a recently published method for fully automatic camera calibration and vehicle speed measurement and report the results on this data set in detail.
Simulation of Patient Flow in Multiple Healthcare Units using Process and Data Mining Techniques for Model Identification
Venue: arXiv cs.CY 2018
Year: 2018

Introduction: An approach to building a hybrid simulation of patient flow is introduced with a combination of data-driven methods for automation of model identification. The approach is described with a conceptual framework and basic methods for combination of different techniques. The implementation of the proposed approach for simulation of acute coronary syndrome (ACS) was developed and used within an experimental study. Methods: Combination of data, text, and process mining techniques and machine learning approaches for analysis of electronic health records (EHRs) with discrete-event simulation (DES) and queueing theory for simulation of patient flow was proposed. The performed analysis of EHRs for ACS patients enable identification of several classes of clinical pathways (CPs) which were used to implement a more realistic simulation of the patient flow. The developed solution was implemented using Python libraries (SimPy, SciPy, and others). Results: The proposed approach enables more realistic and detailed simulation of the patient flow within a group of related departments. Experimental study shows that the improved simulation of patient length of stay for ACS patient flow obtained from EHRs in Federal Almazov North-west Medical Research Centre in Saint Petersburg, Russia. Conclusion: The proposed approach, methods, and solutions provide a conceptual, methodological, and programming framework for implementation of simulation of complex and diverse scenarios within a flow of patients for different purposes: decision making, training, management optimization, and others.
Understanding Convolution for Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Recent advances in deep learning, especially deep convolutional neural networks (CNNs), have led to significant improvement over previous semantic segmentation systems. Here we show how to improve pixel-wise semantic segmentation by manipulating convolution-related operations that are of both theoretical and practical value. First, we design dense upsampling convolution (DUC) to generate pixel-level prediction, which is able to capture and decode more detailed information that is generally missing in bilinear upsampling. Second, we propose a hybrid dilated convolution (HDC) framework in the encoding phase. This framework 1) effectively enlarges the receptive fields (RF) of the network to aggregate global information; 2) alleviates what we call the "gridding issue" caused by the standard dilated convolution operation. We evaluate our approaches thoroughly on the Cityscapes dataset, and achieve a state-of-art result of 80.1% mIOU in the test set at the time of submission. We also have achieved state-of-the-art overall on the KITTI road estimation benchmark and the PASCAL VOC2012 segmentation task. Our source code can be found at https://github.com/TuSimple/TuSimple-DUC .