- talks - lists.cs.princeton.edu

M Homilius general exam
by Melissa M. Lawson 10 May '13

10 May '13

Max Homilius will present his research seminar/general exam on Friday March 17 at 10AM in Room 302 (note room!). The members of his committee are: Olga Troyanskaya (advisor), Mona Singh, and Tom Funkhouser. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------- Abstract ======== Classical pharmacological approaches for the identification of new drug candidates often follow a one disease - one target - one drug paradigm. At the same time, there is little knowledge about the specific mode of action for many compounds and the principles underlying interactions between multiple drugs. I developed a machine learning approach for the prediction of synergistic drug pairs for fungicidal and anti-cancer compounds. This approach takes into account the effects of a compound on multiple target genes that are part of complex biological network, and combines experimental results from different large-scale studies to improve predictions. In addition, I constructed functional networks specific to non-steroidal anti-inflammatory drugs. Measures of differential expression and coexpression of genes after drug treatment were reconciled with these networks and are predictive of the mode of action of the administered drug. Reading list ========== [1] Ethem Alpaydin (2004). Introduction to Machine Learning. First edition. MIT Press. Ch 1 Introduction Ch 2 Supervised Learning Ch 3 Bayesian Decision Theory Ch 4 Parametric Methods Ch 5 Multivariate Methods Ch 8 Nonparametric Methods Ch 10 Linear Discrimination Ch 14 Assessing and Comparing Classification Algorithms Ch 15 Combining Multiple Learners [2] Aryee, M. J., Gutiérrez-Pabello, J. a, Kramnik, I., Maiti, T., & Quackenbush, J. (2009). An improved empirical bayes approach to estimating differential gene expression in microarray time-course data: BETR (Bayesian Estimation of Temporal Regulation). BMC bioinformatics, 10, 409. [3] Cokol, M., Chua, H. N., Tasan, M., Mutlu, B., Weinstein, Z. B., Suzuki, Y., Nergiz, M. E., et al. (2011). Systematic exploration of synergistic drug pairs. Molecular systems biology, 7(544), 544. [4] Dawson, J. a, & Kendziorski, C. (2012). An empirical Bayesian approach for identifying differential coexpression in high-throughput experiments. Biometrics, 68(2), 455–65. [5] Grosser, T., Fries, S., & FitzGerald, G. (2006). Biological basis for the cardiovascular consequences of COX-2 inhibition: therapeutic challenges and opportunities. Journal of Clinical Investigation, 116(1). [6] Jansen, G., Lee, A. Y., Epp, E., Fredette, A., Surprenant, J., Harcus, D., Scott, M., et al. (2009). Chemogenomic profiling predicts antifungal synergies. Molecular systems biology, 5(338), 338. [7] Laenen, G., Thorrez, L., Börnigen, D., & Moreau, Y. (2013). Finding the targets of a drug by integration of gene expression data with a protein interaction network. Molecular BioSystems. [8] Nitsch, D., Gonçalves, J. P., Ojeda, F., De Moor, B., & Moreau, Y. (2010). Candidate gene prioritization by network analysis of differential expression using machine learning approaches. BMC bioinformatics, 11(2007), 460. [9] Poirel, C. L., Rahman, A., Rodrigues, R. R., Krishnan, A., Addesa, J. R., & Murali, T. M. (2013). Reconciling differential gene expression data with molecular interaction networks. Bioinformatics, 29(5), 622–9. [10] Wong, A. K., Park, C. Y., Greene, C. S., Bongo, L. a, Guan, Y., & Troyanskaya, O. G. (2012). IMP: a multi-species functional genomics portal for integration, visualization and prediction of protein functions and networks. Nucleic acids research, 40, W484–90.

1 1

J Fix general exam
by Melissa M. Lawson 10 May '13

10 May '13

