Monday, February 19, 2007

Time and Music

Two quirky computer events over the vacation.

I enter events in my online calendar in Lance-time, i.e., at the time in the time-zone I will be in when the event occurs. Calendar programs don't have Lance-time so I just use Central time. Normally not a really big problem since I just leave the calendar in Central time when I travel. But on this trip I downloaded my calendar to my mobile phone. My mobile phone knows what time-zone I am in so it automatically adjusts the clock (which I like) but also the calendar. So say, an 8 PM flight out of LA, would come up as 6 PM. Software being too smart for its own good.

During my vacation a new folder "Mike's Music" popped up in Itunes. Quite an impressive collection, including the Beatles, CSN&Y and Bruce Springsteen, most of it quite playable. I don't know who you are Mike, or how your music ended up on my machine but thanks for the tunes.

Now that I returned to Chicago the music disappeared without a trace. Go figure.


  1. Hi,

    I guess it is possible, to turn off automatically changing the time zone on a mobile phone. This should solve that issue (if one finds the appropriate switch).

    The iTunes-experience might be explained by other users in the network, sharing their iTunes-library without password.

    best regards

  2. Lance, you should've used OurTunes or some similar program so that you could enjoy Mike's music back in Chicago!

  3. The latest version of OurTunes doesn't work with iTunes >= 7.0 and there is no alternative (at least for Mac OS X) I'm aware of. :( Any ideas?!

  4. Papers accepted to STOC 2007
    Small polynomial-time exact algorithms
    Ken-ichi Kawarabayashi and Bruce Reed.
    Computing crossing number in linear time
    Timothy M. Chan and Mihai Patrascu.
    Voronoi Diagrams in $n\cdot 2^{O(\sqrt{\lg\lg n})}$ Time
    Timothy M. Chan.
    More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
    Anand Bhalgat, Ramesh Hariharan, Debmalya Panigrahi and Kavitha Telikepalli.
    An \tilde{O}(mn) Gomory-Hu tree construction algorithm for unweighted graphs
    Martin Fürer.
    Faster Integer Multiplication
    Virginia Vassilevska, Ryan Williams and Raphael Yuster.
    All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time
    Gianni Franceschini and S. Muthukrishnan.
    Optimal Suffix Selection
    Pinar Heggernes, Christophe Paul, Jan Arne Telle and Yngve Villanger.
    Interval completions with few edges
    Nicholas Harvey and John Dunagan.
    A New Criterion for Variable Metric Solvers of Systems of Linear Equations
    Matthias Englert, Harald Räcke and Matthias Westermann.
    Sorting Buffers for General Metric Spaces
    Gyula Pap.
    Some new results on node-capacitated packing of A-paths
    Approximation Algorithms
    Anna Gilbert, Martin Strauss, Joel Tropp and Roman Vershynin.
    One sketch for all: Fast algorithms for Compressed Sensing
    Sanjeev Arora and Satyen Kale.
    A Combinatorial, Primal-Dual approach to Semidefinite Programs
    Mohit Singh and Lap Chi Lau.
    Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
    Mohsen Bayati, David Gamarnik, Dimitry Katz, Chandra Nair and Prasad Tetali.
    Simple deterministic approximation algorithms for counting
    Claire Kenyon-Mathieu and Warren Schudy.
    How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments
    Sudipto Guha and Kamesh Munagala.
    Approximation Algorithms for Budgeted Learning Problems
    Amit Deshpande and Kasturi Varadarajan.
    Sampling Based Dimension Reduction for Subspace Approximation
    Lap Chi Lau, Joseph (Seffi) Naor, Mohammad Salavatipour and Mohit Singh.
    Survivable Network Design with Degree or Order Constraints
    Sham Kakade, Adam Tauman Kalai and Katrina Ligett.
    Approximation Algorithms Going Online
    Amit Agarwal, Noga Alon and Moses Charikar.
    Improved Approximation for Directed Multicut and Directed Sparsest Cut
    Vojtech Rödl and Mathias Schacht.
    Property testing in hypergraphs and the removal lemma
    CS and Econ and game theory
    Fang Wu and Li Zhang.
    Proportional response dynamics leads to market equilibrium
    Vijay Vazirani and Kamal Jain.
    Eisenberg-Gale Markets: Algorithms and Structural Properties
    Sergiu Hart and Yishay Mansour.
    The Communication Complexity of Uncoupled Nash Equilibrium Procedures
    Shahar Dobzinski and Noam Nisan.
    Limitations of VCG-Based Mechanisms
    Arash Asadpour and Amin Saberi.
    An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
    Quantum computing
    Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha.
    Search via Quantum Walk
    Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz and Ronald de Wolf.
    Exponential separations for one-way quantum communication complexity, with applications to cryptography
    Gus Gutoski and John Watrous.
    Toward a general theory of quantum games
    Peter Hoyer, Troy Lee and Robert Spalek.
    Negative weights make adversaries stronger
    Lower bounds
    Mihai Patrascu.
    Lower Bounds for 2-Dimensional Range Counting
    Ronen Shaltiel and Christopher Umans.
    Low-end uniform hardness vs. randomness tradeoffs for AM

    Julia Chuzhoy and Sanjeev Khanna.
    Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems
    Ishay Haviv and Oded Regev.
    Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
    Leslie Ann Goldberg and Mark Jerrum.
    Inapproximability of the Tutte polynomial
    Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Kunal Talwar.
    Hardness of Routing with Congestion in Directed Graphs
    (Remark: this is a merged version of two submissions)
    Adi Shraibman and Nati Linial.
    Lower Bounds in Communication Complexity Based on Factorization Norms
    Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani.
    Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
    Stefan Dantchev.
    Rank Complexity Gap for Lovasz-Shrijver and Sherali-Adams Proof Systems
    Cristopher Moore, Alexander Russell and Piotr Sniady.
    On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
    Paul Beame, T. S. Jayram and Atri Rudra.
    Lower Bounds for Randomized Read/Write Stream Algorithms
    Per Austrin.
    Balanced Max 2-Sat might not be the hardest
    Alex Samorodnitsky.
    Low-degree tests at large distances
    Amir Shpilka.
    Interpolation of Depth-3 Arithmetic Circuits with two Multiplication Gates
    Alexander Sherstov.
    Separating AC^0 from Depth-2 Majority Circuits
    Thomas Holenstein.
    Parallel Repetition: Simplifications and the No-Signaling Case
    Rafael Pass and Muthuramakrishnan Venkitasubramaniam.
    An Efficient Parallel Repetition Theorem for Arthur-Merlin Games
    Rahul Santhanam.
    Circuit Lower Bounds for Merlin-Arthur Classes
    Venkatesan Guruswami and Prasad Raghavendra.
    A 3-Query PCP over Integers
    Sergey Yekhanin.
    Towards 3-Query Locally Decodable Codes of Subexponential Length
    Jin-Yi Cai and Pinyan Lu.
    Holographic Algorithms: From Art to Science
    Dan Gutfreund, Alexander Healy, Tali Kaufman and Guy Rothblum.
    Verifying and Decoding in Constant Depth
    Analysis of algorithms
    Matthew Andrews, Kyomin Jung and Alexander Stolyar.
    Stability of the Max-Weight Routing and Scheduling Protocol in Dynamic Networks and at Critical Loads
    Stefan Kiefer, Michael Luttenberger and Javier Esparza.
    On the Convergence of Newton's Method for Monotone Systems of Polynomial Equations
    Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis and Sebastien Roch.
    First to Market is not Everything: an Analysis of Preferential Attachment with Fitness
    Udi Wieder and Kunal Talwar.
    Balanced Allocations: The Weighted Case
    Elchanan Mossel and Sebastien Roch.
    On the Submodularity of Influence in Social Networks
    Anna Pagh, Rasmus Pagh and Milan Ruzic.
    Linear Probing with Constant Independence
    Thomas Hayes, Juan C. Vera and Eric Vigoda.
    Randomly coloring planar graphs with fewer colors than the maximum degree
    Jonathan Katz.
    On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation
    Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.
    Zero-Knowledge from Secure Multiparty Computation
    Cynthia Dwork, Frank McSherry and Kunal Talwar.
    The Price of Privacy and the Limits of LP Decoding
    Kobbi Nissim, Sofya Raskhodnikova and Adam Smith.
    Smooth Sensitivity and Sampling in Private Data Analysis
    Iftach Haitner and Omer Reingold.
    Statistically-Hiding Commitment from Any One-Way Function
    Patrick Donovan, Bruce Shepherd, Adrian Vetta and Gordon Wilfong.
    Bifurcated Network Flows
    Elliot Anshelevich and Adriana Karagiozova.
    Terminal Backup, 3D Matching, and Covering Cubic Graphs
    Hagit Attiya and Keren Censor.
    Tight Bounds for Asynchronous Randomized Consensus
    Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto.
    Fourier Meets M\"{o}bius: Fast Subset Convolution
    van vu and Terence Tao.
    The condition number of a randomly perturbed matrix
    Saugata Basu.
    Combinatorial Complexity in O-minimal Geometry
    Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld and Ning Xie.
    Testing k-wise and Almost k-wise Independence
    Mark Braverman and Michael Yampolsky.
    Constructing Non-Computable Julia Sets
    Chris Peikert and Alon Rosen.
    Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors
    Ittai Abraham, Yair Bartal and Ofer Neiman.
    Local Embeddings of Metric Spaces
    Piotr Indyk.
    Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
    Bo Brinkman, Adriana Karagiozova and James Lee.
    Vertex cuts, random walks, and dimension reduction in series-parallel graphs

  5. Good thing you don't have Apple's "Bounjour" client. I think it would have really freaked you out to have random people start IM-ing you.

  6. Check out ( Comment number 8 by Evan shows how to get ourTunes working on a Mac. Still haven't found a Windows alternative yet.