bio | website | |
---|---|---|
location | cincinnati | |
age | ||
visits | member for | 5 years, 7 months |
seen | Feb 26 '10 at 18:39 | |
stats | profile views | 159 |
[[[ how to put line breaks into geetxt profiles is ummm for brand new gmail user. anyone who knows how please send me email ]]]
(gre scores 800M 800V 780A, and proud of them)
The first sublinear string matching algorithm, for the average case, was invented by me as far as I know. Commercially available in 1985, GMACS, GCLISP, from Gold Hill Computers. Finally published at CPM98, with two frenchmen. China uses it to filter emails. Some americans maybe can use it to connect the dots...
Also may be good basis for hunting virusses in networks faster than they may be able to spread.
I also designed some pentium register sets and cache memory circuits for hardware emulation, at Quickturn Design Systems, in the early nineties. Intel was our main customer.
I wrote an NlogN vison system for Cardiff Software, in the mid nineties. The "PLUS" vision system partitions images into four parts, then does vision on each of the four parts, and links up results in linear time. The key was a vector that grew with a fibonacci ratio.
I wrote Stanford Qlisp (parallel lisp) in the late eighties. The key parts for load balancing were the log high local task stacks, and the idle cycle that used one word of memory to begin at successor location of last. Locally LIFO globally FIFO. Good for many types of real resource allocation, including gasoline and number supplies at banks, with very low overhead.
The Cardinal Equivalence Theorem and followups are the area that I have worked on for the last decade.
Sep
24 |
awarded | Autobiographer |
Feb
26 |
comment |
Formalizing “no junk, no confusion”
The Plus Transfrom gave a nearly equivalent english phrase; but the minus votes indicate an error somewhere...hmmm. "monotone" does also include formulas where every proposition is negative; however, I considered that presentation to be confusing junk, in a simple propositional formalism... I use monotone formulas for loop management in complex programs that solve QBFs; "correctness and clarity" are both of the utmost importance in such programs. Correctness is related to "no junk" and "clarity" allows code maintenance and improvements. Removing negation is standard treatment for me. |
Feb
23 |
answered | Formalizing “no junk, no confusion” |
Feb
18 |
answered | Cryptomorphisms |
Jan
30 |
awarded | Teacher |
Jan
29 |
revised |
The shortest path in first passage percolation
Far Corner variant of Midway. Edges length 1, zero fractions. |
Jan
28 |
answered | The shortest path in first passage percolation |
Jan
25 |
answered | Can you prove equivalence without being able to calculate it? |
Jan
25 |
comment |
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.
Aside about answering qbfs: any boolean formula P, given an order, has a related monotone formula Q, for correctly answering all 2^n quantifications of P. The size of Q is only well understood for 2cnfs and formulas that are already monotone. For 2cnf Ps, the size is identical to the size of (P + all resolutions). When P is already monotone, that Is the Q formula. I have not yet looked at variable swapping, for either 2qbfs, or for monotone formulas. Those two solvable cases would be a good place to begin to study variable swaps. |
Jan
25 |
comment |
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.
thank you darsh. I editted the original; question Two: Linear Corollary: Quantified monotone boolean formulas are linearly decidable. (hunting for any previous name) On importance: Equivalence between complexity classes, where few equivalences are known, is important. After good names are given, identitys become easier to apply. Variable order area is where future research lays. The Cardinal Equivalenece provides that the number of valid quantifications remains invariant after shuffling variables; but details about valid quantifications after any swap are a mystery. |
Jan
22 |
revised |
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.
simplified the question and presentation. Added corollary question. |
Jan
21 |
awarded | Editor |
Jan
21 |
revised |
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.
added 3 characters in body |
Jan
21 |
revised |
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.
deleted 2 characters in body; edited tags |
Jan
21 |
asked | cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. |