consider:looking-to-see   687
[1710.10964] At the Roots of Dictionary Compression: String Attractors
A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this fact, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text's size by exploiting its repetitiveness. Lempel-Ziv 77 is probably one of the most successful and known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, and other less-known schemes. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all distinct text's substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives us the approximation ratios of dictionary compressors with respect to the smallest string attractor and allows us to solve several open problems related to the asymptotic relations between the output sizes of different dictionary compressors. We then show that the k-attractor problem - that is, deciding whether a text has a size-t set of positions capturing all substrings of length at most k - is NP-complete for k >= 3. We provide approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower- and upper- bounds for the random access problem on string attractors. Our optimal data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, our solution matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access problem for all these compressors.
compression  strings  feature-extraction  representation  algorithms  computational-complexity  to-understand  nudge-targets  consider:looking-to-see
18 days ago by Vaguery
[1805.07980] Collisionless periodic orbits in the free-fall three-body problem
Although the free-fall three-body problem have been investigated for more than one century, however, only four collisionless periodic orbits have been found. In this paper, we report 234 collisionless periodic orbits of the free-fall three-body system with some mass ratios, including three known collisionless periodic orbits. Thus, 231 collisionless free-fall periodic orbits among them are entirely new. In theory, we can gain periodic orbits of the free-fall three-body system in arbitrary ratio of mass. Besides, it is found that, for a given ratio of masses of two bodies, there exists a generalized Kepler's third law for the periodic three-body system. All of these would enrich our knowledge and deepen our understanding about the famous three-body problem as a whole.
nonlinear-dynamics  stamp-collecting  rather-interesting  nudge-targets  consider:looking-to-see  consider:performance-measures
7 weeks ago by Vaguery
[1805.02436] Combining Tools for Optimization and Analysis of Floating-Point Computations
Recent renewed interest in optimizing and analyzing floating-point programs has lead to a diverse array of new tools for numerical programs. These tools are often complementary, each focusing on a distinct aspect of numerical programming. Building reliable floating point applications typically requires addressing several of these aspects, which makes easy composition essential. This paper describes the composition of two recent floating-point tools: Herbie, which performs accuracy optimization, and Daisy, which performs accuracy verification. We find that the combination provides numerous benefits to users, such as being able to use Daisy to check whether Herbie's unsound optimizations improved the worst-case roundoff error, as well as benefits to tool authors, including uncovering a number of bugs in both tools. The combination also allowed us to compare the different program rewriting techniques implemented by these tools for the first time. The paper lays out a road map for combining other floating-point tools and for surmounting common challenges.
numerical-methods  algorithms  optimization  rather-interesting  floating-point  representation  to-understand  nudge-targets  consider:looking-to-see
7 weeks ago by Vaguery
[1805.02274] On the $f$-Matrices of Pascal-like Triangles Defined by Riordan Arrays
We define and characterize the f-matrices associated to Pascal-like matrices that are defined by ordinary and exponential Riordan arrays. These generalize the face matrices of simplices and hypercubes. Their generating functions can be expressed simply in terms of continued fractions, which are shown to be transformations of the generating functions of the corresponding γ- and h-matrices.
combinatorics  continued-fractions  topology  to-understand  to-write-about  nudge-targets  consider:looking-to-see
8 weeks ago by Vaguery
[1607.01117] Anagram-free Graph Colouring
An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and k-anagram-free colouring.
graph-theory  algorithms  graph-coloring  feature-construction  nudge-targets  consider:looking-to-see  computational-complexity
8 weeks ago by Vaguery
[1612.09443] Transversals in Latin arrays with many distinct symbols
An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an n×n array is a selection of n different symbols from different rows and different columns. We prove that every n×n Latin array containing at least (2−2‾√)n2 distinct symbols has a transversal. Also, every n×n row-Latin array containing at least 14(5−5‾√)n2 distinct symbols has a transversal. Finally, we show by computation that every Latin array of order 7 has a transversal, and we describe all smaller Latin arrays that have no transversal.
combinatorics  existence-proof  rather-interesting  nudge-targets  consider:looking-to-see
8 weeks ago by Vaguery
[1708.09571] Anagram-free colourings of graph subdivisions
An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. A vertex colouring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph colouring was independently introduced by Kam\v{c}ev, {\L}uczak and Sudakov and ourselves. In this paper we introduce the study of anagram-free colourings of graph subdivisions. We show that every graph has an anagram-free 8-colourable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free 10-colourable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.
combinatorics  graph-theory  graph-coloring  computational-complexity  rather-interesting  nudge-targets  consider:looking-to-see
8 weeks ago by Vaguery
[1801.07155] Continued fractions and orderings on the Markov numbers
Markov numbers are integers that appear in the solution triples of the Diophantine equation, x2+y2+z2=3xyz, called the Markov equation. A classical topic in number theory, these numbers are related to many areas of mathematics such as combinatorics, hyperbolic geometry, approximation theory and cluster algebras.
There is a natural map from the rational numbers between zero and one to the Markov numbers. In this paper, we prove two conjectures seen in Martin Aigner's book, Markov's theorem and 100 years of the uniqueness conjecture, that determine an ordering on subsets of the Markov numbers based on their corresponding rational.
The proof uses the cluster algebra of the torus with one puncture and a resulting reformulation of the conjectures in terms of continued fractions. The key step is to analyze the difference in the numerator of a continued fraction when an operation is applied to its entries.
number-theory  continued-fractions  rather-interesting  to-write-about  consider:looking-to-see  consider:generalizations
10 weeks ago by Vaguery
[1803.01422] DAGs with NO TEARS: Smooth Optimization for Structure Learning
Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint and are not well-suited to general purpose optimization packages for their solution. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a smooth, constrained optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting nonconvex, constrained program involves smooth functions whose gradients are easy to compute and only involve elementary matrix operations. By using existing black-box optimization routines, our method uses global search to find an optimal DAG and can be implemented in about 50 lines of Python and outperforms existing methods without imposing any structural constraints.
graph-theory  combinatorics  algorithms  rather-interesting  computational-complexity  to-understand  to-write-about  nudge-targets  consider:looking-to-see  representation
april 2018 by Vaguery
[1801.00663] A Sharp Estimate for Probability Distributions
We consider absolutely continuous probability distributions f(x)dx on ℝ≥0. A result of Feldheim and Feldheim shows, among other things, that if the distribution is not compactly supported, then there exist z>0 such that most events in {X+Y≥2z} are comprised of a 'small' term satisfying min(X,Y)≤z and a 'large' term satisfying max(X,Y)≥z (as opposed to two 'large' terms that are both larger than z)
limsupz→∞ ℙ(min(X,Y)≤z|X+Y≥2z)=1.
The result fails if the distribution is compactly supported. We prove
supz>0 ℙ(min(X,Y)≤z|X+Y≥2z)≥124+8log2(med(X)‖f‖L∞),
where med(X) denotes the median. Interestingly, the logarithm is necessary and the result is sharp up to constants; we also discuss some open problems.
probability-theory  statistics  rather-interesting  nudge-targets  consider:looking-to-see
march 2018 by Vaguery
A hybrid placement strategy for the three-dimensional strip packing problem - ScienceDirect
This paper presents a hybrid placement strategy for the three-dimensional strip packing problem which involves packing a set of cuboids (‘boxes’) into a three-dimensional bin (parallelepiped) of fixed width and height but unconstrained length (the ‘container’). The goal is to pack all of the boxes into the container, minimising its resulting length. This problem has potential industry application in stock cutting (wood, polystyrene, etc. – minimising wastage) and also cargo loading, as well as other applications in areas such as multi-dimensional resource scheduling. In addition to the proposed strategy a number of test results on available literature benchmark problems are presented and analysed. The results of empirical testing of the algorithm show that it out-performs other methods from the literature, consistently in terms of speed and solution quality-producing 28 best known results from 35 test cases.
operations-research  hyperheuristics  metaheuristics  optimization  constraint-satisfaction  nudge-targets  consider:representation  consider:looking-to-see  to-write-about
march 2018 by Vaguery
[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2018 by Vaguery
[1711.03532] Co-Optimization Generation and Distribution Planning in Microgrids
This paper proposes a co-optimization generation and distribution planning model in microgrids in which simultaneous investment in generation, i.e., distributed generation (DG) and distributed energy storage (DES), and distribution, i.e., upgrading the existing distribution network, is considered. The objective of the proposed model is to minimize the microgrid total planning cost which comprises the investment cost of installed generation assets and lines, the microgrid operation cost, and the cost of unserved energy. The microgrid planning solution determines the optimal generation size, location, and mix, as well as required network upgrade. To consider line flow and voltage limits, a linearized power flow model is proposed and used, allowing further application of mixed integer linear programming (MILP) in problem modeling. The proposed model is applied to the IEEE 33-bus standard test system to demonstrate the acceptable performance and the effectiveness of the proposed model.
optimization  network-theory  mathematical-programming  multiobjective-optimization  rather-interesting  operations-research  utilities  nudge-targets  consider:looking-to-see
march 2018 by Vaguery
[1801.01922] Vectorization of Line Drawings via PolyVector Fields
Image tracing is a foundational component of the workflow in graphic design, engineering, and computer animation, linking hand-drawn concept images to collections of smooth curves needed for geometry processing and editing. Even for clean line drawings, modern algorithms often fail to faithfully vectorize junctions, or points at which curves meet; this produces vector drawings with incorrect connectivity. This subtle issue undermines the practical application of vectorization tools and accounts for hesitance among artists and engineers to use automatic vectorization software. To address this issue, we propose a novel image vectorization method based on state-of-the-art mathematical algorithms for frame field processing. Our algorithm is tailored specifically to disambiguate junctions without sacrificing quality.
graphics  algorithms  inference  rather-interesting  feature-construction  nudge-targets  consider:representation  consider:looking-to-see  consider:performance-measures
march 2018 by Vaguery
[1709.06217] Deterministic meeting of sniffing agents in the plane
Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are integers from the set of 0 to L-1. Each agent knows L and knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1 was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than \r{ho} or at distance at least \r{ho} from the other agent, for some real \r{ho} > 1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance.
agent-based  rather-interesting  random-processes  sensors  emergent-design  proof  to-write-about  consider:looking-to-see
march 2018 by Vaguery
[1611.05896] Answering Image Riddles using Vision and Reasoning through Probabilistic Soft Logic
In this work, we explore a genre of puzzles ("image riddles") which involves a set of images and a question. Answering these puzzles require both capabilities involving visual detection (including object, activity recognition) and, knowledge-based or commonsense reasoning. We compile a dataset of over 3k riddles where each riddle consists of 4 images and a groundtruth answer. The annotations are validated using crowd-sourced evaluation. We also define an automatic evaluation metric to track future progress. Our task bears similarity with the commonly known IQ tasks such as analogy solving, sequence filling that are often used to test intelligence.
We develop a Probabilistic Reasoning-based approach that utilizes probabilistic commonsense knowledge to answer these riddles with a reasonable accuracy. We demonstrate the results of our approach using both automatic and human evaluations. Our approach achieves some promising results for these riddles and provides a strong baseline for future attempts. We make the entire dataset and related materials publicly available to the community in ImageRiddle Website (this http URL).
machine-learning  image-processing  natural-language-processing  deep-learning  puzzles  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:integrating-NLP
march 2018 by Vaguery
[1710.01802] Automatic Structural Scene Digitalization
In this paper, we present an automatic system for the analysis and labeling of structural scenes, floor plan drawings in Computer-aided Design (CAD) format. The proposed system applies a fusion strategy to detect and recognize various components of CAD floor plans, such as walls, doors, windows and other ambiguous assets. Technically, a general rule-based filter parsing method is fist adopted to extract effective information from the original floor plan. Then, an image-processing based recovery method is employed to correct information extracted in the first step. Our proposed method is fully automatic and real-time. Such analysis system provides high accuracy and is also evaluated on a public website that, on average, archives more than ten thousands effective uses per day and reaches a relatively high satisfaction rate.
february 2018 by Vaguery
[1802.08535] Can Neural Networks Understand Logical Entailment?
We introduce a new dataset of logical entailments for the purpose of measuring models' ability to capture and exploit the structure of logical expressions against an entailment prediction task. We use this task to compare a series of architectures which are ubiquitous in the sequence-processing literature, in addition to a new model class---PossibleWorldNets---which computes entailment as a "convolution over possible worlds". Results show that convolutional networks present the wrong inductive bias for this class of problems relative to LSTM RNNs, tree-structured neural networks outperform LSTM RNNs due to their enhanced ability to exploit the syntax of logic, and PossibleWorldNets outperform all benchmarks.
Betteridge's-Law  neural-networks  representation  nudge-targets  consider:looking-to-see  low-hanging-fruit  right-tool-for-the-job
february 2018 by Vaguery
[1510.02875] Exploring mod2 n-queens games
We introduce a two player game on an n x n chessboard where queens are placed by alternating turns on a chessboard square whose availability is determined by the number of queens already on the board which can attack that square modulo two. The game is explored along with some variations and its complexity.
mathematical-recreations  chess  enumeration  game-theory  rather-interesting  nudge-targets  consider:looking-to-see
february 2018 by Vaguery
[1801.02262] Magic Polygons and Their Properties
Magic squares are arrangements of natural numbers into square arrays, where the sum of each row, each column, and both diagonals is the same. In this paper, the concept of a magic square with 3 rows and 3 columns is generalized to define magic polygons. Furthermore, this paper will examine the existence of magic polygons, along with several other properties inherent to magic polygons.
mathematical-recreations  magic-squares  combinatorics  number-theory  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see
february 2018 by Vaguery

Copy this bookmark:

description:

tags: