- arXiv.org
- Popular Physics
- Space Physics
- History and Philosophy of Physics
- Optics
- Atomic and Molecular Clusters
- Physics and Society
- Data Analysis, Statistics and Probability
- Fluid Dynamics
- Biological Physics
- General Physics
- Geophysics
- Atomic Physics
- Plasma Physics
- Medical Physics
- Physics Education
- Instrumentation and Detectors
- Classical Physics
- Chemical Physics
- Computational Physics
- Accelerator Physics
- Atmospheric and Oceanic Physics

- Number Theory
- Analysis of PDEs
- Information Theory
- Statistics Theory
- History and Overview
- Mathematical Physics
- Combinatorics
- Operator Algebras
- Algebraic Geometry
- Probability
- Representation Theory
- Complex Variables
- Symplectic Geometry
- Group Theory
- Quantum Algebra
- Optimization and Control
- General Topology
- Dynamical Systems
- Geometric Topology
- Numerical Analysis
- Differential Geometry
- Metric Geometry
- Logic
- General Mathematics
- Spectral Theory
- Category Theory
- Rings and Algebras
- Algebraic Topology
- Classical Analysis and ODEs
- K-Theory and Homology
- Commutative Algebra
- Functional Analysis

- Information Retrieval
- Information Theory
- General Literature
- Formal Languages and Automata Theory
- Computational Engineering, Finance, and Science
- Symbolic Computation
- Emerging Technologies
- Learning
- Computer Vision and Pattern Recognition
- Neural and Evolutionary Computing
- Programming Languages
- Social and Information Networks
- Multiagent Systems
- Databases
- Sound
- Software Engineering
- Operating Systems
- Computer Science and Game Theory
- Hardware Architecture
- Artificial Intelligence
- Systems and Control
- Distributed, Parallel, and Cluster Computing
- Cryptography and Security
- Discrete Mathematics
- Digital Libraries
- Human-Computer Interaction
- Numerical Analysis
- Performance
- Mathematical Software
- Computational Complexity
- Other Computer Science
- Computation and Language
- Logic in Computer Science
- Robotics
- Data Structures and Algorithms
- Computational Geometry
- Computers and Society
- Networking and Internet Architecture
- Multimedia
- Graphics

- A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^2 \overline{m})$ to $O(nm)$, where $n$, $m$, and $\overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization in our previous paper that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph.
- Chain reduction enables reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the others' ability to symbolically represent Boolean functions in compact form. For any Boolean function, its chain-reduced ZDD (CZDD) representation will be no larger than its ZDD representation, and at most twice the size of its BDD representation. The chain-reduced BDD (CBDD) of a function will be no larger than its BDD representation, and at most three times the size of its CZDD representation. Extensions to the standard algorithms for operating on BDDs and ZDDs enable them to operate on the chain-reduced versions. Experimental evaluations on representative benchmarks for encoding word lists, solving combinatorial problems, and operating on digital circuits indicate that chain reduction can provide significant benefits in terms of both memory and execution time.

LCL problems on grids

Māris Ozols Feb 21 2017 15:35 UTCZoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

Māris Ozols Oct 21 2016 21:06 UTC

...(continued)Very nice! Now we finally know how to fairly cut a cake in a finite number of steps! What is more, the number of steps is expected to go down from the whopping $n^{n^{n^{n^{n^n}}}}$ to just barely $n^{n^n}$. I can't wait to get my slice!

https://www.quantamagazine.org/20161006-new-algorithm-solve

Ashley Apr 21 2015 18:42 UTC

...(continued)Thanks for the further comments and spotting the new typos. To reply straight away to the other points:

First, the resulting states might as well stay in the same bin (even though, as you rightly note, the bins no longer correspond to the same bit-strings as before). All that matters is that the

Perplexed Platypus Apr 21 2015 14:55 UTC

...(continued)Thanks for updating the paper so promptly. The updated version addresses all my concerns so far. However I noticed a few extra (minor) things while reading through it.

On page 15, last step of 2(b): if $|\psi_r\rangle$ and $|\psi_t\rangle$ were in the same bin but the combination operation failed

Ashley Apr 20 2015 16:27 UTC

...(continued)Thank you for these very detailed and helpful comments. I have uploaded a new version of the paper to the arXiv to address them, which should appear tomorrow. I will reply to the comments in more detail (and justify the cases where I didn't modify the paper as suggested) when I receive them through

Perplexed Platypus Apr 13 2015 22:37 UTC

...(continued)**Summary and recommendation**

This paper considers a $d$-dimensional version of the problem of finding a given pattern within a text, for random patterns and text. The text is assumed to be picked uniformly at random and has size $n^d$ while the pattern has size $m^d$ and is either uniformly ran

Ashley Apr 12 2015 13:01 UTC

Thanks for the clarification. In fact it seems that I do have this option switched on, with the correct author identifier, so I'm not sure why I didn't get an email about these comments.

Perplexed Platypus Apr 10 2015 13:18 UTC

...(continued)Hi Ashley,

Thanks for your reply, it was very helpful! I thought about e-mailing you but I wanted to preserve my confidentiality as a reviewer. Also, I wanted to see if it is feasible to use SciRate as a platform for interacting with authors during the review process.

I encourage you (and **ot

Ashley Apr 09 2015 20:03 UTC

...(continued)Hi,

Thank you for your very detailed comments / questions about the technical points in this paper. I did happen to check Scirate today but in general (as I suspect with many other people) I don't check it regularly, so for reliable replies it's better just to email me. To reply to your questions i