Counting Finite Topologies
In this paper we study the number of finite topologies on an $n$-element set subject to various restrictions.
Source author record
Eldar Fischer
Eldar Fischer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
12works
9topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
12 published item(s)
preprint2022arXiv
Extensions and Limits of the Specker-Blatter Theorem
The original Specker-Blatter Theorem (1983) was formulated for classes of structures $\mathcal{C}$ of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set $[n]$ is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol $c$, there are $n$ possible interpretations on $[n]$ for $c$. We say that a constant $c$ is {\em hard-wired} if $c$ is always interpreted by the same element $j \in [n]$. In this paper we show: 1. The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. 2. The Specker-Blatter Theorem does not hold already for $\mathcal{C}$ with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers $B_{r,A}$, restricted Stirling numbers of the second kind $S_{r,A}$ or restricted Lah-numbers $L_{r,A}$. Here $r$ is an non-negative integer and $A$ is an ultimately periodic set of non-negative integers.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Fast Distributed Algorithms for Testing Graph Properties
We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called \emph{dense} testing model we emulate sequential tests for nearly all graph properties having $1$-sided tests, while in the \emph{sparse} and \emph{general} models we obtain faster tests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that is of independent interest. This includes a method for distributed maintenance of multiple random walks.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Improving and extending the testing of distributions for shape-restricted properties
Distribution testing deals with what information can be deduced about an unknown distribution over $\{1,\ldots,n\}$, where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of $\{1,\ldots,n\}$. In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a "decomposability" criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in the variation distance. We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties. Our core mechanism is a way of efficiently producing an interval-partition of $\{1,\ldots,n\}$ that satisfies a "fine-grain" quality. We show that with such a partition at hand we can directly move forward with testing individual intervals, instead of first searching for the "correct" partition of $\{1,\ldots,n\}$.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Trading query complexity for sample-based testing and multi-testing scalability
We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm. The proof method involves preparing the original testing algorithm for a combinatorial analysis, which in turn involves a new result about the existence of combinatorial structures (essentially generalized sunflowers) that allow the sample-based tester to replace the original constant query complexity tester.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
On the Power of Conditional Samples in Distribution Testing
In this paper we define and examine the power of the {\em conditional-sampling} oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $μ$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $μ$, conditioned on $S$ (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals $[n]$. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample-complexity remains near-maximal even with conditional sampling.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Testing Formula Satisfaction
We study the query complexity of testing for properties defined by read once formulas, as instances of {\em massively parametrized properties}, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates, with a number of queries exponential in $ε$, doubly exponential in the arity, and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an {\em estimation} algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulas only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $ε$. On the other hand, we show that such testability results do not hold in general for formulas over non-Boolean alphabets; specifically we construct a property defined by a read-once arity $2$ (non-Boolean) formula over an alphabet of size $4$, such that any $1/4$-test for it requires a number of queries depending on the formula size. We also present such a formula over an alphabet of size $5$ that additionally satisfies a strong monotonicity condition.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Every locally characterized affine-invariant property is testable
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Some properties are not even partially testable
For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $ε$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, but can be partitioned into a small number of subsets for which they are partially testable with very few queries. We prove the existence of a property $P$ such that the only subsets $P'$ for which $P$ is $P'$-partially testable are very small. To prove this we introduce new techniques for proving property testing lower bounds. In addition to obtaining some broad-brush criteria for non-testability, this implies a lower bound on the possibility of PCPPs with a sublinear proof. This also implies lower bounds on MAPs, a notion newly defined by Gur and Rothblum. The new techniques rely on analyzing a proposed partial tester. We show that the queries performed by a tester must, with high probability, query indexes where a uniformly random member of the sub-property has low entropy. We then show how one can aggregate the "entropy loss" to deduce that a random choice in the sub-property must have low entropy, and therefore the sub-property must be small. We develop two techniques for aggregating the entropy loss. A simpler technique that applies to non-adaptive testers is based on partitioning the input bits into high query probability parts and parts where there is an entropy loss when conditioned on the high probability parts. Against adaptive testers we develop a technique based on constructing a decision tree. The root-to-leaf paths in this tree rearrange the input into parts where each exhibits entropy loss when conditioned on the path prefix. This decision tree is constructed by combining carefully selected decision trees from those used by the adaptive testing algorithm.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Testing Low Complexity Affine-Invariant Properties
Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, for instance, that the Reed-Muller code over F_p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials except that low degree is preserved by composition with affine maps. The complexity of an affine-invariant property P refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize P. A more precise statement of our main result is that for any fixed prime p >=2 and fixed integer R >= 2, any affine-invariant property P of functions f: F_p^n -> [R] is testable, assuming the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
New Results on Quantum Property Testing
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $\PP_f(j)$ of an outcome $j\in[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $ε$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $\sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $\sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Two-phase algorithms for the parametric shortest path problem
A {\em parametric weighted graph} is a graph whose edges are labeled with continuous real functions of a single common variable. For any instantiation of the variable, one obtains a standard edge-weighted graph. Parametric weighted graph problems are generalizations of weighted graph problems, and arise in various natural scenarios. Parametric weighted graph algorithms consist of two phases. A {\em preprocessing phase} whose input is a parametric weighted graph, and whose output is a data structure, the advice, that is later used by the {\em instantiation phase}, where a specific value for the variable is given. The instantiation phase outputs the solution to the (standard) weighted graph problem that arises from the instantiation. The goal is to have the running time of the instantiation phase supersede the running time of any algorithm that solves the weighted graph problem from scratch, by taking advantage of the advice. In this paper we construct several parametric algorithms for the shortest path problem. For the case of linear function weights we present an algorithm for the single source shortest path problem.
0 citations0 reviewsNo code linkedOpen access