William Wu

Bio

This is an old site that advertises some of the research I did while I was a graduate student at Stanford. Currently I work at Quantitative Engineering Design (QED), a small company I co-founded that builds technology solutions for various industrial clients, mostly in the areas of machine learning, signal processing, and scientific computing. Previously I was affiliated with the NASA/Jet Propulsion Laboratory as a telecommunications engineer and researcher.

Some of my interests include signal processing, communications, combinatorics, probability, optimization, and Mathematica. I also dabble in web consulting and tutoring. You may enjoy wuriddles.com, a website of recreational math puzzles.

I am forever indebted to the support of the Frank H. and Eva Buck Foundation, without which my studies would not have been possible.

Ph.D. Electrical Engineering, Stanford University
- Principal advisor: Brad Osgood
- Associate advisors: John Gill, Thomas Cover
M.S. Mathematics, Stanford University
M.S. Electrical Engineering, Stanford University
B.S. Electrical Eng. and Computer Science, UC Berkeley

For a more personal site that you can waste a lot of time at, click here.

Curriculum Vitae

Click here for my CV.

Research

Note: Needs to be updated.

publication list

Universal Interpolating Systems for Bandlimited Spaces. Osgood, B.; Siripuram, A.; Wu, W. Submitted to IEEE Transactions on Information Theory.
FIND-SS: a fast algorithm for sparse matrix computations related to inversion. Li, S.; Wu, W. Submitted to Journal of Computational Physics.
Verifying 100 Prisoners and a Light Bulb. Ditsmarch, H.; Eijck, J.; Wu, W. JANCL 2010 (Journal of Applied Non-Classical Logics).
Twenty Questions Games Always End With Yes. Wu, W.; Gill, John T. JPL IPN Progress Reports, August 15, 2011.
Delay-Rate Tradeoff for Ergodic Interference Alignment In the Gaussian Case. Koo, Joseph; Wu, W.; Gill, John T. Allerton 2010.
Measurement-Based Channel Management in WLANs. Liu Y.; Wu, W.; Bo, W.. IEEE Wireless Communications and Networking Conference 2010.
100 Prisoners and a Light Bulb -- Logic and Computation. Ditsmarch, H.; Eijck, J.; Wu, W. KR 2010 (Principles of Knowledge, Representation, and Reasoning).
Falling Factorials, Generating Functions, and Conjoint Ranking Tables. Wu, W.; Osgood, B. Journal of Integer Sequences, Vol. 12, 2009, Article 09.7.8.
Dynamic Channel Assignment in Wireless LANs. Bo, W.; Wu, W.; Liu, Y. Power Electronics and Intelligent Transportation Systems (PEITS), 2008.

In preparation:

Discrete Sampling. (Ph.D. Thesis dissertation) Wu, W.; Osgood, B.
Geometry and Algebra of Intersecting Bezier Curves. Wu, W.; Osgood, B.
100 Prisoners and a Light Bulb (algorithms and analyses). Online manuscript. Wu, W.

signal processing

Discrete Sampling

My dissertation research under the direction of Professor Brad Osgood is about a different approach to the sampling and reconstruction of discrete signals. Our work can be thought of as finding analogues to the Nyquist-Shannon Sampling Theorem in different situations.

Our ultimate goal is to develop practical applications in areas such as medical imaging, spectroscopy, and circuits. More details forthcoming.

Wu, William; Osgood, Brad. Discrete Sampling. (PhD defense completed; dissertation to be released. Abstract available here.)

communications engineering

Optimization of Wireless Local Area Networks

The rapid deployment of high density wireless LANs poses many new challenges for network management, such as the dynamic channel assignment problem. Since cell sizes in WLANs are so small, it is common for traffic statistics to fluctuate significantly as users move from one cell to another. Thus, by dynamically assigning the wireless frequency channels used by different access points, network throughput can be optimized. The channel assignment is made based on periodically updated signal and traffic measurements, which are then piped into an interference model that assigns weights to a graph, and finally a semidefinite program is used to solve the max k-cut problem on that graph. Our experiments on a real-world 500 square-meter testbed demonstrate average throughput increases of up to 40%.

