OpenRaiser/Intern-Atlas huggingface dataset:
Directed multicut is W[1]-hard, even for four terminal pairs
Venue: arXiv cs.DS 2018
Year: 2018

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. This negative result almost completely resolves one of the central open problems in the area of parameterized complexity of graph separation problems, posted originally by Marx and Razgon [SIAM J. Comput. 43(2):355-388 (2014)], leaving only the case of three terminal pairs open. Our gadget methodology allows us also to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503-1513 (2013)].
Privacy-Preserving Nonlinear Observer Design Using Contraction Analysis
Venue: arXiv cs.SY 2018
Year: 2018

Real-time information processing applications such as those enabling a more intelligent infrastructure are increasingly focused on analyzing privacy-sensitive data obtained from individuals. To produce accurate statistics about the habits of a population of users of a system, this data might need to be processed through model-based estimators. Moreover, models of population dynamics, originating for example from epidemiology or the social sciences, are often necessarily nonlinear. Motivated by these trends, this paper presents an approach to design nonlinear privacy-preserving model-based observers, relying on additive input or output noise to give differential privacy guarantees to the individuals providing the input data. For the case of output perturbation, contraction analysis allows us to design convergent observers as well as set the level of privacy-preserving noise appropriately. Two examples illustrate the approach: estimating the edge formation probabilities in a dynamic social network, and syndromic surveillance relying on an epidemiological model.
Computability and Complexity of Categorical Structures
Venue: arXiv cs.CC 2018
Year: 2018

We examine various categorical structures that can and cannot be constructed. We show that total computable functions can be mimicked by constructible functors. More generally, whatever can be done by a Turing machine can be constructed by categories. Since there are infinitary constructions in category theory, it is shown that category theory is strictly more powerful than Turing machines. In particular, categories can solve the Halting Problem for Turing machines. We also show that categories can solve any problem in the arithmetic hierarchy.
Indexing of CNN Features for Large Scale Image Search
Venue: arXiv cs.CV 2018
Year: 2018

The convolutional neural network (CNN) features can give a good description of image content, which usually represent images with unique global vectors. Although they are compact compared to local descriptors, they still cannot efficiently deal with large-scale image retrieval due to the cost of the linear incremental computation and storage. To address this issue, we build a simple but effective indexing framework based on inverted table, which significantly decreases both the search time and memory usage. In addition, several strategies are fully investigated under an indexing framework to adapt it to CNN features and compensate for quantization errors. First, we use multiple assignment for the query and database images to increase the probability of relevant images' co-existing in the same Voronoi cells obtained via the clustering algorithm. Then, we introduce embedding codes to further improve precision by removing false matches during a search. We demonstrate that by using hashing schemes to calculate the embedding codes and by changing the ranking rule, indexing framework speeds can be greatly improved. Extensive experiments conducted on several unsupervised and supervised benchmarks support these results and the superiority of the proposed indexing framework. We also provide a fair comparison between the popular CNN features.
Hypergraph coloring up to condensation
Venue: arXiv cs.DM 2018
Year: 2018

Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the $q$-colorability threshold in random $k$-uniform hypergraphs up to an additive error of $\ln 2+\varepsilon_q$, where $\lim_{q\to\infty}\varepsilon_q=0$. The new lower bound on the threshold matches the "condensation phase transition" predicted by statistical physics considerations [Krzakala et al., PNAS 2007].
A New Approach to an Old Problem: The Reconstruction of a Go Game through a Series of Photographs
Venue: arXiv cs.CV 2018
Year: 2018

Given a series of photographs taken during a Go game, we describe the techniques we successfully employ for pinpointing the grid lines of the Go board and for tracking their small movements between consecutive photographs; then we discuss how to approximate the location and orientation of the observer's point of view, in order to compensate for projection effects. Finally we describe the different criteria that jointly form the algorithm for stones' detection, thus enabling us to automatically reconstruct the whole move sequence.
No acute tetrahedron is an 8-reptile
Venue: arXiv cs.CG 2018
Year: 2018

An $r$-gentiling is a dissection of a shape into $r \geq 2$ parts which are all similar to the original shape. An $r$-reptiling is an $r$-gentiling of which all parts are mutually congruent. This article shows that no acute tetrahedron is an $r$-gentile or $r$-reptile for any $r < 9$, by showing that no acute spherical diangle can be dissected into less than nine acute spherical triangles.
A Pessimistic Approximation for the Fisher Information Measure
Venue: arXiv cs.IT 2018
Year: 2018

