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
ComputerPapers:
PRAMs over integers do not compute maxflow efficiently. https://t.co/PokdvrePPv

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 21746

Unqiue Words: 3680

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
None.

ComputerPapers:
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis. https://t.co/F8ZK3PvjWM

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 17000

Unqiue Words: 2698

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
None.

ComputerPapers:
Postselecting probabilistic finite state recognizers and verifiers. https://t.co/pUZS6VZZ7M

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 8076

Unqiue Words: 1663

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 19446

Unqiue Words: 3666

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
None.

ComputerPapers:
Probabilistic verification of all languages. https://t.co/9IkFdNHYN0

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 10444

Unqiue Words: 1930

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
None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 21937

Unqiue Words: 3762

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
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 6996

Unqiue Words: 1467

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
ComputerPapers:
Fair redistricting is hard. https://t.co/4lQ7tVhPVt

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 5553

Unqiue Words: 1736

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 3670

Unqiue Words: 1044

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
None.

ComputerPapers:
List Decoding with Double Samplers. https://t.co/Kwjsrmaeod

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 19104

Unqiue Words: 3063

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible