Alexander Russell
  • Main
  • Publications
  • Projects
  • Teaching
  • Recent & Upcoming Talks
    • Example Talk
  • Publications
    • The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording
    • Adaptive Risk-Limiting Comparison Audits
    • Adaptively Secure Random Beacons for Ungrindable Blockchains
    • Fait Accompli Committee Selection: Improving the Size-Security Tradeoff of Stake-Based Committees
    • Practical Settlement Bounds for Longest-Chain Consensus
    • Predicting Symptom Improvement During Depression Treatment Using Sleep Sensory Data
    • Practical Settlement Bounds for Proof-of-Work Blockchains
    • The Generals' Scuttlebutt: Byzantine-Resilient Gossip Protocols
    • A Composable Security Treatment of ECVRF and Batch Verifications
    • Automatic depression screening using social interaction data on smartphones
    • More the Merrier: Neighbor Discovery on Duty-cycled Mobile Devices in Group Settings
    • Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work - A Provably Secure Blockchain Protocol
    • Dynamic Ad Hoc Clock Synchronization
    • Code Offset in the Exponent
    • Fast Isomorphic State Channels
    • Fusing Location Data for Depression Prediction
    • Germ order for one-dimensional packings
    • Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders
    • Asynchronous Neighbor Discovery on Duty-Cycled Mobile Devices: Models and Schedules
    • Efficient Simulation of Random States and Random Unitaries
    • Ledger Combiners for Fast Settlement
    • Quantum-Access-Secure Message Authentication via Blind-Unforgeability
    • The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
    • Tight Consistency Bounds for Bitcoin
    • Let a Non-barking Watchdog Bite: Cliptographic Signatures with an Offline Watchdog
    • Large-Scale Automatic Depression Screening Using Meta-Data from WiFi Infrastructure
    • Stake-Bleeding Attacks on Proof-of-Stake Blockchains
    • Correcting Subverted Random Oracles
    • Joint Modeling of Heterogeneous Sensing Data for Depression Assessment via Multi-task Learning
    • Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability
    • Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain
    • Generic Semantic Security against a Kleptographic Adversary
    • High Availability for VM Placement and a Stochastic Model for Multiple Knapsack
    • Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
    • Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
    • Multi-view Bi-clustering to Identify Smartphone Sensing Features Indicative of Depression
    • Behavior vs. introspection: Refining prediction of clinical depression via smartphone sensing data
    • Cliptography: Clipping the Power of Kleptographic Attacks
    • Codes, lower bounds, and phase transitions in the symmetric rendezvous problem
    • Efficient Encrypted Keyword Search for Multi-user Data Sharing
    • Markovian Hitters and the Complexity of Blind Rendezvous
    • Group representations that resist random sampling
    • Neighbor Discovery in Wireless Networks with Multipacket Reception
    • Work-Competitive Scheduling on Task Dependency Graphs
    • Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups
    • Asynchronous Adaptive Task Allocation
    • Asynchronous Neighbor Discovery on Duty-cycled Mobile Devices: Integer and Non-Integer Schedules
    • Asynchronous Neighbor Discovery on Duty-cycled Mobile Devices: Integer and Non-Integer Schedules
    • Cliptography: Clipping the Power of Kleptographic Attacks
    • Dealing with undependable workers in decentralized network supercomputing
    • Limitations of Single Coset States and Quantum Algorithms for Code Equivalence
    • Optimal $ε$-Biased Sets with Just a Little Randomness
    • Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
    • A One-time Stegosystem and its Application to Efficient Covert Communication
    • An Entropic Proof of Chang's Inequality
    • Deterministic Blind Rendezvous in Cognitive Radio Networks
    • Online Metric Tracking and Smoothing
    • Single Cell Analysis Reveals the Stochastic Phase of Reprogramming to Pluripotency is an Ordered Probabilistic Process
    • Dealing with Undependable Workers in Decentralized Network Supercomputing
    • Key-Efficient Steganography
    • Malicious takeover of voting systems: Arbitrary code execution on optical scan voting terminals
    • Small-Bias Sets for Nonabelian Groups: Derandomizations of the Alon-Roichman Theorem
    • Approximating the Permanent via Nonabelian Determinants
    • Integrity of Electronic Voting Systems: Fallacious Use of Cryptography
    • The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces
    • A Graph Integral Formulation of the Circuit Partition Polynomial
    • Data Migration in Heterogeneous Storage Systems
    • McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks
    • Neighbor discovery in wireless networks with multipacket reception
    • Spectral Concentration of Positive Functions on Compact Groups
    • The one-way communication complexity of subgroup membership
    • Towards Feasible Implementations of Low-Latency Multi-writer Atomic Registers
    • Limitations of Quantum Coset States for Graph Isomorphism
    • On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
    • Bounds on the Quantum Satisfiability Threshold
    • Finding Conjugate Stabilizer Subgroups in PSL and Related Groups
    • Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
    • Quantum Algorithms for Simon's Problem Over General Groups
    • State-Wide Elections, Optical Scan Voting Systems, and the Pursuit of Integrity
    • Automating Voting Terminal Event Log Analysis
    • Taking Total Control of Voting Systems: Firmware Manipulations on an Optical Scan Voting Terminal
    • Modeling Time and Topology for Animation and Visualization with Examples on Parametric Geometry
    • The Symmetric Group Defies Strong Fourier Sampling
    • Pre-Election Testing and Post-Election Audit of Optical Scan Voting Terminal Memory Cards
    • Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
    • Randomized Work-Competitive Scheduling for Cooperative Computing on k-partite Task Graphs
    • Reliable Implementation of Real Number Algorithms: Theory and Practice
    • Uncertainty Principles for Compact Groups
    • The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
    • An Authentication and Ballot Layout Attack Against an Optical Scan Voting Terminal
    • Failure-Sensitive Analysis of Parallel Algorithms with Controlled Memory Access Concurrency
    • For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
    • On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
    • On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics
    • Quantum Algorithms for Simon's Problem Over General Groups
    • Soft Edge Coloring
    • Computational Topology for Isotopic Surface Reconstruction
    • Generic Quantum Fourier Transforms
    • How to Fool an Unbounded Adversary with a Short Key
    • Distributed Scheduling for Disconnected Cooperation
    • Limitations of Quantum Coset States for Graph Isomorphism
    • Quantum Random Walk with Rydberg Atoms in an Optical Lattice
    • Decoherence in Quantum Walks on the Hypercube
    • Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups
    • The Do-All Problem with Byzantine Processor Failures
    • Computational Topology for Reconstruction of Surfaces with Boundary: Integrating Experiments and Theory
    • Efficient Steganography with Provable Security Guarantees
    • The Symmetric Group Defies Strong Fourier Sampling
    • The Chilean Highway Problem
    • Classical and Quantum Function Reconstruction via Character Evaluation
    • The Complexity of Synchronous Iterative Do-All with Crashes
    • Analysis of Instant and Total Memory Access Concurrency in Robust Parallel Algorithms
    • Generic Quantum Fourier Transforms
    • Inapproximability Results for Equations over Finite Groups
    • Random Cayley Graphs are Expanders: A Simple Proof of the Alon-Roichman Theorem
    • The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups
    • Computational Topology: Ambient Isotopic Approximation of 2-Manifolds
    • A Note on the Set Systems Used for Broadcast Encryption
    • Distributed Cooperation and Adversity: Complexity Trade-offs
    • The Hidden Subgroup Problem and Quantum Computation Using Group Representations
    • Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups
    • The Complexity of Solving Equations Over Finite Groups
    • Failure sensitive analysis for parallel algorithm with controlled memory access concurrency
    • How to Fool an Unbounded Adversary with a Short Key
    • Inapproximability Results for Equations over Finite Groups
    • Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
    • Optimally Work-Competitive Scheduling for Cooperative Computing with Merging Groups
    • Quantum Walks on the Hypercube
    • Perfect Information Leader Election in $łog^* n + O(1)$ Rounds
    • Complexity Bounds on General Hard-Core Predicates
    • Local Scheduling for Distributed Cooperation
    • Optimal Scheduling for Disconnected Cooperation
    • The Complexity of Synchronous Iterative Do-All with Crashes
    • Alternation in Interaction
    • An Easy Reduction of an Isoperimetric Inequality on the Sphere to Extremal Set Theory
    • An Ergodic Theorem for Read-once Non-uniform Deterministic Finite Automata
    • Distributed Cooperation During the Absence of Communication
    • Distributed Cooperation in the Absence of Communication
    • Extraction of Optimally Unbiased Bits from a Biased Source
    • Hard-core functions: Survey and new results
    • Normal Subgroup Reconstruction and Quantum Computation Using Group Representations
    • Spectral Bounds on General Hard Core Predicates
    • The Complexity of Distributed Cooperation in the Presence of Failures
    • Approximating Latin Square Extensions
    • Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
    • The Complexity of Solving Equations Over Finite Groups
    • Symmetric Alternation Captures BPP
    • On Embedding Complete Graphs into Hypercubes
    • A Note on the Asymptotics and Computational Complexity of Graph Distinguishability
    • Extraction of optimally unbiased bits from a biased source
    • Perfect Information Leader Election in $łog^* n + O(1)$ Rounds
    • A Note on Optical Routing on Trees
    • Faster Algorithms for Optical Switch Configuration
    • Approximating Latin Square Extensions
    • Necessary and Sufficient Conditions For Collision-Free Hashing
    • The Relativized Relationship Between Probabilistically Checkable Debate Systems, IP and PSPACE
    • Alternation in interaction
    • Efficient Probabilistic Checkable Proofs and Applications to Approximation
    • Efficient Probabilistically Checkable Proofs and Applications to Approximations
    • Necessary and Sufficient Conditions For Collision-Free Hashing
    • A Critical Look at Experimental Evaluations of EBL
  • Projects
  • Blog
    • 🎉 Easily create your own simple yet highly customizable blog
    • 🧠 Sharpen your thinking with a second brain
    • 📈 Communicate your results effectively with the best data visualizations
    • 👩🏼‍🏫 Teach academic courses
    • ✅ Manage your projects
  • Projects
    • CATCS
    • Theory of Computing
    • UConn letterhead
  • Experience
  • Teaching
    • Advanced Cryptography
    • Introduction to Modern Cryptography

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model

Jan 1, 1999·
Alexander Russell
,
Michael Saks
,
David Zuckerman
· 0 min read
Cite DOI
Type
Conference paper
Publication
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC)
Last updated on Jan 1, 1999
← Approximating Latin Square Extensions Jan 1, 1999
The Complexity of Solving Equations Over Finite Groups Jan 1, 1999 →

© 2024 Me. This work is licensed under CC BY NC ND 4.0

Published with Hugo Blox Builder — the free, open source website builder that empowers creators.