parsimony and linguistics ------------------------- A friend told me about a problem of inferring likely root words given * a set of transformations * a corpus of current words this is a linguistics thing. I wonder if this paper helps DAY W.H.E., JOHNSON D., SANKOFF D., The computational complexity of inferring rooted phylogenies by parsimony, Mathematical Biosciences, 81, pp.33-42, 1986 Can you reconstruct what linguists agree is "indo-european" from some common rule? of human bondage ---------------- It's a coincidence that I'm reading this book now, with its descriptions of a man taken over by love, doing things he knows are unwise solely in order to get a glimpse of the one he loves. "If you loved me half as much as I loved you..." -- shown in its agony. The amazing thing here is the offhandedness , the matter of fact with which it is written. Perhaps this is a book that could stand updating without too much trouble, while a more effusive effort could trip and fall on its own misplaced sentiment. rsr, self-reducibility, incomplete sets --------------------------------------- If a set is rsr, then it is tt-self-reducible (working out the definitions) If a set A is sparse and both A and coA are tt-self-reducible, then A is in P. Therefore no sparse set can be PSPACE complete. question: assuming existence of sparse set in PSPACE - P, can this set be rsr? answer: not if its complement is rsr. so, to show: that the sparse set implied by NEXP != EXP would be in P if it were tt-self-reducible. therefore cannot be rsr. Ladner sets are not "uniformly hard" - i.e. they have arbitrarily long stretches in which they look like the empty set and then like SAT. show that this precludes rsr? well, say that if they were tt-self-reducible, would need to hit different distributions for the empty and for the non-empty portions? incomplete sets in NP and PH ---------------------------- * ladner sets * NP intersect coNP (not complete for NP) * BPP ? * sparse sets more? nag --- That I'll turn out like the burned girl from _Girl, Interrupted_. You know the one I mean; the one who realized one day just what she'd lost. whassup? -------- "are you in a weird mood?" Funny how the minute I try to be informal, that's the question I get. :) tlon, uqbar, arora, sudan ------------------------- The genius of Borges' "Tlon, Uqbar, Orbius Tertius" is not the description of the fictional world of Tlon, but instead the description of the fictionalization of the 'real' world by Tlon. That is, what is important in the story is the idea of introducing a perfect fake; that it happens to take the form of an encyclopedia of a fictional world is of only secondary consequence, perhaps making it more attractive to a certain kind of fiction reader (who might nowadays be found pursuing the Wheel of Time or memorizing Tolkienian genealogies). so there is this idea of being able to reconstruct an entire object given only a few samples, randomly chosen, of its parts. or if not reconstruct, then at least test the validity of. so what kind of story would illustrate the power of *this* idea? or what Bellare's course calls "the zero knowledge perspective" ? undead elmo and new york subways -------------------------------- (unlike other entries here, doesn't even try to be mathy. maybe I'm giving up) ok, thought about this on and off for a while. HRSFA has a mascot, Undead Elmo. So named because it survived a fire and still says the same silly Undead Elmo things. On the subway some weeks ago, I saw "ELMO" scratched on one of the windows. In NYC cabs, I often end up being greeted by Elmo's version of the "buckle up" public service announcements. "Elmo wants you to be SAFE! So buckle up!" and "Remember to get a receipt! What's a receipt?" trying to trade on Elmo's naivete and childish aspect. These public service announcements raise an uncanny anger in me; they are annoying enough to make me wonder, only briefly, about the possibility of ripping the speaker apart with my bare hands. A primal source of annoyance. Add to this the connection between the "undead Elmo" which lies in wait until the correct circumstance, and the inimations of an ELMO CULT in the subways, and we have "UNDEAD ELMO LIES DREAMING BENEATH THE SUBWAYS OF NEW YORK UNTIL THE SCHEDULES ARE RIGHT WHEN HE WILL ARISE AND DEMAND DEFINITIONS OF RECEIPTS" or maybe just DEVOUR US ALL safe queries and complexity theory ---------------------------------- * characterize queries possible with FO + = on blocks * show equivalence between this and, say, starfree regular languages * find properties not expressible in this language (EF games) * Go one level up, see if that's a good idea or not * Explicitly relate predicates expressible to information acheivable * Rule hiding problem is NP-complete, but this is all-or-nothing privacy enhancing technologies ------------------------------- Paper submission due in December. Better write about something. What? - Blinded recipient-hiding encryption ? - Multiple TTP donations? (that's for FC) - Experiments with practice on alt.anonymous.messages? - Stats and experiments with filesharing? - Anonymity and multicast? (Build off limited connectivity model?) seminars to look at ------------------- http://www.qci.jst.go.jp/erato/seminar/innerseminar/tokyo/01-tokyo.html the weird result I'd like 08.08.01 ---------------------------------- We know that SZK = HVSZK , but the proof requires a conversion from private-coin to public-coin proofs. This conversion blows up the number of rounds by a ridiculous amount. Worse, no strong black-box conversion can do better, thanks to Vadhan's results! So the weird thing I'd like to see * a robust definition of private-coin protocol * in order to give a nonconstructive proof of equivalence without the round blowup (i.e. for all n-round private coin protocols there are equivalent O(n)-round public coin protocols) * and a proof-theoretic result about independence for tighter and tighter equivalencies. i.e. getting exact equivalence is equivalent to separation of PH way up, but P != NP ok for a start. is this even true? who knows. That's the problem right now. You could probably enumerate the public-coin protocols? All public-coin protocols have similar looking transcripts... see http://www.math.psu.edu/simpson/fom/postings/0008/msg00011.html http://www.math.psu.edu/simpson/fom/postings/0008/msg00012.html for "nonconstructive existence proofs of algorithms" book lists 08.06.01 ------------------- Amazon has a book list feature. Maybe I should take advantage of this. arithmetization, kriesel, PCP 08.06.01 -------------------------------------- My copy of Benacerraf & Putnam's edited essays on phil of mathematics has an article by Georg Kriesel on "Hilbert's Programme." * Looking for a notion of "Proof fragility" - motivated by FOM list discussions concerning the ability of mathematicians to tell if a proof will work or not. fill gaps, fix minor errors, etc. Mathematician "Intuition." - ANY formal way to treat this? An informal recounting of psychology of proof-fixing doesn't seem that interesting. (As pointed out by A. Urquhart's message, "intuition" can lead us astray by wishful thinking. I also read his e-mail as a parody of the near worshipful tone or wondering tone taken sometimes by these discussions.) - PCP has proof fragility notion - pick random places in proof and see if it works. - how many places can you pick before it's wrong? - the massive, massive formatting problem with PCPs - who would understand a proof of 1+1 = 2 as a PCP? - more to the point, no one writes PCP natively - even more, we want robust proofs, not fragile ones! * Arithmetization's role in Goedel's proof and in the PCP theorem - when could we have had PCP?" alex healy's question about NPI behavior 08.06.01 ------------------------------------------------- Alex Healy also asks an interesting question about the behavior of incomplete sets in NP - P. Denote by NPI the set of languages neither in P nor NP-complete. Such sets exist if P != NP. * Is there a maximal p-degree D1 in NPI with NP > D1? * A minimal p-degree D0 in NPI with D0 > P ? (perhaps I have the < > backwards) Note this would not contradict the infinitude of any NPI hierarchy which may exist. alex healy's brainteaser, marraige!, independence 08.06.01 ---------------------------------------------------------- Finally got around to reading a paper written by Alex Healy and sent out to a group of friends. (Including me, which is cool). (BTW, Alex, if you're reading this and object to my including it here, let me know and I'll take it down.) The paper concerns a brainteaser involving auctions. It occurred to me the other day that I'd seen a similar problem before. Adriana Karagiozova had mentioned it to me as the "marraige problem." You date women one after the other; at some point you must stop and pick one to marry. How do you maximize your chance of marrying the "best" woman? (i.e. you get numbers n1, n2, n3, ... and at each number can decide to stop or to continue...but you don't get any number again). The difference between the two problems is that in Alex's version, the number of numbers is finite and fixed (if I read correctly). In the marraige problem, the number is not necessarily finite. well, in real life it is, because we all die. but suppose a monogamous immortal wanted to play the marraige game. Yet the strategy for the two is the same. Does the infinitude of the marraige variation make a difference? What about a variant of the game in which you play infinitely long - you have to pick, then restart the game. Is this any different? What about a tree version, in which you get to pick from three options at each decision point 1) stay 2) go left 3) go right where "left" and "right" have * same * different distributions? Is that the same or different? This problem feels like an appropriate version of it could hit independence results. Now if only I could figure out what. the ruler game (w/Musiker + Schlaifer) revisit 08.06.01 ------------------------------------------------------- This came up back at the end of school. Gregg and Jon and I came up with this during some discussion of Coulomb rulers. I pushed it towards a game because, well, I was and am impressed by Ehrenfeuct-Fraisse games. (It would please me to no end if you can show things are inexpressible by measurement). Two players - the Assigner (A) and the Measurer (M). The Measurer has a straightedge which will become a ruler by having marks placed on it. The Assigner then pi_2 hard importance, recursion theory, complexity theory 08.04.01 ------------------------------------------------------------------ * Hartmanis paper on "Importance of being Pi_2 hard" * Shows that property of "accepts language in NP - P" is Pi_2 hard * Shows a list of machines with property can't be r.e. or build Sigma_2 set -- and Sigma_2 != Pi_2 provably in recursion theory * Now show that NP-complete sets are r.e. ! * Result: complexity theoretic result from recursion theory. * What about using this to get incompleteness results all the way up the polynomial time hierarchy? NP - P is Sigma_1 - Sigma_0 now Sigma_2 - Pi_1 would be EA - coNP - show property is like Pi_3 hard - show that list of machines can't be r.e. or Sigma_3 - show SigmaP_2 complete sets are r.e. (can this be done?) (or do we need to go "up"?) cramer-shoup revisit 08.04.01 ----------------------------- As usual, I made a mistake. it's not obvious that the cramer-shoup signature scheme proof needs the parameter e to be B-smooth. I don't even know how I came up with that idea. The good news is that it seems that maybe you need is the product of n numbers e1...en to be relatively prime to phi(n) = p-1 q-1. where you don't know phi(n). or at least, that the size of the largest factor in such a product should not be too large. Now if n is a Germain prime, then phi(n) is 4p'q', so you're ok. wait, could you test (e, phi(n)) by taking a^e mod n and seeing if it's 1? ah, but e has only a factor. so that won't work. To look at : the probability two numbers are relatively prime, and maybe the distribution of their largest common factor? This is where mathematica comes in handy! fast generation of non-smooth numbers 07.24.01 ---------------------------------------------- Cramer-Shoup signatures require generation of a new prime p for each signature. This is because their proof for "type III forgery" requires that a certain parameter not be B-smooth for a bound B. Primes certainly aren't smooth in this sense, as they have no factors other than themselves and 1. So Cramer and Shoup spend a lot of time optimizing the generation of primes in the range required (~63 bits), using deep results due to Bach, Bleichenbacher, and others. Maybe this doesn't scale so well. (Have to check that). Actually, doesn't need to scale unless the hash function gets bigger. Why not just generate a composite number which is sufficiently non-smooth instead? when is this faster or slower than generating new primes? Naive thing to do : go back and figure out what the bound B should be. Then compute the product of all primes < B. Take GCD of that and a candidate number. if GCD 1, pass else fail. How big is that product? it's #of primes * size of each prime so really really loosely upper bounded by something like pi(2^63) * 63 (because B can't be any bigger than the parameter...) which is like 2^63, and so way too big to deal with. Is there a better way to generate non B-smooth numbers? can we find one better than primality testing? is there a crossover point? -- Maybe generate a large set of numbers and take GCDs pairwise with all of them. Reject any with too small factors which show up. Pick randomly from the remaining. -- Create a B-smooth number and add 1 ? what's the chance of being divisible by other primes in that set then? 19 is a special age 07.24.01 ---------------------------- Rebecca turns 19 tomorrow. 19 is a special age - if you write it in binary 10011 (16 + 2 + 1) and cyclic shift right to obtain 11001 you see that 19 shifted right is the same as 19 reversed (in binary). The next age for which this happens is 31 (11111), I think. There are likely lots of other combinatorial properties on ages floating around. Yap's hash problem 07.24.01 --------------------------- Given a set of edges of cardinality n (and that's *all* we know), find a function H which * is a 'evenly distributed output' function in the sense of universal hashing * has vertices as the domain * "preserves vertex relations" - i.e. edges * allows combination of vertices via some quick update, such as + or *. Since function doesn't have to be one-way, maybe look at ax + b chop 1 mod p ... adding 2 values together and subtracting b is "almost" a(x1 + x2) + b mod p More on Ajtai-Dwork 07.24.01 ---------------------------- Nicholas Hopper graciously points out that the error when AD has a complementation property destroys the communication properties of the scheme. Perhaps the OR-homomorphic property can still be salvaged. Perhaps some error correction can be applied. Ajtai-Dwork has an OR-homomorphic property? 07.07.01 ---------------------------------------------------- I have been thinking about homomorphic signature schemes recently, thanks to David Wagner, Rob Johnson, and Dawn Song. This has me thinking - do all public-key schemes give rise to homomorphic functions? RSA and discrete log schemes do. So on to the rest. It seems that Ajtai-Dwork may have an OR-homomorphic property, or maybe even better. The Ajtai-Dwork scheme uses a random vector u as its secret key. u is chosen from a special distribution of lattice vectors, but that doesn't really matter yet. A message x is decrypted by computing the dot product x.u and then we have D(x) = 0 if x.u is "sufficiently close" to an integer 1 otherwise The nice thing here is that the dot product distributes over vector addition. So if we have two vectors x and y, u.(x+y) = u.x + u.y . Now let c_0 be any encryption of 0 and c_1 be any encryption of 1. We'll have u.(c_0 + c_0) = u.c_0 + u.c_0 = an integer + a small error u.(c_0 + c_1) = an integer + a large error u.(c_1 + c_1) = an integer + some error which could maybe be engineered to be less than 1? if that all works out, it gives us the truth table 0 O 0 0 1 O 0 1 1 O 1 1 for the operation O Alex Healy notes that if we can get NOT on top of that, then we'd really be in business. Suppose we publish a vector f and guarantee that u.f is equal to some integer n_f + e_f, with e_f = delta. and fix delta = 0.5 Then c_0 + f = c_1 and c_1 + f = c_0. Of course this probably screws up the encryption error or something. Maybe an alternative is to fix it so that 1 O 1 = 0, which would give us an XOR. There's got to be a reason why this fails miserably. Otherwise an *algebraic cryptosystem* would have been sitting under our noses for four *years*!! Likely what will happen is that it will be impossible to accurately carry out the homomorphic operation more than a constant number of times since the error will mount. (On the other hand, it is possible to rebalance errors here by adding and subtracting f ?) Relation here to Rene Peralta's notion of "certifiable" and "constructible" sets for ZKPs... Papers for "Showing CS to Outsiders" ---------------------------------- I received a message in my inbox asking for papers for a study on communicating what CS is all about to non-CS people. Two things come to mind * Metaphors from CS, their uses, abuses in other fields - aka "what do Turing Machines have to tell us about philosophy of mind?" Indeed, what *DO* Turing Machines have to tell us about philosophy of mind? Besides giving us the "undecidable" as yet another transcendental signifier? - grammars in linguistics and programming languages - Sherry Turkle's work - Penrose and so on. - Hofstadter, too. - JF Traub's "Information based complexity" This whole area bothers me. Someday I'll have to write a screed about the misappropriations of metaphors from computer science. Even when the CS described is *correct* - in contradistinction with Sokal's project of debunking flat out *wrong* math. * A Collection of fun results in tension Everyone always does the undecidability of the halting problem as the introduction to CS. That's nice. It's also very 1930. After Godel Escher Bach, what else is there to do? Why not try something else? Which gives an idea of what could be done now, by you? Outline for a paper I'll probably never write: 0. Intro 1. Proving Negatives By Playing Games - Logic - Expressing properties in logic - Inexpressibility in logic as "proving a negative." - Erenfeuct-Fraisse games and inexpressibility results; use _Descriptive Complexity_ 2. Turning Negatives Into Positives - Cryptography and adversaries - Adversaries limited to specific powers - One-way functions and lower bounds - Pseudo-Random Functions and totally perfect crypto 3. Playing Games Too Well - EF games and lower bounds - Natural Proofs - every lower bound gives a distinguishing algorithm! - "Listen to the proof" - extraction of algorithms from proofs. - Tension between lower bound proof techniques and pseudo-random functions. Paradox? The big question here is whether EF games give rise to natural proofs. 4. Way Out - Oracles - Escape from the "real world" and into "oracle" worlds. Relativize! - P != NP with probability 1 - One-way functions and one-way trapdoor functions - But the RO hypothesis is false! - Non-relativizing results in complexity theory and cryptography - way forward? 5. CS On The Brink (Conclusion) * Fusion of various disciplines * "Meta" - proofs themselves are objects! * "Never Say Die" - not satisfied with "too complex" or "no techniques" * Many results in tension, but that's the fun part! * Problems to Think About Quantum Energy Classes ---------------------- * Chen-Diao paper claims that they achieve an exponentially fast quantum search algorithm, in contradiction to the optimality proofs for Grover's algorithm. "Time-energy tradeoff." They're probably wrong, but. * Is "energy" in this sense a complexity measure in the sense of Blum? * Note - energy is not the same as ink, because energy > time and ink < time. (It takes 1 time unit to overwrite a symbol). - Is there a complexity measure larger than time? "time + 1" A natural complexity measure?