Publications of Benjamin Rossman
%% Papers Published
@article{fds370199,
Author = {Kush, D and Rossman, B},
Title = {TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH
ISOMORPHISM},
Journal = {SIAM Journal on Computing},
Volume = {52},
Number = {1},
Pages = {273-325},
Year = {2023},
Month = {January},
Abstract = {For a fixed "pattern"" graph G, the colored G-subgraph
isomorphism problem (denoted by SUB(G)) asks, given an
n-vertex graph H and a coloring V (H) → V (G), whether H
contains a properly colored copy of G. The complexity of
this problem is tied to parameterized versions of P =? NP
and L =? NL, among other questions. An overarching goal is
to understand the complexity of SUB(G), under different
computational models, in terms of natural invariants of the
pattern graph G. In this paper, we establish a close
relationship between the formula complexity of SUB(G) and an
invariant known as tree-depth (denoted by (G)). SUB(G) is
known to be solvable by monotone AC0 formulas of size O(n
(G)). Our main result is an n Ω ((G)1/3) lower bound for
formulas that are monotone or have sublogarithmic depth.
This complements a lower bound of Li, Razborov, and Rossman
[SIAM J. Comput., 46 (2017), pp. 936-971] relating
tree-width and AC0 circuit size. As a corollary, it implies
a stronger homomorphism preservation theorem for firstorder
logic on finite structures [B. Rossman, An improved
homomorphism preservation theorem from lower bounds in
circuit complexity, in 8th Innovations in Theoretical
Computer Science Conference, LIPIcs. Leibniz Int. Proc.
Inform. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern,
Germany, 2017, 27]. The technical core of this result is an
nΩ (k) lower bound in the special case where G is a
complete binary tree of height k, which we establish using
the pathset framework introduced in B. Rossman [SIAM J.
Comput., 47 (2018), pp. 1986-2028]. (The lower bound for
general patterns follows via a recent excluded-minor
characterization of tree-depth [W. Czerwiński, W. Nadara,
and M. Pilipczuk, SIAM J. Discrete Math., 35 (2021), pp.
934-947; K. Kawarabayashi and B. Rossman, A polynomial
excluded-minor approximation of treedepth, in Proceedings of
the 2018 Annual ACMSIAM Symposium on Discrete Algorithms,
2018, pp. 234-246]. Additional results of this paper extend
the pathset framework and improve upon both the best known
upper and lower bounds on the average-case formula size of
SUB(G) when G is a path.},
Doi = {10.1137/20M1372925},
Key = {fds370199}
}
@article{fds369327,
Author = {He, W and Rossman, B},
Title = {Symmetric Formulas for Products of Permutations},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {251},
Year = {2023},
Month = {January},
ISBN = {9783959772631},
Abstract = {We study the formula complexity of the word problem WordSn,k
: (0, 1)kn2 → (0, 1): given n-by-n permutation matrices
M1,..., Mk, compute the (1, 1)-entry of the matrix product
M1 · · · Mk. An important feature of this function is
that it is invariant under action of Snk−1 given by
(π1,..., πk−1)(M1,..., Mk) = (M1π1−1,
π1M2π2−1,..., πk−2Mk−1πk−−11, πk−1Mk). This
symmetry is also exhibited in the smallest known unbounded
fan-in (and, or, not)-formulas for WordSn,k, which have size
nO(log k). In this paper we prove a matching nΩ(log k)
lower bound for Snk−1-invariant formulas computing
WordSn,k. This result is motivated by the fact that a
similar lower bound for unrestricted (non-invariant)
formulas would separate complexity classes NC1 and Logspace.
Our more general main theorem gives a nearly tight
nd(k1/d−1) lower bound on the Gk−1invariant depth-d
(maj, and, or, not)-formula size of WordG,k for any finite
simple group G whose minimum permutation representation has
degree n. We also give nearly tight lower bounds on the
Gk−1-invariant depth-d (and, or, not)-formula size in the
case where G is an abelian group.},
Doi = {10.4230/LIPIcs.ITCS.2023.68},
Key = {fds369327}
}
@article{fds364199,
Author = {Cavalar, BP and Kumar, M and Rossman, B},
Title = {Monotone Circuit Lower Bounds from Robust
Sunflowers.},
Journal = {Algorithmica},
Volume = {84},
Number = {12},
Pages = {3655-3685},
Year = {2022},
Month = {January},
Abstract = {Robust sunflowers are a generalization of combinatorial
sunflowers that have applications in monotone circuit
complexity Rossman (SIAM J. Comput. 43:256-279, 2014), DNF
sparsification Gopalan et al. (Comput. Complex. 22:275-310
2013), randomness extractors Li et al. (In: APPROX-RANDOM,
LIPIcs 116:51:1-13, 2018), and recent advances on the
Erdős-Rado sunflower conjecture Alweiss et al. (In:
Proceedings of the 52nd Annual ACM SIGACT Symposium on
Theory of Computing, STOC. Association for Computing
Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf
compression to sunflower theorems via regularity, 2019) Rao
(Discrete Anal. 8,2020). The recent breakthrough of Alweiss,
Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the
52nd Annual ACM SIGACT Symposium on Theory of Computing,
STOC. Association for Computing Machinery, New York, NY,
USA, 2020) gives an improved bound on the maximum size of a
<i>w</i>-set system that excludes a robust sunflower. In
this paper, we use this result to obtain an exp ( n 1 / 2 -
o ( 1 ) ) lower bound on the monotone circuit size of an
explicit <i>n</i>-variate monotone function, improving the
previous best known exp ( n 1 / 3 - o ( 1 ) ) due to Andreev
(Algebra and Logic, 26:1-18, 1987) and Harnik and Raz (In:
Proceedings of the Thirty-Second Annual ACM Symposium on
Theory of Computing, ACM, New York, 2000). We also show an
exp ( Ω ( n ) ) lower bound on the monotone
<i>arithmetic</i> circuit size of a related polynomial via a
very simple proof. Finally, we introduce a notion of robust
clique-sunflowers and use this to prove an n Ω ( k ) lower
bound on the monotone circuit size of the CLIQUE function
for all k ⩽ n 1 / 3 - o ( 1 ) , strengthening the bound of
Alon and Boppana (Combinatorica, 7:1-22,
1987).},
Doi = {10.1007/s00453-022-01000-3},
Key = {fds364199}
}
@article{fds359224,
Author = {Rossman, B},
Title = {Shrinkage of decision lists and DNF formulas},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {185},
Year = {2021},
Month = {February},
ISBN = {9783959771771},
Abstract = {We establish nearly tight bounds on the expected shrinkage
of decision lists and DNF formulas under the p-random
restriction Rp for all values of p ∈ [0, 1]. For a
function f with domain {0, 1}n, let DL(f) denote the minimum
size of a decision list that computes f. We show that E[
DL(fRp) ] ≤ DL(f)log2/(1-p)(1 1+ - p p) . For example,
this bound is pDL(f) when p = √5-2 ≈ 0.24. For Boolean
functions f, we obtain the same shrinkage bound with respect
to DNF formula size plus 1 (i.e., replacing DL(·) with
DNF(·) + 1 on both sides of the inequality).},
Doi = {10.4230/LIPIcs.ITCS.2021.70},
Key = {fds359224}
}
@article{fds362474,
Author = {Kawarabayashi, KI and Rossman, B},
Title = {A polynomial excluded-minor approximation of
treedepth},
Journal = {Journal of the European Mathematical Society},
Volume = {24},
Number = {4},
Pages = {1449-1470},
Year = {2021},
Month = {January},
Abstract = {Treedepth is a minor-monotone graph invariant in the family
of "width measures"that includes treewidth and pathwidth.
The characterization and approximation of these invariants
in terms of excluded minors has been a topic of interest in
the study of sparse graphs. A celebrated result of Chekuri
and Chuzhoy (2014) shows that treewidth is polynomially
approximated by the largest k×k grid minor in a graph. In
this paper, we give an analogous polynomial approximation of
treedepth via three distinct obstructions: grids, balanced
binary trees, and paths. Namely, we show that there is a
constant c such that every graph with treedepth Ω(kc) has
at least one of the following minors (each of treedepth at
least k): • a k×k grid, • a complete binary tree of
height k, or • a path of order 2k. Moreover, given a graph
G we can, in randomized polynomial time, find an embedding
of one of these minors or conclude that treedepth of G is at
most O(kc). This result has applications in various settings
where bounded treedepth plays a role. In particular, we
describe one application in finite model theory, an improved
homomorphism preservation theorem over finite structures
[Rossman, 2017], which was the original motivation for our
investigation of treedepth.},
Doi = {10.4171/JEMS/1133},
Key = {fds362474}
}
@article{fds355193,
Author = {Kush, D and Rossman, B},
Title = {Tree-depth and the formula complexity of subgraph
isomorphism},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Volume = {2020-November},
Pages = {31-42},
Year = {2020},
Month = {November},
ISBN = {9781728196213},
Abstract = {For a fixed'pattern' graph G, the colored G-subgraph
isomorphism problem (denoted text{SUB}(G)) asks, given an
n-vertex graph H and a coloring V(H) rightarrow V(G),
whether H contains a properly colored copy of G. The
complexity of this problem is tied to parameterized versions
of P=? NP and L=? NL, among other questions. An overarching
goal is to understand the complexity of text{SUB}(G), under
different computational models, in terms of natural
invariants of the pattern graph G. In this paper, we
establish a close relationship between the formula
complexity of text{SUB}(G) and an invariant known as
tree-depth (denoted td (G)). text{SUB}(G) is known to be
solvable by monotone AC{0} formulas of size
O(n{text{td}(G)}). Our main result is an
n{widetilde{Omega}(text{td}(G){1/3})} lower bound for
formulas that are monotone or have sub-logarithmic depth.
This complements a lower bound of Li, Razborov and Rossman
[8] relating tree-width and AC circuit size. As a corollary,
it implies a stronger homomorphism preservation theorem for
first-order logic on finite structures [14]. The technical
core of this result is an n{Omega(k)} lower bound in the
special case where G is a complete binary tree of height k,
which we establish using the pathset framework introduced in
[15]. (The lower bound for general patterns follows via a
recent excluded-minor characterization of tree-depth [4],
[6].) Additional results of this paper extend the pathset
framework and improve upon both, the best known upper and
lower bounds on the average-case formula size of
text{SUB}(G) when G is a path.},
Doi = {10.1109/FOCS46700.2020.00012},
Key = {fds355193}
}
@article{fds354207,
Author = {Rossman, B},
Title = {Thresholds in the Lattice of Subspaces of
Fqn},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {12118 LNCS},
Pages = {504-515},
Year = {2020},
Month = {January},
ISBN = {9783030617912},
Abstract = {Let Q be an ideal (downward-closed set) in the lattice of
linear subspaces of Fqn, ordered by inclusion. For 0 ⩽
k⩽ n, let μk(Q) denote the fraction of k-dimensional
subspaces that belong to Q. We show that these densities
satisfyμk(Q)=11+z⟹μk+1(Q)⩽11+qz.This implies a sharp
threshold theorem: if μk(Q) ⩽ 1 - ε, then μℓ(Q) ⩽
ε for ℓ= k+ O(logq(1 / ε) ).},
Doi = {10.1007/978-3-030-61792-9_40},
Key = {fds354207}
}
@article{fds354208,
Author = {Cavalar, BP and Kumar, M and Rossman, B},
Title = {Monotone Circuit Lower Bounds from Robust
Sunflowers},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {12118 LNCS},
Pages = {311-322},
Year = {2020},
Month = {January},
ISBN = {9783030617912},
Abstract = {Robust sunflowers are a generalization of combinatorial
sunflowers that have applications in monotone circuit
complexity[14], DNF sparsification[6], randomness
extractors[8], and recent advances on the Erdős-Rado
sunflower conjecture[3, 9, 12]. The recent breakthrough of
Alweiss, Lovett, Wu and Zhang[3] gives an improved bound on
the maximum size of a w-set system that excludes a robust
sunflower. In this paper, we use this result to obtain an
exp (n1/2-o(1)) lower bound on the monotone circuit size of
an explicit n-variate monotone function, improving the
previous record exp (n1/3-o(1)) of Harnik and Raz[7]. We
also show an exp (Ω(n) ) lower bound on the monotone
arithmetic circuit size of a related polynomial. Finally, we
introduce a notion of robust clique-sunflowers and use this
to prove an nΩ(k) lower bound on the monotone circuit size
of the CLIQUE function for all k≤ n1/3-o(1), strengthening
the bound of Alon and Boppana[1].},
Doi = {10.1007/978-3-030-61792-9_25},
Key = {fds354208}
}
@article{fds348666,
Author = {Rossman, B},
Title = {Criticality of regular formulas},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {137},
Year = {2019},
Month = {July},
ISBN = {9783959771160},
Abstract = {We define the criticality of a boolean function f : {0, 1}n
→ {0, 1} as the minimum real number λ ≥ 1 such that P
DTdepth(fRp) ≥ t ≤ (pλ)t for all p ∈ [0, 1] and t ∈
N, where Rp is the p-random restriction and DTdepth is
decision-tree depth. Criticality is a useful parameter: it
implies an O(2(1− 21λ )n) bound on the decision-tree size
of f, as well as a 2−Ω(k/λ) bound on Fourier weight of f
on coefficients of size ≥ k. In an unpublished manuscript
[11], the author showed that a combination of Håstad’s
switching and multi-switching lemmas [5, 6] implies that AC0
circuits of depth d + 1 and size s have criticality at most
O(log s)d. In the present paper, we establish a stronger
O(d1 log s)d bound for regular formulas: the class of AC0
formulas in which all gates at any given depth have the same
fan-in. This result is based on (i) a novel switching lemma
for bounded size (unbounded width) DNF formulas, and (ii) an
extension of (i) which analyzes a canonical decision tree
associated with an entire depth-d formula. As corollaries of
our criticality bound, we obtain an improved #SAT algorithm
and tight Linial-Mansour-Nisan Theorem for regular formulas,
strengthening previous results for AC0 circuits due to
Impagliazzo, Matthews, Paturi [7] and Tal [17]. As a further
corollary, we increase from o(logloglognn ) to o(log n) the
number of quantifier alternations for which the QBF-SAT
(quantified boolean formula satisfiability) algorithm of
Santhanam and Williams [14] beats exhaustive
search.},
Doi = {10.4230/LIPIcs.CCC.2019.1},
Key = {fds348666}
}
@article{fds348667,
Author = {Rossman, B and Srinivasan, S},
Title = {Separation of AC0[⊕] formulas and
circuits},
Journal = {Theory of Computing},
Volume = {15},
Year = {2019},
Month = {January},
Abstract = {We give the first separation between the power of formulas
and circuits in the AC0[⊕] basis (unbounded fan-in AND,
OR, NOT and MOD2 gates). We show that there exist
poly(n)-size depth-d circuits that are not equivalent to any
depth-d formula of size no(d) for all d ≤
O(log(n)/loglog(n)). This result is obtained by a
combination of new lower and upper bounds for Approximate
Majorities, the class of Boolean functions {0,1}n → {0,1}
that agree with the Majority function on a 3/4 fraction of
the inputs. AC0[⊕] formula lower bound. We show that every
depth-d AC0[⊕] formula of size s has a 1/4-error
polynomial approximation over F2 of degree
O((1/d)logs)d−1. This strengthens a classic
O(logs)d−1degree approximation for circuits due to
Razborov (1987). Since any polynomial that approximates the
Majority function has degree Ω(√n), this result implies
an exp(Ω(dn1/2(d−1))) lower bound on the depth-d AC0[⊕]
formula size of all Approximate Majority functions for all d
≤ O(logn). Monotone AC0 circuit upper bound. For all d ≤
O(log(n)/loglog(n)), we give a randomized construction of
depth-d monotone AC0 circuits (without NOT or MOD2 gates) of
size exp(O(n1/2(d−1))) that compute an Approximate
Majority function. This strengthens a construction of
formulas of size exp(O(dn1/2(d−1))) due to Amano
(2009).},
Doi = {10.4086/toc.2019.v015a017},
Key = {fds348667}
}
@article{fds348668,
Author = {Rossman, B},
Title = {Subspace-invariant AC0 formulas},
Journal = {Logical Methods in Computer Science},
Volume = {15},
Number = {3},
Pages = {3:1-3:12},
Year = {2019},
Month = {January},
Abstract = {We consider the action of a linear subspace U of {0, 1}n on
the set of AC0 formulas with inputs labeled by literals in
the set (formula presented), where an element u ∈ U acts
on formulas by transposing the ith pair of literals for all
i ∈ [n] such that ui = 1. A formula is U-invariant if it
is fixed by this action. For example, there is a well-known
recursive construction of depth d + 1 formulas of size
O(n·2dn1/d) computing the n-variable parity function; these
formulas are easily seen to be P-invariant where P is the
subspace of even-weight elements of {0, 1}n. In this paper
we establish a nearly matching 2d(n1/d−1) lower bound on
the P-invariant depth d + 1 formula size of parity.
Quantitatively this improves the best known (formula
presented) lower bound for unrestricted depth d + 1 formulas
[Ros15], while avoiding the use of the switching lemma. More
generally, for any linear subspaces U ⊂ V, we show that if
a Boolean function is U-invariant and non-constant over V,
then its U-invariant depth d + 1 formula size is at least
2d(m1/d−1) where m is the minimum Hamming weight of a
vector in U⊥\V⊥.},
Doi = {10.23638/LMCS-15(3:3)2019},
Key = {fds348668}
}
@article{fds348669,
Author = {Rossman, B},
Title = {The Average Sensitivity of Bounded-Depth
Formulas},
Journal = {Computational Complexity},
Volume = {27},
Number = {2},
Pages = {209-223},
Year = {2018},
Month = {June},
Abstract = {We show that unbounded fan-in Boolean formulas of depth
d + 1 and size s have average sensitivity O(1dlogs)d. In
particular, this gives a tight 2Ω(d(n1/d-1)) lower bound on
the size of depth d + 1 formulas computing the parity
function. These results strengthen the corresponding
2Ω(n1/d) and O(log s) d bounds for circuits due to Håstad
(Proceedings of the 18th annual ACM symposium on theory of
computing, ACM, New York, 1986) and Boppana (Inf Process
Lett 63(5): 257–261, 1997). Our proof technique studies a
random process where the switching lemma is applied to
formulas in an efficient manner.},
Doi = {10.1007/s00037-017-0156-0},
Key = {fds348669}
}
@article{fds348671,
Author = {Kawarabayashi, KI and Rossman, B},
Title = {A polynomial excluded-minor approximation of
treedepth},
Journal = {Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms},
Pages = {234-246},
Year = {2018},
Month = {January},
ISBN = {9781611975031},
Abstract = {Treedepth is a well-studied graph invariant in the family of
"width measures" that includes treewidth and pathwidth.
Understanding these invariants in terms of excluded minors
has been an active area of research. The recent Grid Minor
Theorem of Chekuri and Chuzhoy [12] establishes that
treewidth is polynomially approximated by the largest k ≤k
grid minor. In this paper, we give a similar polynomial
excluded-minor approximation for treedepth in terms of three
basic obstructions: grids, tree, and paths. Specifically, we
show that there is a constant c such that every graph of
treedepth ≤ kc contains one of the following minors (each
of treedepth ≤ k): ≤ the k ≤ k grid, ≤ the complete
binary tree of height k, ≤ the path of order 2k. Let us
point out that we cannot drop any of the above graphs for
our purpose. Moreover, given a graph G we can, in randomized
polynomial time, find either an embedding of one of these
minors or conclude that treedepth of G is at most kc. This
result has potential applications in a variety of settings
where bounded treedepth plays a role. In addition to some
graph structural applications, we describe a surprising
application in circuit complexity and finite model theory
from recent work of the second author [28].},
Doi = {10.1137/1.9781611975031.17},
Key = {fds348671}
}
@article{fds348670,
Author = {Rossman, B},
Title = {Formulas versus circuits for small distance
connectivity},
Journal = {SIAM Journal on Computing},
Volume = {47},
Number = {5},
Pages = {1986-2028},
Year = {2018},
Month = {January},
Abstract = {We prove an nΩ (log k) lower bound on the AC0formula size
of Distance k(n) Connectivity for all k(n) ≤ log log n and
formulas up to depth log n/(log log n)O(1). This lower bound
strongly separates the power of bounded-depth formulas
versus circuits, since Distance k(n) Connectivity is
solvable by polynomial-size AC0circuits of depth O(log k).
For all d(n) ≤ log log log n, it follows that
polynomial-size depth-d circuits-which are a semantic
subclass of nO(d)size depth-d formulas-are not a semantic
subclass of no(d)-size formulas of much higher depth log
n/(log log n)O(1). Our lower bound technique
probabilistically associates each gate in an AC0 formula
with an object called a pathset. We show that with high
probability these random pathsets satisfy a family of
density constraints called smallness, a property akin to low
average sensitivity. We then study a complexity measure on
small pathsets, which lower bounds the AC0 formula size of
Distance k(n) Connectivity. The heart of our technique is an
nΩ (log k) lower bound on this pathset complexity
measure.},
Doi = {10.1137/15M1027310},
Key = {fds348670}
}
@article{fds350209,
Author = {Rossman, B},
Title = {Lower bounds for subgraph isomorphism},
Journal = {Proceedings of the International Congress of Mathematicians,
ICM 2018},
Volume = {4},
Pages = {3443-3464},
Year = {2018},
Month = {January},
ISBN = {9789813272934},
Abstract = {We consider the problem of determining whether an
Erdős–Rényi random graph contains a subgraph isomorphic
to a fixed pattern, such as a clique or cycle of constant
size. The computational complexity of this problem is tied
to fundamental open questions including P vs. NP and NC1 vs.
L. We give an overview of unconditional average-case lower
bounds for this problem (and its colored variant) in a few
important restricted classes of Boolean circuits.},
Key = {fds350209}
}
@article{fds348672,
Author = {Rossman, B},
Title = {An improved homomorphism preservation theorem from lower
bounds in circuit complexity},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {67},
Year = {2017},
Month = {November},
ISBN = {9783959770293},
Abstract = {Previous work of the author [39] showed that the
Homomorphism Preservation Theorem of classical model theory
remains valid when its statement is restricted to finite
structures. In this paper, we give a new proof of this
result via a reduction to lower bounds in circuit
complexity, specifically on the AC0 formula size of the
colored subgraph isomorphism problem. Formally, we show the
following: if a first-order sentence φ of quantifier-rank k
is preserved under homomorphisms on finite structures, then
it is equivalent on finite structures to an
existential-positive sentence of quantifier-rank kO(1).
Quantitatively, this improves the result of [39], where the
upper bound on the quantifier-rank of is a non-elementary
function of k.},
Doi = {10.4230/LIPIcs.ITCS.2017.27},
Key = {fds348672}
}
@article{fds348673,
Author = {Håstad, J and Rossman, B and Servedio, RA and Tan,
LY},
Title = {An average-case depth hierarchy theorem for boolean
circuits},
Journal = {Journal of the ACM},
Volume = {64},
Number = {5},
Year = {2017},
Month = {August},
Abstract = {We prove an average-case depth hierarchy theorem for Boolean
circuits over the standard basis of AND, OR, and NOT gates.
Our hierarchy theorem says that for every d ≥ 2, there is
an explicit n-variable Boolean function f , computed by a
linear-size depth-d formula,which is such that any depth-(d
- 1) circuit that agrees with f on (1/2 + on (1)) fraction
of all inputs must have size exp(nΩ(1/d) ). This answers an
open question posed by Hastad in his Ph.D. thesis (Hastad
1986b). Our average-case depth hierarchy theorem implies
that the polynomial hierarchy is infinite relative to a
random oracle with probability 1, confirming a conjecture of
Hastad (1986a), Cai (1986), and Babai (1987). We also use
our result to show that there is no "approximate converse"
to the results of Linial, Mansour, Nisan (Linial et al.
1993) and (Boppana 1997) on the total influence of
bounded-depth circuits. A key ingredient in our proof is a
notion of random projections which generalize random
restrictions.},
Doi = {10.1145/3095799},
Key = {fds348673}
}
@article{fds348674,
Author = {Kawachi, A and Rossman, B and Watanabe, O},
Title = {The Query Complexity of Witness Finding},
Journal = {Theory of Computing Systems},
Volume = {61},
Number = {2},
Pages = {305-321},
Year = {2017},
Month = {August},
Abstract = {We study the following information-theoretic witness finding
problem: for a hidden nonempty subset W of {0,1}n, how many
non-adaptive randomized queries (yes/no questions about W)
are needed to guess an element x∈{0,1}n such that x∈W
with probability >1/2? Motivated by questions in complexity
theory, we prove tight lower bounds with respect to a few
different classes of queries: •We show that the monotone
query complexity of witness finding is Ω(n2). This matches
an O(n2) upper bound from the Valiant-Vazirani Isolation
Lemma [8].•We also prove a tight Ω(n2) lower bound for
the class of NP queries (queries defined by an NP machine
with an oracle to W). This shows that the classic
search-to-decision reduction of Ben-David, Chor, Goldreich
and Luby [3] is optimal in a certain black-box
model.•Finally, we consider the setting where W is an
affine subspace of {0,1}n and prove an Ω(n2) lower bound
for the class of intersection queries (queries of the form
“W∩ S≠ ∅?” where S is a fixed subset of {0,1}n).
Along the way, we show that every monotone property defined
by an intersection query has an exponentially sharp
threshold in the lattice of affine subspaces of
{0,1}n.},
Doi = {10.1007/s00224-016-9708-y},
Key = {fds348674}
}
@article{fds348675,
Author = {Rossman, B and Srinivasan, S},
Title = {Separation of AC0[⊕] formulas and
circuits},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {80},
Year = {2017},
Month = {July},
ISBN = {9783959770415},
Abstract = {This paper gives the first separation between the power of
formulas and circuits of equal depth in the AC0[⊕] basis
(unbounded fan-in AND, OR, NOT and MOD2 gates). We show, for
all d(n) ≤ O( log n/log log n ), that there exist
polynomial-size depth-d circuits that are not equivalent to
depth-d formulas of size no(d) (moreover, this is optimal in
that no(d) cannot be improved to nO(d)). This result is
obtained by a combination of new lower and upper bounds for
Approximate Majorities, the class of Boolean functions {0,
1}n → {0, 1} that agree with the Majority function on 3/4
fraction of inputs. AC0[⊕] formula lower bound. We show
that every depth-d AC0[⊕] formula of size s has a
1/8-error polynomial approximation over F2 of degree O( 1/d
log s)d-1. This strengthens a classic O(log s)d-1 degree
approximation for circuits due to Razborov [12]. Since the
Majority function has approximate degree ⊖(√ n), this
result implies an exp(ω(dn1/2(d-1))) lower bound on the
depth-d AC0[⊕] formula size of all Approximate Majority
functions for all d(n) ≤ O(log n). Monotone AC0 circuit
upper bound. For all d(n) ≤ O( log n/log log n ), we give
a randomized construction of depth-d monotone AC0 circuits
(without NOT or MOD2 gates) of size exp(O(n1/2(d-1))) that
compute an Approximate Majority function. This strengthens a
construction of formulas of size exp(O(dn 1/2(d-1) )) due to
Amano [1].},
Doi = {10.4230/LIPIcs.ICALP.2017.50},
Key = {fds348675}
}
@article{fds348676,
Author = {Rossman, B},
Title = {Subspace-invariant AC0 formulas},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {80},
Year = {2017},
Month = {July},
ISBN = {9783959770415},
Abstract = {The n-variable PARITY function is computable (by a
well-known recursive construction) by AC0 formulas of depth
d + 1 and leafsize n·2dn1/d. These formulas are seen to
possess a certain symmetry: they are syntactically invariant
under the subspace P of even-weight elements in {0, 1}n,
which acts (as a group) on formulas by toggling negations on
input literals. In this paper, we prove a 2d(n1/d-1) lower
bound on the size of syntactically P-invariant depth d + 1
formulas for PARITY. Quantitatively, this beats the best
2ω(d(n1/d-1)) lower bound in the noninvariant setting
[16].},
Doi = {10.4230/LIPIcs.ICALP.2017.93},
Key = {fds348676}
}
@article{fds348677,
Author = {Li, Y and Razborov, A and Rossman, B},
Title = {On the AC0 complexity of subgraph
isomorphism},
Journal = {SIAM Journal on Computing},
Volume = {46},
Number = {3},
Pages = {936-971},
Year = {2017},
Month = {January},
Abstract = {Let P be a fixed graph (hereafter called a \pattern"), and
let Subgraph(P) denote the problem of deciding whether a
given graph G contains a subgraph isomorphic to P. We are
interested in AC0-complexity of this problem, determined by
the smallest possible exponent C(P) for which Subgraph(P)
possesses bounded-depth circuits of size nC(P)+o(1).
Motivated by the previous research in the area, we also
consider its \colorful" version Subgraphcol(P) in which the
target graph G is V (P)-colored, and the average-case
version Subgraphave(P) under the distribution G(n, n-θ(P)),
where θ(P) is the threshold exponent of P. Defining Ccol(P)
and Cave(P) analogously to C(P), our main contributions can
be summarized as follows: (1) Ccol(P) coincides with the
treewidth of the pattern P up to a logarithmic factor. This
shows that the previously known upper bound by Alon, Yuster,
and Zwick [J. ACM, 42 (1995), pp. 844-856] is almost tight.
(2) We give a characterization of Cave(P) in purely
combinatorial terms up to a multiplicative factor of 2. This
shows that the lower bound technique of Rossman [Proceedings
of the 40th ACM Symposium on Theory of Computing, 2008, pp.
721-730] is essentially tight for any pattern P whatsoever.
(3) We prove that if Q is a minor of P, then Subgraphcol(Q)
is reducible to Subgraphcol(P) via a linear-size monotone
projection. At the same time, we show that there is no
monotone projection whatsoever that reduces Subgraph(M3) to
Subgraph(P3+M2) (P3 is a path on three vertices, Mk is a
matching with k edges, and "+" stands for the disjoint
union). This result strongly suggests that the colorful
version of the subgraph isomorphism problem is much better
structured and well-behaved than the standard (worst-case,
uncolored) one.},
Doi = {10.1137/14099721X},
Key = {fds348677}
}
@article{fds348678,
Author = {Robere, R and Pitassi, T and Rossman, B and Cook,
SA},
Title = {Exponential Lower Bounds for Monotone Span
Programs},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Volume = {2016-December},
Pages = {406-415},
Year = {2016},
Month = {December},
ISBN = {9781509039333},
Abstract = {Monotone span programs are a linear-algebraic model of
computation which were introduced by Karchmer and Wigderson
in 1993 [1]. They are known to be equivalent to linear
secret sharing schemes, and have various applications in
complexity theory and cryptography. Lower bounds for
monotone span programs have been difficult to obtain because
they use non-monotone operations to compute monotone
functions, in fact, the best known lower bounds are
quasipolynomial for a function in (nonmonotone) P [2]. A
fundamental open problem is to prove exponential lower
bounds on monotone span program size for any explicit
function. We resolve this open problem by giving exponential
lower bounds on monotone span program size for a function in
monotone P. This also implies the first exponential lower
bounds for linear secret sharing schemes. Our result is
obtained by proving exponential lower bounds using
Razborov's rank method [3], a measure that is strong enough
to prove lower bounds for many monotone models. As
corollaries we obtain new proofs of exponential lower bounds
for monotone formula size, monotone switching network size,
and the first lower bounds for monotone comparator circuit
size for a function in monotone P. We also obtain new
polynomial degree lower bounds for Nullstellensatz
refutations using an interpolation theorem of Pudlak and
Sgall [4]. Finally, we obtain quasipolynomial lower bounds
on the rank measure for the st-connectivity function,
implying tight bounds for st-connectivity in all of the
computational models mentioned above.},
Doi = {10.1109/FOCS.2016.51},
Key = {fds348678}
}
@article{fds348679,
Author = {Pitassi, T and Rossman, B and Tan, LY and Servedio,
RA},
Title = {Poly-logarithmic Frege depth lower bounds via an expander
switching lemma},
Journal = {Proceedings of the Annual ACM Symposium on Theory of
Computing},
Volume = {19-21-June-2016},
Pages = {644-657},
Year = {2016},
Month = {June},
ISBN = {9781450341325},
Abstract = {We show that any polynomial-size Frege refutation of a
certain linear-size unsatisfiable 3-CNF formula over n
variables must have depth Ω(√logn). This is an
exponential improvement over the previous best results
(Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson
2002) which give Ω(log log n) lower bounds. The 3-CNF
formulas which we use to establish this result are Tseitin
contradictions on 3-regular expander graphs. In more detail,
our main result is a proof that for every d, any depth-d
Frege refutation of the Tseitin contradiction over these
n-node graphs must have size nΩ(logn n)/d2). A key
ingredient of our approach is a new switching lemma for a
carefully designed random restriction process over these
expanders. These random restrictions reduce a Tseitin
instance on a 3-regular n-node expander to a Tseitin
instance on a random subgraph which is a topological
embedding of a 3-regular n'-node expander, for some n' which
is not too much less than n. Our result involves Ω(√logn)
iterative applications of this type of random
restriction.},
Doi = {10.1145/2897518.2897637},
Key = {fds348679}
}
@article{fds348680,
Author = {Rossman, B and Servedio, RA and Tan, LY},
Title = {An Average-Case Depth Hierarchy Theorem for Boolean
Circuits},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Volume = {2015-December},
Pages = {1030-1048},
Year = {2015},
Month = {December},
ISBN = {9781467381918},
Abstract = {We prove an average-case depth hierarchy theorem for Boolean
circuits over the standard basis of AND, OR, and NOT gates.
Our hierarchy theorem says that for every d ≥ 2, there is
an explicit n-variable Boolean function f, computed by a
linear-size depth-d formula, which is such that any depth-(d
- 1) circuit that agrees with f on (1/2 + on(1)) fraction of
all inputs must have size exp(nΩ(1/d)). This answers an
open question posed by Has tad in his Ph.D. Thesis [Has86b].
Our average-case depth hierarchy theorem implies that the
polynomial hierarchy is infinite relative to a random oracle
with probability 1, confirming a conjecture of Has tad
[Has86a], Cai [Cai86], and Babai [Bab87]. We also use our
result to show that there is no 'approximate converse' to
the results of Linial, Mansour, Nisan [LMN93] and Boppana
[Bop97] on the total influence of constant-depth circuits,
thus answering a question posed by Kalai [Kal12] and Hatami
[Hat14]. A key ingredient in our proof is a notion of random
projections which generalize random restrictions.},
Doi = {10.1109/FOCS.2015.67},
Key = {fds348680}
}
@article{fds348681,
Author = {Rossman, B},
Title = {The Average Sensitivity of Bounded-Depth
Formulas},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Volume = {2015-December},
Pages = {424-430},
Year = {2015},
Month = {December},
ISBN = {9781467381918},
Abstract = {We show that unbounded fan-in boolean formulas of depth d +
1 and size s have average sensitivity O(log s/d)d. In
particular, this gives a tight 2Ω(d(n1/d - 1)) lower bound
on the size of depth d + 1 formulas computing the PARITY
function. These results strengthen the corresponding
O(logs)d and 2Ω(n1/d) bounds for circuits due to Boppana
(1997) and Has tad (1986). Our proof technique studies a
random process associated with formulas, in which the
Switching Lemma is efficiently applied to sub
formulas.},
Doi = {10.1109/FOCS.2015.33},
Key = {fds348681}
}
@article{fds348682,
Author = {Rossman, B},
Title = {Correlation bounds against monotone NC1},
Journal = {Leibniz International Proceedings in Informatics,
LIPIcs},
Volume = {33},
Pages = {392-411},
Year = {2015},
Month = {June},
ISBN = {9783939897811},
Abstract = {This paper gives the first correlation bounds under product
distributions, including the uniform distribution, against
the class mNC1 of polynomial-size O(log n)-depth monotone
circuits. Our main theorem, proved using the pathset
complexity framework introduced in [56], shows that the
average-case k-CYCLE problem (on Erdos-Rényi random graphs
with an appropriate edge density) is 1/2+ 1/poly(n) hard for
mNC1. Combining this result with O'Donnell's hardness
amplification theorem [43], we obtain an explicit monotone
function of n variables (in the class mSAC1) which is
1/2+n-1/2+∈ hard for mNC1 under the uniform distribution
for any desired constant ∈ > 0. This bound is nearly best
possible, since every monotone function has agreement 1/2 +
Ω(log n√n) with some function in mNC1 [44]. Our
correlation bounds against mNC1 extend smoothly to
non-monotone NC1 circuits with a bounded number of negation
gates. Using Holley's monotone coupling theorem [30], we
prove the following lemma: with respect to any product
distribution, if a balanced monotone function f is 1/2 + δ
hard for monotone circuits of a given size and depth, then f
is 1/2 + (2t+1 - 1)δ hard for (non-monotone) circuits of
the same size and depth with at most t negation gates. We
thus achieve a lower bound against NC1 circuits with (1/2 -
∈) log n negation gates, improving the previous record of
1/6 log log n [7]. Our bound on negations is "half" optimal,
since dlog(n + 1)e negation gates are known to be fully
powerful for NC1 [3, 21].},
Doi = {10.4230/LIPIcs.CCC.2015.392},
Key = {fds348682}
}
@article{fds348684,
Author = {Li, Y and Razborov, A and Rossman, B},
Title = {On the AC0 complexity of subgraph
isomorphism},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Pages = {344-353},
Year = {2014},
Month = {December},
ISBN = {9781479965175},
Abstract = {Let P be a fixed graph (hereafter called a "pattern"), and
let SUBGRAPH(P) denote the problem of deciding whether a
given graph G contains a subgraph isomorphic to P. We are
interested in AC0-complexity of this problem, determined by
the smallest possible exponent C(P) for which SUBGRAPH(P)
possesses bounded-depth circuits of size nC(P)+σ(1).
Motivated by the previous research in the area, we also
consider its "colorful" version SUBGRAPHcol(P) in which the
target graph G is V(P)-colored, and the average-case version
SUBGRAPHave(P) under the distribution G(n, n θ(P)), where
è(P) is the threshold exponent of P. Defining Ccol(P) and
Cave(P) analogously to C(P), our main contributions can be
summarized as follows. Ccol(P) coincides with the tree-width
of the pattern P within a logarithmic factor. This shows
that the previously known upper bound by Alon, Yuster, Zwick
[3] is almost tight. We give a characterization of Cave(P)
in purely combinatorial terms within a multiplicative factor
of 2. This shows that the lower bound technique of Rossman
[21] is essentially tight, for any pattern P whatsoever. We
prove that if Q is a minor of P then SUBGRAPHcol(Q) is
reducible to SUBGRAPHcol(P) via a linear-size monotone
projection. At the same time, we show that there is no
monotone projection whatsoever that reduces SUBGRAPH(M3) to
SUBGRAPH(P3 +M2) (P3 is a path on 3 vertices, Mk is a
matching with k edges, and "+" stands for the disjoint
union). This result strongly suggests that the colorful
version of the subgraph isomorphism problem is much better
structured and well-behaved than the standard (worstcase,
uncolored) one.},
Doi = {10.1109/FOCS.2014.44},
Key = {fds348684}
}
@article{fds348686,
Author = {Rossman, B},
Title = {The monotone complexity of k-clique on random
graphs},
Journal = {SIAM Journal on Computing},
Volume = {43},
Number = {1},
Pages = {256-279},
Year = {2014},
Month = {January},
Abstract = {We present lower and upper bounds showing that the
average-case complexity of the k-Clique problem on monotone
circuits is nk/4+O(1). Similar bounds for AC0 circuits were
shown in Rossman [Proceedings of the 40th Annual ACM
Symposium on Theory of Computing, 2008, pp. 721-730] and
Amano [Comput. Complexity, 19 (2010), pp. 183-210]. © by
SIAM.},
Doi = {10.1137/110839059},
Key = {fds348686}
}
@article{fds348685,
Author = {Rossman, B},
Title = {Formulas vs. circuits for small distance
connectivity},
Journal = {Proceedings of the Annual ACM Symposium on Theory of
Computing},
Pages = {203-212},
Year = {2014},
Month = {January},
ISBN = {9781450327107},
Abstract = {We give the first super-polynomial separation in the power
of bounded-depth boolean formulas vs. circuits.
Specifically, we consider the problem Distance κ (n)
Connectivity, which asks whether two specified nodes in a
graph of size n are connected by a path of length at most
κ(n). This problem is solvable (by the recursive doubling
technique) on circuits of depth O(log κ) and size O(κn3).
In contrast, we show that solving this problem on formulas
of depth log n/(log log n)O(1) requires size nΩ(log κ) for
all κ (n) ≤ log log n. As corollaries: (i) It follows
that polynomial-size circuits for Distance κ (n)
Connectivity require depth Ω(log κ) for all κ (n) ≤ log
log n. This matches the upper bound from recursive doubling
and improves a previous Ω(log log κ) lower bound of Beame,
Impagliazzo and Pitassi [BIP98]. (ii) We get a tight lower
bound of sΩ(d) on the size required to simulate size-s
depth-d circuits by depth-d formulas for all s(n) = nO(1)
and d(n) ≤ log log log n. No lower bound better than s(1)
was previously known for any d(n) ≰ O(1). Our proof
technique is centered on a new notion of pathset complexity,
which roughly speaking measures the minimum cost of
constructing a set of (partial) paths in a universe of size
n via the operations of union and relational join, subject
to certain density constraints. Half of our proof shows that
bounded-depth formulas solving Distance κ(n) Connectivity
imply upper bounds on pathset complexity. The other half is
a combinatorial lower bound on pathset complexity. © 2014
ACM.},
Doi = {10.1145/2591796.2591828},
Key = {fds348685}
}
@article{fds348683,
Author = {Kawachi, A and Rossman, B and Watanabe, O},
Title = {The query complexity of witness finding},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {8476 LNCS},
Pages = {218-231},
Year = {2014},
Month = {January},
ISBN = {9783319066851},
Abstract = {We study the following information-theoretic witness finding
problem: for a hidden nonempty subset W of {0,1} n, how many
non-adaptive randomized queries (yes/no questions about W)
are needed to guess an element x∈ {0,1} n such that x∈ W
with probability >∈1/2? Motivated by questions in
complexity theory, we prove tight lower bounds with respect
to a few different classes of queries: We show that the
monotone query complexity of witness finding is Ω(n 2).
This matches an O(n 2) upper bound from the Valiant-Vazirani
Isolation Lemma [8]. We also prove a tight Ω(n 2) lower
bound for the class of NP queries (queries defined by an NP
machine with an oracle to W). This shows that the classic
search-to-decision reduction of Ben-David, Chor, Goldreich
and Luby [3] is optimal in a certain black-box model.
Finally, we consider the setting where W is an affine
subspace of {0,1} n and prove an Ω(n 2) lower bound for the
class of intersection queries (queries of the form
"W∈∈S∈∈ ?" where S is a fixed subset of {0,1} n ).
Along the way, we show that every monotone property defined
by an intersection query has an exponentially sharp
threshold in the lattice of affine subspaces of {0,1} n . ©
2014 Springer International Publishing Switzerland.},
Doi = {10.1007/978-3-319-06686-8_17},
Key = {fds348683}
}
@article{fds348687,
Author = {Rossman, B},
Title = {A tight upper bound on the number of variables for
average-case k-clique on ordered graphs},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {7456 LNCS},
Pages = {282-290},
Year = {2012},
Month = {September},
ISBN = {9783642326202},
Abstract = {A first-order sentence φ defines k-clique in the
average-case if lim/n→∞ Pr/G=G(n,p) [G unknown sign φ
⇔ G contains a k-clique] = 1 where G = G(n,p) is the
Erdos-Rényi random graph with p (= p(n)) the exact
threshold such that Pr[G(n,p) has a k-clique] = 1/2. We are
interested in the question: How many variables are required
to define average-case k-clique in first-order logic? Here
we consider first-order logic in vocabularies which, in
addition to the adjacency relation of G, may include fixed
"background" relations on the vertex set {1,...,n} (for
example, linear order). Some previous results on this
question: - With no background relations, k/2 variables are
necessary and k/2+ O(1) variables are sufficient (Ch. 6 of
[7]). - With arbitrary background relations, k/4 variables
are necessary [6]. - With arithmetic background relations
(<, +, x), k/4+O(1) variables are sufficient (Amano [1]). In
this paper, we tie up a loose end (matching the lower bound
of [6] and improving the upper bound of [1]) by showing that
k/4+O(1) variables are sufficient with only a linear order
in the background. © 2012 Springer-Verlag.},
Doi = {10.1007/978-3-642-32621-9_21},
Key = {fds348687}
}
@article{fds348688,
Author = {Kopparty, S and Rossman, B},
Title = {The homomorphism domination exponent},
Journal = {European Journal of Combinatorics},
Volume = {32},
Number = {7},
Pages = {1097-1114},
Year = {2011},
Month = {October},
Abstract = {We initiate a study of the homomorphism domination exponent
of a pair of graphs F and G, defined as the maximum real
number c such that |Hom(F,T)|≥|Hom(G,T)|c for every graph
T. The problem of determining whether HDE(F,G)≥1 is known
as the homomorphism domination problem, and its decidability
is an important open question arising in the theory of
relational databases. We investigate the combinatorial and
computational properties of the homomorphism domination
exponent, proving upper and lower bounds and isolating
classes of graphs F and G for which HDE(F,G) is computable.
In particular, we present a linear program computing
HDE(F,G) in the special case, where F is chordal and G is
series-parallel. © 2011 Elsevier Ltd.},
Doi = {10.1016/j.ejc.2011.03.009},
Key = {fds348688}
}
@article{fds348690,
Author = {Rossman, B},
Title = {Choiceless computation and symmetry},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {6300 LNCS},
Pages = {565-580},
Year = {2010},
Month = {September},
ISBN = {9783642150241},
Abstract = {Many natural problems in computer science concern structures
like graphs where elements are not inherently ordered. In
contrast, Turing machines and other common models of
computation operate on strings. While graphs may be encoded
as strings (via an adjacency matrix), the encoding imposes a
linear order on vertices. This enables a Turing machine
operating on encodings of graphs to choose an arbitrary
element from any nonempty set of vertices at low cost (the
Augmenting Paths algorithm for Bipartite Matching being an
example of the power of choice). However, the outcome of a
computation is liable to depend on the external linear order
(i.e., the choice of encoding). Moreover,
isomorphism-invariance/encoding-independence is an
undecidable property of Turing machines. This trouble with
encodings led Blass, Gurevich and Shelah [3] to propose a
model of computation known as BGS machines that operate
directly on structures. BGS machines preserve symmetry at
every step in a computation, sacrificing the ability to make
arbitrary choices between indistinguishable elements of the
input structure (hence "choiceless computation"). Blass et
al. also introduced a complexity class CPT+C (Choiceless
Polynomial Time with Counting) defined in terms of
polynomially bounded BGS machines. While every property
finite structures in CPT+C is polynomial-time computable in
the usual sense, it is open whether conversely every
isomorphism-invariant property in P belongs to CPT+C. In
this paper we give evidence that CPT+C P by proving the
separation of the corresponding classes of function
problems. Specifically, we show that there is an
isomorphism-invariant polynomial-time computable function
problem on finite vector spaces ("given a finite vector
space V, output the set of hyperplanes in V") that is not
computable by any CPT+C program. In addition, we give a new
simplified proof of the Support Theorem, which is a key step
in the result of [3] that a weak version of CPT+C absent
counting cannot decide the parity of sets. © 2010
Springer-Verlag Berlin Heidelberg.},
Doi = {10.1007/978-3-642-15025-8_28},
Key = {fds348690}
}
@article{fds373986,
Author = {Rossman, B and Schwentick, T and Thérien, D and Vollmer,
H},
Title = {Circuits, Logic, and Games},
Journal = {Dagstuhl Seminar Proceedings},
Volume = {10061},
Year = {2010},
Month = {January},
Key = {fds373986}
}
@article{fds348689,
Author = {Rossman, B},
Title = {The monotone complexity of k-clique on random
graphs},
Journal = {Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, FOCS},
Pages = {193-201},
Year = {2010},
Month = {January},
ISBN = {9780769542447},
Abstract = {It is widely suspected that Erdocombining double acute
accents-Rényi random graphs are a source of hard instances
for clique problems. Giving further evidence for this
belief, we prove the first average-case hardness result for
the k-clique problem on monotone circuits. Specifically, we
show that no monotone circuit of size O(nk/4) solves the
k-clique problem with high probability on G(n, p) for two
sufficiently far-apart threshold functions p(n) (for
instance n-2/(k-1) and 2n-2/(k-1)). Moreover, the exponent
k/4 in this result is tight up to an additive constant. One
technical contribution of this paper is the introduction of
quasi-sunflowers, a new relaxation of sunflowers in which
petals may overlap slightly on average. A "quasi-sunflower
lemma" (à la the Erdocombining double acute accents-Rado
sunflower lemma) leads to our novel lower bounds within
Razborov's method of approximations. © 2010
IEEE.},
Doi = {10.1109/FOCS.2010.26},
Key = {fds348689}
}
@article{fds348691,
Author = {Demaine, ED and Mozes, S and Rossman, B and Weimann,
O},
Title = {An optimal decomposition algorithm for tree edit
distance},
Journal = {ACM Transactions on Algorithms},
Volume = {6},
Number = {1},
Year = {2009},
Month = {December},
Abstract = {The edit distance between two ordered rooted trees with
vertex labels is the minimum cost of transforming one tree
into the other by a sequence of elementary operations
consisting of deleting and relabeling existing nodes, as
well as inserting new nodes. In this article, we present a
worst-case O(n 3)-time algorithm for the problem when the
two trees have size n, improving the previous best O(n3 log
n)-time algorithm. Our result requires a novel adaptive
strategy for deciding how a dynamic program divides into
subproblems, together with a deeper understanding of the
previous algorithms for the problem. We prove the optimality
of our algorithm among the family of decomposition strategy
algorithmswhich also includes the previous fastest
algorithmsby tightening the known lower bound of ω(n2 log2
n) to ω(n3), matching our algorithm's running time.
Furthermore, we obtain matching upper and lower bounds for
decomposition strategy algorithms of Θ(nm2 (1 + log n/m))
when the two trees have sizes m and n and m < n. © 2009
ACM.},
Doi = {10.1145/1644015.1644017},
Key = {fds348691}
}
@article{fds348692,
Author = {Rossman, B},
Title = {Ehrenfeucht-Fraïssé Games on Random Structures},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {5514 LNAI},
Pages = {350-364},
Year = {2009},
Month = {August},
ISBN = {9783642022609},
Abstract = {Certain results in circuit complexity (e.g., the theorem
that AC 0 functions have low average sensitivity) [5, 17]
imply the existence of winning strategies in
Ehrenfeucht-Fraïssé games on pairs of random structures
(e.g., ordered random graphs G∈=∈G(n,1/2) and G
∈+∈∈=∈G∈ ∪∈{random edge}). Standard
probabilistic methods in circuit complexity (e.g., the
Switching Lemma [11] or Razborov-Smolensky Method [19, 21]),
however, give no information about how a winning strategy
might look. In this paper, we attempt to identify specific
winning strategies in these games (as explicitly as
possible). For random structures G and G ∈+∈, we prove
that the composition of minimal strategies in r-round
Ehrenfeucht-Fraïssé games and is almost surely a winning
strategy in the game . We also examine a result of [20] that
ordered random graphs H∈=∈G(n,p) and H
∈+∈∈=∈H∈ ∪∈{random k-clique} with p(n)∈
≪-∈2/(k∈-∈1) (below the k-clique threshold) are
almost surely indistinguishable by -variable first-order
sentences of any fixed quantifier-rank r. We describe a
winning strategy in the corresponding r-round -pebble game
using a technique that combines strategies from several
auxiliary games. © 2009 Springer Berlin
Heidelberg.},
Doi = {10.1007/978-3-642-02261-6_28},
Key = {fds348692}
}
@article{fds348694,
Author = {Rossman, B},
Title = {Homomorphism preservation theorems},
Journal = {Journal of the ACM},
Volume = {55},
Number = {3},
Year = {2008},
Month = {July},
Abstract = {The homomorphism preservation theorem (h.p.t.), a result in
classical model theory, states that a first-order formula is
preserved under homomorphisms on all structures (finite and
infinite) if and only if it is equivalent to an
existential-positive formula. Answering a long-standing
question in finite model theory, we prove that the h.p.t.
remains valid when restricted to finite structures (unlike
many other classical preservation theorems, including the o
- Tarski theorem and Lyndon's positivity theorem).
Applications of this result extend to constraint
satisfaction problems and to database theory via a
correspondence between existential-positive formulas and
unions of conjunctive queries. A further result of this
article strengthens the classical h.p.t.: we show that a
first-order formula is preserved under homomorphisms on all
structures if and only if it is equivalent to an
existential-positive formula of equal quantifier-rank. ©
2008 ACM.},
Doi = {10.1145/1379759.1379763},
Key = {fds348694}
}
@article{fds348695,
Author = {Dawar, A and Richerby, D and Rossman, B},
Title = {Choiceless polynomial time, counting and the
Cai-Fürer-Immerman graphs},
Journal = {Annals of Pure and Applied Logic},
Volume = {152},
Number = {1-3},
Pages = {31-50},
Year = {2008},
Month = {March},
Abstract = {We consider Choiceless Polynomial Time (over(C, ̃) PT), a
language introduced by Blass, Gurevich and Shelah, and show
that it can express a query originally constructed by Cai,
Fürer and Immerman to separate fixed-point logic with
counting (IFP + C) from P. This settles a question posed by
Blass et al. The program we present uses sets of unbounded
finite rank: we demonstrate that this is necessary by
showing that the query cannot be computed by any program
that has a constant bound on the rank of sets used, even in
over(C, ̃) PT(Card), an extension of over(C, ̃) PT with
counting. © 2007 Elsevier B.V. All rights
reserved.},
Doi = {10.1016/j.apal.2007.11.011},
Key = {fds348695}
}
@article{fds348693,
Author = {Rossman, B},
Title = {On the constant-depth complexity of k-clique},
Journal = {Proceedings of the Annual ACM Symposium on Theory of
Computing},
Pages = {721-730},
Year = {2008},
Month = {January},
ISBN = {9781605580470},
Abstract = {We prove a lower bound of ω(nK/4) on the size of
constant-depth circuits solving the k-clique problem on
n-vertex graphs (for every constant k). This improves a
lower bound of ω(nk/59d2) due to Beame where d is the
circuit depth. Our lower bound has the advantage that it
does not depend on the constant d in the exponent of n, thus
breaking the mold of the traditional size-depth tradeoff.
Our k-elique lower bound derives from a stronger result of
independent interest. Suppose fn : {0, l} n(n/2)→ {0, l}
is a sequence of functions computed by constant-depth
circuits of size O(nt). Let G be an Erdös-Rényi random
graph with vertex set {1, . . . , n} and independent edge
probabilities n-a where a ≤ 1/2t-1. Let A be a uniform
random k-element subset of {1, . . . , n} (where k is any
constant independent of n) and let KA denote the clique
supported on A. We prove that fn(G) = fn(G U KA)
asymptotically almost surely. These results resolve a
long-standing open question in finite model theory (going
back at least to Immerman in 1982). The m-variable fragment
of first-order logic, denoted by FOm, consists of the
first-order sentences which involve at most m variables. Our
results imply that the bounded variable hierarchy FO1 ⊂
FO2 ⊂ . . . ⊂ FO m ⊂ . . . is strict in terms of
expressive power on finite ordered graphs. It was previously
unknown that FO3 is less expressive than full first-order
logic on finite ordered graphs. © Copyright 2008
ACM.},
Doi = {10.1145/1374376.1374480},
Key = {fds348693}
}
@article{fds348697,
Author = {Blass, A and Gurevich, Y and Rosenzweig, D and Rossman,
B},
Title = {Interactive small-step algorithms I: Axiomatization},
Journal = {Logical Methods in Computer Science},
Volume = {3},
Number = {4},
Year = {2007},
Month = {November},
Abstract = {In earlier work, the Abstract State Machine Thesis — that
arbitrary algorithms are behaviorally equivalent to abstract
state machines — was established for several classes of
algorithms, including ordinary, interactive, small-step
algorithms. This was accomplished on the basis of
axiomatizations of these classes of algorithms. Here we
extend the axiomatization and, in a companion paper, the
proof, to cover interactive small-step algorithms that are
not necessarily ordinary. This means that the algorithms (1)
can complete a step without necessarily waiting for replies
to all queries from that step and (2) can use not only the
environment’s replies but also the order in which the
replies were received.},
Doi = {10.2168/LMCS-3(4:3)2007},
Key = {fds348697}
}
@article{fds348698,
Author = {Blass, A and Gurevich, Y and Rosenzweig, D and Rossman,
B},
Title = {Interactive small-step algorithms II: Abstract state
machines and the characterization theorem},
Journal = {Logical Methods in Computer Science},
Volume = {3},
Number = {4},
Year = {2007},
Month = {November},
Abstract = {In earlier work, the Abstract State Machine Thesis — that
arbitrary algorithms are behaviorally equivalent to abstract
state machines — was established for several classes of
algorithms, including ordinary, interactive, small-step
algorithms. This was accomplished on the basis of
axiomatizations of these classes of algorithms. In a
companion paper [5] the axiomatisation was extended to cover
interactive small-step algorithms that are not necessarily
ordinary. This means that the algorithms (1) can complete a
step without necessarily waiting for replies to all queries
from that step and (2) can use not only the environment’s
replies but also the order in which the replies were
received. In order to prove the thesis for algorithms of
this generality, we extend here the definition of abstract
state machines to incorporate explicit attention to the
relative timing of replies and to the possible absence of
replies. We prove the characterization theorem for extended
ASMs with respect to general algorithms as axiomatised in
[5].},
Doi = {10.2168/LMCS-3(4:4)2007},
Key = {fds348698}
}
@article{fds348699,
Author = {Rossman, B},
Title = {Successor-invariant first-order logic on finite
structures},
Journal = {Journal of Symbolic Logic},
Volume = {72},
Number = {2},
Pages = {601-618},
Year = {2007},
Month = {June},
Abstract = {We consider successor-invariant first-order logic (FO +
succ) inv, consisting of sentences Φ involving an
"auxiliary" binary relation S such that (Θ, S1) |= Φ ⇔
(Θ, S2) |= Φ for all finite structures Θ and successor
relations S1, S2 on Θ. A successor-invariant sentence Φ
has a well-defined semantics on finite structures Θ with no
given successor relation: one simply evaluates Φ on (Θ, S)
for an arbitrary choice of successor relation S. In this
article, we prove that (FO + succ)inv is more expressive on
finite structures than first-order logic without a successor
relation. This extends similar results for order-invariant
logic [8] and epsilon-invariant logic [10]. © 2007,
Association for Symbolic Logic.},
Doi = {10.2178/jsl/1185803625},
Key = {fds348699}
}
@article{fds348696,
Author = {Demaine, ED and Mozes, S and Rossman, B and Weimann,
O},
Title = {An optimal decomposition algorithm for tree edit
distance},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {4596 LNCS},
Pages = {146-157},
Year = {2007},
Month = {January},
ISBN = {9783540734192},
Abstract = {The edit distance between two ordered rooted trees with
vertex labels is the minimum cost of transforming one tree
into the other by a sequence of elementary operations
consisting of deleting and relabeling existing nodes, as
well as inserting new nodes. In this paper, we present a
worst-case O(n 3)-time algorithm for this problem, improving
the previous best O(n3 log n)-time algorithm [7]. Our result
requires a novel adaptive strategy for deciding how a
dynamic program divides into subproblems, together with a
deeper understanding of the previous algorithms for the
problem. We prove the optimality of our algorithm among the
family of decomposition strategy algorithms-which also
includes the previous fastest algorithms-by tightening the
known lower bound of Q(n2 log2 n) [4] to Ωn 3), matching
our algorithm's running time. Furthermore, we obtain
matching upper and lower bounds of ⊖(nm2(1 + log m/n))
when the two trees have sizes m and n where m < n. ©
Springer-Verlag Berlin Heidelberg 2007.},
Doi = {10.1007/978-3-540-73420-8_15},
Key = {fds348696}
}
@article{fds348700,
Author = {Dawar, A and Richerby, D and Rossman, B},
Title = {Choiceless polynomial time, counting and the
cai-fürer-immerman graphs: (Extended abstract)},
Journal = {Electronic Notes in Theoretical Computer
Science},
Volume = {143},
Number = {SPEC. ISS.},
Pages = {13-26},
Year = {2006},
Month = {January},
Abstract = {We consider Choiceless Polynomial Time (C̃PT), a language
introduced by Blass, Gurevich and Shelah, and show that it
can express a query originally constructed by Cai, Fürer
and Immerman to separate fixed-point logic with counting
(IFP + C) from P. This settles a question posed by Blass et
al. The program we present uses sets of unbounded finite
rank: we demonstrate that this is necessary by showing that
the query cannot be computed by any program that has a
constant bound on the rank of sets used, even in
C̃PT(Card), an extension of C̃PT with counting. © 2005
Elsevier B.V. All rights reserved.},
Doi = {10.1016/j.entcs.2005.05.024},
Key = {fds348700}
}
@article{fds348701,
Author = {Rossman, B},
Title = {Existential positive types and preservation under
homomorphisms},
Journal = {Proceedings - Symposium on Logic in Computer
Science},
Pages = {467-476},
Year = {2005},
Month = {October},
Abstract = {We prove the Finite Homomorphism Preservation Theorem: a
first-order formula is preserved under homomorphisms on
finite structures iff it is equivalent in the finite to an
existential positive formula. We also strengthen the
classical homomorphism preservation theorem by showing that
a formula is preserved under homomorphisms on all structures
iff it is equivalent to an existential positive formula of
the same quantifier rank. Our method involves analysis of
existential positive types and a new notion of existential
positive saturation. © 2005 IEEE.},
Key = {fds348701}
}
@article{fds348702,
Author = {Gurevich, Y and Rossman, B and Schulte, W},
Title = {Semantic essence of AsmL},
Journal = {Theoretical Computer Science},
Volume = {343},
Number = {3},
Pages = {370-412},
Year = {2005},
Month = {October},
Abstract = {The Abstract State Machine Language, AsmL, is a novel
executable specification language based on the theory of
Abstract State Machines. AsmL is object-oriented, provides
high-level mathematical data-structures, and is built around
the notion of synchronous updates and finite choice. AsmL is
fully integrated into the .NET framework and Microsoft
development tools. In this paper, we explain the design
rationale of AsmL and provide static and dynamic semantics
for a kernel of the language. © 2005 Elsevier B.V. All
rights reserved.},
Doi = {10.1016/j.tcs.2005.06.017},
Key = {fds348702}
}
@article{fds348703,
Author = {Gurevich, Y and Rossman, B and Schulte, W},
Title = {Semantic essence of asml: Extended abstract},
Journal = {Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics)},
Volume = {3188},
Pages = {240-259},
Year = {2004},
Month = {January},
Abstract = {The Abstract State Machine Language, AsmL, is a novel
executable specification language based on the theory of
Abstract State Machines. AsmL is object-oriented, provides
high-level mathematical datastructures, and is built around
the notion of synchronous updates and finite choice. AsmL is
fully integrated into the .NET framework and Microsoft
development tools. In this paper, we explain the design
rationale of AsmL and sketch semantics for a kernel of the
language. The details will appear in the full version of the
paper. © Springer-Verlag 2004.},
Doi = {10.1007/978-3-540-30101-1_11},
Key = {fds348703}
}
@article{fds348704,
Author = {Rossman, B},
Title = {Successor-invariance in the finite},
Journal = {Proceedings - Symposium on Logic in Computer
Science},
Pages = {148-157},
Year = {2003},
Month = {January},
Abstract = {A first-order sentence θ of vocabulary σ {S} is
successor-invariant in the finite if for every finite
σ-structure M and successor relations S1 and S2 on M, (M,
S1) |= θ ⇔ (M, S2) |= θ. In this paper I give an example
of a non-first-order definable class of finite structures
which is, however, defined by a successor-invariant
first-order sentence. This strengthens a corresponding
result for order-invariance in the finite, due to Y.
Gurevich.},
Key = {fds348704}
}