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

Optimal $ε$-Biased Sets with Just a Little Randomness

Jan 1, 2015·
Cristopher Moore
,
Alexander Russell
· 0 min read
Cite DOI
Type
Journal article
Publication
SIAM Journal on Discrete Mathematics
Last updated on Jan 1, 2015
← Limitations of Single Coset States and Quantum Algorithms for Code Equivalence Jan 1, 2015
Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups Jan 1, 2015 →

© 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.