Sorting in \(c \log n\) parallel steps
From MaRDI portal
Publication:1056541
DOI10.1007/BF02579338zbMath0523.68048OpenAlexW1587590810WikidataQ63431207 ScholiaQ63431207MaRDI QIDQ1056541
János Komlós, Endre Szemerédi, Miklós Ajtai
Publication date: 1983
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579338
Related Items
Iterated nearest neighbors and finding minimal polytopes, Computing the smallest \(k\)-enclosing circle and related problems, Algorithms for ham-sandwich cuts, More on the complexity of slice functions, On the relationship between the diameter and the size of a boundary of a directed graph, Methods for message routing in parallel machines, On efficient parallel strong orientation, Multi-processor scheduling and expanders, A theory of strict P-completeness, Reverse shortest path problem for unit-disk graphs, Distributed algorithms in synchronous broadcasting networks, The graph clustering problem has a perfect zero-knowledge interactive proof, Accelerating certain outputs of merging and sorting networks, Recursive construction for 3-regular expanders, Parallel integer sorting using small operations, Parallel ear decomposition search (EDS) and st-numbering in graphs, Distributed sorting algorithms for multi-channel broadcast networks, Towards optimal parallel bucket sorting, A parallel algorithm for the generation of a permutation and applications, An optimal parallel algorithm for triangulating a set of points in the plane, Better lower bounds for monotone threshold formulas, Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM, Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults, An O(log n) time parallel algorithm for triangulating a set of points in the plane, An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits, A parallel bucket sort, Merging almost sorted sequences yields a 24-sorter, Sorting strings and constructing digital search trees in parallel, Exploiting few inversions when sorting: Sequential and parallel algorithms, Broadcasting with random faults, Eigenvalues and expanders, An efficient parallel algorithm for planarity, On the distribution of comparisons in sorting algorithms, Parallel computational geometry, L-infinity interdistance selection by parametric search, An efficient parallel algorithm for random sampling, Sorting in rounds, Optimal parallel selection has complexity O(log log N), Parametric search made practical, Efficient monotone circuits for threshold functions, Hybridsort revisited and parallelized, Selecting distances in arrangements of hyperplanes spanned by points., The queue-read queue-write asynchronous PRAM model, Real-time emulations of bounded-degree networks, Optimal slope selection via cuttings, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Sorting nine inputs requires twenty-five comparisons, Sorting roughly sorted sequences in parallel, Bounds on the size of test sets for sorting and related networks, A sorting network in bounded arithmetic, A new scheme for the deterministic simulation of PRAMs in VLSI, A complexity theory of efficient parallel algorithms, Parallel selection, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of \(\epsilon\)-nets, Comment on Kochol's paper ``Efficient monotone circuits for threshold functions, On the complexity of min-max sorting networks, Clique problem, cutting plane proofs and communication complexity, Exact algorithms for the bottleneck Steiner tree problem, Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons, A note on the token distribution problem, Randomized optimal algorithm for slope selection, An optimal parallel adaptive sorting algorithm, Picture-hanging puzzles, Highly linked tournaments, Negation-limited circuit complexity of symmetric functions, Optimal randomized parallel algorithms for computational geometry, Finding effective ``Force targets for two-dimensional, multifinger frictional grips, An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model, A parallelization of Miller's \(n^{\log n}\) isomorphism technique, The unpredictable deviousness of models, Optimal slope selection via expanders, Highly symmetric expanders, Extended formulations for polygons, An efficient counting network, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, The generalized packet routing problem, Graphs whose every transitive orientation contains almost every relation, Improved sorting networks with O(log N) depth, Optimal merging and sorting on the EREW PRAM, A note on adaptive parallel sorting, Constructing sorting networks from k-sorters, Improving the average delay of sorting, Smallest compact formulation for the permutahedron, Parallel iterated bucket sort, Sorting networks of logarithmic depth, further simplified, On O(Tlog T) reduction from RAM computations to satisfiability, Sorting in linear time?, More general parallel tree contraction: Register allocation and broadcasting in a tree, Periodic comparator networks, Hamiltonian paths in Cayley graphs, A parallel-design distributed-implementation (PDDI) general-purpose computer, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, Finding Euler tours in parallel, A simple optimal parallel algorithm for the minimum coloring problem on interval graphs, Shallow grates, On parallel integer sorting, Parallel comparison merging of many-ordered lists, On the complexity of slice functions, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Monotone simulations of non-monotone proofs., Shift lifts preserving Ramanujan property, Monotone Boolean formulas can approximate monotone linear threshold functions, Proofs with monotone cuts, Secure wire shuffling in the probing model, Fast periodic correction networks, On the diameter and bisector size of Cayley graphs, Perfectly secure oblivious parallel RAM, Faster merging networks with a small constant period, Oblivious RAM with \textit{worst-case} logarithmic overhead, PRAM's towards realistic parallelism: BRAM's, Rearranging a sequence of points onto a line, Cooperative Boolean systems with generically long attractors I, Computing the smallest k-enclosing circle and related problems, Secure Multi-party Shuffling, Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes, Dense expanders and pseudo-random bipartite graphs, LABELING POINTS WITH RECTANGLES OF VARIOUS SHAPES, OPTIMAL PARALLEL PREPROCESSING ALGORITHMS FOR TESTING WEAK VISIBILITY OF POLYGONS FROM SEGMENTS, A unified \(O(\log N)\) and optimal sorting vector algorithm, Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Sorting Short Keys in Circuits of Size ${o(n \log n)}$, Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\), A computer-assisted optimal depth lower bound for nine-input sorting networks, The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks, Adaptively secure garbling schemes for parallel computations, Expanders and Diffusers, A lower bound for sorting networks based on the shuffle permutation, Time-optimal simulations of networks by universal parallel computers, Reliable minimum finding comparator networks, Cooperative Boolean systems with generically long attractors. II, Lower bounds for Boolean circuits of bounded negation width, On (Valiant’s) Polynomial-Size Monotone Formula for Majority, Assouad-Nagata dimension and gap for ordered metric spaces, Combinatorial search in two and more rounds, Discrete Fréchet distance for closed curves, A framework for automated distributed implementation of component-based models, Algorithms and lower bounds for comparator circuits from shrinkage, Klee's measure problem made oblivious, Optimal single-server private information retrieval, Linear-time 2-party secure merge from additively homomorphic encryption, \textsf{MacORAMa}: optimal oblivious RAM with integrity, Unnamed Item, Representing shared data on distributed-memory parallel computers, Constraints, MMSNP and expander relational structures, Recursion and parallel algorithms in geometric modeling problems, A note on searching line arrangements and applications, Atomic snapshots using lattice agreement, Counting networks with arbitrary fan-out, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, On the theory of interconnection networks for parallel computers, A super-logarithmic lower bound for hypercubic sorting networks, Bisecting three classes of lines, Resizing cardinality constraints for MaxSAT, Parallel matching for ranking all teams in a tournament, Generic top-down discrimination for sorting and partitioning in linear time, Constructing Extended Formulations from Reflection Relations, The impact of randomization in smoothing networks, On partial sorting in restricted rounds, Efficient algorithms for the sum selection problem and \(k\) maximum sums problem, Unnamed Item, Is there an oblivious RAM lower bound for online reads?, Is there an oblivious RAM lower bound for online reads?, Fast algorithms for bit-serial routing on a hypercube, Single-exception sorting networks and the computational complexity of optimal sorting network verification, Searching games with errors -- fifty years of coping with liars, Comparator networks for binary heap construction, More Efficient Parallel Integer Sorting, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, Fragile complexity of adaptive algorithms, Fragile complexity of comparison-based algorithms, Fragile complexity of adaptive algorithms, On Rearrangement of Items Stored in Stacks, Deterministic Graphical Games Revisited, On Expressing Majority as a Majority of Majorities, Locality-preserving oblivious RAM, Structured encryption and dynamic leakage suppression, Generic Constant-Round Oblivious Sorting Algorithm for MPC, Representing Permutations with Few Moves, Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits, On the complexity of monotone circuits for threshold symmetric Boolean functions, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Unnamed Item, Permutatorial optimization via the permutahedron, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, Comparator networks for binary heap construction, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, A note on constructing binary heaps with periodic networks., Parallel preprocessing for path queries without concurrent reading., Unnamed Item, Improved fast integer sorting in linear space, On the negation-limited circuit complexity of merging, Improving the efficiency of parallel minimum spanning tree algorithms, Algorithmic results for ordered median problems, Diameters and Eigenvalues, OptORAMa: optimal oblivious RAM
Cites Work