This is joint work in collaboration with NEC Research Labs in Beijing, China, where I worked for a summer while participating in the Stanford-Tsinghua Engineering Exchange Program.

Liu, Yongqiang; Wu, William; Wang, Bo; et al. Measurement-Based Channel Assignment in WLANs. IEEE Wireless Communications and Networking Conference 2010.
Wang, Bo; Wu, William; Liu, Yongqiang. Dynamic Channel Assignment in Wireless LANs. IEEE Power Electronics and Intelligent Transportation Systems, 2008.
- Local paper copy: click here
- Presentation slides: click here
Wu, William; Chen, Jiehua.. SCP-Based Channel Assignment. (In progress. I would like someone to implement our algorithms on a real WLAN testbed and evaluate the performance, so that we can strengthen the paper. If you are interested, please contact me.)

combinatorics

Combinatorics of Falling Factorials

Question: What do the Fourier uncertainty principle, Stirling numbers, and the EE Quals have in common?

Answer: Falling factorials.

We investigate the coefficients $c_{l,m}^{(k)}$ generated by expressing the falling factorial $(xy)^{falling k}$ as a linear combination of falling factorial products $(xy)^{falling k) = \sum_{1 \leq l,m \leq k} c_{l,m}^{(k)} x^{falling l} y^{falling m}$ . Algebraic and combinatorial properties of these coefficients are discussed, in relation to Stirling numbers, binomial coefficients, and generating functions for conjoint ranking tables.

Wu, William; Osgood, Brad. Falling Factorials, Generating Functions, and Conjoint Ranking Tables. Journal of Integer Sequences, Vol. 12 (2009), Article 09.7.8.
- Local paper copy: click here
- Presentation slides: click here

information theory

Twenty Questions Games Always End With "YES!"

In information theory courses, Huffman coding is often presented as the optimal strategy for playing the classic parlor game of Twenty Questions. However, Thomas Cover observed the following caveat in the 1990s: Twenty Questions games always end with a reply of "Yes," whereas Huffman codewords need not obey this constraint. wyld stallyns In this short and cute paper, John T. Gill III brings resolution to this issue, and proves that even in games of Twenty Questions, the relationship between the average number of questions and the entropy still remains the same. As Forrest Gump would say, "One less thing to worry about."

Gill, John T.; Wu, William. Twenty Questions Games Always End With Yes.
- Watch the best 20 Questions game ever: click here

Interference Alignment

The theory of interference alignment introduced by Cadambe and Jafar expanded the region of known achievable rates for wireless interference channels. Nazer, Gastpar, Jafar, and Vishwanath examined interference alignment in the ergodic setting, in which the key idea is to wait for pairs of channel realizations which, upon summation, cancel out the off-diagonal interference components. We expand on ergodic interference alignment by considering larger collections of channel realizations which have the interference cancellation property, and formulating the corresponding delay-rate tradeoff. Mathematical techniques employed include Markov chains, coupon collection, and combinatorics.

This is joint work with principal investigator Joseph Koo and John T. Gill III.

Koo, Joseph; Wu, William; Gill, John T. Delay-Rate Tradeoff for Ergodic Interference Alignment in the Gaussian Case. In preparation for Allerton 2010.

puzzles

100 Prisoners And a Light Bulb

"One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst each other. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The prisoner will be able to observe the current state of the light bulb. If he wishes, he can toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a protocol that will guarantee their freedom?"

Working with the combined efforts of many members of [wu:forums] since 2002, we have embarked on a never-ending journey to find new more efficient algorithms and protocols for solving the 100 prisoners and a light bulb riddle, most of which are not well-known. In an investigation with collaborators Hans van Ditmarsch and Jan van Eijck, we show how the riddle can be studied using dynamic epistemic logic.

van Ditmarsch, Hans; van Eijck, Jan; Wu, William. 100 Prisoners and a Light Bulb: Logic and Computation. KR 2010 (Principles of Knowledge, Representation, and Reasoning). For a preprint that has more details (but does not fit the page limits of KR), check this out.
Wu, William. 100 Prisoners and a Light Bulb. Online document uploaded in 2002; since then, it has been referenced in several places. A never-ending work in progress with no submission plans, but if you have suggestions, feel free.
- Programmed simulation of 100 Prisoners: click here

