 |
Selected Articles and Manuscripts
- Leader Election, Collective Coin-Flipping and
Distributed
Computation
- C. Georgiou, A. Russell, and A. Shvartsman. Work
Competitive
Scheduling for Cooperative Computing with Dynamic Groups. SIAM Journal on Computing,
accepted. A preliminary version appeared in
proceedings of the
Thirty-Fifth Annual ACM Symposium on Theory of Computing
(STOC), 2003. San Diego, CA.
- C. Georgiou, A. Russell, and A. Shvartsman. The
Complexity of
Synchronous Iterative Do-All with Crashes. In proceedings of the 15th International Symposium on
Distributed Computing (DISC), 2001. Lisbon, Portugal.
- A. Fernandez, Ch. Georgiou, A. Russell, and A.
Shvartsman.
The Do-All problem with Byzantine processor failures. Theoretical Computer Science,
333(3):433-454, March 2005.
- G. Malewicz, A. Russell, and A. Shvartsman. Distributed
Cooperation in
the Absence of Communication. In proceedings of the 14th International Symposium on
Distributed Computing (DISC). Oct 4-6, 2000, Toledo, Spain. A
brief announcement appeared in the Proceedings of the 19th Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computating
(PODC). July 16-19, Portland, OR.
- A. Russell, M. Saks and D. Zuckerman.
Lower Bounds for Leader Election and Collective Coin-Flipping in the
Perfect Information Model. SIAM Journal on Computing,
31(6):1645-1662, 2003. Also in Proceedings
of the
Thirty-First Annual ACM Symposium on Theory of
Computing (STOC). Atlanta, Georgia, May 1-4, 1999.
- A. Russell and D. Zuckerman. Perfect
Information Leader Election in log* n + O(1) Rounds. Journal of
Computer and System Sciences, 63:612-626, 2001. Also in Proceedings of the
Thirty-Ninth Annual Symposium on Foundations of Computer Science
(FOCS), Palo Alto, California, November 8-11, 1998.
- Survey Article: C. Georgiou, A. Russell, and
A. Shvartsman. Distributed Cooperation and Adversity:
Complexity Trade-Offs. In Proceedings of the Principles of Computing and
Knowledge: Paris C. Kanellakis Memorial Workshop (PK50),
2003. San Diego, CA.
- Survey Article: A. Russell and
A. Shvartsman. Distributed Computation Meets Design Theory: Local
Scheduling for Disconnected Cooperation. Bulletin of the EATCS,
75:120-131, June, 2002.
- Quantum Computation
- S. Hallgren, A. Ta-Shma, and A. Russell. Normal Subgroup
Reconstruction
and Quantum Computation Using Group Representations. In Proceedings of the
Thirty-Second Annual ACM Symposium on Theory of
Computing (STOC), pages 627--635, Portland, OR, May 2000. ACM.
- C. Moore, D. Rockmore, and A. Russell. Generic Quantum
Fourier Transforms. In Proceedings of the Fifteenth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA,
January 11-13 2004. ACM. A preliminary version appeared in the Quantum Physics E-print
archive, report quant-ph/0304064.
- C. Moore, D. Rockmore, A. Russell, and L. Schulman. The Hidden Subgroup
Problem in Affine Groups: Basis Selection in Fourier Sampling. In Proceedings
of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),
New Orleans, LA, January 11-13 2004. ACM. A preliminary version
appeared in the Quantum
Physics E-print archive, report quant-ph/0211124.
- C. Moore and A. Russell. Quantum Walks on the Hypercube.
In Proceedings of the Sixth International Workshop on
Randomization and
Approximation Techniques in Computer Science
(RANDOM). Cambridge, MA, 13-15 September, 2002. Lecture Notes
in Computer Science, Springer-Verlag.
- C. Moore and A. Russell. The Symmetric Group Defies
Strong Fourier Sampling: Part II. Quantum Physics E-print
archive, report quant-ph/0501066.
- C. Moore, A. Russell, and L. Schulman. The Symmetric
Group Defies Strong Fourier Sampling: Part I. Quantum Physics E-print
archive, report quant-ph/0501056.
- I. Shparlinski and A. Russell. Classical and Quantum
Polynomial Reconstruction via Legendre Symbol Evaluation. Journal of Complexity 20:(2-3), pp.
404-422. A preliminary version appeared in the Quantum Physics E-print
archive, report quant-ph/0212016.
- Interactive Proofs
- M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient
probabilistically checkable proofs and applications to approximation.
In Proceedings of the Twenty-Fifth ACM Symposium on the Theory of
Computing (STOC),
pages 294--304, San Diego, California, 16-18 May 1993. [BibTex
Record]. See also: Errata
- M. Kiwi, C. Lund, A. Russell, D. Spielman, and R.
Sundaram. Alternation
in interaction. In Proceedings of the Ninth Annual Structure in
Complexity Theory Conference, pages 294--303, Amsterdam, The
Netherlands,
28 June-1 July, 1994. [BibTeX
Record]. IEEE, 1994.
- J. Holmerin, L. Engebretsen, and A. Russell. Inapproximability
Results for Equations Over Finite Groups. In Proceedings of the
29th International Colloquium on Automata, Languages, and
Programming (ICALP). Malaga, Spain, 8 July-13 July, 2002. This
paper was awarded ICALP's best paper award. Theoretical Computer Science,
312(1):17-45, 2004.
- A. Russell and R. Sundaram. The
relativized relationship between probabilistically checkable debate
systems,
IP, and PSPACE. Information Processing Letters,
53(2):61--68,
January 1995. [BibTeX
Record].
- Cryptography
- Mikael Goldmann, Mats Naslund, and Alexander Russell.
Complexity
bounds on general-hard core predicates. Journal of Cryptology,
14(3):177-195, 2001.
- M. Goldmann and A. Russell. Spectral
Bounds on General Hard Core Predicates. 17th International Symposium
on Theoretical Aspects of Computer Science (STACS). Lille,
France. February, 2000.
- S. R. Kumar and A. Russell. A note on the set systems
used for
broadcast encryption. In the Proceedings of the Fourteenth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 470-471,
Baltimore, MD, January 2003. ACM.
- M. Naslund and A. Russell. Extraction
of Optimally Unbiased Bits from a Biased Source. IEEE
Transactions on Information Theory. 46(3), May 2000. A
preliminary
version appeared in 1997 IEEE Information Theory
Workshop. Killarney, Kerry, Ireland. July, 1997.
- A. Russell. Necessary and
sufficient conditions for collision-free hashing. Journal
of Cryptology, 8(2):87--99, Spring 1995. [BibTeX
Record]. Also in CRYPTO '92. ([BibTeX
Record].)
- A. Russell and H. Wang. How to Fool an Unbounded
Adversary with a
Short Key. In Proceedings of the 21st Annual EuroCrypt
Conference, 28 April 28- 2 May, Amsterdam, The Netherlands. [postscript] [acrobat]. See also a
previous edition as an ePrint Archived Article: A. Russell and H. Wang.
Efficient
Asymmetric Encryption for Rich Message Spaces Under General
Assumptions. IACR ePrint Cryptography Archive, 2001-028. [postscript], [pdf], [BibTeX].
- Survey Article: M. Naslund and A. Russell.
Hard-Core
Functions: Survey and New Results. NORDSEC 1999.
- Computational Complexity Theory
- E. Allender, S. Arora, M. Kearns, C. Moore, and A.
Russell. A Note on the
Representational
Incompatibility of Function Approximation and Factored
Dynamics. In proceedings of the Sixteenth Annual Conference on
Neural Information Processing Systems (NIPS). Vancouver,
Canada.
December 9-14, 2002.
- M. Goldmann and A. Russell. The
Computational Complexity of Solving Systems of Equations over Finite
Groups. Information and Computation, 178:253-262, 2002.
Also in the Proceedings of the Fourteenth Annual
IEEE Conference on Computational Complexity. Atlanta,
Georgia. May, 1999.
- M. Goldmann and A. Russell and D. Therien. An Ergodic
Theorem for
Read-Once Non-Uniform Deterministic Finite Automata. Information
Processing Letters. 73 (2000), pp. 23-28.
- A. Russell and R. Sundaram. Symmetric
alternation captures BPP. Computational
Complexity 7(2): 152-162.
- Combinatorics and Information Theory
- M. Klugerman, A. Russell, R. Sundaram. A
note on embedding complete graphs into hypercubes. Discrete
Mathematics (186)1-3(1998), pages 289-293.
- S. R. Kumar, A. Russell, R. Sundaram. Approximating
latin square extensions. Algorithmica
24:2, pages 128-138. A preliminary version appeared in Computing
and Combinatorics : Second Annual International Conference, COCOON
'96, Hong Kong, June 17-19, 1996. Proceedings appeared in Lecture
Notes in computer Science, Springer. December, 1995.
- Z. Landau and A. Russell. Random
Cayley Graphs are Expanders: a Simple Proof of the Alon-Roichman Theorem.
Electronic Journal
of Combinatorics 11(1), R62, 2004.
- A. Russell. Haar Measure and the Passage from the
Combinatorial
to the Continuous: an Easy Reduction of an Isoperimetric Inequality on
the Sphere to Extremal Set Theory. American Mathematical
Monthly. January, 2000.
- A. Russell and R. Sundaram. A
Note on the Asymptotics and Computational Complexity of Graph
Distinguishability. Electronic
Journal of Combinatorics
5(1), R23. 1998.
- Routing
- S. R. Kumar, R. Panigrahy, A. Russell, R. Sundaram. A
Note on Optical Routing on Trees. Information Processing Letters,
62(6):296-300, June 1997. [BibTeX
Record].
- S. R. Kumar, A. Russell, R. Sundaram. Faster
Algorithms for Optimal Switch Configuration. IEEE International
Conference on Communications. June, 1997.
- M. Kiwi, A. Russell. The Chilean highway problem.
Theoretical Computer Science, 326:329--342, 2004.
- Translations
|
