Top 10 Arxiv Papers Today in Computational Complexity


2.003 Mikeys
#1. PRAMs over integers do not compute maxflow efficiently
Luc Pellissier, Thomas Seiller
Finding lower bounds in complexity theory has proven to be an extremely difficult task. In this article, we analyze two proofs of complexity lower bound: Ben-Or's proof of minimal height of algebraic computational trees deciding certain problems and Mulmuley's proof that restricted Parallel Random Access Machines (prams) over integers can not decide P-complete problems efficiently. We present the aforementioned models of computation in a framework inspired by dynamical systems and models of linear logic : graphings. This interpretation allows to connect the classical proofs to topological entropy, an invariant of these systems; to devise an algebraic formulation of parallelism of computational models; and finally to strengthen Mulmuley's result by separating the geometrical insights of the proof from the ones related to the computation and blending these with Ben-Or's proof. Looking forward, the interpretation of algebraic complexity theory as dynamical system might shed a new light on research programs such as Geometric...
more | pdf | html
Figures
Tweets
ComputerPapers: PRAMs over integers do not compute maxflow efficiently. https://t.co/PokdvrePPv
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 21746
Unqiue Words: 3680

1.998 Mikeys
#2. State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis
Tomoyuki Yamakami
The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem parameterized by the number of Boolean variables. From this hypothesis, it follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of decision problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L$\neq$NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. https://t.co/F8ZK3PvjWM
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 17000
Unqiue Words: 2698

0.0 Mikeys
#3. Postselecting probabilistic finite state recognizers and verifiers
Maksims Dimitrijevs, Abuzer Yakaryılmaz
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs using rational-valued transitions can do different variants of equality checks and they can verify some nonregular unary languages. Then, we allow them to use real-valued transitions (magic-coins) and show that they can recognize uncountably many binary languages by help of a counter and verify uncountably many unary languages by help of a prover. We also present some corollaries on probabilistic counter automata.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Postselecting probabilistic finite state recognizers and verifiers. https://t.co/pUZS6VZZ7M
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8076
Unqiue Words: 1663

0.0 Mikeys
#4. Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program.
more | pdf | html
Figures
None.
Tweets
M157q_News_RSS: Fooling Polytopes. (arXiv:1808.04035v1 [https://t.co/v2KswNHWZT]) https://t.co/bJaTLeyjzQ We give a pseudorandom generator that fools $m$-facet polytopes over
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 19446
Unqiue Words: 3666

0.0 Mikeys
#5. Probabilistic verification of all languages
Maksims Dimitrijevs, Abuzer Yakaryılmaz
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any language, there is a constant-space weak-IPS (the non-members may not be rejected with high probability); and, (iii) for any language, there is a constant-space IPS with two provers where the verifier reads the input once. Additionally, we show that uncountably many binary (unary) languages can be verified in constant space and in linear (quadratic) expected time.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Probabilistic verification of all languages. https://t.co/9IkFdNHYN0
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 10444
Unqiue Words: 1930

0.0 Mikeys
#6. PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. Building on the inherent connection...
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 21937
Unqiue Words: 3762

0.0 Mikeys
#7. On the Computational Complexity of Length- and Neighborhood-Constrained Path Problems
Max-Jonathan Luckow, Till Fluschnik
Finding paths in graphs is a fundamental graph-theoretic task. In this work, we study the task of finding a path with some constraints on its length and the number of vertices neighboring the path, that is, being outside of and incident with the path. Herein, we consider short and long path on the one side, and small and large neighborhoods on the other side---yielding four decision problems. We show that all four problems are NP-complete, even in planar graphs with small maximum degree. Moreover, we study all four variant when parameterized by the bound $k$ on the length of the path, by the bound $\ell$ on the size of neighborhood, and by $k+\ell$.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6996
Unqiue Words: 1467

0.0 Mikeys
#8. Fair redistricting is hard
Richard Kueng, Dustin G. Mixon, Soledad Villar
Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is NP-hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is NP-hard.
more | pdf | html
Figures
Tweets
ComputerPapers: Fair redistricting is hard. https://t.co/4lQ7tVhPVt
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 5553
Unqiue Words: 1736

0.0 Mikeys
#9. Undecidable word problem in subshift automorphism groups
Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, Pascal Vanier
This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly this degree.
more | pdf | html
Figures
None.
Tweets
MathPaper: Undecidable word problem in subshift automorphism groups. https://t.co/2Xcea22pZF
mathGRbot: Pierre Guillon (I2M), Emmanuel Jeandel (CARTE), Jarkko Kari, Pascal Vanier (LACL) : Undecidable word problem in subshift automorphism groups https://t.co/URMFcuRwdG
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 3670
Unqiue Words: 1044

0.0 Mikeys
#10. List Decoding with Double Samplers
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta Shma
We develop the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [IEEE Trans. Inform. Theory, 38(2):509--516, 1992.]. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code $C$ (i.e., it runs the unique decoder for $C$ in a black box way). Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: List Decoding with Double Samplers. https://t.co/Kwjsrmaeod
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 19104
Unqiue Words: 3063

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 58,338 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 58,338 papers.