geometry

Geometry and Algebra of Bezier Curves

This has been an ongoing research project for years now. We have been stuck on one last proof for a long time. If you are an expert in the number theory of binomial coefficients and are interested in publishing a paper, contact us!

Joint work with Brad Osgood and Summer 2009 EE REU student Justin Hsu.

Wu, William; Osgood, Brad. Geometry and Algebra of Bezier Curves. (in progress)

Teaching

University Teaching

I served as head Teaching Assistant (TA) for EE376A: Information Theory at Stanford University during the Winter 2008-2009 quarter, taught by Professor Thomas Cover. eit The course covered Chapters 1 through 9 of Elements of Information Theory. TA responsibilities included office hours, managing graders, review sessions, handouts, exams, errata, improving old solutions, and redesigning the course website.

Below are some of the extra materials I wrote while serving as a TA.

About Claude Shannon. Accomplishments, life, and legacy of Shannon.
Midterm Review. Information theory algebra, AEP, entropy rate, 2nd Law of Thermodynamics, gambling, data compression.
Final Review. High-level review of EE376A, Kolmogorov complexity, inequalities, channel capacity, gaussian channel capacity.
Random Numbers. All students were asked to write down a number less than 10. A statistical analysis of the results is performed. Special thanks to Jiehua Chen for her expert assistance with this.

Teaching evaluation survey results. I received the Hugh Hildreth Skilling teaching award from the EE department that year.

TA survey results

Mathematics Tutoring

I have served as a math tutor since 2002 in the California Bay Area and New York City, both privately and in tandem with university-affiliated tutoring organizations such as SUMO at Stanford and TBP at UC Berkeley. I have tutored a wide variety of subjects, including:

Test Prep: SAT Math, ACT Math, GMAT Math, SAT II Math, GRE Math
High School: prealgebra, algebra, geometry, trigonometry, calculus, AP Physics
College Math: single and multivariable calculus, linear algebra, ordinary differential equations, probability, statistics
Advanced Math: real analysis, complex analysis, probability theory, stochastic processes, signal processing, fourier analysis, PDEs, group theory, discrete math and combinatorics, linear systems
Mathematical Programming: MATLAB, Mathematica, LaTeX
Consulting: Solutions to particular problems on a per need basis.

I take students at all levels and from all walks of life, including working professionals such as engineers and police officers, graduate students pursuing advanced degrees in finance and economics, and undergraduates taking calculus.

I have also designed many customized curricula for gifted high school students who have run out of math classes to take at their local junior high or high school, and unfortunately are often restricted by the bureaucracy from taking the most advanced courses due to their year or age. Call me crazy, but based on my experience, the chances of finding a better tutor than me to fill this void are slim to none. For a few samples of lesson plans I've made for advanced students, see here:

If you are interested in my services, please e-mail me at wu AT themathpath DOT com.

Technical Workshops

I am available to give interactive workshops for industry on any of the following topics:

programming in mathematica
programming in matlab
introduction to network coding
elementary probability theory
introductory real analysis
learn to juggle in an hour (or two)

A sample of the presentation quality that can be expected from these tutorials can be seen in the following slides.

Web Design

A fuller portfolio is available here, although this also has been redacted for confidentiality reasons. I have also built sites for researchers and private institutions.

wuriddles.com / http://www.ocf.berkeley.edu/~wwu/riddles: One of the net's best resources for serious mathematical puzzles. Includes an active forum with +10,000 registered members and daily problem-solving discussions. Math markup is now also available. Featured on slashdot, the MENSA journal, and the best selling book How Would You Move Mount Fuji? by William Poundstone.
wuism.net / http://www.ocf.berkeley.edu/~wwu: A personal site hosting various webpages I made while in undergrad; you may find something interesting.

Hobbies

juggling	tutoring	web design	nunchaku

drawing and fractal art	skating	emulation	reading
$blue rose fractal$

Contact Information

email: willywu AT alumni DOT stanford DOT edu