Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications of Benjamin Rossman    :chronological  alphabetical  by type listing:

%%    
@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 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},
   url = {http://dx.doi.org/10.4171/JEMS/1133},
   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 = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Volume = {2020-November},
   Pages = {31-42},
   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 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},
   url = {http://dx.doi.org/10.1007/978-3-030-61792-9_40},
   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},
   url = {http://dx.doi.org/10.1007/978-3-030-61792-9_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ő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},
   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 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},
   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 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},
   url = {http://dx.doi.org/10.23638/LMCS-15(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 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},
   url = {http://dx.doi.org/10.1007/s00037-017-0156-0},
   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},
   url = {http://dx.doi.org/10.1137/1.9781611975031.17},
   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},
   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 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},
   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 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},
   url = {http://dx.doi.org/10.1145/3095799},
   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},
   url = {http://dx.doi.org/10.1007/s00224-016-9708-y},
   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},
   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 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},
   url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.93},
   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},
   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 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 = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Volume = {2016-December},
   Pages = {406-415},
   Year = {2016},
   Month = {December},
   ISBN = {9781509039333},
   url = {http://dx.doi.org/10.1109/FOCS.2016.51},
   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},
   url = {http://dx.doi.org/10.1145/2897518.2897637},
   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 = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Volume = {2015-December},
   Pages = {1030-1048},
   Year = {2015},
   Month = {December},
   ISBN = {9781467381918},
   url = {http://dx.doi.org/10.1109/FOCS.2015.67},
   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 = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Volume = {2015-December},
   Pages = {424-430},
   Year = {2015},
   Month = {December},
   ISBN = {9781467381918},
   url = {http://dx.doi.org/10.1109/FOCS.2015.33},
   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},
   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 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 = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Pages = {344-353},
   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 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},
   url = {http://dx.doi.org/10.1137/110839059},
   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},
   url = {http://dx.doi.org/10.1145/2591796.2591828},
   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},
   url = {http://dx.doi.org/10.1007/978-3-319-06686-8_17},
   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},
   url = {http://dx.doi.org/10.1007/978-3-642-32621-9_21},
   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},
   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
             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 = {3642150241},
   url = {http://dx.doi.org/10.1007/978-3-642-15025-8_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,
             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{fds348689,
   Author = {Rossman, B},
   Title = {The monotone complexity of k-clique on random
             graphs},
   Journal = {Annual Symposium on Foundations of Computer Science
             (Proceedings)},
   Pages = {193-201},
   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
             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},
   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
             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 = {364202260X},
   url = {http://dx.doi.org/10.1007/978-3-642-02261-6_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
             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},
   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 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},
   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 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},
   url = {http://dx.doi.org/10.1145/1374376.1374480},
   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},
   url = {http://dx.doi.org/10.2168/LMCS-3(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, 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},
   url = {http://dx.doi.org/10.2168/LMCS-3(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, 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},
   url = {http://dx.doi.org/10.2178/jsl/1185803625},
   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 = {3540734198},
   url = {http://dx.doi.org/10.1007/978-3-540-73420-8_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
             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},
   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 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},
   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 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},
   url = {http://dx.doi.org/10.1007/978-3-540-30101-1_11},
   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}
}

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320