Alexander Russell

Qiang Tang

Moti Yung

Hong-Sheng Zhou

Proceedings of the Advances in Cryptology - CRYPTO 2018, 2018

2017

Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Coomputer Science (FOCS 2014).

[BibT_eX]

[DOI]

Julia Chuzhoy

SIAM J. Comput., 2017

Forkable Strings are Rare.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake protocol.

[BibT_eX]

[DOI]

Bernardo Machado David

Peter Gazi

IACR Cryptol. ePrint Arch., 2017

High Availability for VM Placement and a Stochastic Model for Multiple Knapsack.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on Computer Communication and Networks, 2017

Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2017, 2017

Generic Semantic Security against a Kleptographic Adversary.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017

2016

Codes, lower bounds, and phase transitions in the symmetric rendezvous problem.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Destroying Steganography via Amalgamation: Kleptographically CPA Secure Public Key Encryption.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

A Provably Secure Proof-of-Stake Blockchain Protocol.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

Behavior vs. introspection: refining prediction of clinical depression via smartphone sensing data.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE Wireless Health, 2016

Markovian Hitters and the Complexity of Blind Rendezvous.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Efficient Encrypted Keyword Search for Multi-user Data Sharing.

[BibT_eX]

[DOI]

Proceedings of the Computer Security - ESORICS 2016, 2016

Multi-view Bi-clustering to Identify Smartphone Sensing Features Indicative of Depression.

[BibT_eX]

[DOI]

Proceedings of the First IEEE International Conference on Connected Health: Applications, 2016

2015

Neighbor Discovery in Wireless Networks with Multipacket Reception.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2015

Dealing with undependable workers in decentralized network supercomputing.

[BibT_eX]

[DOI]

Seda Davtyan

Theor. Comput. Sci., 2015

Optimal ε-Biased Sets with Just a Little Randomness.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

Limitations of single coset states and quantum algorithms for code equivalence.

[BibT_eX]

[DOI]

Hang T. Dinh

Quantum Inf. Comput., 2015

Work-Competitive Scheduling on Task Dependency Graphs.

[BibT_eX]

[DOI]

Chadi Kari

Parallel Process. Lett., 2015

Cliptography: Clipping the Power of Kleptographic Attacks.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2015

Asynchronous Neighbor Discovery on Duty-cycled Mobile Devices: Integer and Non-Integer Schedules.

[BibT_eX]

[DOI]

Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2015

Asynchronous Adaptive Task Allocation.

[BibT_eX]

[DOI]

Proceedings of the 35th IEEE International Conference on Distributed Computing Systems, 2015

2014

An Entropic Proof of Chang's Inequality.

[BibT_eX]

[DOI]

Russell Impagliazzo

SIAM J. Discret. Math., 2014

A One-Time Stegosystem and Applications to Efficient Covert Communication.

[BibT_eX]

[DOI]

Yona Raekow

J. Cryptol., 2014

Group representations that resist random sampling.

[BibT_eX]

[DOI]

Shachar Lovett

Electron. Colloquium Comput. Complex., 2014

Heat and Noise on Cubes and Spheres: The Sensitivity of Randomly Rotated Polynomial Threshold Functions.

[BibT_eX]

[DOI]

CoRR, 2014

Technical Report: Dealing with Undependable Workers in Decentralized Network Supercomputing.

[BibT_eX]

[DOI]

Seda Davtyan

CoRR, 2014

Online Metric Tracking and Smoothing.

[BibT_eX]

[DOI]

Sixia Chen

Algorithmica, 2014

Deterministic Blind Rendezvous in Cognitive Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the IEEE 34th International Conference on Distributed Computing Systems, 2014

2013

Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem

[BibT_eX]

[DOI]

Sixia Chen

CoRR, 2013

Malicious takeover of voting systems: arbitrary code execution on optical scan voting terminals.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Applied Computing, 2013

Small-Bias Sets for Nonabelian Groups - Derandomizations of the Alon-Roichman Theorem.

[BibT_eX]

[DOI]

Sixia Chen

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Approximating the Permanent via Nonabelian Determinants.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2012

Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups

[BibT_eX]

[DOI]

Hari Krovi

CoRR, 2012

Optimal epsilon-biased sets with just a little randomness

[BibT_eX]

[DOI]

CoRR, 2012

Integrity of electronic voting systems: fallacious use of cryptography.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Applied Computing, 2012

