In this paper, we study corners in tree‐like and permutation tableaux. Tree‐like tableaux are in bijection with other combinatorial structures, including permutation tableaux, and have a connection to the partially asymmetric simple exclusion process (PASEP), an important model of an interacting particles system. In particular, in the context of tree‐like tableaux, a corner corresponds to a node occupied by a particle that could jump to the right while inner corners indicate a particle with an empty node to its left. Thus, the total number of corners represents the number of nodes at which PASEP can move, that is, the total current activity of the system. As the number of inner corners and regular corners is connected, we limit our discussion to just regular corners and show that asymptotically, the number of corners in a tableau of length
 NSFPAR ID:
 10260111
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 57
 Issue:
 4
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 12481271
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Waves of misery is a phenomenon where spikes of many node splits occur over short periods of time in tree indexes. Waves of misery negatively affect the performance of tree indexes in insertionheavy workloads. Waves of misery have been first observed in the context of the Btree, where these waves cause unpredictable index performance. In particular, the performance of search and indexupdate operations deteriorate when a wave of misery takes place, but is more predictable between the waves. This paper investigates the presence or lack of waves of misery in several Rtree variants, and studies the extent of which these waves impact the performance of each variant. Interestingly, although having poorer query performance, the Linear and Quadratic Rtrees are found to be more resilient to waves of misery than both the Hilbert and R*trees. This paper presents several techniques to reduce the impact in performance of the waves of misery for the Hilbert and R*trees. One way to eliminate waves of misery is to force node splits to take place at regular times before nodes become full to achieve deterministic performance. The other way is that upon splitting a node, do not split it evenly but rather at different node utilization factors. This allows leaf nodes not to fill at the same pace. We study the impact of two new techniques to mitigate waves of misery after the tree index has been constructed, namely Regular Elective Splits (RES, for short) and Unequal Random Splits (URS, for short). Our experimental investigation highlights the tradeoffs in performance of the introduced techniques and the pros and cons of each technique. 
We give new upper and lower bounds on the power of several restricted classes of arbitraryorder readonce branching programs (ROBPs) and standardorder ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for spacebounded computation.  Regular SOBPs of length n and width ⌊w(n+1)/2⌋ can exactly simulate general SOBPs of length n and width w, and moreover an n/2o(n) blowup in width is necessary for such a simulation. Our result extends and simplifies prior averagecase simulations (Reingold, Trevisan, and Vadhan (STOC 2006), Bogdanov, Hoza, Prakriya, and Pyne (CCC 2022)), in particular implying that weighted pseudorandom generators (Braverman, Cohen, and Garg (SICOMP 2020)) for regular SOBPs of width poly(n) or larger automatically extend to general SOBPs. Furthermore, our simulation also extends to general (even readmany) oblivious branching programs.  There exist natural functions computable by regular SOBPs of constant width that are averagecase hard for permutation SOBPs of exponential width. Indeed, we show that InnerProduct mod 2 is averagecase hard for arbitraryorder permutation ROBPs of exponential width.  There exist functions computable by constantwidth arbitraryorder permutation ROBPs that are worstcase hard for exponentialwidth SOBPs.  Readtwice permutation branching programs of subexponential width can simulate polynomialwidth arbitraryorder ROBPs.more » « less

The notion of comparison between system runs is fundamental in formal verification. This concept is implicitly present in the verification of qualitative systems, and is more pronounced in the verification of quantitative systems. In this work, we identify a novel mode of comparison in quantitative systems: the online comparison of the aggregate values of two sequences of quantitative weights. This notion is embodied by comparator automata (comparators, in short), a new class of automata that read two infinite sequences of weights synchronously and relate their aggregate values. Weshowthat aggregate functions that can be represented with B¨uchi automaton result in comparators that are finitestate and accept by the B¨uchi condition as well. Such ωregular comparators further lead to generic algorithms for a number of wellstudied problems, including the quantitative inclusion and winning strategies in quantitative graph games with incomplete information, as well as related nondecision problems, such as obtaining a f inite representation of all counterexamples in the quantitative inclusion problem. We study comparators for two aggregate functions: discountedsum and limitaverage. We prove that the discountedsum comparator is ωregular iff the discountfactor is an integer. Not every aggregate function, however, has an ωregular comparator. Specifically, we show that the language of sequencepairs for which limitaverage aggregates exist is neither ωregular nor ωcontextfree. Given this result, we introduce the notion of prefixaverage as a relaxation of limitaverage aggregation, and show that it admits ωcontextfree comparators i.e. comparator automata expressed by B¨uchi pushdown automata.more » « less

For each fully commutative permutation, we construct a “boolean core,” which is the maximal boolean permutation in its principal order ideal under the right weak order. We partition the set of fully commutative permutations into the recently defined crowded and uncrowded elements, distinguished by whether or not their RSK insertion tableaux satisfy a sparsity condition. We show that a fully commutative element is uncrowded exactly when it shares the RSK insertion tableau with its boolean core. We present the dynamics of the right weak order on fully commutative permutations, with particular interest in when they change from uncrowded to crowded. In particular, we use consecutive permutation patterns and descents to characterize the minimal crowded elements under the right weak order.

null (Ed.)We consider the problem of collective exploration of a known n node edgeweighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when colocated: when two agents meet, one can transfer part of its energy to the other. For an nnode path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an nnode tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energysharing agents is NPhard, even for 3regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.more » « less