{"id":663,"date":"2011-05-26T19:23:05","date_gmt":"2011-05-27T00:23:05","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=663"},"modified":"2021-09-15T12:00:09","modified_gmt":"2021-09-15T17:00:09","slug":"projects-aplenty","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=663","title":{"rendered":"Projects aplenty"},"content":{"rendered":"

When ambitious students ask me for projects to work on, I usually kick myself for not having a list of favorite open problems that I can simply point them to.\u00a0 Sure, half a year ago I listed some of my favorite open problems in quantum complexity theory<\/a>—but what can I give the majority of students who are more classically-inclined?\u00a0 The following haphazard list is my attempt at an answer.\u00a0 Some of the “problems” are open-ended or ill-defined, some are actually implementation projects, some are no doubt trivial or solved, others are no doubt hopelessly difficult, and a couple are shamelessly filched from MathOverflow<\/a> or CS Theory StackExchange<\/a>.\u00a0 Almost all are missing motivation and context.\u00a0 Without further apologies…<\/em><\/p>\n

1. Create a zoo of cryptographic primitives (one-way functions, one-way permutations, pseudorandom generators, etc.) and the relationships between them, paralleling the Complexity Zoo<\/a>.<\/p>\n

2. Build a public library of 3SAT instances, with as few variables and clauses as possible, that would have noteworthy consequences if solved.\u00a0 (For example, instances encoding the RSA factoring challenges.)\u00a0 Investigate the performance of the best current SAT-solvers on this library.<\/p>\n

3. Find an explicit n (the smaller the better) for which you can prove that the value of BB(n) (the nth<\/sup> Busy Beaver number<\/a>) is independent of ZF set theory.\u00a0 More generally, find a way to enumerate the proofs of ZF set theory, which requires a shorter or simpler program<\/a> than the “obvious” proof-enumerating program.<\/p>\n

4. Call a cellular automaton “physically universal”<\/a> if any polynomial-time transformation on any subset of n bits can be implemented by choosing a suitable initial configuration of the surrounding poly(n) bits.\u00a0 (Note that my definition is potentially more inclusive than Janzing’s.)\u00a0 Find interesting examples of cellular automata that you can prove are or are not physically universal.<\/p>\n

5. Prove explicit lower bounds<\/a> on the number of arithmetic operations needed to compute the permanents and determinants of 3×3 and 4×4 matrices.\u00a0 In the 4×4 case, can you obtain a separation between the permanent and the determinant?<\/p>\n

6. Are there proofs with (say) n2<\/sup> symbols, in a proof system of your choice, for which (a) there exist proofs of the same statements with n symbols, but (b) finding the shorter proofs is computationally intractable?<\/p>\n

7. Call a set of k-by-k unitary matrices U1<\/sub>,…,Uk<\/sub> “linear-optics universal,” if for any n, any n-by-n unitary matrix U, and any \u03b5>0, it’s possible to approximate U to within error \u03b5 by applying some finite set of Ui<\/sub>‘s to various ordered lists of k of the n indices.\u00a0 Give necessary and sufficient conditions for a set of unitaries to be linear-optics universal.<\/p>\n

8. How hard is it to sample a (nearly) uniformly-random n-by-n invertible matrix over GF(2)?\u00a0 Clearly it can be done in matrix multiplication time, but can we give evidence that it can’t be done in less?<\/p>\n

9. Is “collinearity logic” in NP?\u00a0 In other words: given a collection of n points in the Euclidean plane, together with a list of triples of points that should be collinear and a list of triples that should not<\/em> be collinear, is the problem of deciding whether the requirements are consistent in NP?\u00a0 (It follows from known results about the existential theory of reals that this problem is in PSPACE; I thank Peter Shor for that observation.)<\/p>\n

10. Given a weighted bipartite graph, is there a polynomial-time algorithm to decide whether or not there are two perfect matchings with the same weight<\/a>?<\/p>\n

11. Give nontrivial examples of problems that are complete for PromiseBPP.\u00a0 Could approximating the permanent of a nonnegative matrix<\/a> be an example of such a problem?\u00a0 Alternatively, can that problem be solved in randomized NC?<\/p>\n

12. Given an explicit description of a Boolean circuit C of size (say) n3<\/sup>, and promised there exists a circuit of size (say) n2<\/sup> that computes almost the same function as C, how hard is it to find the smaller approximating circuit?\u00a0 Can we give cryptographic evidence that this problem is hard?\u00a0 What additional assumptions about C make the problem easy (ideally, easy for reasons that require looking at the structure of C, rather than just treating it as a black box)?<\/p>\n

13. What is the randomized one-way communication complexity of the Group Membership Problem<\/a> (in which, given a finite group G known to both players, Alice knows a subgroup H\u2264G, Bob knows an element x of G, and Alice’s goal is to send Bob a short message that enables him to decide whether x is in H)?<\/p>\n

14. Study the lower bounds on Manifestly-Orthogonal Tree Size in my paper Multilinear Formulas and Skepticism of Quantum Computing<\/a>.\u00a0 In particular, do these lower bounds evade the Razborov-Rudich natural proofs barrier?<\/p>\n

15. Prove an oracle separation between BPP and PBPNC<\/sup>.\u00a0 (Likewise, prove an oracle separation between BQP and BPPBQNC<\/sup>.)<\/p>\n

16. Are there plausible pseudorandom functions computable by ACC0<\/sup> circuits?<\/p>\n

17. Prove a strong anti-concentration theorem<\/a> for the permanent of a matrix of iid Gaussian entries.<\/p>\n

18. Given the truth table of a Boolean function f:{0,1}n<\/sup>*{0,1}m<\/sup>\u2192{0,1}, are there efficient algorithms to compute (or approximate) the randomized and quantum one-way communication complexities of f?<\/p>\n

19. Classify the possible sets of classical reversible gates acting on bits, by the sets of transformations that they generate.\u00a0 (I.e., what is the analogue of Post’s lattice<\/a> in this setting?)\u00a0 As a warmup, classify the possible sets of classical reversible gates that act linearly over GF(2) (like the NOT and CNOT gates).<\/p>\n

20. Do there exist probability distributions D1<\/sub>,D2<\/sub> over n-bit strings such that (D1<\/sub>2<\/sup>+D2<\/sub>2<\/sup>)\/2 (an equal mixture of two independent samples from D1<\/sub> and two independent samples from D2<\/sub>) is efficiently samplable, even though D1<\/sub> and D2<\/sub> themselves are not<\/em> efficiently samplable?\u00a0 (This is closely-related to a beautiful question posed by Daniel Roy, of whether the de Finetti Theorem<\/a> has a “polynomial-time analogue.”)<\/p>\n

21. Is BB(n) (the nth<\/sup> Busy Beaver number<\/a>) odd infinitely often?\u00a0 Is it decidable whether BB(n) is odd?<\/p>\n

22. Show there are tasks that Turing machines with (d+1)-dimensional tapes can solve polynomially faster than Turing machines with d-dimensional tapes.<\/p>\n

23. Extend my results from A Counterexample to the Generalized Linial-Nisan Conjecture<\/a> to show that \u03a32<\/sub>PA<\/sup> \u2260 \u03a02<\/sub>PA<\/sup> with probability 1, relative to a random oracle A.<\/p>\n

24. Given a function f:[N]\u2192[N], which is promised to be either one-to-one or two-to-one, what’s the optimal MA-protocol for proving f is one-to-one (i.e., what’s the optimal tradeoff<\/a> between the size of the witness and the number of queries needed to verify it)?<\/p>\n","protected":false},"excerpt":{"rendered":"

When ambitious students ask me for projects to work on, I usually kick myself for not having a list of favorite open problems that I can simply point them to.\u00a0 Sure, half a year ago I listed some of my favorite open problems in quantum complexity theory—but what can I give the majority of students […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5],"tags":[],"class_list":["post-663","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=663"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/663\/revisions"}],"predecessor-version":[{"id":5842,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/663\/revisions\/5842"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}