The problem of determining the intrinsic quality of a signal processing system with respect to the inference of an unknown deterministic parameter $θ$ is considered. While the Fisher information measure $F(θ)$ forms a classical tool for such a problem, direct computation of the information measure can become difficult in various situations. For the estimation theoretic performance analysis of nonlinear measurement systems, the form of the likelihood function can make the calculation of the information measure $F(θ)$ challenging. In situations where no closed-form expression of the statistical system model is available, the analytical derivation of $F(θ)$ is not possible at all. Based on the Cauchy-Schwarz inequality, we derive an alternative information measure $S(θ)$. It provides a lower bound on the Fisher information $F(θ)$ and has the property of being evaluated with the mean, the variance, the skewness and the kurtosis of the system model at hand. These entities usually exhibit good mathematical tractability or can be determined at low-complexity by real-world measurements in a calibrated setup. With various examples, we show that $S(θ)$ provides a good conservative approximation for $F(θ)$ and outline different estimation theoretic problems where the presented information bound turns out to be useful.
Inference From Visible Information And Background Knowledge
Venue: arXiv cs.LO 2018
Year: 2018

We provide a wide-ranging study of the scenario where a subset of the relations in a relational vocabulary are visible to a user --- that is, their complete contents are known --- while the remaining relations are invisible. We also have a background theory --- invariants given by logical sentences --- which may relate the visible relations to invisible ones, and also may constrain both the visible and invisible relations in isolation. We want to determine whether some other information, given as a positive existential formula, can be inferred using only the visible information and the background theory. This formula whose inference we are concered with is denoted as the \emph{query}. We consider whether positive information about the query can be inferred, and also whether negative information -- the sentence does not hold -- can be inferred. We further consider both the instance-level version of the problem, where both the query and the visible instance are given, and the schema-level version, where we want to know whether truth or falsity of the query can be inferred in some instance of the schema.
Pricing Policies for Selling Indivisible Storable Goods to Strategic Consumers
Venue: arXiv cs.GT 2018
Year: 2018

We study the dynamic pricing problem faced by a monopolistic retailer who sells a storable product to forward-looking consumers. In this framework, the two major pricing policies (or mechanisms) studied in the literature are the preannounced (commitment) pricing policy and the contingent (threat or history dependent) pricing policy. We analyse and compare these pricing policies in the setting where the good can be purchased along a finite time horizon in indivisible atomic quantities. First, we show that, given linear storage costs, the retailer can compute an optimal preannounced pricing policy in polynomial time by solving a dynamic program. Moreover, under such a policy, we show that consumers do not need to store units in order to anticipate price rises. Second, under the contingent pricing policy rather than the preannounced pricing mechanism, (i) prices could be lower, (ii) retailer revenues could be higher, and (iii) consumer surplus could be higher. This result is surprising, in that these three facts are in complete contrast to the case of a retailer selling divisible storable goods Dudine et al. (2006). Third, we quantify exactly how much more profitable a contingent policy could be with respect to a preannounced policy. Specifically, for a market with $N$ consumers, a contingent policy can produce a multiplicative factor of $Ω(\log N)$ more revenues than a preannounced policy, and this bound is tight.
Trading Networks with Bilateral Contracts
Venue: arXiv cs.GT 2018
Year: 2018

We consider a model of matching in trading networks in which firms can enter into bilateral contracts. In trading networks, stable outcomes, which are immune to deviations of arbitrary sets of firms, may not exist. We define a new solution concept called trail stability. Trail-stable outcomes are immune to consecutive, pairwise deviations between linked firms. We show that any trading network with bilateral contracts has a trail-stable outcome whenever firms' choice functions satisfy the full substitutability condition. For trail-stable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategy-proofness, and comparative statics of firm entry and exit. We also introduce weak trail stability which is implied by trail stability under full substitutability. We describe relationships between the solution concepts.
Oblivious Fronthaul-Constrained Relay for a Gaussian Channel
Venue: arXiv cs.IT 2018
Year: 2018

We consider systems in which the transmitter conveys messages to the receiver through a capacity-limited relay station. The channel between the transmitter and the relay-station is assumed to be a frequency selective additive Gaussian noise channel. It is assumed that the transmitter can shape the spectrum and adapt the coding technique so as to optimize performance. The relay operation is oblivious (nomadic transmitters), that is, the specific codebooks used are unknown. We find the reliable information rate that can be achieved with Gaussian signaling in this setting, and to that end, employ Gaussian bottleneck results combined with Shannon's incremental frequency approach. We also prove that, unlike classical water-pouring, the allocated spectrum (power and bit-rate) of the optimal solution could frequently be discontinuous. These results can be applied to a MIMO transmission scheme. We also investigate the case of an entropy limited relay. We present lower and upper bounds on the optimal performance (in terms of mutual information), and derive an analytical approximation.
Toward an Efficient Multi-class Classification in an Open Universe
Venue: arXiv cs.LG 2018
Year: 2018