Jordan Fix will present his research seminar/general exam on Thursday May 16 at 10AM in Room 402. The members of his committee are: David August (advisor), David Wentzlaff (ELE), and Andrew Appel. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------------- Abstract: The emergence of multicore architectures necessitates new techniques such as transactional memory (TM) to gain performance without burdening programmers. This talk presents the first evaluation of a hardware multi-threaded transactional (MTX) memory system and improves upon prior proposed designs. MTX enables more diverse parallelization schemes than traditional TM systems which restrict transactions to a single thread, limiting their applicability. Prior software-based MTX memory systems require extra book keeping threads and instructions to manage speculative memory, imposing more overhead than a hardware-based implementation. The proposed hardware MTX memory system employs new transactional instructions, adds new cache state, and is implemented on top of a snoopy MOESI cache coherence protocol, allowing transactions spanning multiple threads to determine their state by snooping coherence messages. Reading List: Textbooks: • J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 • A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 Papers: • Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional memory: architectural support for lock-free data structures. In Proceedings of the 20th annual international symposium on computer architecture (ISCA '93) • S. Gopal, T. Vijaykumar, J. Smith, and G. Sohi. 1998. Speculative Versioning Cache. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture (HPCA '98). • Lance Hammond, Vicky Wong, Mike Chen, Brian D. Carlstrom, John D. Davis, Ben Hertzberg, Manohar K. Prabhu, Honggo Wijaya, Christos Kozyrakis, and Kunle Olukotun. 2004. Transactional Memory Coherence and Consistency. In Proceedings of the 31st annual international symposium on Computer architecture (ISCA '04). • Nir Shavit and Dan Touitou. 1995. Software transactional memory. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (PODC '95). • Arun Raman, Hanjun Kim, Thomas R. Mason, Thomas B. Jablin, and David I. August. 2010. Speculative parallelization using software multi-threaded transactions. In Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems (ASPLOS XV). • N. Vachharajani. Intelligent Speculation for Pipelined Multithreading. PhD thesis, Department of Computer Science, Princeton University, Princeton, New Jersey, United States, November 2008. • J. Greggory Steffan, Christopher B. Colohan, Antonia Zhai, and Todd C. Mowry. 2000. A scalable approach to thread-level speculation. In Proceedings of the 27th annual international symposium on Computer architecture (ISCA '00) • María Jesús Garzarán, Milos Prvulovic, José María Llabería, Víctor Viñals, Lawrence Rauchwerger, and Josep Torrellas. 2005. Tradeoffs in buffering speculative memory state for thread-level speculation in multiprocessors. ACM Transactions on Architecture and Code Optimization (TACO '05). • James R. Goodman. 1983. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th annual international symposium on Computer architecture (ISCA '83). • P. Sweazey and A. J. Smith. 1986. A class of compatible cache consistency protocols and their support by the IEEE futurebus. In Proceedings of the 13th annual international symposium on Computer architecture (ISCA '86).

1 0

P Prabhu FPO
by Melissa M. Lawson 09 May '13

09 May '13

Prakash Prabhu will present his FPO on Thursday May 16 at 2PM in Room 402. The members of his committee are: David August, advisor; David Walker and JP Singh, readers; Kai Li and Margaret Martonosi, nonreaders. A copy of his thesis, "Semantic Language Extensions for Implicit Parallel Programming", is on display in Room 310. Everyone is invited to attend his talk.

1 0

F Yu general exam
by Melissa M. Lawson 07 May '13

07 May '13

Fisher Yu will present his research seminar/general exam on Tuesday May 14 at 2PM in Room 402. The members of his committee are: Tom Funkhouser (advisor), Szymon Rusinkiewicz, and Adam Finkelstein. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------- Abstract: City scale reconstruction is gaining more and more attention these years driven by its popularity in consumer market. It can help people get familiar with a new place without physically being there. Nowadays, people can view the 3D city models from aerial view or check the panorama images of the street. However, although the street level virtual scene can give the users an immersed experience in the virtual environment, the technology to build large scale detailed 3D textured models is still not mature enough for the customers. In this project, we make use of both laser range scanning and images from Google Street View project to recover the 3D shapes and their texture by combining the sparse shape information of the range scans and detailed texture information of the images. As we are working towards the goal, there are mainly three problems we need to solve, namely, adjusting pose estimation, increase the resolution of the scans, and fill the holes in the regions the scanners failed to reach. To adjust the pose estimation, we build a framework to optimize the laser and image poses together. Also, we can optimize the scan point positions and their subdivided mesh by considering both photo consistency and scan measurement. Our methods can now work on a number of sample environments. Reading List: Szeliski, R. (2010). Computer vision: Algorithms and applications. Springer-Verlag New York Inc. Musialski, P., Wonka, P., Aliaga, D. G., Wimmer, M., Van Gool, L., & Purgathofer, W. (2012). A Survey of Urban Reconstruction. Eurographics 2012 - State of the Art Reports. Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000). Bundle Adjustment — A Modern Synthesis. Vision Algorithms: Theory and Practice Furukawa, Y., & Ponce, J. (2010). Accurate, Dense, and Robust Multiview Stereopsis. Pattern Analysis and Machine Intelligence Furukawa, Y., Curless, B., Seitz, S. M., & Szeliski, R. (2010). Towards Internet-scale multi-view stereo. Computer Vision and Pattern Recognition Snavely, N., Seitz, S. M., & Szeliski, R. (2007). Modeling the World from Internet Photo Collections. International Journal of Computer Vision Kazhdan, M., & Hoppe, H. (2013). Screened Poisson Surface Reconstruction. ACM Transactions on Graphics . Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision Pollefeys, M., Nistér, D., Frahm, J., Akbarzadeh, A., Mordohai, P., Clipp, B., Engels, C., et al. (2007). Detailed Real-Time Urban 3D Reconstruction from Video. International Journal of Computer Vision Seitz, S. M., Curless, B., Diebel, J., Scharstein, D., & Szeliski, R. (2006). A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms. Computer Vision and Pattern Recognition Hernández, C., & Vogiatzis, G. (2010). Shape from photographs : a multi-view stereo pipeline. Computer Vision Studies in Computational Intelligence Sorkine, O. (2005). Laplacian mesh processing. Eurographics 2005 - State of the Art Reports

