Welcome to TinyToCS

• TinyToCS Volume 1 Chairs' Note
  
  TinyToCS shows promise. We are encouraged by these proceedings, and the broader dialogue is only beginning. Stay tuned.
  Peter Bailis and Justine Sherry UC Berkeley

Humans and Computers Unite!

• Improving Data Management Applications Using Microtask Platforms
  
  Judiciously leveraging microtask platforms can enable more powerful data management applications that are otherwise impossible.
  Jiannan Wang Tsinghua University, Reynold Xin UC Berkeley
• Sorting it All Out with Humans in the Loop
  
  When ranking with humans, ratings are cheap and nice. To improve quality, please compare, for a price. Hammertime.
  Adam Marcus, Eugene Wu, David Karger, Samuel Madden, Robert Miller MIT CSAIL
• Relative Comfort of People with Acting Robots by Theatre and Technology Experience
  
  People involved with both theatre & technology are more comfortable with acting robots than just theatre people, but less so than techies.
  David V. Lu Washington University in St. Louis
• Bots are Users, Too! Rethinking the Roles of Software Agents in HCI
  
  Bots are users of systems just as humans are. HCI practitioners must not forget to design for both bot-computer and human-bot interaction.
  R. Stuart Geiger University of California, Berkeley

Semantics, Semantics

• Towards an Emergent Semantic Web
  
  Inductive fuzzy grassroots ontologies form a basis for computing with words. In time they will allow the Web to merge with the Semantic Web.
  Edy Portmann UC Berkeley EECS
• Fast Semantic Relatedness: WordNet::Similarity vs Roget's Thesaurus
  
  The fastest & best-correlated WordNet MSRs, respectively, take 82 & 182 times longer than Roget's MSR, yet all are statistically equivalent.
  Alistair Kennedy, Stan Szpakowicz University of Ottawa
• ConceptNet 5
  
  ConceptNet 5 is released. It's a free semantic network in many languages, enabling reasoning and machine learning about what words mean.
  Rob Speer, Catherine Havasi MIT Media Lab

Of Clusters and Clouds

• Please mind the gap between intra- and inter-chassis parallelism! (and how it can be closed)
  
  Existing, easy-to-use distributed programming models are sufficient to enable multiscale parallel computation inside and across machines.
  Malte Schwarzkopf University of Cambridge Computer, Laboratory, Derek G. Murray Microsoft Research Silicon Valley, Steven Hand University of Cambridge Computer Laboratory
• Lifting cloud infrastructure service consumers to providers
  
  Nested virtualisation is a low-overhead mechanism to partially repurpose leased compute resources. This leads to recursive cloud providers.
  Josef Spillner Technische Universitat Dresden, Andrey Brito Universidade Federal de Campina Grande
• A Novel Approach for Fault Diagnosis on Computational Grids
  
  The automatic tests written during software's development phase can also be used to identify faulty components during its production stage.
  Alexandre Duarte Universidade Federal da Paraiba

Clustering, Correlation, and Optimization

• Fast Deterministic Single-Linkage 2D-Spatial Cluster Analysis
  
  Find the Delaunay triangulation of the points with Sweephull, then Kruskal's MST until the required cluster count is reached. O(n log n).
  Daniel Goldbach University of New South Wales
• Beating brute-force: Improved algorithms for finding correlations, and related problems
  
  One can find correlated variables in time O(n^1.6 ). Similar ideas give faster algorithms for Closest-Pair, and learning juntas/parities.
  Gregory Valiant Microsoft Research
• Persistency for higher-order pseudo-boolean maximization
  
  A pseudo-Boolean function is a posiform [1]. Write its maximization as vertex packing. Solve a bipartite problem [3]; et voila: persistency!
  Petter Strandmark Lund University

Data and Data Manipulation

• The End of an Architectural Era for Analytical Databases
  
  Data warehouse systems should be modular, flexible, easy to provision, and support machine learning. It's time to rethink the system design.
  Reynold Xin AMPLab, UC Berkeley
• Exact and Near-miss Clone Detection in Spreadsheets
  
  Clone detection in spreadsheets is useful both to reveal opportunities for improving the spreadsheet and to detect actual errors.
  Felienne Hermans Delft University of Technology
• Tastes Great, Less Filling: Low-Impact OLAP MapReduce Queries on High-Performance OLTP Systems
  
  OLAP queries executed as MapReduce jobs in an OLTP DBMS achieve same latency as distributed transactions but improve throughput by 20%-50%
  Xin Jia, Andrew Pavlo, Stanley Zdonik Brown University

Life on the Web

• Is Internet traffic becoming less centralized over time?
  
  In 2002, 18 of 10000 ASes controlled 45% of Internet traffic. In 2010, 18 of 35000 controlled 45%. Internet traffic is not decentralizing.
  Peter Boothe Manhattan College