Classification is a fundamental task in machine learning and data mining. Existing classification methods are designed to classify unknown instances within a set of previously known training classes. Such a classification takes the form of a prediction within a closed-set of classes. However, a more realistic scenario that fits real-world applications is to consider the possibility of encountering instances that do not belong to any of the training classes, $i.e.$, an open-set classification. In such situation, existing closed-set classifiers will assign a training label to these instances resulting in a misclassification. In this paper, we introduce Galaxy-X, a novel multi-class classification approach for open-set recognition problems. For each class of the training set, Galaxy-X creates a minimum bounding hyper-sphere that encompasses the distribution of the class by enclosing all of its instances. In such manner, our method is able to distinguish instances resembling previously seen classes from those that are of unknown ones. To adequately evaluate open-set classification, we introduce a novel evaluation procedure. Experimental results on benchmark datasets show the efficiency of our approach in classifying novel instances from known as well as unknown classes.
Waste Makes Haste: Bounded Time Protocols for Envy-Free Cake Cutting with Free Disposal
Venue: arXiv cs.DS 2018
Year: 2018

We consider the classic problem of envy-free division of a heterogeneous good ("cake") among several agents. It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite algorithm for 3 or more agents. The impossibility result, however, assumes that the entire cake must be allocated. In this paper we replace the entire-allocation requirement with a weaker \emph{partial-proportionality} requirement: the piece given to each agent must be worth for it at least a certain positive fraction of the entire cake value. We prove that this version of the problem is solvable in bounded time even when the pieces must be connected. We present simple, bounded-time envy-free cake-cutting algorithms for: (1) giving each of $n$ agents a connected piece with a positive value; (2) giving each of 3 agents a connected piece worth at least 1/3; (3) giving each of 4 agents a connected piece worth at least 1/7; (4) giving each of 4 agents a disconnected piece worth at least 1/4; (5) giving each of $n$ agents a disconnected piece worth at least $(1-ε)/n$ for any positive $ε$.
A Light CNN for Deep Face Representation with Noisy Labels
Venue: arXiv cs.CV 2018
Year: 2018

The volume of convolutional neural network (CNN) models proposed for face recognition has been continuously growing larger to better fit large amount of training data. When training data are obtained from internet, the labels are likely to be ambiguous and inaccurate. This paper presents a Light CNN framework to learn a compact embedding on the large-scale face data with massive noisy labels. First, we introduce a variation of maxout activation, called Max-Feature-Map (MFM), into each convolutional layer of CNN. Different from maxout activation that uses many feature maps to linearly approximate an arbitrary convex activation function, MFM does so via a competitive relationship. MFM can not only separate noisy and informative signals but also play the role of feature selection between two feature maps. Second, three networks are carefully designed to obtain better performance meanwhile reducing the number of parameters and computational costs. Lastly, a semantic bootstrapping method is proposed to make the prediction of the networks more consistent with noisy labels. Experimental results show that the proposed framework can utilize large-scale noisy data to learn a Light model that is efficient in computational costs and storage spaces. The learned single network with a 256-D representation achieves state-of-the-art results on various face benchmarks without fine-tuning. The code is released on https://github.com/AlfredXiangWu/LightCNN.
Deep learning is a good steganalysis tool when embedding key is reused for different images, even if there is a cover source-mismatch
Venue: arXiv cs.MM 2018
Year: 2018