Key-Efficient Steganography.

[BibT_eX]

[DOI]

Proceedings of the Information Hiding - 14th International Conference, 2012

2011

A Graph Integral Formulation of the Circuit Partition Polynomial.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2011

Quantum Fourier sampling, Code Equivalence, and the quantum security of the McEliece and Sidelnikov cryptosystems

[BibT_eX]

[DOI]

Hang Dinh

CoRR, 2011

The One-Way Communication Complexity of Subgroup Membership.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2011

Towards Feasible Implementations of Low-Latency Multi-writer Atomic Registers.

[BibT_eX]

[DOI]

Nicolas C. Nicolaou

Proceedings of The Tenth IEEE International Symposium on Networking Computing and Applications, 2011

Data Migration in Heterogeneous Storage Systems.

[BibT_eX]

[DOI]

Chadi Kari

Yoo-Ah Kim

Proceedings of the 2011 International Conference on Distributed Computing Systems, 2011

McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks.

[BibT_eX]

[DOI]

Hang Dinh

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

Geometric Topology & Visualizing 1-Manifolds.

[BibT_eX]

[DOI]

Proceedings of the Topological Methods in Data Analysis and Visualization, 2011

2010

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism.

[BibT_eX]

[DOI]

Piotr Sniady

SIAM J. Comput., 2010

Quantum and randomized lower bounds for local search on vertex-transitive graphs.

[BibT_eX]

[DOI]

Hang T. Dinh

Quantum Inf. Comput., 2010

Finding conjugate stabilizer subgroups in PSL and related groups.

[BibT_eX]

[DOI]

Aaron Denney

Quantum Inf. Comput., 2010

Limitations of quantum coset states for graph isomorphism.

[BibT_eX]

[DOI]

J. ACM, 2010

Approximate Representations and Approximate Homomorphisms

[BibT_eX]

[DOI]

CoRR, 2010

Regarding a Representation-Theoretic Conjecture of Wigderson

[BibT_eX]

[DOI]

CoRR, 2010

The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks

[BibT_eX]

[DOI]

Hang Dinh

CoRR, 2010

How close can we come to a parity function when there isn't one?

[BibT_eX]

[DOI]

CoRR, 2010

Circuit partitions and #P-complete products of inner products

[BibT_eX]

[DOI]

CoRR, 2010

Bounds on the Quantum Satisfiability Threshold.

[BibT_eX]

[DOI]

Sergey Bravyi

Proceedings of the Innovations in Computer Science, 2010

2009

State-wide elections, optical scan voting systems, and the pursuit of integrity.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Forensics Secur., 2009

Quantum algorithms for Simon's problem over nonabelian groups.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Randomness-optimal Steganography

[BibT_eX]

[DOI]

CoRR, 2009

Efficient Steganography with Provable Security Guarantees

[BibT_eX]

[DOI]

Yona Raekow

CoRR, 2009

Bounds on the quantum satisfibility threshold

[BibT_eX]

[DOI]

Sergey Bravyi

CoRR, 2009

The One-Way Communication Complexity of Group Membership

[BibT_eX]

[DOI]

CoRR, 2009

Automating Voting Terminal Event Log Analysis.

[BibT_eX]

[DOI]

Proceedings of the 2009 Electronic Voting Technology Workshop / Workshop on Trustworthy Elections, 2009

Taking total control of voting systems: firmware manipulations on an optical scan voting terminal.

[BibT_eX]

[DOI]

Proceedings of the 2009 ACM Symposium on Applied Computing (SAC), 2009

2008

Modeling time and topology for animation and visualization with examples on parametric geometry.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

The Symmetric Group Defies Strong Fourier Sampling.

[BibT_eX]

[DOI]

Leonard J. Schulman

SIAM J. Comput., 2008

A simple constant-probability RP reduction from NP to Parity P.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Pre-Election Testing and Post-Election Audit of Optical Scan Voting Terminal Memory Cards.

[BibT_eX]

[DOI]

Proceedings of the 2008 USENIX/ACCURATE Electronic Voting Workshop, 2008

Randomized Work-Competitive Scheduling for Cooperative Computing on k-partite Task Graphs.

[BibT_eX]

[DOI]

Chadi Kari

Proceedings of The Seventh IEEE International Symposium on Networking Computing and Applications, 2008

Topological Neighborhoods for Spline Curves: Practice & Theory.