1 0

Talk: Implications of Non Volatile Memory on Software Architectures- Tues. May 7, 12pm
by Nicole E. Wagenblast 07 May '13

07 May '13

Implications of Non Volatile Memory on Software Architectures Nisha Talagala , Fusion-io Tuesday, May 7, 2013, 12:00pm Computer Science 402 Flash based non volatile memory is revolutionizing data center architectures, improving application performance by bridging the gap between DRAM and disk. Future non volatile memories promise performance even closer to DRAM. While flash adoption in industry started as disk replacement, the past several years have seen data center architectures change to take advantage of flash as a new memory tier in both servers and storage. This talk covers the implications of nonvolatile memory on software. We describe the stresses that non volatile memory places on existing application and OS designs, and illustrate optimizations to exploit flash as a new memory tier. Until the introduction of flash, there has been no compelling reason to change the existing operating system storage stack. We will describe the technologies contained in the upcoming Fusion-io Software Developer Kit (ioMemory SDK) that allow applications to leverage the native capabilities of non-volatile memory as both an I/O device and a memory device. The technologies described will include new I/O based APIs and libraries to leverage the ioMemory Virtual Storage Layer, as well as features for extending DRAM into flash for cost and power reduction. Finally, we describe Auto-Commit-Memory, a new persistent memory type that will allow applications to combine the benefits of persistence with programming semantics and performance levels normally associated with DRAM. Nisha Talagala is Lead Architect at Fusion-io, where she works on innovation in non volatile memory technologies and applications. Nisha has more than 10 years of expertise in software development, distributed systems, storage, I/O solutions, and non-volatile memory. She has worked as technology lead for server flash at Intel - where she led server platform non volatile memory technology development and partnerships. Prior to Intel, Nisha was the CTO of Gear6, where she developed clustered computing caches for high performance I/O environments. Nisha also served at Sun Microsystems, where she developed storage and I/O solutions and worked on file systems. Nisha earned her PhD at UC Berkeley where she did research on clusters and distributed storage. Nisha hold more than 30 patents in distributed systems, networking, storage, performance and non-volatile memory

2 1

Prof. Radu Teodorescu, Seminar on May 14
by Margaret Martonosi 07 May '13

07 May '13

Hello--- Prof. Radu Teodorescu from Ohio State will be visiting on Tuesday May 14 and giving a lunchtime seminar in CS402. (Noon lunch, followed by 12:30 seminar). The title and abstract are below. If you are interested in a one-on-one meeting with Radu, please either sign up on the google doc visitors spreadsheet: https://docs.google.com/spreadsheet/ccc?key=0AgeypYYNTzO8dEhneUxHV0Q3eEJQUj… Or let me know your scheduling constraints between 11am and 6pm, and I will grab a one-on-one slot for you. Thanks, Margaret > Designing Energy-Efficient Microprocessors in the Era of Unpredictable Transistors > > ABSTRACT: > Energy efficiency is now a principal design constraint across all computing markets - from supercomputers to smartphones. Performance growth in these markets can only be sustained going forward through significant improvements in the energy efficiency of computation. A very effective approach to improving microprocessor energy efficiency is to lower supply voltage to very close to the transistor's threshold voltage, into the so-called near-threshold region. Near-threshold operation reduces energy consumption by an order of magnitude but comes at the cost of reduced frequency, degraded reliability and increased parameter variability. > > In this talk I will describe hardware and software co-design techniques that address and alleviate the challenges of low-voltage computing, bringing it closer to commercial feasibility. These include techniques for reducing the effects of process and voltage variability and a new approach for runtime reduction of voltage margins prototyped in a state-of-the-art server processor. > > BIO: > Radu Teodorescu is an Assistant Professor in the Department of Computer Science and Engineering at The Ohio State University where he leads the Computer Architecture Research Lab. He received his PhD from University of Illinois at Urbana-Champaign in 2008. His research interests include computer architecture with a focus on energy efficient microprocessor design and the impact of technology scaling on reliability and process variability. He received a CAREER award from the National Science Foundation in 2012, the W. J. Poppelbaum award from University of Illinois in 2008 and an Intel Fellowship in 2007. Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