• Conceptualizing Transparency on Online Social Networks
  
  Sharing decisions on Online Social Networks are reducible to RBAC concepts, making Visual Role Mining applicable to increase transparency.
  Michael Netter University of Regensburg
• On the Security of Conference and Journal Submission Sites
  
  HotCRP sites should use SSL. It should suffice to add "SSLRequireSSL" to HOTCRPDIR/.htaccess. You might need a valid certificate, too [1].
  Jeffrey C. Mogul HP Labs, Eddie Kohler Harvard University
• Inferring Visibility: Who's (Not) Talking to Whom?
  
  Most network operators don't know what routes pass through their network. They can find out using statistical inference on observed traffic.
  Gonca Gursun, Natali Ruchansky, Evimaria Terzi, and Mark Crovella Boston University

Out, out, damn bugs! (and security holes)

• Safe Haskell
  
  Safe Haskell enforces type safety in Haskell and adds a notion of trust to modules. This allows security to be built at the language level.
  David Terei Stanford University, Simon Marlow Microsoft Research, Simon Peyton Jones Microsoft Research, David Mazieres Stanford University
• Fake Emulation Environment to Prevent Malware from Executing
  
  Faking just enough of common emulation and analysis environments might prevent certain kinds malware from executing their malicious payload.
  Collin Mulliner Technische Universitat Berlin
• Secure Programming via Safety Games
  
  To write a correct and secure program, one can find a winning Defender strategy for a two-player turn-based safety game.
  William Harris University of Wisconsin, Madison
• 33 Bits of Entropy: Myths and Fallacies of "Personally Identifiable Information"
  
  Anonymization of rich consumer data is infeasible--people are unique, and any piece of data can help reidentify. 33 bits of entropy will do.
  Arvind Narayanan Princeton University

Software Systems and Development

• User-Friendly Failure Diagnosis
  
  Crash the system every-which-way with failure injection. Build table of error messages. When users hit trouble, look up error msgs in table.
  Ariel Rabkin Princeton University
• How to aggregate software metrics?
  
  When aggregating metrics to assess software maintainability, Gini, Theil, Hoover, and Atkinson strongly correlate.
  Bogdan Vasilescu, Alexander Serebrenik, Mark G.J. van den Brand Eindhoven University of Technology
• Effects of Centralized and Distributed Version Control on Commit Granularity
  
  In a study of six CVC and six DVC repositories we found that the median size of code commits in DVC is 38% larger than in CVC.
  Jochen Wuttke University of Washington, Ivan Beschastnikh University of Washington, Yuriy Brun University of Massachusetts
• Portably solving the access(2)/open(2) race
  
  access(2)/open(2) file-system races can be prevented by omitting access(2) and using seteuid(2)/setegid(2) before open(2) on a modern OS.
  Stephen Checkoway Johns Hopkins University

Bots and Robots

• Extending Simultaneous Localization and Mapping to Resource Limited Micro-Aerial Vehicle Swarms
  
  Designing hierarchical data structures for map representation key to scaling SLAM algorithms to large swarms of resource-constrained robots
  Markus Burkardt Cornell University, Karthik Dantu Harvard University
• Robots Building With Goop
  
  Physical systems have uncertainty. We embrace it and design robust algorithms for robotic construction with continuous, goopy materials.
  Nils Napp, Radhika Nagpal Harvard University
• Impact of Mobility on Link Quality and Packet Loss in Low-Power Radios
  
  Continuous broadcast rather than low-power alternatives are most efficient for coordination of a swarm of micro-aerial vehicles
  Michael Bechard Eastern Nazarene College, Karthik Dantu Harvard University

Sequences, Strings, and Natural Languages

• From Peaks to Valleys, Running Up and Down: Fast Permutation Pattern Matching
  
  We designed a PPM algorithm with O (1.8^run(T)) runtime [2]. This improves both base and exponent. For T with few runs it is especially fast.
  Marie-Louise Bruner, Martin Lackner Vienna University of Technology
• Approximate string matching as an algebraic computation
  
  Matching a pattern approximately to every substring in a text = computing in the classical braid group, where crossings are made idempotent.
  Alexander Tiskin University of Warwick
• On finding cross-lingual article pairs
  
  Cross-lingual merging of Honduran geotagged Wikipedia articles based on article names and locations alone results in 99.4% correct pairs.
  Dirk Ahlers Search Consultant
• Alice and Bob's Adventures in Barterland
  
  Meetings as information exchange mechanisms can be featured, integrated and used as inference engines for solving problems like NLP [1, 2, 3].
  Michele Bottone Matroid

Networks and Networked Systems

• Torii-HLMAC: Distributed, Fault-tolerant Data Center Architecture with Multiple Tree-based Addressing and Forwarding
  
  Just a few messages exchanged once the architecture is built and done! Have a high-bandwidth, load-balanced data center network forever
  Elisa Rojas, Guillermo Ibanez Universidad de Alcala, Madrid