[BibT_eX]

[DOI]

Proceedings of the Reliable Implementation of Real Number Algorithms: Theory and Practice, 2008

2007

The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2007

Failure-Sensitive Analysis of Parallel Algorithms with Controlled Memory Access Concurrency.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2007

Quantum Computing and the Hunt for Hidden Symmetry.

[BibT_eX]

Bull. EATCS, 2007

An Authentication and Ballot Layout Attack Against an Optical Scan Voting Terminal.

[BibT_eX]

[DOI]

Proceedings of the 2007 USENIX/ACCURATE Electronic Voting Technology Workshop, 2007

Quantum algorithms for Simon's problem over general groups.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Soft Edge Coloring.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

Tampering with Special Purpose Trusted Computing Devices: A Case Study in Optical Scan E-Voting.

[BibT_eX]

[DOI]

Laurent Michel

Andrew See

Seda Davtyan

Proceedings of the 23rd Annual Computer Security Applications Conference (ACSAC 2007), 2007

On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics.

[BibT_eX]

[DOI]

Hang T. Dinh

Yuan Su

Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006

How to fool an unbounded adversary with a short key.

[BibT_eX]

[DOI]

Hong Wang

IEEE Trans. Inf. Theory, 2006

Computational topology for isotopic surface reconstruction.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Generic quantum Fourier transforms.

[BibT_eX]

[DOI]

Daniel N. Rockmore

ACM Trans. Algorithms, 2006

Distributed scheduling for disconnected cooperation.

[BibT_eX]

[DOI]

Distributed Comput., 2006

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

CoRR, 2006

Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping.

[BibT_eX]

[DOI]

Proceedings of the Computational Science, 2006

2005

The Do-All problem with Byzantine processor failures.

[BibT_eX]

[DOI]

Antonio Fernández

Theor. Comput. Sci., 2005

Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

The Symmetric Group Defies Strong Fourier Sampling: Part II

[BibT_eX]

[DOI]

CoRR, 2005

The Symmetric Group Defies Strong Fourier Sampling: Part I

[BibT_eX]

[DOI]

Leonard J. Schulman

CoRR, 2005

Computational Topology for Reconstruction of Surfaces with Boundary: Integrating Experiments and Theory.

[BibT_eX]

[DOI]

Proceedings of the 2005 International Conference on Shape Modeling and Applications (SMI 2005), 2005

Efficient Steganography with Provable Security Guarantees.

[BibT_eX]

[DOI]

Yona Raekow

Proceedings of the Information Hiding, 7th International Workshop, 2005

Quantum Noisy Rational Function Reconstruction.

[BibT_eX]

[DOI]

Sean Hallgren

Igor E. Shparlinski

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

Improved algorithms for multiplex PCR primer set selection with amplification length constraints.

[BibT_eX]

[DOI]

Ion I. Mandoiu

Proceedings of 3rd Asia-Pacific Bioinformatics Conference, 17-21 January 2005, Singapore, 2005

2004

The chilean highway problem.

[BibT_eX]

[DOI]

Marcos A. Kiwi

Theor. Comput. Sci., 2004

Inapproximability results for equations over finite groups.

[BibT_eX]

[DOI]

Lars Engebretsen

Jonas Holmerin

Theor. Comput. Sci., 2004

Analysis of memory access concurrency in robust parallel algorithms.

[BibT_eX]

[DOI]

Stud. Inform. Univ., 2004

Classical and quantum function reconstruction via character evaluation.

[BibT_eX]

[DOI]

Igor E. Shparlinski

J. Complex., 2004

The complexity of synchronous iterative Do-All with crashes.

[BibT_eX]

[DOI]

Distributed Comput., 2004

Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

[BibT_eX]

[DOI]

Ion I. Mandoiu

CoRR, 2004

Random Cayley Graphs are Expanders: a Simple Proof of the Alon-Roichman Theorem.

[BibT_eX]

[DOI]

Zeph Landau

Electron. J. Comb., 2004

The power of basis selection in fourier sampling: hidden subgroup problems in affine groups.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

Computational topology: ambient isotopic approximation of 2-manifolds.

[BibT_eX]

[DOI]

Nina Amenta

Thomas J. Peters

Theor. Comput. Sci., 2003

The Hidden Subgroup Problem and Quantum Computation Using Group Representations.

[BibT_eX]

[DOI]

Sean Hallgren

Amnon Ta-Shma