Since the BOSS competition, in 2010, most steganalysis approaches use a learning methodology involving two steps: feature extraction, such as the Rich Models (RM), for the image representation, and use of the Ensemble Classifier (EC) for the learning step. In 2015, Qian et al. have shown that the use of a deep learning approach that jointly learns and computes the features, is very promising for the steganalysis. In this paper, we follow-up the study of Qian et al., and show that, due to intrinsic joint minimization, the results obtained from a Convolutional Neural Network (CNN) or a Fully Connected Neural Network (FNN), if well parameterized, surpass the conventional use of a RM with an EC. First, numerous experiments were conducted in order to find the best " shape " of the CNN. Second, experiments were carried out in the clairvoyant scenario in order to compare the CNN and FNN to an RM with an EC. The results show more than 16% reduction in the classification error with our CNN or FNN. Third, experiments were also performed in a cover-source mismatch setting. The results show that the CNN and FNN are naturally robust to the mismatch problem. In Addition to the experiments, we provide discussions on the internal mechanisms of a CNN, and weave links with some previously stated ideas, in order to understand the impressive results we obtained.
The Invisible Hand of Dynamic Market Pricing
Venue: arXiv cs.GT 2018
Year: 2018

Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrarily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done. We further extend our results to Bayesian and bounded rationality models.
Reconstruction of depth-3, top fan-in two circuits over characteristic zero fields
Venue: arXiv cs.DS 2018
Year: 2018

Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $ΣΠΣ(2)$ circuits over $\mathbb{F}$ ($char(\mathbb{F})=0$), i.e. depth$-3$ circuits with fan-in $2$ at the top addition gate and having coefficients from a field of characteristic $0$. The algorithm needs only a blackbox query access to the polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ of degree $d$, computable by a $ΣΠΣ(2)$ circuit $C$. In addition, we assume that "simple rank" of this polynomial (essential number of variables after removing gcd of the two multiplication gates) is bigger than a constant. Our algorithm runs in time $poly(n, d)$ and returns an equivalent $ΣΠΣ(2)$ circuit(with high probability). The problem of reconstructing $ΣΠΣ(2)$ circuits over finite fields was first proposed by Shpilka in [24]. The generalization to $ΣΠΣ(k)$ circuits, $k = O(1)$ (over finite fields) was addressed by Karnin and Shpilka in [15]. The techniques in these previous involve iterating over all objects of certain kinds over the ambient field and thus running time depends on size of the field $\mathbb{F}$. Their reconstruction algorithm uses lower bounds on the lengths of Linear Locally Decodable Codes with $2$ queries. In our settings, such ideas immediately pose a problem and we need new ideas to handle the case of the characteristic $0$ field $\mathbb{F}$. Our main techniques are based on the use of Quantitative Syslvester Gallai Theorems from the work of Barak et.al. [3] to find a small collection of subspaces to project onto. The heart of our paper lies in subtle applications of Quantitative Sylvester Gallai theorems to prove why projections w.r.t. these subspaces can be glued.
A Study of Time-varying Cost Parameter Estimation Methods in Automated Transportation Systems based on Mobile Robots
Venue: arXiv cs.RO 2018
Year: 2018

Control of systems of automated guided vehicles involves action planning at many levels. For efficient control of these systems, accurate estimation of cost parameters (speed, energy, task completion performance, \textit{et~cetera} is required. These parameters change along time, particularly in battery-operated robots, which are very sensitive to battery level variations. This work addresses the problem of on-line cost parameter identification and estimation for proper control decisions of the individual mobile robots and for the system as a whole. Several filtering and estimation methods have been investigated with respect to travelling times, which are dramatically affected by battery charges and condition of facility's floors, among other factors. Results show that these parameters depend on the robot, the route and the moment, so they are linked to a particular robot, a region of the floor and a time period (or to a battery level). Moreover, differences with static, pre-runtime travelling time computations, either heuristically or by characterization of real robots, are large enough to affect to system's performance and overall productivity and efficiency.
NEWCAST: Anticipating Resource Management and QoE Provisioning for Mobile Video Streaming
Venue: arXiv cs.MM 2018
Year: 2018

The knowledge of future throughput variations in mobile networks becomes more and more possible today thanks to the rich contextual information provided by mobile applications and services and smartphone sensors. It is even likely that such contextual information, which may include traffic, mobility and radio conditions will lead to a novel agile resource management not yet thought of. In this paper, we propose an framework (called NEWCAST) that anticipates the throughput variations to deliver video streaming content. We develop an optimization problem that realizes a fundamental trade-off among critical metrics that impact the user's perceptual quality of experience (QoE) and the cost of system utilization. Both simulated and real-world throughput traces collected from [1], were carried out to evaluate the performance of NEWCAST. In particular, we show from our numerical results that NEWCAST provides the efficiency that the new 5G architectures require in terms of computational complexity and robustness. We also implement a prototype system of NEWCAST and evaluate it in a real environment with a real player to show its efficiency and scalability compared to baseline adaptive bitrate algorithms.
Simple set cardinality estimation through random sampling
Venue: arXiv cs.DM 2018
Year: 2018

We present a simple algorithm that estimates the cardinality $n$ of a set $V$ when allowed to sample elements of $V$ uniformly and independently at random. Our algorithm with probability $(1-δ)$ returns a $(1\pmε)-$approximation of $n$ drawing $O\big(\sqrt{n} \cdot ε^{-1}\sqrt{\log(δ^{-1})}\big)$ samples (for $ε^{-1}\sqrt{\log(δ^{-1})} = O(\sqrt{n})$).