• Achieving Collision Freedom without Modifying Communication Protocols in Wireless Rechargeable Sensor Networks
  
  Control charging patterns to wake up nodes at different time intervals. Now your wireless rechargeable sensor network is collision-free!
  Yuanchao Shu Zhejiang University, Yuelong Tian Zhejiang University, Yu Gu Singapore University of Technology and Design, Jiming Chen Zhejiang University
• All-path: Finding Simply Fastest Path and Balancing Load by Flooding ARP Packets as Path Probes
  
  To select the fastest path in network, start a race of ARP Request replicas at the edge bridge and lock it with first-arrival port learning
  Guillermo Ibanez, Elisa Rojas Universidad de Alcala, Madrid
• Weaker Links for Synchronization
  
  Weak links can be a better choice than reliable links for clock synchronization in a wireless sensor network.
  Ted Herman University of Iowa

Videogame Theory

• Constrained Videogame Content Generation with Answer Set Programming
  
  Answer set programming allows the rapid development of tightly-constrained videogame content generators without inventing new algorithms.
  Adam M. Smith Expressive Intelligence Studio, UC Santa Cruz
• Simplified Harvest Moon is NP-Complete
  
  There exists a trivial bijection from all instances of BKP to all instances of Simplified Harvest Moon (SHM). Therefore, SHM is NP-complete.
  Steven Braeger University of Central Florida
• Collecting Things Under Time Pressure is Hard
  
  3D games with gravity that require gathering objects to ensure traversing edges within a time-limit can be reduced from the NP-complete CPP.
  Jayson Lynch Massachusetts Institute of Technology

Publishing and Publications

• Google Scholar Metrics h5-index correlated with Impact Factor
  
  Google Scholar Metrics h5-index is correlated with Impact Factor ranking some Computer Science conferences close to top-tier journals
  Michael O'Neill University College Dublin
• Data Publishing Using Nanopublications
  
  The nanopublication model incentivizes rapid, citable data dissemination, interoperability, semantic reasoning, and knowledge discovery.
  Mark Thompson, Erik Schultes, Marco Roos, Barend Mons LUMC
• Narrowing the Readability Gap Between Scientific Papers and the World Wide Web
  
  Paper references as anchor hyperlinks can improve the readability and, ultimately, increase the entropy of the scientific corpora.
  Michele Catasta EPFL

TinyToCS and Twitter

• TinyTOCS as an Experimental Laboratory
  
  When rethinking academic publishing, don't retrofit a cathedral onto what should be a bazaar [1].
  George Porter University of California, San Diego
• An Upper-Bound on Information Contained Within a Tweet
  
  Max bits/tweet? UTF8=31b/chr Can use chrs forbidden by RFC3629 Composing chars count as distinct codepts Max bits is 4339 (-1 for ctrl chrs)
  Karl Koscher University of Washington
• TweeCards: Tweets Go Postal
  
  I cn snd postcards 2 all my tweeps! w/photos & QR 2! Prvcy? addr escrow via DHT! @USPS&@Twitter make $$ via ads&estamps. OMG!! #tweecards [1]
  Mary Baker, Jeffrey C. Mogul, Ian Robinson HP Labs
• The end of TinyToCS is nigh
  
  The upper bound for meaningful distinct Tiny ToCS articles, assuming ASCII encoding, is 95¹⁴⁰ - just above 7.6 unnonagintillion (10²⁷⁶).
  Josef Spillner Technische Universitat Dresden

Tiny ToCS Volume 1 Organizers

• Peter Bailis, University of California-Berkeley
• Justine Sherry, University of California-Berkeley

• Elaine Angelino, Harvard University
• Leilani Battle, Massachusetts Institute of Technology
• Gilbert Bernstein, University of Washington
• Yonatan Bisk, University of Illinois at Urbana-Champaign
• Keenan Crane, California Institute of Technology
• John Dickerson, Carnegie Mellon University
• Stephanie Steinhardt, Cornell University
• Joshua Hailpern, University of Illinois at Urbana-Champaign
• Bryan Kate, Harvard University
• Kevin Karsch, University of Illinois at Urbana-Champaign
• Katrina LaCurts, Massachusetts Institute of Technology
• Amit Levy, Stanford University
• Jonathan Long, University of California-Berkeley
• Adam Marcus, Massachusetts Institute of Technology
• Jacob Nelson, University of Washington
• Katrina Panovich, Massachusetts Institute of Technology
• Andy Pavlo, Brown University
• Alex Rasmussen, University of California-San Diego
• Franziska Roesner, University of Washington
• Gregory Valiant, University of California-Berkeley
• Eugene Wu, Massachusetts Institute of Technology
• Jean Yang, Massachusetts Institute of Technology

• Jon Kuroda, University of California-Berkeley