SIAM J. Comput., 2003

A note on the set systems used for broadcast encryption.

[BibT_eX]

[DOI]

Ravi Kumar

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Distributed Cooperation and Adversity: Complexity Trade-Offs.

[BibT_eX]

[DOI]

Proceedings of the PCK50, 2003

2002

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

[BibT_eX]

[DOI]

Michael E. Saks

David Zuckerman

SIAM J. Comput., 2002

The Complexity of Solving Equations over Finite Groups.

[BibT_eX]

[DOI]

Inf. Comput., 2002

Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation.

[BibT_eX]

Bull. EATCS, 2002

Quantum Walks on the Hypercube.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Optimally work-competitive scheduling for cooperative computing with merging groups.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

Failure sensitive analysis for parallel algorithm with controlled memory access concurrency.

[BibT_eX]

Proceedings of the Procedings of the 6th International Conference on Principles of Distributed Systems. OPODIS 2002, 2002

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

2001

Complexity Bounds on General Hard-Core Predicates.

[BibT_eX]

[DOI]

Mats Näslund

J. Cryptol., 2001

Perfect Information Leader Election in log* n+O (1) Rounds.

[BibT_eX]

[DOI]

David Zuckerman

J. Comput. Syst. Sci., 2001

Efficient Encryption for Rich Message Spaces Under General Assumptions.

[BibT_eX]

[DOI]

Hong Wang

IACR Cryptol. ePrint Arch., 2001

Optimal Scheduling for Distributed Cooperation Without Communication.

[BibT_eX]

Proceedings of the SIROCCO 8, 2001

Optimal scheduling for disconnected cooperation.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Local Scheduling for Distributed Cooperation.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA 2001), 2001

2000

Extraction of optimally unbiased bits from a biased source.

[BibT_eX]

[DOI]

Mats Näslund

IEEE Trans. Inf. Theory, 2000

An Easy Reduction of an Isoperimetric Inequality on the Sphere to Extremal Set Theory.

[BibT_eX]

[DOI]

Am. Math. Mon., 2000

An ergodic theorem for read-once non-uniform deterministic finite automata.

[BibT_eX]

[DOI]

Denis Thérien

Inf. Process. Lett., 2000

Alternation in interaction.

[BibT_eX]

[DOI]

Comput. Complex., 2000

Distributed Cooperation During the Absence of Communication.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 14th International Conference, 2000

Normal subgroup reconstruction and quantum computation using group representations.

[BibT_eX]

[DOI]

Sean Hallgren

Amnon Ta-Shma

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Spectral Bounds on General Hard Core Predicates.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Distributed cooperation in the absence of communication (brief announcement).

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

The Complexity of Distributed Cooperation in the Presence of Failures.

[BibT_eX]

Proceedings of the Procedings of the 4th International Conference on Principles of Distributed Systems, 2000

1999

Approximating Latin Square Extensions.

[BibT_eX]

[DOI]

Ravi Kumar

Algorithmica, 1999

1998

On embedding complete graphs into hypercubes.

[BibT_eX]

[DOI]

Michael Klugerman

Discret. Math., 1998

A Note on the Asymptotics and Computational Complexity of Graph Distinguishability.

[BibT_eX]

[DOI]

Electron. J. Comb., 1998

Symmetric Alternation Captures BPP.

[BibT_eX]

[DOI]

Comput. Complex., 1998

Perfect Information Leader Election in log*<i>n</i> + <i>O</i>(1) Rounds.

[BibT_eX]

[DOI]

David Zuckerman

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

A Note on Optical Routing on Trees.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

Faster Algorithms for Optical Switch Configuration.

[BibT_eX]

[DOI]

Ravi Kumar

Proceedings of the 1997 IEEE International Conference on Communications: Towards the Knowledge Millennium, 1997

1995

Necessary and Sufficient Condtions for Collision-Free Hashing.

[BibT_eX]

[DOI]

J. Cryptol., 1995

The Relativized Relationship Between Probabilistically Chackable Debate Systems, IP and PSPACE.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

1994

Efficient probabilistic checkable proofs and applications to approximation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Efficient probabilistically checkable proofs and applications to approximations.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Necessary and Sufficient Conditions For Collision-Free Hashing.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1992

1991

A Critical Look at Experimental Evaluations of EBL.

[BibT_eX]

[DOI]

Alberto M. Segre

Charles Elkan