- The Second P=?NP Poll.
(A Guest column in Lane Hemaspaandra's Complexity Column.)
POLL2012
- The Complexity of Grid Coloring.
(with Daniel Apon and Kevin Lawler).
GRIDCOL
- Three proofs of the Hypergraph Ramsey Theorem
(with Andy Parrish and Sanai Sandow).
HYPER
- A Statement in Combinatorics that is
Independent of ZFC.
(with Stephen Fenner)
In Progress.
ZFCRADO.PDF
- The Tug of War Game.
William Gasarch and Nick Sovich and Paul Zimand.
TUG.PDF
- Rectangle Free Colorings of Grids.
(with Fenner, Glover, and Purewal).
GRIDPAPER.PDF
GRIDTALK.PDF
In progress.
- Limits on the Computational Power of Random Strings.
(with Eric Allender and Luke Friedman)
RANDOMSTRINGS.PDF
To appear in
*Information and Computation*Special issue devotedto ICALP 2011. - Lower Bounds on van der Waerden Numbers:
Randomized- and Deterministic-Constructife
(with Bernhard Haeupler)
LOWERVDW
*Electronic Journal of Combinatorics*Vol 18, 2011 - The complexity of finding SUBSEQ(A)
(with Fenner and Postow)
*Theory of Computing Systems*Vol 45, No. 3, 2009, 577-612. SUBSEQ.PDF (Version here has appendices that the journal version did not have.) - The Complexity of Learning SUBSEQ(A)
(with Stephen Fenner and Brian Postow)
*Journal of Symbolic Logic*Vol. 74, No. 3, 2009, 939-975. learnsubseq.PDF Earlier Conf Version: learnsubseqCONF.PDF. - Inferring answers from data
(with A. Lee)
*Journal of Computing and Systems Sciences*, (To appear) Conference Version in COLT97. ANSWERS.PDF - Finding Large 3-free Sets I: the Small n Case
(with James Glenn and Clyde Kruskal),
*Journal of Computing and Systems Sciences*, Volume 74, No. 4, June 2008. 628-655. 3apI.PDF - A Nearly Tight Lower Bound for Restricted Private Information Retrieval Protocols
(with Richard Beigel and Lance Fortnow),
*Computational Complexity*. Vol 15, No 1, 2006, 82-91. pirlower.PDF - The Multiparty Communication Complexity of Exact-T:
Improved Bounds and New Problems.
(with Richard Beigel and James Glenn),
*Mathematical Foundations of Computer Science*2006. (I post the long version, which is not the same as the conference version. It has more in it.) multicomm.PDF - Lower bounds on the Deterministic
and Quantum Communication Complexity
of HAM(n,a).
(with A. Ambains, A. Srinivasan, A. Utis)
*Proceedings of the 17th International Symposisum on Algorithms (ISAAC)*, 2006. HAM.PDF - Constant Time Parallel Sorting: An Empirical View
(with E. Golub and C. Kruskal)
*Journal of Computer and Systems Science*Vol 67, 2003, pages 63-91. emp-p-sort.PDF, - Some connections between bounded query classes and non-uniform complexity
(with A. Amir and R. Beigel),
*Information and Computation*Vol 186, 2003, 104-139. Earlier Version in CCC90. Link is to long version that is also at eccc archive. NONUNIFORM.PDF - A Survey on Private Information Retrieval
*Bulletin of the European Association for Theoretical Computer Science*Vol 82, February 2004, pages 72-107. Computational Complexity Column. pirsurvey.PDF - When Does a Random Robin Hood Win?
(with E. Golub and A. Srinivasan)
*Theoretical Computer Science*Vol 304, 2003, pages 477-484. robinhood.PDF - Gems in the field of bounded queries.
*Computability and Models*Edited by Cooper and Goncharov. 2003. GEMS.PDF - Automata Techniques for Query Inference Machines
(with G. Hird),
*Annals of Pure and Applied Logic*Vol. 117, 171-203, 2002. AUT-TECH-QUERY-INF.PDF Earlier version in COLT95, with title*Reduction in Learning via Queries* - Max and min limiters
(with James Owings and Georgia Martin),
*Archives of Mathematical Logic*Vol. 41, 2002, pp 483-495. MAX-MIN-DELIM.PDF - AHA: An Illuminating Perspective.
(With Dan Garcia and David Ginat)
*Thirty third annual SIGCSE Technical Symposium on Computer Science Education*, Feb 2002. (AHA.PDF) - The P=?NP Poll.
*SIGACT NEWS*2002. Complexity Theory Column. POLL.PDF - The Communication Complexity of Enumeration, Elimination, and Selection
(with Andris Ambainis, Harry Buhrman, Bala Kalyanasundaram, Leen Torenvliet)
Vol 63., pages 148-185, 2001.
(Special issue for COMPLEXITY 2000).
COMM.PDF
- A Survey of Constant Time Parallel Sorting,
for
*Bulletin of the European Association for Theoretical Computer Science*(with Evan Golub and Clyde Kruskal), Vol 72, pages 84-102, October 2000, Computational Complexity Column. SURVEY-CONST-TIME-SORTING.PDF - Squares in a Square: An On-line question
(with A.Ambainis).
Geocombinatorics,
Vol X, No 1, 2000
SQUARES.PDF.
- Computability,
*Handbook of Discrete and Combinatorial Mathematics*. Edited by Kenneth Rosen. Published by CRC Press (Boca Raton, Florida). COMPUT.PDF - The Complexity of ODD(n,A)
(with R. Beigel, M. Kummer, G. Martin, T. McNichol, and F. Stephan)
*Journal of Symbolic Logic*, Vol. 65, 1-18, 2000. Earlier Version in MFCS96. ODD.PDF - A techniques-oriented survey of bounded queries.
(with Frank Stephan).
*Models and Computability (invited papers from Logic Colloquium '97)*(Lecture Note Series 259), Editted by Cooper and Truss. London Mathematical Society 117-156, 1999. Forschungsberichte Mathematische Logik 32 / 1998, Mathematisches Institut, Universitaet Heidelberg, Heidelberg, 1998. BDQ-SURVEY-TECH.PDF - On the Number of Automorphisms of a Graph
(with R. Beals, R. Chang and J. Toran),
*Chicago Journal of Theory*. Feburary 1999. Earlier version in CCC95. NUMAUTO.PDF - When can one load a set of dice so that the sum is uniformily distributed?
(with C. Kruskal)
*Mathematics Magazine*. Vol. 72, No. 2, 1999, pp 133-138. DICE.PDF - A Survey of Recursive Combinatorics.
*Handbook of Recursive Mathematics Volume 2*. Edited by Ershov, Goncharov, Marek, Nerode, and Remmel. 1998. Pages 1041-1176. Published by Elsevier RCOMBSUR.PDF - Addition in lg(n) + O(1) Steps on Average: A Simple Analysis
(with R. Beigel, M. Li, L. Zhang),
*Theoretical Computer Science*. Vol 191, 1998, 245-248. ADD.PDF - Recursion theory and Reverse Mathematics
(with Jeffery Hirst).
*Mathematical Logic Quarterly*. Vol. 44, 1998, 465-473. RR.PDF - On the Finiteness of the Recursive
Chromatic Number
(with A. Lee).
*Annals of Pure and Applied Logic*Vol. 93, 73-81, 1998. FINITE-REC-CHROM-NUMBER.PDF - Classification via Information
(with M. Plezskoch, M. Velauthapillai, and F. Stephan),
*Annals of Mathematics and Artificial Intelligence*. Vol. 23, 147-168, 1998. CLASSIFICATION.PDF Earlier version in ALT94. - Relative Sizes of Learnable Sets
(with L. Fortnow, R. Freivalds, M. Kummer, S. Kurtz, C. Smith, and F. Stephan),
*Theoretical Computer Science*Vol 197(1-2):139-156, 1998. Earlier version in ICALP95 with the name*Measure, Category, and Learning Theory*MEASURE.PDF - Bounded Queries in Recursion Theory
(With Georgia Martin).
Birkhauser. 1998.
- Bounded Queries and Approximation
(with R. Chang and C. Lund),
*SIAM Journal of Computing*, Vol. 26, 1997, 188-209 BDQAPPROX.PDF Earlier version in FOCS93 did not have Lund as co-author. - Implementing WS1S via Finite Finite Automata.
*Automata Implementation*. (with James Glenn) In*Workshop on Implementing Automata-1996*Edited by Raymond, Wood, and Yu. Lecture Notes in Computer Science 1260. 1997 WIA96.PDF - Binary search and recursive graph problems
(with K. Guimaraes)
*Theoretical Computer Science*Vol 181, 1997, 119-139. (Special issue for LATIN 95 conference). BINARY.PDF Subsumeds the conference papers*On the number of components of a recursive graph*from LATIN 92. and*Unbounded search and recursive graphs*from LATIN 95. - Asking Questions Versus Verifiability
(with M. Velauthapillai),
*Fundamenta Informaticae*Vol. 30, 1-9, 1997 VERIFY.PDF Earlier version in AII92. - A Survey of Inductive Inference with an Emphasis
on Learning via Queries (with C. Smith).
*Complexity, Logic, and Recursion Theory*. Edited by A. Sorbi. Published by M. Dekker. Volume 187. 1997. LVQSUR.PDF. - The Complexity of Problems,
*Advances in Computers Volume 43*. Edited by Marvin Zelkowitz. Published by Academic Press. 1996. COMPLEXITY.PDF - Frequencey Computation and Bounded Queries
(with R. Beigel and E. Kinber)
*Theoretical Computer Science*, Vol. 163, 1996, 177-192. Earlier version in CCC95. BDQFREQ.PDF - Learning via Queries with Teams and Anomalies
(with E. Kinber, M. Pleszkoch, C. Smith, and T. Zeugmann),
*Fundamenta Informaticae*, Vol. 23, Number 1, May 1995, pp. 67-89. LVQTEAMS.PDF Earlier version in COLT90. - Recursion theoretic models of learning: some results and intuitions,
(with C. Smith)
*Annals of Mathematics and Artificial Intelligence*, Vol. 15, II, 1995, pp. 155-166. MODELS.PDF - OptP-Completeness as the Normal Behavior of NP-Complete
Problems (with M. Krentel and K. Rappoport),
*Math Systems Theory*, Vol. 28, 1995, 487-514 BDQOPT.PDF - Extremes in the Degrees of Inferability
(with
L. Fortnow,
S. Jain,
E. Kinber,
M. Kummer,
S. Kurtz,
M. Pleszkoch,
T. Slaman,
F. Stephan,
R. Solovay),
*Annals of Pure and Applied Logic*, Vol. 66, 1994, pp. 231-276. EXTREMES.PDF Subsumes both*Learning via Queries to an Oracle*from COLT89 and*Degrees of Inferability*from COLT92. - On Honest Polynomial Reductions and P=NP
(with R. Downey, and M. Moses),
*Annals of Pure and Applied Logic*, Vol. 70, 1994, pp. 1-27. Earlier version in CCC89. HONEST.PDF (The version on line is the CCC89 version.) - Terse, Superterse, and Verbose Sets (with R. Beigel,
J. Gill, and J. Owings),
*Information and Computation*, Vol. 103, 1993, pp. 68-85, 1993. BDQTERSE.PDF - On Checking Versus Evaluation of Multiple Queries
(with Lane Hemachandra and Albrech Hoene),
*Information and Computation*, Vol. 105, 1993, pp. 72-93. CHECK.PDF Earlier version in MFCS90. - Index Sets in Recursive Combinatorics
(with G. Martin),
*Logical Methods (In honor of Anil Nerodes's Sixtieth Birthday)*. Edited by Crossley, Remmel, Shore, and Sweedler. 1993. Edited by Birkhaeuser, Boston. - Learning via Queries to [+,<]
(with M. Pleszkoch and R. Solovay),
*Journal of Symbolic Logic*, LVQPLUS.PDF Earlier version in COLT90 - Learning Programs with an Easy to Calculate Set of Errors
(with Rameshkumar Sitarman, C. Smith, and
Mahendran Velauthapillai),
*Fundamentica Informaticae*, Vol. 16, No. 3-4, pp. 355-370, 1992. ERRORS.PDF Earlier version appearedin COLT88 and AII89. - Learning via Queries (with C. Smith),
*Journal of the Association of Computing Machinery*, Vol. 39, 1992, pp. 649-675. LVQ.PDF, Earlier versions appeared at COLT88 and FOCS88. - Selection Problems using m-ary queries (with K. Guimaraes
and J. Purtilo),
*Computational Complexity*, Vol. 2, 1992, pp. 256-276. ARITY.PDF - The Mapmaker's Dilemma (with R. Beigel),
*Discrete Applied Math (Special Issue on Theoretical Computer Science)*, Vol. 34, 1991, pp. 37-48. MAP.PDF - On Selecting the k Largest with Restricted Quadratic Queries,
*Information Processing Letters*, Vol. 38, 1991, pp. 193-195. - A Survey of Bounded Queries in Recursion Theory,
*Sixth Annual Conferences on Structure in Complexity Theory*, Chicago, June 1991. BDQSUR.PDF - Training Sequences (with D. Angluin and C. Smith),
*Theoretical Computer Science*, Vol. 66, 1989, pp. 255-272. TRAINING.PDF Earlier version without Angluin at AII86 was called*On the inference of sequences of functions* - On the Complexity of Finding the Chromatic Number of a Recursive Graph I:
The Bounded Case (with R. Beigel),
*Annals of Pure and Applied Logic*, Vol. 45, 1989, pp. 1-38. FINDCHROMNUMBER1.PDF - On the Complexity of Finding the Chromatic Number of a Recursive Graph II:
The Unbounded Case (with R. Beigel),
*Annals of Pure and Applied Logic*, Vol. 45, 1989, pp. 227-247. FINDCHROMNUMBER2.PDF - Bounded Query Classes and the Difference Hierarchy
(with R. Beigel and L. Hay),
*Archive for Math. Logic*, Vol. 29, 1989, pp. 69-84. BDQDIFF.PDF - Nondeterministic Bounded Query Reducibilities (with R. Beigel,
and J. Owings),
*Annals of Pure and Applied Logic*, Vol. 41, 1989, pp. 107-118. BDQ-NONDET.PDF - Polynomial Terse Sets (with A. Amir),
*Information and Computation*, Vol. 77, No. 1, 1988, pp. 37-56. Earlier version in CCC87. AMIRGASARCH.PDF - Oracles for Deterministic vs. Alternating Classes,
*SIAM Journal of Computing*, Vol. 16, Aug 1987, pp. 613-627. ORACLESEVSSIG.PDF - Oracles: Three New Results.
*Marcel Dekker Lecture Notes in Pure and Applied Mathematics Vol. 106*, Edited by D.W. Kueker, E.G.K. Lopez-Escobar, and C.H. Smith, 1987, pp. 219-252. - Relativizations Comparing NP and Exponential Time (with S. Homer),
*Information and Control*, Vol. 58, July 1983, pp. 88-100. ORACLESEVSNP.PDF