tag:blogger.com,1999:blog-3722233.post117189245319165049..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Time and MusicLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-83743527400141308962007-07-09T23:52:00.000-05:002007-07-09T23:52:00.000-05:00Check out (http://www.selfproclaimedexpert.com/?p=...Check out (http://www.selfproclaimedexpert.com/?p=127) Comment number 8 by Evan shows how to get ourTunes working on a Mac. Still haven't found a Windows alternative yet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1172352797073413432007-02-24T15:33:00.000-06:002007-02-24T15:33:00.000-06:00Good thing you don't have Apple's "Bounjour" clien...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1171923457495056312007-02-19T16:17:00.000-06:002007-02-19T16:17:00.000-06:00Papers accepted to STOC 2007----------------------...Papers accepted to STOC 2007<BR/>----------------------------------------------<BR/>Small polynomial-time exact algorithms<BR/>--------------------------------------------------<BR/>Ken-ichi Kawarabayashi and Bruce Reed. <BR/> Computing crossing number in linear time <BR/>Timothy M. Chan and Mihai Patrascu. <BR/> Voronoi Diagrams in $n\cdot 2^{O(\sqrt{\lg\lg n})}$ Time <BR/>Timothy M. Chan. <BR/> More Algorithms for All-Pairs Shortest Paths in Weighted Graphs <BR/>Anand Bhalgat, Ramesh Hariharan, Debmalya Panigrahi and Kavitha Telikepalli. <BR/> An \tilde{O}(mn) Gomory-Hu tree construction algorithm for unweighted graphs <BR/>Martin Fürer. <BR/> Faster Integer Multiplication <BR/>Virginia Vassilevska, Ryan Williams and Raphael Yuster. <BR/> All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time <BR/>Gianni Franceschini and S. Muthukrishnan. <BR/> Optimal Suffix Selection <BR/>Pinar Heggernes, Christophe Paul, Jan Arne Telle and Yngve Villanger. <BR/> Interval completions with few edges <BR/>Nicholas Harvey and John Dunagan. <BR/> A New Criterion for Variable Metric Solvers of Systems of Linear Equations <BR/>Matthias Englert, Harald Räcke and Matthias Westermann. <BR/> Sorting Buffers for General Metric Spaces <BR/>Gyula Pap. <BR/> Some new results on node-capacitated packing of A-paths <BR/>------------------------------------------------------------------------<BR/>Approximation Algorithms<BR/>--------------------------------------------------------------------------<BR/>Anna Gilbert, Martin Strauss, Joel Tropp and Roman Vershynin. <BR/> One sketch for all: Fast algorithms for Compressed Sensing <BR/>Sanjeev Arora and Satyen Kale. <BR/> A Combinatorial, Primal-Dual approach to Semidefinite Programs <BR/>Mohit Singh and Lap Chi Lau. <BR/> Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal <BR/>Mohsen Bayati, David Gamarnik, Dimitry Katz, Chandra Nair and Prasad Tetali. <BR/> Simple deterministic approximation algorithms for counting <BR/>Claire Kenyon-Mathieu and Warren Schudy. <BR/> How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments <BR/>Sudipto Guha and Kamesh Munagala. <BR/> Approximation Algorithms for Budgeted Learning Problems <BR/>Amit Deshpande and Kasturi Varadarajan. <BR/> Sampling Based Dimension Reduction for Subspace Approximation <BR/>Lap Chi Lau, Joseph (Seffi) Naor, Mohammad Salavatipour and Mohit Singh. <BR/> Survivable Network Design with Degree or Order Constraints <BR/>Sham Kakade, Adam Tauman Kalai and Katrina Ligett. <BR/> Approximation Algorithms Going Online <BR/>Amit Agarwal, Noga Alon and Moses Charikar. <BR/> Improved Approximation for Directed Multicut and Directed Sparsest Cut <BR/>Vojtech Rödl and Mathias Schacht. <BR/> Property testing in hypergraphs and the removal lemma <BR/>------------------------------------------------------------<BR/>CS and Econ and game theory<BR/>----------------------------------------------------------<BR/>Fang Wu and Li Zhang. <BR/> Proportional response dynamics leads to market equilibrium <BR/>Vijay Vazirani and Kamal Jain. <BR/> Eisenberg-Gale Markets: Algorithms and Structural Properties <BR/>Sergiu Hart and Yishay Mansour. <BR/> The Communication Complexity of Uncoupled Nash Equilibrium Procedures <BR/>Shahar Dobzinski and Noam Nisan. <BR/> Limitations of VCG-Based Mechanisms <BR/>Arash Asadpour and Amin Saberi. <BR/> An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods <BR/>---------------------------------------------<BR/>Quantum computing<BR/>--------------------------------------------<BR/>Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. <BR/> Search via Quantum Walk <BR/>Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz and Ronald de Wolf. <BR/> Exponential separations for one-way quantum communication complexity, with applications to cryptography <BR/>Gus Gutoski and John Watrous. <BR/> Toward a general theory of quantum games <BR/>Peter Hoyer, Troy Lee and Robert Spalek. <BR/> Negative weights make adversaries stronger <BR/>------------------------------------------------------------------<BR/>Lower bounds<BR/>--------------------------------------------------------------------<BR/>Mihai Patrascu. <BR/> Lower Bounds for 2-Dimensional Range Counting <BR/>Ronen Shaltiel and Christopher Umans. <BR/> Low-end uniform hardness vs. randomness tradeoffs for AM <BR/><BR/>Julia Chuzhoy and Sanjeev Khanna. <BR/> Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems <BR/>Ishay Haviv and Oded Regev. <BR/> Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors <BR/>Leslie Ann Goldberg and Mark Jerrum. <BR/> Inapproximability of the Tutte polynomial <BR/>Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Kunal Talwar. <BR/> Hardness of Routing with Congestion in Directed Graphs<BR/>(Remark: this is a merged version of two submissions) <BR/>Adi Shraibman and Nati Linial. <BR/> Lower Bounds in Communication Complexity Based on Factorization Norms <BR/>Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani. <BR/> Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut <BR/>Stefan Dantchev. <BR/> Rank Complexity Gap for Lovasz-Shrijver and Sherali-Adams Proof Systems <BR/>Cristopher Moore, Alexander Russell and Piotr Sniady. <BR/> On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism <BR/>Paul Beame, T. S. Jayram and Atri Rudra. <BR/> Lower Bounds for Randomized Read/Write Stream Algorithms <BR/>Per Austrin. <BR/> Balanced Max 2-Sat might not be the hardest <BR/>-------------------------------------------------<BR/>Complexity<BR/>-------------------------------------------------<BR/>Alex Samorodnitsky. <BR/> Low-degree tests at large distances <BR/>Amir Shpilka. <BR/> Interpolation of Depth-3 Arithmetic Circuits with two Multiplication Gates <BR/>Alexander Sherstov. <BR/> Separating AC^0 from Depth-2 Majority Circuits <BR/>Thomas Holenstein. <BR/> Parallel Repetition: Simplifications and the No-Signaling Case <BR/>Rafael Pass and Muthuramakrishnan Venkitasubramaniam. <BR/> An Efficient Parallel Repetition Theorem for Arthur-Merlin Games <BR/>Rahul Santhanam. <BR/> Circuit Lower Bounds for Merlin-Arthur Classes <BR/>Venkatesan Guruswami and Prasad Raghavendra. <BR/> A 3-Query PCP over Integers <BR/>Sergey Yekhanin. <BR/> Towards 3-Query Locally Decodable Codes of Subexponential Length <BR/>Jin-Yi Cai and Pinyan Lu. <BR/> Holographic Algorithms: From Art to Science <BR/>Dan Gutfreund, Alexander Healy, Tali Kaufman and Guy Rothblum. <BR/> Verifying and Decoding in Constant Depth <BR/>-----------------------------------------<BR/>Analysis of algorithms<BR/>--------------------------------------------<BR/>Matthew Andrews, Kyomin Jung and Alexander Stolyar. <BR/> Stability of the Max-Weight Routing and Scheduling Protocol in Dynamic Networks and at Critical Loads <BR/>Stefan Kiefer, Michael Luttenberger and Javier Esparza. <BR/> On the Convergence of Newton's Method for Monotone Systems of Polynomial Equations <BR/>Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis and Sebastien Roch. <BR/> First to Market is not Everything: an Analysis of Preferential Attachment with Fitness <BR/>Udi Wieder and Kunal Talwar. <BR/> Balanced Allocations: The Weighted Case <BR/>Elchanan Mossel and Sebastien Roch. <BR/> On the Submodularity of Influence in Social Networks <BR/>Anna Pagh, Rasmus Pagh and Milan Ruzic. <BR/> Linear Probing with Constant Independence <BR/>Thomas Hayes, Juan C. Vera and Eric Vigoda. <BR/> Randomly coloring planar graphs with fewer colors than the maximum degree <BR/>--------------------------------------------------------------------<BR/>Crypto<BR/>-----------------------------------------------------------------<BR/>Jonathan Katz. <BR/> On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation <BR/>Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. <BR/> Zero-Knowledge from Secure Multiparty Computation <BR/>Cynthia Dwork, Frank McSherry and Kunal Talwar. <BR/> The Price of Privacy and the Limits of LP Decoding <BR/>Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. <BR/> Smooth Sensitivity and Sampling in Private Data Analysis <BR/>Iftach Haitner and Omer Reingold. <BR/> Statistically-Hiding Commitment from Any One-Way Function <BR/>--------------------------------------------------------------------<BR/>Stuff<BR/>-----------------------------------------------------------------<BR/>Patrick Donovan, Bruce Shepherd, Adrian Vetta and Gordon Wilfong. <BR/> Bifurcated Network Flows <BR/>Elliot Anshelevich and Adriana Karagiozova. <BR/> Terminal Backup, 3D Matching, and Covering Cubic Graphs <BR/>Hagit Attiya and Keren Censor. <BR/> Tight Bounds for Asynchronous Randomized Consensus <BR/>Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. <BR/> Fourier Meets M\"{o}bius: Fast Subset Convolution <BR/>van vu and Terence Tao. <BR/> The condition number of a randomly perturbed matrix <BR/>Saugata Basu. <BR/> Combinatorial Complexity in O-minimal Geometry <BR/>Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld and Ning Xie. <BR/> Testing k-wise and Almost k-wise Independence <BR/>Mark Braverman and Michael Yampolsky. <BR/> Constructing Non-Computable Julia Sets <BR/>Chris Peikert and Alon Rosen. <BR/> Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors <BR/>Ittai Abraham, Yair Bartal and Ofer Neiman. <BR/> Local Embeddings of Metric Spaces <BR/>Piotr Indyk. <BR/> Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 <BR/>Bo Brinkman, Adriana Karagiozova and James Lee. <BR/> Vertex cuts, random walks, and dimension reduction in series-parallel graphsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1171921645934867182007-02-19T15:47:00.000-06:002007-02-19T15:47:00.000-06:00The STOC 2007 accepted papers list is now out.The <A HREF="http://research.microsoft.com/research/theory/feige/homepagefiles/stoc2007accept.txt" REL="nofollow"> STOC 2007 accepted papers list</A> is now out.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1171901788283691042007-02-19T10:16:00.000-06:002007-02-19T10:16:00.000-06:00The latest version of OurTunes doesn't work with i...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?!Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1171900199450151922007-02-19T09:49:00.000-06:002007-02-19T09:49:00.000-06:00Lance, you should've used OurTunes or some similar...Lance, you should've used OurTunes or some similar program so that you could enjoy Mike's music back in Chicago!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1171899011475306532007-02-19T09:30:00.000-06:002007-02-19T09:30:00.000-06:00Hi,I guess it is possible, to turn off automatical...Hi,<BR/><BR/>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).<BR/><BR/>The iTunes-experience might be explained by other users in the network, sharing their iTunes-library without password.<BR/><BR/>http://www.apple.com/ilife/tutorials/itunes/it6-1.html<BR/><BR/>best regardsAnonymousnoreply@blogger.com