1 0

H Luo general exam
by Melissa M. Lawson 06 May '13

06 May '13

Haipeng Luo will present his research seminar/general exam on Monday May 13 at 2PM in Room 402. The members of his committee are: Rob Schapire, Sebastien Bubeck (ORFE), and Moses Charikar. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- Title : Online Learning with Unknown Time Horizon Abstract : We consider online learning when the time horizon T is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which “pretends” that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is bounded by O(sqrt(T*lnN)), where N is the number of actions. Furthermore, the constant in our regret bound approaches 1, which is better than the best previously known bound for this setting (as far as we know). Moreover, our algorithm can be generalized to other games, such as predicting with expert advice. Reading List : Textbooks: 1. Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012. 2. Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games (Chapter 2,4,6,7). Cambridge University Press, 2006. Papers: 3. Jacob Abernethy and Manfred K. Warmuth. Repeated games against budgeted adversaries. In Advances in Neural Information Processing Systems 24, 2010. 4. Jacob Abernethy, Manfred K. Warmuth, and Joel Yellin. Optimal strategies from random walks. In Proceedings of the 21st Annual Conference on Learning Theory, 2008. 5. Jacob Abernethy, Alekh Agarwal, Peter L. Bartlett, Alexander Rakhlin. A Stochastic View of Optimal Regret through Minimax Duality. arXiv:0903.5328, 2009. 6. Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-conﬁdent on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48–75, 2002. 7. Nicolo Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, May 1997. 8. Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. arXiv:0903.2851, 2009. 9. Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79–103, 1999. 10. David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999. 11. Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. In 30th Annual Symposium on Foundations of Computer Science, pages 256–261, 1989. 12. Alexander Rakhlin, Ohad Shamir, Karthik Sridharan. Relax and Randomize: From Value to Algorithms. arXiv:1204.0870, 2012. 13. V. G. Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153–173, April 1998.

1 0

K Edwards general exam
by Melissa M. Lawson 06 May '13

06 May '13

