%% Papers Published
@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},
url = {http://dx.doi.org/10.4230/LIPIcs.ITCS.2021.70},
Abstract = {We establish nearly tight bounds on the expected shrinkage
of decision lists and DNF formulas under the prandom
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/(1p)(1 1+  p p) . For example,
this bound is pDL(f) when p = √52 ≈ 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 excludedminor approximation of
treedepth},
Journal = {Journal of the European Mathematical Society},
Volume = {24},
Number = {4},
Pages = {14491470},
Year = {2021},
Month = {January},
url = {http://dx.doi.org/10.4171/JEMS/1133},
Abstract = {Treedepth is a minormonotone 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 = {Treedepth and the formula complexity of subgraph
isomorphism},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Volume = {2020November},
Pages = {3142},
Year = {2020},
Month = {November},
ISBN = {9781728196213},
url = {http://dx.doi.org/10.1109/FOCS46700.2020.00012},
Abstract = {For a fixed'pattern' graph G, the colored Gsubgraph
isomorphism problem (denoted text{SUB}(G)) asks, given an
nvertex 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
treedepth (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 sublogarithmic depth.
This complements a lower bound of Li, Razborov and Rossman
[8] relating treewidth and AC circuit size. As a corollary,
it implies a stronger homomorphism preservation theorem for
firstorder 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 excludedminor characterization of treedepth [4],
[6].) Additional results of this paper extend the pathset
framework and improve upon both, the best known upper and
lower bounds on the averagecase 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 = {504515},
Year = {2020},
Month = {January},
ISBN = {9783030617912},
url = {http://dx.doi.org/10.1007/9783030617929_40},
Abstract = {Let Q be an ideal (downwardclosed set) in the lattice of
linear subspaces of Fqn, ordered by inclusion. For 0 ⩽
k⩽ n, let μk(Q) denote the fraction of kdimensional
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/9783030617929_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 = {311322},
Year = {2020},
Month = {January},
ISBN = {9783030617912},
url = {http://dx.doi.org/10.1007/9783030617929_25},
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ősRado
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 wset system that excludes a robust
sunflower. In this paper, we use this result to obtain an
exp (n1/2o(1)) lower bound on the monotone circuit size of
an explicit nvariate monotone function, improving the
previous record exp (n1/3o(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 cliquesunflowers and use this
to prove an nΩ(k) lower bound on the monotone circuit size
of the CLIQUE function for all k≤ n1/3o(1), strengthening
the bound of Alon and Boppana[1].},
Doi = {10.1007/9783030617929_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},
url = {http://dx.doi.org/10.4230/LIPIcs.CCC.2019.1},
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 prandom restriction and DTdepth is
decisiontree depth. Criticality is a useful parameter: it
implies an O(2(1− 21λ )n) bound on the decisiontree 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 multiswitching 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
fanin. 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 depthd formula. As corollaries of
our criticality bound, we obtain an improved #SAT algorithm
and tight LinialMansourNisan 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 QBFSAT
(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 AC^{0}[⊕] formulas and
circuits},
Journal = {Theory of Computing},
Volume = {15},
Year = {2019},
Month = {January},
url = {http://dx.doi.org/10.4086/toc.2019.v015a017},
Abstract = {We give the first separation between the power of formulas
and circuits in the AC0[⊕] basis (unbounded fanin AND,
OR, NOT and MOD2 gates). We show that there exist
poly(n)size depthd circuits that are not equivalent to any
depthd 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
depthd AC0[⊕] formula of size s has a 1/4error
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 depthd 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
depthd 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 = {Subspaceinvariant AC^{0} formulas},
Journal = {Logical Methods in Computer Science},
Volume = {15},
Number = {3},
Pages = {3:13:12},
Year = {2019},
Month = {January},
url = {http://dx.doi.org/10.23638/LMCS15(3:3)2019},
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 Uinvariant if it
is fixed by this action. For example, there is a wellknown
recursive construction of depth d + 1 formulas of size
O(n·2dn1/d) computing the nvariable parity function; these
formulas are easily seen to be Pinvariant where P is the
subspace of evenweight elements of {0, 1}n. In this paper
we establish a nearly matching 2d(n1/d−1) lower bound on
the Pinvariant 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 Uinvariant and nonconstant over V,
then its Uinvariant 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/LMCS15(3:3)2019},
Key = {fds348668}
}
@article{fds348669,
Author = {Rossman, B},
Title = {The Average Sensitivity of BoundedDepth
Formulas},
Journal = {Computational Complexity},
Volume = {27},
Number = {2},
Pages = {209223},
Year = {2018},
Month = {June},
url = {http://dx.doi.org/10.1007/s0003701701560},
Abstract = {We show that unbounded fanin Boolean formulas of depth
d + 1 and size s have average sensitivity O(1dlogs)d. In
particular, this gives a tight 2Ω(d(n1/d1)) 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/s0003701701560},
Key = {fds348669}
}
@article{fds348671,
Author = {Kawarabayashi, KI and Rossman, B},
Title = {A polynomial excludedminor approximation of
treedepth},
Journal = {Proceedings of the Annual Acm Siam Symposium on Discrete
Algorithms},
Pages = {234246},
Year = {2018},
Month = {January},
ISBN = {9781611975031},
url = {http://dx.doi.org/10.1137/1.9781611975031.17},
Abstract = {Treedepth is a wellstudied 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
excludedminor 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 = {19862028},
Year = {2018},
Month = {January},
url = {http://dx.doi.org/10.1137/15M1027310},
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 boundeddepth formulas
versus circuits, since Distance k(n) Connectivity is
solvable by polynomialsize AC0circuits of depth O(log k).
For all d(n) ≤ log log log n, it follows that
polynomialsize depthd circuitswhich are a semantic
subclass of nO(d)size depthd formulasare 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 = {34433464},
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 averagecase 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},
url = {http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.27},
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 firstorder sentence φ of quantifierrank k
is preserved under homomorphisms on finite structures, then
it is equivalent on finite structures to an
existentialpositive sentence of quantifierrank kO(1).
Quantitatively, this improves the result of [39], where the
upper bound on the quantifierrank of is a nonelementary
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 averagecase depth hierarchy theorem for boolean
circuits},
Journal = {Journal of the Acm},
Volume = {64},
Number = {5},
Year = {2017},
Month = {August},
url = {http://dx.doi.org/10.1145/3095799},
Abstract = {We prove an averagecase 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 nvariable Boolean function f , computed by a
linearsize depthd 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 averagecase 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
boundeddepth 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 = {305321},
Year = {2017},
Month = {August},
url = {http://dx.doi.org/10.1007/s002240169708y},
Abstract = {We study the following informationtheoretic witness finding
problem: for a hidden nonempty subset W of {0,1}n, how many
nonadaptive 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 ValiantVazirani 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
searchtodecision reduction of BenDavid, Chor, Goldreich
and Luby [3] is optimal in a certain blackbox
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/s002240169708y},
Key = {fds348674}
}
@article{fds348675,
Author = {Rossman, B and Srinivasan, S},
Title = {Separation of AC^{0}[⊕] formulas and
circuits},
Journal = {Leibniz International Proceedings in Informatics,
Lipics},
Volume = {80},
Year = {2017},
Month = {July},
ISBN = {9783959770415},
url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.50},
Abstract = {This paper gives the first separation between the power of
formulas and circuits of equal depth in the AC0[⊕] basis
(unbounded fanin AND, OR, NOT and MOD2 gates). We show, for
all d(n) ≤ O( log n/log log n ), that there exist
polynomialsize depthd circuits that are not equivalent to
depthd 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 depthd AC0[⊕] formula of size s has a
1/8error polynomial approximation over F2 of degree O( 1/d
log s)d1. This strengthens a classic O(log s)d1 degree
approximation for circuits due to Razborov [12]. Since the
Majority function has approximate degree ⊖(√ n), this
result implies an exp(ω(dn1/2(d1))) lower bound on the
depthd 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 depthd monotone AC0 circuits
(without NOT or MOD2 gates) of size exp(O(n1/2(d1))) that
compute an Approximate Majority function. This strengthens a
construction of formulas of size exp(O(dn 1/2(d1) )) due to
Amano [1].},
Doi = {10.4230/LIPIcs.ICALP.2017.50},
Key = {fds348675}
}
@article{fds348676,
Author = {Rossman, B},
Title = {Subspaceinvariant AC^{0} formulas},
Journal = {Leibniz International Proceedings in Informatics,
Lipics},
Volume = {80},
Year = {2017},
Month = {July},
ISBN = {9783959770415},
url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.93},
Abstract = {The nvariable PARITY function is computable (by a
wellknown 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 evenweight 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/d1) lower
bound on the size of syntactically Pinvariant depth d + 1
formulas for PARITY. Quantitatively, this beats the best
2ω(d(n1/d1)) 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 AC^{0} complexity of subgraph
isomorphism},
Journal = {Siam Journal on Computing},
Volume = {46},
Number = {3},
Pages = {936971},
Year = {2017},
Month = {January},
url = {http://dx.doi.org/10.1137/14099721X},
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 AC0complexity of this problem, determined by
the smallest possible exponent C(P) for which Subgraph(P)
possesses boundeddepth 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 averagecase
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. 844856] 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.
721730] 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 linearsize 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 wellbehaved than the standard (worstcase,
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 = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Volume = {2016December},
Pages = {406415},
Year = {2016},
Month = {December},
ISBN = {9781509039333},
url = {http://dx.doi.org/10.1109/FOCS.2016.51},
Abstract = {Monotone span programs are a linearalgebraic 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 nonmonotone 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 stconnectivity function,
implying tight bounds for stconnectivity 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 = {Polylogarithmic Frege depth lower bounds via an expander
switching lemma},
Journal = {Proceedings of the Annual Acm Symposium on Theory of
Computing},
Volume = {1921June2016},
Pages = {644657},
Year = {2016},
Month = {June},
ISBN = {9781450341325},
url = {http://dx.doi.org/10.1145/2897518.2897637},
Abstract = {We show that any polynomialsize Frege refutation of a
certain linearsize unsatisfiable 3CNF 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, BenSasson
2002) which give Ω(log log n) lower bounds. The 3CNF
formulas which we use to establish this result are Tseitin
contradictions on 3regular expander graphs. In more detail,
our main result is a proof that for every d, any depthd
Frege refutation of the Tseitin contradiction over these
nnode 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 3regular nnode expander to a Tseitin
instance on a random subgraph which is a topological
embedding of a 3regular 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 AverageCase Depth Hierarchy Theorem for Boolean
Circuits},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Volume = {2015December},
Pages = {10301048},
Year = {2015},
Month = {December},
ISBN = {9781467381918},
url = {http://dx.doi.org/10.1109/FOCS.2015.67},
Abstract = {We prove an averagecase 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 nvariable Boolean function f, computed by a
linearsize depthd 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 averagecase 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 constantdepth 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 BoundedDepth
Formulas},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Volume = {2015December},
Pages = {424430},
Year = {2015},
Month = {December},
ISBN = {9781467381918},
url = {http://dx.doi.org/10.1109/FOCS.2015.33},
Abstract = {We show that unbounded fanin 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 NC^{1}},
Journal = {Leibniz International Proceedings in Informatics,
Lipics},
Volume = {33},
Pages = {392411},
Year = {2015},
Month = {June},
ISBN = {9783939897811},
url = {http://dx.doi.org/10.4230/LIPIcs.CCC.2015.392},
Abstract = {This paper gives the first correlation bounds under product
distributions, including the uniform distribution, against
the class mNC1 of polynomialsize O(log n)depth monotone
circuits. Our main theorem, proved using the pathset
complexity framework introduced in [56], shows that the
averagecase kCYCLE problem (on ErdosRé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+n1/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
nonmonotone 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 (nonmonotone) 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 AC^{0} complexity of subgraph
isomorphism},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Pages = {344353},
Year = {2014},
Month = {December},
ISBN = {9781479965175},
url = {http://dx.doi.org/10.1109/FOCS.2014.44},
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 AC0complexity of this problem, determined by
the smallest possible exponent C(P) for which SUBGRAPH(P)
possesses boundeddepth 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 averagecase 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 treewidth
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 linearsize 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 wellbehaved than the standard (worstcase,
uncolored) one.},
Doi = {10.1109/FOCS.2014.44},
Key = {fds348684}
}
@article{fds348686,
Author = {Rossman, B},
Title = {The monotone complexity of kclique on random
graphs},
Journal = {Siam Journal on Computing},
Volume = {43},
Number = {1},
Pages = {256279},
Year = {2014},
Month = {January},
url = {http://dx.doi.org/10.1137/110839059},
Abstract = {We present lower and upper bounds showing that the
averagecase complexity of the kClique 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. 721730] and
Amano [Comput. Complexity, 19 (2010), pp. 183210]. © 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 = {203212},
Year = {2014},
Month = {January},
ISBN = {9781450327107},
url = {http://dx.doi.org/10.1145/2591796.2591828},
Abstract = {We give the first superpolynomial separation in the power
of boundeddepth 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 polynomialsize 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 sizes
depthd circuits by depthd 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
boundeddepth 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 = {218231},
Year = {2014},
Month = {January},
ISBN = {9783319066851},
url = {http://dx.doi.org/10.1007/9783319066868_17},
Abstract = {We study the following informationtheoretic witness finding
problem: for a hidden nonempty subset W of {0,1} n, how many
nonadaptive 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 ValiantVazirani
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
searchtodecision reduction of BenDavid, Chor, Goldreich
and Luby [3] is optimal in a certain blackbox 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/9783319066868_17},
Key = {fds348683}
}
@article{fds348687,
Author = {Rossman, B},
Title = {A tight upper bound on the number of variables for
averagecase kclique 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 = {282290},
Year = {2012},
Month = {September},
ISBN = {9783642326202},
url = {http://dx.doi.org/10.1007/9783642326219_21},
Abstract = {A firstorder sentence φ defines kclique in the
averagecase if lim/n→∞ Pr/G=G(n,p) [G unknown sign φ
⇔ G contains a kclique] = 1 where G = G(n,p) is the
ErdosRényi random graph with p (= p(n)) the exact
threshold such that Pr[G(n,p) has a kclique] = 1/2. We are
interested in the question: How many variables are required
to define averagecase kclique in firstorder logic? Here
we consider firstorder 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 SpringerVerlag.},
Doi = {10.1007/9783642326219_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 = {10971114},
Year = {2011},
Month = {October},
url = {http://dx.doi.org/10.1016/j.ejc.2011.03.009},
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
seriesparallel. © 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 = {565580},
Year = {2010},
Month = {September},
ISBN = {3642150241},
url = {http://dx.doi.org/10.1007/9783642150258_28},
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,
isomorphisminvariance/encodingindependence 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 polynomialtime computable in
the usual sense, it is open whether conversely every
isomorphisminvariant 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
isomorphisminvariant polynomialtime 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
SpringerVerlag Berlin Heidelberg.},
Doi = {10.1007/9783642150258_28},
Key = {fds348690}
}
@article{fds348689,
Author = {Rossman, B},
Title = {The monotone complexity of kclique on random
graphs},
Journal = {Annual Symposium on Foundations of Computer Science
(Proceedings)},
Pages = {193201},
Year = {2010},
Month = {January},
ISBN = {9780769542447},
url = {http://dx.doi.org/10.1109/FOCS.2010.26},
Abstract = {It is widely suspected that Erdocombining double acute
accentsRényi random graphs are a source of hard instances
for clique problems. Giving further evidence for this
belief, we prove the first averagecase hardness result for
the kclique problem on monotone circuits. Specifically, we
show that no monotone circuit of size O(nk/4) solves the
kclique problem with high probability on G(n, p) for two
sufficiently farapart threshold functions p(n) (for
instance n2/(k1) and 2n2/(k1)). 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
quasisunflowers, a new relaxation of sunflowers in which
petals may overlap slightly on average. A "quasisunflower
lemma" (à la the Erdocombining double acute accentsRado
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},
url = {http://dx.doi.org/10.1145/1644015.1644017},
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
worstcase 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 = {EhrenfeuchtFraï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 = {350364},
Year = {2009},
Month = {August},
ISBN = {364202260X},
url = {http://dx.doi.org/10.1007/9783642022616_28},
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
EhrenfeuchtFraï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 RazborovSmolensky 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 rround
EhrenfeuchtFraï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 kclique} with p(n)∈
≪∈2/(k∈∈1) (below the kclique threshold) are
almost surely indistinguishable by variable firstorder
sentences of any fixed quantifierrank r. We describe a
winning strategy in the corresponding rround pebble game
using a technique that combines strategies from several
auxiliary games. © 2009 Springer Berlin
Heidelberg.},
Doi = {10.1007/9783642022616_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},
url = {http://dx.doi.org/10.1145/1379759.1379763},
Abstract = {The homomorphism preservation theorem (h.p.t.), a result in
classical model theory, states that a firstorder formula is
preserved under homomorphisms on all structures (finite and
infinite) if and only if it is equivalent to an
existentialpositive formula. Answering a longstanding
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 existentialpositive formulas and
unions of conjunctive queries. A further result of this
article strengthens the classical h.p.t.: we show that a
firstorder formula is preserved under homomorphisms on all
structures if and only if it is equivalent to an
existentialpositive formula of equal quantifierrank. ©
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
CaiFürerImmerman graphs},
Journal = {Annals of Pure and Applied Logic},
Volume = {152},
Number = {13},
Pages = {3150},
Year = {2008},
Month = {March},
url = {http://dx.doi.org/10.1016/j.apal.2007.11.011},
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 fixedpoint 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 constantdepth complexity of kclique},
Journal = {Proceedings of the Annual Acm Symposium on Theory of
Computing},
Pages = {721730},
Year = {2008},
Month = {January},
ISBN = {9781605580470},
url = {http://dx.doi.org/10.1145/1374376.1374480},
Abstract = {We prove a lower bound of ω(nK/4) on the size of
constantdepth circuits solving the kclique problem on
nvertex 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 sizedepth tradeoff.
Our kelique 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 constantdepth
circuits of size O(nt). Let G be an ErdösRényi random
graph with vertex set {1, . . . , n} and independent edge
probabilities na where a ≤ 1/2t1. Let A be a uniform
random kelement 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
longstanding open question in finite model theory (going
back at least to Immerman in 1982). The mvariable fragment
of firstorder logic, denoted by FOm, consists of the
firstorder 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 firstorder
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 smallstep algorithms I: Axiomatization},
Journal = {Logical Methods in Computer Science},
Volume = {3},
Number = {4},
Year = {2007},
Month = {November},
url = {http://dx.doi.org/10.2168/LMCS3(4:3)2007},
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, smallstep
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 smallstep 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/LMCS3(4:3)2007},
Key = {fds348697}
}
@article{fds348698,
Author = {Blass, A and Gurevich, Y and Rosenzweig, D and Rossman,
B},
Title = {Interactive smallstep algorithms II: Abstract state
machines and the characterization theorem},
Journal = {Logical Methods in Computer Science},
Volume = {3},
Number = {4},
Year = {2007},
Month = {November},
url = {http://dx.doi.org/10.2168/LMCS3(4:4)2007},
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, smallstep
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 smallstep 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/LMCS3(4:4)2007},
Key = {fds348698}
}
@article{fds348699,
Author = {Rossman, B},
Title = {Successorinvariant firstorder logic on finite
structures},
Journal = {Journal of Symbolic Logic},
Volume = {72},
Number = {2},
Pages = {601618},
Year = {2007},
Month = {June},
url = {http://dx.doi.org/10.2178/jsl/1185803625},
Abstract = {We consider successorinvariant firstorder 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 successorinvariant sentence Φ
has a welldefined 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 firstorder logic without a successor
relation. This extends similar results for orderinvariant
logic [8] and epsiloninvariant 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 = {146157},
Year = {2007},
Month = {January},
ISBN = {3540734198},
url = {http://dx.doi.org/10.1007/9783540734208_15},
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
worstcase 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 algorithmswhich also
includes the previous fastest algorithmsby 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. ©
SpringerVerlag Berlin Heidelberg 2007.},
Doi = {10.1007/9783540734208_15},
Key = {fds348696}
}
@article{fds348700,
Author = {Dawar, A and Richerby, D and Rossman, B},
Title = {Choiceless polynomial time, counting and the
caifürerimmerman graphs: (Extended abstract)},
Journal = {Electronic Notes in Theoretical Computer
Science},
Volume = {143},
Number = {SPEC. ISS.},
Pages = {1326},
Year = {2006},
Month = {January},
url = {http://dx.doi.org/10.1016/j.entcs.2005.05.024},
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 fixedpoint 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 = {467476},
Year = {2005},
Month = {October},
Abstract = {We prove the Finite Homomorphism Preservation Theorem: a
firstorder 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 = {370412},
Year = {2005},
Month = {October},
url = {http://dx.doi.org/10.1016/j.tcs.2005.06.017},
Abstract = {The Abstract State Machine Language, AsmL, is a novel
executable specification language based on the theory of
Abstract State Machines. AsmL is objectoriented, provides
highlevel 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 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 = {240259},
Year = {2004},
Month = {January},
url = {http://dx.doi.org/10.1007/9783540301011_11},
Abstract = {The Abstract State Machine Language, AsmL, is a novel
executable specification language based on the theory of
Abstract State Machines. AsmL is objectoriented, provides
highlevel 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. © SpringerVerlag 2004.},
Doi = {10.1007/9783540301011_11},
Key = {fds348703}
}
@article{fds348704,
Author = {Rossman, B},
Title = {Successorinvariance in the finite},
Journal = {Proceedings Symposium on Logic in Computer
Science},
Pages = {148157},
Year = {2003},
Month = {January},
Abstract = {A firstorder sentence θ of vocabulary σ {S} is
successorinvariant 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 nonfirstorder definable class of finite structures
which is, however, defined by a successorinvariant
firstorder sentence. This strengthens a corresponding
result for orderinvariance in the finite, due to Y.
Gurevich.},
Key = {fds348704}
}
