OpenRaiser/Intern-Atlas huggingface dataset:
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
Venue: arXiv cs.DS 2014
Year: 2014

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. proved that a certain configuration LP can be used to estimate the optimal value within a factor ${1}/{(4+ε)}$, for any $ε>0$, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee. A natural question that arises from their work is if the difference between these guarantees is inherent or because of a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. and provide a novel analysis that lets us significantly improve the bound on its running time: from $2^{O(n)}$ to $n^{O(\log n)}$. Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.
A mathematical problem for security analysis of hash functions and pseudorandom generators
Venue: arXiv cs.CR 2014
Year: 2014

In this paper, we specify a class of mathematical problems, which we refer to as "Function Density Problems" (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.
A Classification of Weakly Acyclic Games
Venue: arXiv cs.GT 2014
Year: 2014

Weakly acyclic games form a natural generalization of the class of games that have the finite improvement property (FIP). In such games one stipulates that from any initial joint strategy some finite improvement path exists. We classify weakly acyclic games using the concept of a scheduler introduced in arXiv:1202.2209. We also show that finite games that can be solved by the iterated elimination of never best response strategies are weakly acyclic. Finally, we explain how the schedulers allow us to improve the bounds on finding a Nash equilibrium in a weakly acyclic game.
Poisson noise reduction with non-local PCA
Venue: arXiv cs.CV 2014
Year: 2014

Photon-limited imaging arises when the number of photons collected by a sensor array is small relative to the number of detector elements. Photon limitations are an important concern for many applications such as spectral imaging, night vision, nuclear medicine, and astronomy. Typically a Poisson distribution is used to model these observations, and the inherent heteroscedasticity of the data combined with standard noise removal methods yields significant artifacts. This paper introduces a novel denoising algorithm for photon-limited images which combines elements of dictionary learning and sparse patch-based representations of images. The method employs both an adaptation of Principal Component Analysis (PCA) for Poisson noise and recently developed sparsity-regularized convex optimization algorithms for photon-limited images. A comprehensive empirical evaluation of the proposed method helps characterize the performance of this approach relative to other state-of-the-art denoising methods. The results reveal that, despite its conceptual simplicity, Poisson PCA-based denoising appears to be highly competitive in very low light regimes.
Using Short Synchronous WOM Codes to Make WOM Codes Decodable
Venue: arXiv cs.IT 2014
Year: 2014

In the framework of write-once memory (WOM) codes, it is important to distinguish between codes that can be decoded directly and those that require that the decoder knows the current generation to successfully decode the state of the memory. A widely used approach to construct WOM codes is to design first nondecodable codes that approach the boundaries of the capacity region, and then make them decodable by appending additional cells that store the current generation, at an expense of a rate loss. In this paper, we propose an alternative method to make nondecodable WOM codes decodable by appending cells that also store some additional data. The key idea is to append to the original (nondecodable) code a short synchronous WOM code and write generations of the original code and of the synchronous code simultaneously. We consider both the binary and the nonbinary case. Furthermore, we propose a construction of synchronous WOM codes, which are then used to make nondecodable codes decodable. For short-to-moderate block lengths, the proposed method significantly reduces the rate loss as compared to the standard method.
Assisted Common Information with an Application to Secure Two-Party Sampling
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we generalize the notion of common information of two dependent variables introduced by Gács & Körner. They defined common information as the largest entropy rate of a common random variable two parties observing one of the sources each can agree upon. It is well-known that their common information captures only a limited form of dependence between the random variables and is zero in most cases of interest. Our generalization, which we call the Assisted Common Information system, takes into account almost-common information ignored by Gács-Körner common information. In the assisted common information system, a genie assists the parties in agreeing on a more substantial common random variable; we characterize the trade-off between the amount of communication from the genie and the quality of the common random variable produced using a rate region we call the region of tension. We show that this region has an application in deriving upperbounds on the efficiency of secure two-party sampling, which is a special case of secure multi-party computation, a central problem in modern cryptography. Two parties desire to produce samples of a pair of jointly distributed random variables such that neither party learns more about the other's output than what its own output reveals. They have access to a set up - correlated random variables whose distribution is different from the desired distribution - and noiseless communication. We present an upperbound on the rate at which a given set up can be used to produce samples from a desired distribution by showing a monotonicity property for the region of tension: a protocol between two parties can only lower the tension between their views. Then, by calculating the bounds on the region of tension of various pairs of correlated random variables, we derive bounds on the rate of secure two-party sampling.
Church: a language for generative models
Venue: arXiv cs.PL 2014
Year: 2014

We introduce Church, a universal language for describing stochastic generative processes. Church is based on the Lisp model of lambda calculus, containing a pure Lisp as its deterministic subset. The semantics of Church is defined in terms of evaluation histories and conditional distributions on such histories. Church also includes a novel language construct, the stochastic memoizer, which enables simple description of many complex non-parametric models. We illustrate language features through several examples, including: a generalized Bayes net in which parameters cluster over trials, infinite PCFGs, planning by inference, and various non-parametric clustering models. Finally, we show how to implement query on any Church program, exactly and approximately, using Monte Carlo techniques.
Epidemic Spreading with External Agents
Venue: arXiv cs.SI 2014
Year: 2014

We study epidemic spreading processes in large networks, when the spread is assisted by a small number of external agents: infection sources with bounded spreading power, but whose movement is unrestricted vis-à-vis the underlying network topology. For networks which are `spatially constrained', we show that the spread of infection can be significantly speeded up even by a few such external agents infecting randomly. Moreover, for general networks, we derive upper-bounds on the order of the spreading time achieved by certain simple (random/greedy) external-spreading policies. Conversely, for certain common classes of networks such as line graphs, grids and random geometric graphs, we also derive lower bounds on the order of the spreading time over all (potentially network-state aware and adversarial) external-spreading policies; these adversarial lower bounds match (up to logarithmic factors) the spreading time achieved by an external agent with a random spreading policy. This demonstrates that random, state-oblivious infection-spreading by an external agent is in fact order-wise optimal for spreading in such spatially constrained networks.
TempEval-3: Evaluating Events, Time Expressions, and Temporal Relations
Venue: arXiv cs.CL 2014
Year: 2014

We describe the TempEval-3 task which is currently in preparation for the SemEval-2013 evaluation exercise. The aim of TempEval is to advance research on temporal information processing. TempEval-3 follows on from previous TempEval events, incorporating: a three-part task structure covering event, temporal expression and temporal relation extraction; a larger dataset; and single overall task quality scores.
A Geometric Algorithm for Scalable Multiple Kernel Learning
Venue: arXiv cs.LG 2014
Year: 2014

We present a geometric formulation of the Multiple Kernel Learning (MKL) problem. To do so, we reinterpret the problem of learning kernel weights as searching for a kernel that maximizes the minimum (kernel) distance between two convex polytopes. This interpretation combined with novel structural insights from our geometric formulation allows us to reduce the MKL problem to a simple optimization routine that yields provable convergence as well as quality guarantees. As a result our method scales efficiently to much larger data sets than most prior methods can handle. Empirical evaluation on eleven datasets shows that we are significantly faster and even compare favorably with a uniform unweighted combination of kernels.
Web Data Extraction, Applications and Techniques: A Survey
Venue: arXiv cs.IR 2014
Year: 2014

Web Data Extraction is an important problem that has been studied by means of different scientific tools and in a broad range of applications. Many approaches to extracting data from the Web have been designed to solve specific problems and operate in ad-hoc domains. Other approaches, instead, heavily reuse techniques and algorithms developed in the field of Information Extraction. This survey aims at providing a structured and comprehensive overview of the literature in the field of Web Data Extraction. We provided a simple classification framework in which existing Web Data Extraction applications are grouped into two main classes, namely applications at the Enterprise level and at the Social Web level. At the Enterprise level, Web Data Extraction techniques emerge as a key tool to perform data analysis in Business and Competitive Intelligence systems as well as for business process re-engineering. At the Social Web level, Web Data Extraction techniques allow to gather a large amount of structured data continuously generated and disseminated by Web 2.0, Social Media and Online Social Network users and this offers unprecedented opportunities to analyze human behavior at a very large scale. We discuss also the potential of cross-fertilization, i.e., on the possibility of re-using Web Data Extraction techniques originally designed to work in a given domain, in other domains.
Left Recursion in Parsing Expression Grammars
Venue: arXiv cs.FL 2014
Year: 2014

Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG libraries in several programming languages. A frequently missed feature of PEGs is left recursion, which is commonly used in Context-Free Grammars (CFGs) to encode left-associative operations. We present a simple conservative extension to the semantics of PEGs that gives useful meaning to direct and indirect left-recursive rules, and show that our extensions make it easy to express left-recursive idioms from CFGs in PEGs, with similar results. We prove the conservativeness of these extensions, and also prove that they work with any left-recursive PEG. PEGs can also be compiled to programs in a low-level parsing machine. We present an extension to the semantics of the operations of this parsing machine that let it interpret left-recursive PEGs, and prove that this extension is correct with regards to our semantics for left-recursive PEGs.
Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
Venue: arXiv cs.DS 2014
Year: 2014

The most well-known conjecture in the context of matroid secretary problems claims the existence of a constant-factor approximation applicable to any matroid. Whereas this conjecture remains open, modified forms of it were shown to be true, when assuming that the assignment of weights to the secretaries is not adversarial but uniformly random (Soto [SODA 2011], Oveis Gharan and Vondrák [ESA 2011]). However, so far, there was no variant of the matroid secretary problem with adversarial weight assignment for which a constant-factor approximation was found. We address this point by presenting a 9-approximation for the \emph{free order model}, a model suggested shortly after the introduction of the matroid secretary problem, and for which no constant-factor approximation was known so far. The free order model is a relaxed version of the original matroid secretary problem, with the only difference that one can choose the order in which secretaries are interviewed. Furthermore, we consider the classical matroid secretary problem for the special case of laminar matroids. Only recently, a constant-factor approximation has been found for this case, using a clever but rather involved method and analysis (Im and Wang, [SODA 2011]) that leads to a 16000/3-approximation. This is arguably the most involved special case of the matroid secretary problem for which a constant-factor approximation is known. We present a considerably simpler and stronger $3\sqrt{3}e\approx 14.12$-approximation, based on reducing the problem to a matroid secretary problem on a partition matroid.
Receive Combining vs. Multi-Stream Multiplexing in Downlink Systems with Multi-Antenna Users
Venue: arXiv cs.IT 2014
Year: 2014

In downlink multi-antenna systems with many users, the multiplexing gain is strictly limited by the number of transmit antennas $N$ and the use of these antennas. Assuming that the total number of receive antennas at the multi-antenna users is much larger than $N$, the maximal multiplexing gain can be achieved with many different transmission/reception strategies. For example, the excess number of receive antennas can be utilized to schedule users with effective channels that are near-orthogonal, for multi-stream multiplexing to users with well-conditioned channels, and/or to enable interference-aware receive combining. In this paper, we try to answer the question if the $N$ data streams should be divided among few users (many streams per user) or many users (few streams per user, enabling receive combining). Analytic results are derived to show how user selection, spatial correlation, heterogeneous user conditions, and imperfect channel acquisition (quantization or estimation errors) affect the performance when sending the maximal number of streams or one stream per scheduled user---the two extremes in data stream allocation. While contradicting observations on this topic have been reported in prior works, we show that selecting many users and allocating one stream per user (i.e., exploiting receive combining) is the best candidate under realistic conditions. This is explained by the provably stronger resilience towards spatial correlation and the larger benefit from multi-user diversity. This fundamental result has positive implications for the design of downlink systems as it reduces the hardware requirements at the user devices and simplifies the throughput optimization.
Derivation of the Maximum a Posterori Estimate for Discrete Time Descriptor Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this report a derivation of the MAP state estimator objective function for general (possibly non-square) discrete time causal/non-causal descriptor systems is presented. The derivation made use of the Kronecker Canonical Transformation to extract the prior distribution on the descriptor state vector so that Maximum a Posteriori (MAP) point estimation can be used. The analysis indicates that the MAP estimate for index 1 causal descriptor systems does not require any model transformations and can be found recursively. Furthermore, if the descriptor system is of index 2 or higher and the noise free system is causal, then the MAP estimate can also be found recursively without model transformations provided that model causality is accounted for in designing the stochastic model.
The Price of Privacy in Untrusted Recommendation Engines
Venue: arXiv cs.LG 2014
Year: 2014

Recent increase in online privacy concerns prompts the following question: can a recommender system be accurate if users do not entrust it with their private data? To answer this, we study the problem of learning item-clusters under local differential privacy, a powerful, formal notion of data privacy. We develop bounds on the sample-complexity of learning item-clusters from privatized user inputs. Significantly, our results identify a sample-complexity separation between learning in an information-rich and an information-scarce regime, thereby highlighting the interaction between privacy and the amount of information (ratings) available to each user. In the information-rich regime, where each user rates at least a constant fraction of items, a spectral clustering approach is shown to achieve a sample-complexity lower bound derived from a simple information-theoretic argument based on Fano's inequality. However, the information-scarce regime, where each user rates only a vanishing fraction of items, is found to require a fundamentally different approach both for lower bounds and algorithms. To this end, we develop new techniques for bounding mutual information under a notion of channel-mismatch, and also propose a new algorithm, MaxSense, and show that it achieves optimal sample-complexity in this setting. The techniques we develop for bounding mutual information may be of broader interest. To illustrate this, we show their applicability to $(i)$ learning based on 1-bit sketches, and $(ii)$ adaptive learning, where queries can be adapted based on answers to past queries.
Can Quantum Communication Speed Up Distributed Computation?
Venue: arXiv cs.DC 2014
Year: 2014

The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication {\em does not} help in substantially speeding up distributed algorithms for these problems compared to the classical setting. In order to obtain this result, we extend the technique of Das Sarma et al. [SICOMP 2012] to obtain a uniform approach to prove non-trivial lower bounds for quantum distributed algorithms for several graph optimization (both exact and approximate versions) as well as verification problems, some of which are new even in the classical setting, e.g. tight randomized lower bounds for Hamiltonian cycle and spanning tree verification, answering an open problem of Das Sarma et al., and a lower bound in terms of the weight aspect ratio, matching the upper bounds of Elkin [STOC 2004]. Our approach introduces the {\em Server model} and {\em Quantum Simulation Theorem} which together provide a connection between distributed algorithms and communication complexity. The Server model is the standard two-party communication complexity model augmented with additional power; yet, most of the hardness in the two-party model is carried over to this new model. The Quantum Simulation Theorem carries this hardness further to quantum distributed computing. Our techniques, except the proof of the hardness in the Server model, require very little knowledge in quantum computing, and this can help overcoming a usual impediment in proving bounds on quantum distributed algorithms.
A colouring protocol for the generalized Russian cards problem
Venue: arXiv cs.IT 2014
Year: 2014

In the generalized Russian cards problem, Alice, Bob and Cath draw $a$, $b$ and $c$ cards, respectively, from a deck of size $a+b+c$. Alice and Bob must then communicate their entire hand to each other, without Cath learning the owner of a single card she does not hold. Unlike many traditional problems in cryptography, however, they are not allowed to encode or hide the messages they exchange from Cath. The problem is then to find methods through which they can achieve this. We propose a general four-step solution based on finite vector spaces, and call it the "colouring protocol", as it involves colourings of lines. Our main results show that the colouring protocol may be used to solve the generalized Russian cards problem in cases where $a$ is a power of a prime, $c=O(a^2)$ and $b=O(c^2)$. This improves substantially on the set of parameters for which solutions are known to exist; in particular, it had not been shown previously that the problem could be solved in cases where the eavesdropper has more cards than one of the communicating players.
The Cutting Plane Method is Polynomial for Perfect Matchings
Venue: arXiv cs.DS 2014
Year: 2014

The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland '85, Lovasz and Plummer '86, Trick '87, Fischetti and Lodi '07) and its convergence has been an open question. We give a cutting plane algorithm that converges in polynomial-time using only Edmonds' blossom inequalities; it maintains half-integral intermediate LP solutions supported by a disjoint union of odd cycles and edges. Our main insight is a method to retain only a subset of the previously added cutting planes based on their dual values. This allows us to quickly find violated blossom inequalities and argue convergence by tracking the number of odd cycles in the support of intermediate solutions.