Katherine Edwards will present her research seminar/general exam on Friday May 10 at 2PM in room 302. The members of her committee are: Paul Seymour (Math) advisor, Moses Charikar, and Mark Braverman. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ----------------------------- Edge-coloring 7- and 8-regular planar graphs In 1974, Seymour conjectured the following: Let G be a k-regular planar (multi)graph, such that for every odd set X of vertices of G, at least k edges of G have one end in X and the other in V (G) nX. Then G is k-edge-colorable. For k = 3 this is equivalent to the four-color theorem. The cases k = 4; 5 were solved by Guenin, the case k = 6 by Dvorak, Kawarabayashi and Kral, and the case k = 7 by Edwards and Kawarabayashi. In joint work with Chudnovsky and Seymour, we now have a proof for the case k = 8, and that is the topic of this talk. Reading list [1] Paolo Codato, Michele Conforti, and Claudia Sera ni. Packing t-joins. Journal of Graph Theory, 22(4):293{296, 1996. [2] WJ Cook, WH Cunningham, WR Pulleyblank, and A Schrijver. Combinatorial Opti- mization. 1998. New York, NY: Wiley-Interscience. [3] Bertrand Guenin. Packing t-joins and edge colouring in planar graphs. 2003. [4] Penny Haxell and Jessica McDonald. On characterizing vizing's edge colouring bound. Journal of Graph Theory, 69(2):160-168, 2012. [5] Takao Nishizeki and Kenichi Kashiwagi. On the 1.1 edge-coloring of multigraphs. SIAM Journal on Discrete Mathematics, 3(3):391-410, 1990. [6] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B, 70(1):2 -44, 1997. [7] P.D. Seymour. The matroids with the max-flow min-cut property. Journal of Combina- torial Theory, Series B, 23(2-3):189-222, 1977. [8] P.D. Seymour. On multi-colourings of cubic graphs, and conjectures of fulkerson and tutte. Proc. London Math. Soc, 38(3):423-460, 1979. [9] P.D. Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London Mathematical Society, 3(1):178-192, 1981.

1 0

Y Naamad general exam
by Melissa M. Lawson 06 May '13

06 May '13

Yonatan Naamad will present his research seminar/general exam on Friday May 10 at 1o:30 AM in room 302 (note time and room!). The members of his committee are: Moses Charikar (advisor), Mark Braverman, and Zeev Dvir. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------- One measure of the complexity of a problem is its query complexity, or the number of queries an algorithm must make to the input in order to output a provably-correct solution. In this talk, I'll discuss my work on establishing the query complexity of the generalized sorting problem, where we wish to establish a total order on a collection of n elements when the set of possible pairwise comparisons is restricted to a certain subset of the C(n,2) pairs of elements. If the subset is complete -- containing all C(n,2) pairs -- then the query complexity of the problem is well known to be Omega(n log n). In 2011, Huang, Kannan, and Khanna gave the first nontrivial result in the more general setting, establishing a (randomized) query complexity upper-bound of O(n^(3/2) log n). We discuss recent improvements upon their work. Based on joint work with Moses Charikar and Sampath Kannan. -- and my reading list is 1. (Book) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. 2. Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky: Matching Nuts and Bolts. SODA 1994: 690-696 3. Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query Strategies for Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002) 4. Anupam Gupta, Amit Kumar: Sorting and Selection with Structured Costs. FOCS 2001: 416-425 5. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna: Algorithms for the Generalized Sorting Problem. FOCS 2011: 738-747 6. Jeff Kahn, Jeong Han Kim: Entropy and Sorting. J. Comput. Syst. Sci. 51(3): 390-399 (1995) 7. Jeff Kahn, Nathan Linial: Balancing extensions via Brunn-Minkowski. Combinatorica 11(4): 363-368 (1991) 8. Jeff Kahn, Michael E. Saks, Dean Sturtevant: A topological approach to evasiveness. Combinatorica 4(4): 297-306 (1984) 9. Sampath Kannan, Sanjeev Khanna: Selection with monotone comparison cost. SODA 2003: 10-17 10. Krzysztof Onak, Pawel Parys: Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. FOCS 2006: 379-388 11. Andrew Chi-Chih Yao: Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput. 17(3): 517-520 (1988)

1 0

G Hu general exam
by Melissa M. Lawson 03 May '13

03 May '13

Guangda Hu will present his research seminar/general exam on Thursday May 9 at 3PM in Room 402. The members of his committee are: Zeev Dvir, advisor, Moses Charikar, and Mark Braverman. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------- Abstract: Locally decodable code (LDC) is an error-correcting code that every bit of the original message can be recovered by reading only a small number of bits in the code. A major question is about the minimum length of constant query LDCs. It is known that 2-query LDC has length at least exponential of the message length. However, there is a huge gap between the lower and upper bounds if the query number is greater than 2. The lower bound for 3-query LDC is only quadratic while the best known construction has super-polynomial length. The constructions of constant query LDCs all had exponential length until a very recent breakthrough. The sub-exponential, although still super-polynomial, constructions of LDCs are based on matching vector (MV) families. An MV family is defined as two lists of n-dimensional vectors in Z_m, where only the corresponding vectors of the two lists have inner product 0. A larger MV family implies a shorter code. MV families also arise in other combinatorial contexts as well, where a large MV family can also imply new results. Therefore it is interesting to figure out the maximum size of MV families. For prime m, the upper bound of MV families are already tight. However, the question was not well understood for general composite m. In [DGY11], an upper bound m^{n-1+o(1)} was proved and m^{n/2} was conjectured. In [BDL13], the bound was improved to m^{n/2+O(log m)}. Inspired by previous works, we proved a new upper bound m^{n/2+O(1)}. Comparing to the known MV constructions, this is almost tight for m>>n. Reading List: Textbook: Computational Complexity: A modern approach. [ARORA-BARAK] [Yek08] Towards 3-query locally decodable codes of subexponential length. Sergey Yekhanin. [Efr09] 3-query Locally Decodable Codes of Subexponential Length. Klim Efremenko. [DGY11] Matching Vector Codes. Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin. [KT00] On the efficiency of local decoding procedures for error-correcting codes. Jonathan Katz, Luca Trevisan. [GKST02] Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan. [Woo07] New Lower Bounds for General Locally Decodable Codes. David P. Woodruff. [Woo10] A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. David P. Woodruff. [DS06] Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Zeev Dvir, Amir Shpilka. [BDWY11] Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff. [BDL13] New Bounds for Matching Vector Families. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett.

1 0